Основные понятия алгебры логики
Алгебра логики – это раздел математики, изучающий высказывания, рассматриваемые со стороны их логических значений (истинности и ложности) и логических операций над ними.
Логическое высказывание – это любое повествовательное предложение, в отношении которого можно однозначно сказать, истинно оно или ложно.
Для обозначения истины (истинного высказывания) используется символ 1, а для обозначения лжи (ложного высказывания) используется символ 0.
Рассмотрим примеры логических высказываний (см. Таблицу 1):
Таблица 1. Примеры логических выражений
Предложение | Характеристика с точки зрения алгебры логики |
Иваново – Родина Первого Совета | Истинное логическое высказывание |
За зимой наступит весна | Истинное логическое высказывание |
В городе Иваново проживают только граждане России | Ложное логическое высказывание |
После дождя всегда тепло | Ложное логическое высказывание |
После вторника будет выходной | Не является логическим высказыванием, т.к. не известно, о каком человеке, каком месяце и дне идет речь (если у человека текущий график работы, возможно, что у него в среду будет выходной, в противном случае среда – рабочий день; если в среду будет праздничный день, например, 8 марта, то этот день также будет выходным) |
Употребляемые в обычной речи слова и словосочетания «не», «и», «или», «если…то», «тогда и только тогда» и др. позволяют из уже заданных высказываний строить более сложные высказывания. Такие слова и словосочетания называют логическими связками. Высказывания, образованные с помощью логических связок – называют составными высказываниями. Высказывания, не являющиеся составными, называют элементарными.
Для обозначения логических высказываний, им назначают имена. Например, если А – высказывание «В четверг был дождь», В – высказывание «В пятницу было солнечно», то составное высказывание «В четверг был дождь, а в пятницу было солнечно», можно записать в виде:
А и В.
Здесь А, В – логические высказывания (могут быть либо истинными, либо ложными), и – логическая связка.
Каждая логическая связка рассматривается как операция над логическими высказываниями и имеет свое название и обозначение (см. Таблицу 2):
Таблица 2. Логические связки
№ | Логическая связка | Название | Обозна-чение | Высказы-вание | Математическая запись |
и | конъюнкция логическое умножение | Ù, & *, And | A и В | A Ù B, A & B A * B, A And B | |
или | дизъюнкция логическое сложение | Ú +, Or | A или В | A Ú B A + B, A Or B | |
не | инверсия, логическое отрицание | , , Not | не А | А, , Not A | |
Если…то | импликация, логическое следование | →, Þ | Если A, то В | A → B A Þ B | |
тогда и только тогда | эквивалентность, равносильность, логическое тождество | «, º Û, ~ | А тогда и только тогда, когда В | А«В, АºВ АÛВ, А~В |
Импликацию можно выразить через дизъюнкцию и отрицание:
A → B = А Ú B | (1) |
Эквивалентность можно выразить через отрицание, дизъюнкцию и конъюнкцию:
A «B = (А Ú B) Ù (B Ú А) | (2) |
Вычисление значения логического выражения производится слева направо в соответствии с таблицей истинности (см. Таблицу 3) и приоритетом выполнения логических операций (см. Таблицу 4). Порядок выполнения операций можно менять, используя круглые скобки.
Таблица 3. Таблица истинности
A | B | A Ú B | A Ù B | A |
Таблица 4. Приоритет выполнения логических операций
Приоритет операции | Логическая операция |
Первый (высший) | Логическое отрицание |
Второй | Конъюнкция (логическое умножение) |
Третий | Дизъюнкция (логическое сложение) |
Четвертый | Импликация (следование) |
Пятый (низший) | Эквивалентность (равносильность) |
Основные законы алгебры логики
В алгебре логики выполняются следующие основные законы, позволяющие производить тождественные преобразования логических выражений (см. Таблицу5.)
Таблица 5. Основные законы алгебры логики
Закон | Для ИЛИ | Для И | |
Переместительный | xÚy = yÚx | xÙy = yÙx | (3) |
Сочетательный | xÚ(yÚz) = (xÚy)Úz | xÙ(yÙz) = (xÙy)Ùz | (4) |
Распределительный | xÙ(yÚz) = xÙyÚ xÙz | xÚ yÙz = (xÚy) Ù (xÚz) | (5) |
Правила Де Моргана | (xÚy)= xÙ(y) | (xÙy)= xÚ(y) | (6) |
Идемпотенции | xÚx=x | xÙx=x | (7) |
Поглощения | xÚxÙy=x | xÙ(xÚy)=x | (8) |
Склеивания | xÙyÚ(x)Ùy=y | (xÚy)Ù (xÚy)=y | (9) |
Операция с переменной с ее инверсией | xÚ(x)=1 | xÙ(x)=0 | (10) |