Формулы упрощения логических выражений в информатике

Формулы упрощения логических выражений в информатике

Это символы не жёстко привязаны к соотв. операциям, можно использовать другие.

Примеры логических выражений

С применением отрицания

Со знаком "эквивалентно"

Со знаком "следствие"

С применением конъюкции и дизъюнкции

С применением Не-и и Не-или

В калькуляторе вы сможете упростить выражения, содержащие следующие операции: NOT, XOR, AND, OR, NAND, NOR, NOT

© Контрольная работа РУ — калькуляторы онлайн

Законы логики и правила преобразования логических выражений.

Изучаем основные законы логики, учимся преобразовывать логические выражения, используя логические законы, вводим понятие “нормальная форма логической формулы”, закрепляем навыки упрощения логических выражений, используя логические законы.

  1. Обучающие:
  1. Изучить основные законы логики
  2. Научить преобразовывать логические выражения, используя логические законы
  3. Ввести понятие “нормальная форма логической формулы”
  4. Закрепить навыки упрощения логических выражений, используя логические законы
  5. Научить решать логические задачи
  6. Закрепить навыки решения логических задач
  • Развивающие:
    1. Развивать логическое мышление
    2. Развивать внимание
    3. Развивать память
    4. Развивать речь учащихся
    5. Воспитывающие:
      1. Воспитывать умение слушать учителя и одноклассников
      2. Воспитывать аккуратность ведения тетради
      3. Воспитывать дисциплинированность
      4. Ход урока

        Здравствуйте, ребята. Мы продолжаем изучать основы логики и тема нашего сегодняшнего урока «Законы логики и правила преобразования логических выражений». Изучив данную тему, вы узнаете, основные законы логики, научитесь упрощать логические выражения, используя логические законы, решать логические задачи

        Проверка домашнего задания

        Какой у вас получился ответ в домашней задаче? (2)

        Откройте свои тетради там, где вы выполняли домашнюю работу, я пройду посмотрю

        Объяснение нового материала

        Переходим к новой теме.

        В алгебре логики имеется ряд законов, позволяющих производить равносильные преобразования логических выражений. Приведем соотношения, отражающие эти законы.

        1. Закон двойного отрицания:

        А = .

        Двойное отрицание исключает отрицание.

        2. Переместительный (коммутативный) закон:

        — для логического сложения:

        — для логического умножения:

        Результат операции над высказываниями не зависит от того, в каком порядке берутся эти высказывания.

        В обычной алгебре 2 + 3 = 3 + 2, 2 ´ 3 = 3 ´ 2.

        3. Сочетательный (ассоциативный) закон:

        — для логического сложения:

        — для логического умножения:

        При одинаковых знаках скобки можно ставить произвольно или вообще опускать.

        В обычной алгебре: (2 + 3) + 4 = 2 + (3 + 4) = 2 + 3 + 4, 5 ´ (6 ´ 7) = 5 ´ (6 ´ 7) = 5 ´ 6 ´ 7.

        4. Распределительный (дистрибутивный) закон:

        — для логического сложения:

        — для логического умножения:

        Определяет правило выноса общего высказывания за скобку.

        В обычной алгебре: (2 + 3) ´ 4 = 2 ´ 4 + 3 ´4.

        5. Закон общей инверсии (законы де Моргана):

        — для логического сложения

        = & ;

        — для логического умножения:

        = Ú

        6. Закон идемпотентности

        — для логического сложения:

        — для логического умножения:

        Закон означает отсутствие показателей степени.

        7. Законы исключения констант:

        — для логического сложения:

        — для логического умножения:

        8. Закон противоречия:

        A& = 0.

        Невозможно, чтобы противоречащие высказывания были одновременно истинными.

        9. Закон исключения третьего:

        A Ú = 1.

        10. Закон поглощения:

        — для логического сложения:

        — для логического умножения:

        11. Закон исключения (склеивания):

        — для логического сложения:

        — для логического умножения:

        (A Ú B)&( Ú B) = B.

        12. Закон контрапозиции (правило перевертывания):

        Формула имеет нормальную форму, если в ней отсут­ствуют знаки эквивалентности, импликации, двойного от­рицания, при этом знаки отрицания находятся только при переменных.

        Пример 1. Найдите X, если Ú = В.

        Упростим левую часть равенства. Какими законами воспользуемся? Для преобразования левой части равенства последовательно воспользуемся законом де Моргана для логического сложения и законом двойного отрицания:

        ( & ) Ú ( &A)

        Согласно распределительному закону для логического сложения:

        &( Ú A)

        Согласно закону исключения третьего и закона исключения констант:

        &1 =

        Полученную левую часть приравняем правой:

        = В

        Окончательно получим, что

        X = .

        Пример 2. Упростите логическое выражение (A Ú B Ú C)&

        Читайте также:  Nfs underground 2 требует 2 диск

        Посмотрите на выражение, посмотрите на законы, что можно сделать?

        Согласно закону общей инверсии для логического сложения (первому закону Моргана) и закону двойного отрицания:

        (A Ú B Ú C)& = (A Ú B Ú C)&( &B& )

        Согласно распределительному (дистрибутивному) закону для логического сложения:

        (A Ú B Ú C)&( &B& ) = (A& ) Ú (B& ) Ú (C& ) Ú (A&B) Ú (B&B) Ú (C&B) Ú (A& ) Ú (B& ) Ú (C& )

        Согласно закона противоречия:

        (A& ) = 0; (C& ) = 0

        Согласно закона идемпотентности

        Подставляем значения и, используя переместительный (коммутативный) закон и группируя слагаемые, получаем:

        0 Ú (A&B) Ú ( &B) Ú B Ú (C&B) Ú ( &B) Ú (C& ) Ú (A& ) Ú 0

        Согласно закона исключения (склеивания)

        (A&B) Ú ( &B) = B
        (C&B) Ú ( &B) = B

        Подставляем значения и получаем:

        0 Ú B Ú B Ú B Ú (C& ) Ú (A& ) Ú 0

        Согласно закона исключения констант для логического сложения и закона идемпотентности:

        Подставляем значения и получаем:

        B Ú (C& ) Ú (A& )

        Упростить логическую формулу:

        Сегодня мы продолжаем изучать тему “Законы логики и правила преобразования логических выражений”. Будем упрощать выражения и учиться решать логические задачи

        Но для начала проверим как вы выполнили домашнее задание (1 ученик у доски, остальные показывают в тетрадях).

        1.Упростить логическое выражение

        Чтобы проверить правильность упрощения, нужно построить таблицы истинности для исходного и полученного логического выражения. Результирующие столбцы должны совпадать.

        2. Логическое выражение называется тождественно – ложным, если оно принимает значения 0 на всех наборах входящих в него простых высказываний.

        Упростить выражение и показать, что оно тождественно – ложное

        2.Логическое выражение называется тождественно – истинным, если оно принимает значения 1 на всех наборах входящих в него простых высказываний.

        Упростить выражение и показать, что оно тождественно – истинное

        3.Переведите к виду логической формулы вы­сказывание: «Неверно, что если погода пасмурная, то дождь идет тогда и только тогда, когда нет ветра».

        Решение. Определим следующие простые высказывания:

        П — «пасмурная погода»;
        Д — «идет дождь»;
        В — «дует ветер».

        Тогда соответствующее логическое выражение запишется так:

        Перейдем к решению логических задач. Логические задачи обычно формулируются на естествен­ном языке. В первую очередь их необходимо формализовать, то есть записать на языке алгебры высказываний. Полученные логические выражения необходимо упростить и проанализировать. Для этого иногда бывает необходимо построить таблицу истинности полученного логического выражения. Несложные задачи решаются путем логических рассуждений.

        В школе-новостройке в каждой из двух аудиторий может находиться либо кабинет информатики, либо кабинет физики. На дверях аудиторий повесили шутливые таблички. На первой повесили табличку «По крайней мере, в одной из этих аудиторий размешается кабинет информатики», а на второй аудитории — табличку с надписью «Кабинет физики находится в другой аудитории». Проверяющему, который пришел в школу, известно только, что надписи на табличках либо обе истинны, либо обе ложны. Помогите проверяющему найти кабинет информатики.

        Переведем условие задачи на язык логики высказывании. Так как в каждой из аудиторий может находиться кабинет информатики, то пусть:

        Читайте также:  Movavi как повернуть видео на 90

        А = «В первой аудитории находится кабинет информатики»;
        В = «Во второй аудитории находится кабинет информатики».

        Отрицаний этих высказывании:

        А = «В первой аудитории находится кабинет физики»;
        В = «Bo второй аудитории находится кабинет физики».

        Высказывание, содержащееся на табличке на двери первой аудитории, соответствует логическому выражению:

        Высказывание, содержащееся на табличке на двери вто­рой аудитории, соответствует логическому выражению:

        Содержащееся в условии задачи утверждение о том, что надписи на табличках либо одновременно истинные, либо одновременно ложные в соответствии с законом исключен­ного третьего записывается следующим образом:

        Подставим вместо X и Y соответствующие формулы:

        Упростим сначала первое слагаемое. В соответствии с законом дистрибутивности умножения относительно сложения:

        В соответствии с законом непротиворечия:

        Упростим теперь второе слагаемое. В соответствии с первым законом де Моргана и законом двойного отрицания:

        В соответствии с законом непротиворечия:

        В результате получаем:

        Для того чтобы выполнялось равенство В & А = 1, В и А должны быть равны 1, то есть соответствующие им высказывания истинны.

        Ответ: В первой аудитории находится кабинет физики, а во второй — кабинет информатики.

        5. Упростить логические выражения. Правильность упрощения логических выражений проверить с помощью таблиц истинности для исходных и полученных логических формул.

        В процессе составления расписания уроков учителя высказали свои пожелания. Учитель математики, высказал пожелание про­водить первый или второй урок, учитель информатики — первый или третий, а учитель физики второй или третий урок. Сколько существует возможных вариантов расписания и каковы они?

        Проверим, как вы выполнили домашнюю работу.

        Продолжаем решать задачи и упрощать логические выражения

        Кто из учеников А, В, С и D играет, а кто не играет в шахматы, если известно следующее:

        • а) если А или В играет, то С не играет;
        • б) если В не играет, то играют С и D;
        • в) С играет

        Решение. Определим следующие простые высказывания:

        • А — «ученик А играет в шахматы»;
        • В — «ученик В играет в шахматы»;
        • С — «ученик С играет в шахматы»;
        • D — «ученик D играет в шахматы».

        Запишем произведение указанных сложных высказываний:

        Упростим эту формулу:

        ((A v В) → С) & (В → С & D) & С = ((А v В) v С) & (В v С & D) & С = (А & В) v С) & (В v С & D) & C = A & B & C & D =1.

        Отсюда А = 0, В = 1, С = 1, D = 1.

        Ответ: в шахматы играют ученики В,С и D, а ученик А не играет.

        Для написания любой логической функции может быть использовано логическое выражение, после чего можно составить логическую схему. Как правило, все логические выражения упрощают для получения максимально простой и дешевой логической схемы. В сущности, логическая схема, выражение и логическая функция, являются тремя различными языками, повествующими об одном и том же.

        Логические выражения упрощают при помощи различных законов алгебры логики. Часть преобразований напоминает преобразования формул, выполняемые в классической алгебре (например, применение сочетательного и переместительного законов, вынесение за скобки равенства общего множителя и так далее). Для других преобразований используют свойства, которых лишены операции классической алгебры.

        Любые законы алгебры логики выводят для главных логических операций следующим образом: НЕ — инверсия (то есть, отрицание); ИЛИ — дизъюнкция (то есть, логическое сложение); И — конъюнкция (то есть, логическое умножение).

        Читайте также:  Код ошибки 0x000000f4 windows 7 решение

        Закон двойного отрицания состоит в том, что операция НЕ является обратимой: если ее использовать два раза, логическое значение в результате останется неизменным.

        Сущность закона исключенного третьего состоит в том, что каждое логическое выражение при любых условиях является истинным, либо ложным. Если A=1, тогда A=0, а также наоборот. Конъюнкция данных величин всегда равняется 0, дизъюнкция равна 1.

        Закон повторения и операции с константами легко можно проверить, используя таблицы истинности операций ИЛИ и И.

        Сочетательный и переместительный законы имеют такой же вид, как в математике. Аналогия с привычной всем классической алгеброй.

        Для дизъюнкции распределительный закон состоит просто в раскрытии скобок. Для конъюнкции выражение неизвестно, в математике подобное равенство является неверным. Начнем доказывать с правой части. Сначала раскроем скобки:

        Используем закон повторение, гласящий, что A⋅A=A,

        A+A⋅B=A⋅(1+B)=A⋅1=A, следовательно, (A+B)⋅(A+C)=A+B⋅C.

        Мы доказали равенство.

        Правил, используемые для раскрытия инверсии сложных выражений, назвали именем известного логика и математика де Моргана. Суть состоит в том, что общее отрицание не только распространяется на отдельные выражения, а еще и дизъюнкция заменяется конъюнкцией (а также наоборот). Для доказательства данных правил используются таблицы истинности.

        Основная часть аксиом и законов алгебры логики записаны попарно. Внимательно изучая пары, можно сформулировать принцип двойственности, звучащий следующим образом: если осуществить в тождестве замены конъюнкции, а также дизъюнкции. И также элементов 1 и 0 (при их наличии), получится тождество. Данное свойство именуют принципом двойственности.

        Упрощения логических выражений в примерах

        Формула, вытекающая из распределительного закона. При ее выведении применили вышеупомянутое правило де Моргана для дизъюнкции, а также использовали закон двойного отрицания, после чего сомножитель X, вынесли за скобку, тогда как в скобках получили закон исключённого третьего, а также применили операцию с константами.

        Примеры упрощения логических выражений

        Пример первый

        Кто из рабочих, обозначенных, как A, B, C, D работает на заводе, а кто нет, если нам даны следующие условия:

        • если работает A либо работает B, тогда не работает C;
        • если не работает B, тогда работает D, а также работает C.

        Решение задачи. Обозначим несколько простых высказываний:

        1. A рабочий A на заводе работает;
        2. B рабочий B на заводе работает;
        3. C рабочий C на заводе работает;
        4. D рабочий D на заводе работает.

        Сформулировав данные из условия при помощи этих простых высказываний, получим следующее:

        Получаем следующую конъюнкцию: ((A+B)→C)⋅(B→C⋅D)⋅C.

        После упрощения данной формулы получаем, что A равно 0, B равно 1, C равно 1, D равно 1.

        Ответ: ученик A на заводе не работает, а ученики B, C, D играют.

        В этом примере применено правило де Моргана, затем использован распределительный закон, после этого применен закон исключенного третьего, потом использован переместительный закон. За ним реализован закон повторения, потом опять применен переместительный закон и, наконец, использован закон поглощения.

        Чтобы отыскать решения логического уравнения можно также применить упрощение логических выражений.

        Нужно отыскать все решения данного уравнения

        Применив правило де Моргана, получим

        а затем применяем закон поглощения и получаем

        Чтобы логическая сумма равнялась нулю, все слагаемые должны равняться нулю, из чего следует, что

        A равно 1, B равно 0, C равно 0, D равно 0.

        Ссылка на основную публикацию
        Фиксированная шапка сайта при прокрутке
        Допустим у вас важная информация например контакты находятся в шапке и вы хотите что бы они всегда были на веду...
        Удаление последнего элемента списка
        Введение. Основные операции О дносвязный список – структура данных, в которой каждый элемент (узел) хранит информацию, а также ссылку на...
        Удаление дубликатов фотографий на русском бесплатно
        Здравствуйте Уважаемый Друг. У каждого из нас на компьютере хранится большое количество различных фотографий изображений и тому подобных картинок. Парой...
        Фиксированное меню при скролле
        Создаём эффект залипания при прокручивании страницы на блоках меню навигации, бокового виджета и меню с помощью jQuery и без него....
        Adblock detector