Булевая алгебра

Тождества Булевой алгебры Основная задача математической логики — на основании ложности или истинности простых высказываний определить значение сложного высказывания. Логические операции В алгебре высказываний логические связки заменяются логическими операциями. И — логическое умножение или конъюнкция Обозначение операции в алгебре высказываний: И, , , &. Обозначение в языках программирования: and. Если обозначить простые высказывания А = «Саша играет на гитаре»; В = «Саша играет на фортепиано», тогда сложное высказывание F = «Саша играет на гитаре и на фортепиано» можно записать как F = А  В. Логические переменные А и В, входящие в формулу, могут принимать значения 1 (ИСТИНА) или 0 (ЛОЖЬ). Значение функции логического умножения F можно определить по таблице истинности данной функции. Таблица истинности показывает, какие значения принимает логическая функция при всех возможных наборах ее аргументов. Таблица истинности операции И Диаграмма Эйлера — Венна А В F = А  В 0 0 0 0 1 0 1 0 0 1 1 1 В алгебре множеств конъюнкции соответствует операция пересечения множеств. Из таблицы видно, что конъюнкция истинна тогда и только тогда, когда оба исходных высказывания истинны. Между таблицей истинности и диаграммой Эйлера – Венна существует взаимно однозначное соответствие. Поэтому число единиц для F всегда будет совпадать с числом заштрихованных областей на диаграмме. ИЛИ — логическое сложение или дизъюнкция Обозначение операции в алгебре высказываний: ИЛИ,  , +. Обозначение в языках программирования: or. Обозначим сложное высказывание «Мама купила торт или конфеты» буквой F и запишем его на языке алгебры логики. Пусть А — «Мама купила торт»; В — «Мама купила конфеты», тогда F = А  В. Таблица истинности операции ИЛИ Диаграмма Эйлера-Венна А В F = А  В 0 0 0 0 1 1 В алгебре множеств дизъюнкции соответствует операция объединения множеств. А В 1 0 1 1 1 1 Из таблицы истинности видно, что дизъюнкция двух высказываний является ложной тогда и только тогда, когда оба исходных высказывания ложны и истинной, когда хотя бы одно из двух высказываний истинно. НЕ — логическое отрицание или инверсия Обозначение отрицания в алгебре высказываний: НЕ А,А, ┐А. Обозначение в языках программирования: not. Пусть А = «Четыре — четное число» — истинное высказывание, тогда высказывание «Четыре — нечетное число» будет являться отрицанием высказывания А и будет ложно. На языке алгебры логики это будет выглядеть как F =А. Таблица истинности операции НЕ Диаграмма Эйлера-Венна А F = А 0 1 1 0 ЕСЛИ–ТО — логическое следование или импликация Обозначение импликации в алгебре высказываний: → . Пусть высказывание А = «Данный четырёхугольник — квадрат» и высказывание В = «Около данного четырёхугольника можно описать окружность». Тогда составное высказывание F = А → В понимается как «Если данный четырёхугольник квадрат, то около него можно описать окружность». Таблица истинности операции «импликация» Диаграмма Эйлера-Венна А В F = А → В 0 0 1 0 1 1 1 0 0 1 1 1 В формуле F = А → В переменная А называется основанием, а В — следствием. Говорят, «Если А, то В», «А влечет В» или «Из А следует В». Импликация является одной из самых важных операций алгебры логики. Из таблицы истинности видно, что импликация истинна всегда, за исключением случая, когда основание А истинно, а следствие В — ложно. Чтобы лучше понять эту логическую операцию, рассмотрим два высказывания и их импликацию: А = У ребенка высокая температура; В = Ребенок болен; А → В = Если у ребенка высокая температура, то он болен. Подставим в таблицу истинности высказывания, соответствующие входным значениям А и В и проанализируем значение F. 1: (А=0, В=0) У ребенка нет высокой температуры; Ребенок не болен; F = 1. 2: (А=0, В=1) У ребенка нет высокой температуры; Ребенок болен; F = 1. А А А В 3: (А=1, В=0) У ребенка высокая температура; Ребенок не болен; F = 0. 4: (А=1, В=1) У ребенка высокая температура; Ребенок болен; F = 1. Истинность 1 и 4 строк и ложность 3 строки очевидна. В строке 2 видим, что при ложном основании следствие может быть и истинным. В нашем примере — не всякая болезнь сопровождается высокой температурой. Чтобы лучше понять диаграмму Эйлера–Венна, выразим операцию «импликация» через базовые операции ИЛИ и НЕ: А → В =А  В Проверьте по таблице истинности, что две формулы А → В и А  В являются равносильными, т. к. у них совпадают значения последнего столбца таблицы. РАВНОСИЛЬНО — логическое равенство или эквиваленция Эквиваленция (двойная импликация) — это логическая операция, выражаемая связками тогда и только тогда…, когда; необходимо и достаточно; равносильно; в том и только том случае. Обозначение эквиваленции в алгебре высказываний: ↔, ~, ≡. Пусть высказывание А = «Идет дождь» и высказывание В = «На небе тучи». Тогда составное высказывание F = А ↔ В понимается как «Дождь идет тогда и только тогда, когда на небе есть тучи». Таблица истинности операции «эквиваленция» Диаграмма Эйлера-Венна А В F = А ↔ В 0 0 1 0 1 0 1 0 0 1 1 1 Функция F = А ↔ В (А равносильно В) истинна только в том случае, когда А и В либо оба истинны, либо оба ложны. Рассмотрим два высказывания (А, В) и составное высказывание F = А ↔ В. А = Крыши домов мокрые; В = Идет дождь. А ↔ В = Крыши домов мокрые тогда и только тогда, когда идет дождь. Подставьте в таблицу истинности высказывания, соответствующие входным значениям А и В (0 и 1) и проанализируйте значение F. А В А → В  А А  В 0 0 1 0 1 1 1 0 0 1 1 1 А В Таблицы истинности Для каждого составного высказывания (логического выражения) можно построить таблицу истинности, которая показывает, при каких комбинациях исходных значений все логическое выражение истинно, а при каких ложно. Рассмотрим алгоритм построения таблицы истинности на примере логического выражения F = А С  В. 1. Определяем количество переменных в логическом выражении. В нашем выражении три переменные (А, В, С). Каждая переменная может принимать значение 0 и 1. Все возможные сочетания переменных называют набором входных переменных. 2. Количество строк в таблице равно количеству наборов входных переменных, которое определяем по формуле Q = 2 ∙ N , где N — количество переменных в выражении. В нашем примере Q = 23 = 8. В таблице будет 8 строк. 3. Количество столбцов в таблице равно количеству переменных плюс количество операций. В нашей таблице будет 6 столбцов: 3 переменные (А, В, С) + 3 операции (НЕ, И, ИЛИ). 4. Строим таблицу размером 8х6, добавляем сверху обозначения столбцов и заполняем входные наборы данных. Как быстро и без ошибок заполнить входные наборы переменных Способ 1. Общее количество наборов (у нас 8) разделим пополам и заполним первый столбец так: 4 нуля, затем 4 единицы. Теперь 4 разделим пополам и заполним второй столбец: 2 нуля, 2 единицы, 2 нуля, 2 единицы. Разделим 2 пополам и заполним третий столбец: ноль, единица, ноль, единица и т. д. до конца столбца. Способ 2. Каждый набор переменных составляет его порядковый номер (0, 1, 2, 3, 4, 5, 6, 7), записанный в двоичной системе счисления. Для трех переменных получим: 000, 001, 010, 011, 100, 101, 110, 111. Заполняем остальные столбцы таблицы, выполняя логические операции над переменными с учетом приоритета операций и в соответствии с их таблицами истинности. F = А С  В A В С  С С  В А С  В 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 1 1 1 0 1 1 0 0 0 1 0 0 1 0 1 1 0 1 0 0 0 1 1 0 1 1 1 1 1 1 0 0 1 Из таблицы видно, что логическое выражение истинно при следующих наборах переменных (А, В, С): 1. (0, 1, 0); 2. ___________ 3. ____________ 4. ____________. Основные законы алгебры логики В алгебре логики имеется ряд законов, позволяющих производить равносильные преобразования логических выражений. Закон Для ИЛИ Для И Переместительный А  В = В  А А ∙ В = В ∙ А Сочетательный (А  В)  С = А  (В  С) (А ∙ В) ∙ С = А ∙ (В ∙ С) Распределительный (А  В) ∙ С = А ∙ С  В ∙ С (А ∙ В)  С = (А  С) ∙ (В  С) Правила де Моргана А  В = А ∙В А ∙ В = А В Идемпотентности А  А = А А ∙ А = А Исключения третьего и противоречия А А = 1 А ∙А = 0 Операции с константами А  1 = 1 А  0 = А А ∙ 1 = А А ∙ 0 = 0 Поглощения А  (А ∙ В) = А А ∙ (А  В) = А Склеивания (А ∙ В)  (А ∙ В) = В (А  В) ∙ (А  В) = В Контрапозиции А → В = В →А Двойного отрицания А = А Формулы упрощения А → В =А  В А ↔ В = (А → В) ∙ (В → А) = (А  В) ∙ (В  А) Упрощение логических формул Любую логическую формулу, применяя законы логики, можно записать в виде логического выражения через инверсию, конъюнкцию и дизъюнкцию. Такая форма представления называется нормальной. Под упрощением логической формулы понимают равносильное преобразование, приводящее к формуле, которая содержит меньшее число операций конъюнкции и дизъюнкции и не содержит отрицаний неэлементарных формул. Приемы и способы упрощения логических выражений При преобразовании логических формул используют законы алгебры логики, правила операций с логическими константами, а также некоторые приемы, применяемые в обычной алгебре, например, вынесение общего множителя за скобки. Примеры упрощения логических формул: х ∙у  х ∙ у ∙ z  х ∙у ∙ z  х ∙ у ∙ z = х ∙ (у  у ∙ z у ∙ z  у ∙ z) = х ∙ ((у  у ∙ z)  (у ∙ z  у ∙z)) = х ∙ 1 = х 5) х ∙ у z = х ∙ у ∙ z = (х у) ∙ z Дважды применяется правило де Моргана и закон двойного отрицания. 1 (А А) х вынесли за скобки (А  1 = 1) сгруппировали слагаемые 6) (х ∙у  z) ∙ (х  у)  z = х ∙у ∙х  х ∙у ∙ у  z ∙х  z ∙ у  z = = 0  0  (z ∙ (х  у)) z = (z z) ∙ (х  у z) = х  у z 7) х →у  х = х у  х = х ∙у  х = х ∙ у  х = х ∙ (у  1) = х ∙ 1 = х распределительный 0 0 закон для ИЛИ распределительный закон для И 1 формула упрощения для импликации формула де Моргана