Основные понятия алгебры логики. Простые и сложные высказывания. Основные операции алгебры логики. Законы Морганы

1 Основные понятия алгебры логики. Простые и сложные высказывания. Основные операции алгебры логики. Законы Морганы. Изучив материал, студент должен знать:  основные понятия формальной логики;  высказывание и суждение;  истинность и ложность высказываний;  основные логические операции, таблицы истинности, логические формулы. Изучив материал, студент должен уметь: определять истинность и ложность высказываний;   применять логические операции;  представлять логические выражения в виде формул;  выполнять упрощение формул. Для анализа и синтеза схем в ЭВМ при алгоритмизации и программировании широко используется математический аппарат алгебры логики (булевой алгебры). Основное понятие булевой алгебры — выказывание. Высказывания бывают простые и сложные. Под простым высказыванием понимается повествовательное предложение, в отношении которого имеет смысл утверждение о его истинности или ложности. При этом считается, что высказывание удовлетворяет закону исключенного третьего, т.е. каждое высказывание или истинно или ложно и не может быть одновременно и истинным и ложным (третьего не дано). Высказывания обозначаются латинскими буквами и могут принимать одно из двух значений: ЛОЖЬ (значение 0) или ИСТИНА (значение 1). Например, содержание высказывания А: «дважды два равно четырем» ИСТИНА А = 1, высказывание В: «три больше пяти» всегда есть ЛОЖЬ В=0, а высказывание «сейчас идет снег» может быть истинным или ложным. Два высказывания А и В называются равносильными, если они имеют одинаковые значения истинности, записывается А = В. Содержание высказываний учитывается только при введении их буквенных обозначений, и в дальнейшем над ними можно производить 2 любые действия, предусмотренные алгеброй высказываний. Если над исходными элементами алгебры выполнены некоторые разрешенные в алгебре логики операции, то результаты операций также будут элементами этой алгебры. Сложное высказывание можно построить из простых с помощью логических операций: отрицания, конъюнкции, дизъюнкции, импликации и логических выражений, представляющих собой комбинации логических операций. Рассмотрим их подробней. Операцией отрицания А называют высказывание À (или –А, или ∀ говорят не А), которое истинно тогда, когда А ложно, и ложно тогда, когда А истинно. Например, если событие А состоит в том, что «завтра экзамен», то À «завтра НЕ будет экзамена», истинность одного утверждения автоматически означает ложность второго. Отрицание — унарная (т.е. для одного операнда) логическая операция. Ей соответствует языковая конструкция, использующая частицу НЕ. Это правило можно записать в виде следующей таблицы: А 1 À 1 Такая таблица называется таблицей истинности. Конъюнкцией (логическим умножением) двух высказываний А и В является новое высказывание С, которое истинно только тогда, когда истинны оба высказывания, записывается С = А∧В или С = А&В, или С = А*В (при этом говорят С равно А И В). Например, пусть высказывание А состоит в том, что «высота шкафа меньше высоты двери», событие В «ширина шкафа меньше ширины двери», событие С «шкаф можно внести в дверь, если ширина шкафа меньше ширины двери И высота шкафа меньше высоты двери», т.е. данная операция применяется, если два высказывания связываются союзом И. Таблица истинности этой операции, как следует из определения, имеет вид 3 А 1 1 В 1 1 А&В 1 Т.е. результатом конъюнкции (логического умножения) будет 1 только в том случае, когда значения обоих операндов 1. Дизъюнкцией (логическим сложением) двух высказываний А и В является новое высказывание С, которое истинно, если истинно хотя бы одно высказывание. Записывается С = A∨В, или, правда очень редко, может быть записано С = A+В (при этом говорят: С равно А ИЛИ В). Например, пусть высказывание А состоит в том, что «студент может добираться домой на автобусе», событие В «студент может добираться домой на троллейбусе», событие С «студент добрался домой на автобусе ИЛИ троллейбусе», т.е. данная операция применяется, если два высказывания связываются союзом ИЛИ. Таблица истинности такой операции следующая: А 1 1 В 1 1 A∨B 1 1 1 Т.е. результатом дизъюнкции (логического сложения) будет 1, если хотя бы один из операндов имеет значение 1. Импликацией двух высказываний А (А называется посылкой) и В (В называется заключением) является новое высказывание С, которое ложно только тогда, когда посылка истинна, а заключение ложно, записывается С = А→В (при этом говорят: из А следует В). Примером такой операции может быть любое рассуждение типа: если произошло событие А, то произойдет событие В, например, «если идет дождь, то на небе тучи». Очевидно, операция не симметрична, т.е. из В→А не всегда истинно, в нашем примере «если на небе тучи, то идет дождь» не всегда истинно. 4 Таблица истинности импликации имеет вид А В А→В 1 1 1 1 1 1 1 Т.е. результатом импликации будет 0 только тогда, когда посылка 1, а заключение 0. Импликация имеет следующие свойства: А→В ≠ В→А А→А = 1 0→А = 1 1→А =А А→1 =1 А→0 = À Эквиваленцией двух высказываний А и В является новое высказывание С, которое истинно только тогда, когда оба высказывания имеют одинаковые значения истинности, записывается С = А↔В (.С = А = В). Примером такой операции может быть любое высказывание типа: событие А равносильно событию В. Например, «идет дождь» равносильно «капает из тучи». Таблица истинности: А 1 1 В 1 1 А↔В 1 1 Т.е. результатом эквиваленции будет 1 тогда, когда оба высказывания имеют одинаковые значения (либо 0, либо 1). Эквиваленция имеет следующие свойства: А↔В = В↔А А↔В = Â ↔ À 5 А↔1 = А А↔0 = À С помощью (логических логических переменных и операций констант) из можно простых высказываний построить логические выражения, которые также называются булевскими функциями. Например, С= (( À ∨ В) → В) ∨ А. Чтобы избежать большого количества скобок в булевских функциях, принято следующее соглашение о старшинстве операций. Первыми выполняются операции в скобках, затем операции в следующем порядке: отрицание, конъюнкция и дизъюнкция слева направо, импликация, эквиваленция. Зависимости между логическими операциями Операции не являются независимыми; одни из них могут быть выражены через другие. Можно доказать с помощью таблиц истинности следующие равносильности: À =А – закон двойного отрицания А&В = В&А – коммутативный закон для конъюнкции A∨B = B∨A – коммутативный закон для дизъюнкции (А&В)&С = А&(В&С) – ассоциативный закон для конъюнкции (A∨B)∨C = A∨(B∨C) – ассоциативный закон для дизъюнкции дистрибутивные законы А&(В∨С) = (А&В)∨(А&С) A∨(В&С) = (A∨В)&(A∨С) законы де Моргана À & Â= À∨ Â À ∨ Â=À&Â 6 A&A = A – закон идемпотенции для конъюнкции A∨A = A – закон идемпотенции для дизъюнкции A&1 = A – закон единицы для конъюнкции A&0 = 0 – закон нуля для конъюнкции A∨1 = 1 – закон единицы для дизъюнкции A∨0 = A – закон нуля для дизъюнкции A∨ À = 1 – закон исключения третьего A& À = 0 – закон противоречия A→ В = À ∨В А↔В = (А→В)&(В→А) = ( À ∨В)&(A∨ Â)= (A&В)∨( À & Â) законы поглощения A∨(А&В) = А А&(A∨В) = А А&( À ∨В) = А&В A∨( À &B) = A∨В Одну и ту же зависимость между логическими переменными можно выразить различными формулами. Поэтому важно иметь возможность приводить формулы с помощью эквивалентных преобразований к некоторому стандартному виду. Существует несколько стандартных форм, к которым приводятся логические выражения с помощью эквивалентных преобразований. Первая из них — дизъюнктивная нормальная форма (ДНФ), имеет вид Al∨A2∨...∨An, где каждое из составляющих высказываний есть конъюнкция простых высказываний и их отрицаний, например: В = ( À1 & А2 & A3)∨(А4 & А5) 7 Вторая — конъюнктивная нормальная форма (КНФ), имеет вид А1∧А2∧...∧An, где каждое из составляющих есть дизъюнкция простых высказываний и их отрицаний, например: В = ( À1 ∨А2∨ À 3 ) & (А4∨А5) & А6. Задать булевскую функцию можно, определяя ее значения для всех наборов значений аргументов. Каждый аргумент может иметь два значения: 0 и 1, следовательно, n аргументов могут принимать 2n различных наборов. Пусть, например, булевская функция имеет три аргумента: X1, Х2, Х3. Общее число наборов 23 = 8; зададим таблицу истинности функции, указав для каждого набора значение функции. № X1 1 2 3 4 5 1 6 1 7 1 8 1 Для составления X2 X3 F 1 1 1 1 1 1 1 1 1 1 1 1 алгебраической формы по результатам таблицы сделаем следующее. В комбинациях, где функция принимает значение 1, единицу заменим именем функции, а нуль – именем с отрицанием (т.е. комбинации 0 0 1 поставим в соответствие выражение Õ1 & Õ 2 &Х3), все элементы соединим знаками дизъюнкции, для рассматриваемого примера получим F(X1, X2, Х3) = ( Õ1 & Õ 2 &Х3)∨( Õ1 &Х2&Х3)∨(Х1& Õ 2 &Х3)∨ (Х1&Х2&Х3). Как нетрудно заметить, построенная функция удовлетворяет заданной таблице истинности. Функция представляет дизъюнктивную нормальную форму. Кроме того, заметим, что в каждую группу дизъюнкций входят все аргументы функции. Такая ДНФ называется совершенной, а каждая группа дизъюнкций называется конституэнтой единицы. 8 Аналогично, для комбинаций, где функция принимает значение нуля, можно построить алгебраическую форму F(X1,X2,X3) = (X1∨X2∨X3)& (X1∨ Õ 2 ∨X3)&( Õ1 ∨X2∨X3)&( Õ1 ∨ Õ 2 ∨X3), которая также удовлетворяет заданной таблице истинности и представляет собой конъюнктивную нормальную форму, в данном случае совершенную. Каждая конъюнкция называется конституэнтой нуля. Таким образом, любая функция может быть разложена на конституэнты (составляющие). Эти соотношения используются для синтеза логических функций и вычислительных схем. Далее будет показано, как, основываясь на булевой алгебре, создаются цифровые устройства.