Основы алгебры логики

Алгебра логики

Алгебра логики изучает высказывания и действия над ними. Высказывание — это повествовательное предложение, о котором можно однозначно сказать, истинно оно или ложно. Истинному высказыванию ставится в соответствие значение $1$, ложному — значение $0$. Например, высказывание «$5>3$» истинно и имеет значение $1$, а высказывание «$10<2$» ложно и имеет значение $0$.

Высказывания можно обозначать буквами $A$, $B$, $x$, $y$ и другими переменными. Над ними выполняются логические операции, из которых строятся более сложные логические выражения.

Основные логические операции

Отрицание (инверсия) высказывания $A$ обозначается $\neg A$ и меняет его значение на противоположное: если $A=1$, то $\neg A=0$; если $A=0$, то $\neg A=1$. Читается как «не $A$» или «неверно, что $A$».

Конъюнкция двух высказываний обозначается $A\land B$ и читается как «$A$ и $B$». Конъюнкция истинна только тогда, когда истинны оба высказывания одновременно.

Дизъюнкция обозначается $A\lor B$ и читается как «$A$ или $B$». Дизъюнкция истинна, если истинно хотя бы одно из двух высказываний.

Импликация обозначается $A\to B$ и читается как «из $A$ следует $B$» или «если $A$, то $B$». Импликация ложна только в одном случае: когда условие $A$ истинно, а следствие $B$ ложно.

Эквивалентность обозначается $A\leftrightarrow B$ или $A\equiv B$. Она истинна тогда, когда значения $A$ и $B$ совпадают: оба равны $0$ или оба равны $1$.

Исключающее ИЛИ обозначается $A\oplus B$. Оно истинно тогда, когда значения $A$ и $B$ различаются.

Для исключающего ИЛИ таблица выглядит следующим образом:

Таким образом, основные операции удобно запомнить следующим образом: $A\land B$ требует две единицы; $A\lor B$ требует хотя бы одну единицу; $A\to B$ ложно только для пары $1\to0$; $A\leftrightarrow B$ истинно при одинаковых значениях; $A\oplus B$ — при разных.

Порядок выполнения логических операций

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

вычисляется как

Если порядок действий может быть понят неоднозначно, лучше явно использовать скобки. Особенно это важно при переносе логического выражения в программу: приоритет операций в Python не полностью совпадает с привычной математической записью.

Логические операции в Python

В Python значения $0$ и $1$ можно использовать как ложь и истину соответственно. Основные операции алгебры логики записываются следующим образом:

Например, логическое выражение

в Python записывается так:

(not A) and (B or C)

Для импликации отдельного логического оператора в Python нет. Поэтому её можно преобразовать по формуле

и записать:

(not A) or B

В задачах ЕГЭ часто используется более короткая запись:

A <= B

Для значений $0$ и $1$ она действительно имеет ту же таблицу истинности, что и импликация:

Получаем соответственно значения $1,1,0,1$, то есть таблицу истинности импликации.

Однако здесь есть важный момент. Оператор <= в Python является не логической операцией, а операцией сравнения. Поэтому Python обрабатывает его по своим правилам приоритета. Операции сравнения <=, ==, != имеют более высокий приоритет, чем логические операции not, and и or. Кроме того, несколько сравнений подряд Python может воспринимать как цепочку сравнений. Поэтому при замене импликации на <= её необходимо заключать в скобки.

Например,

нужно записывать так:

(A <= B) and (C <= D)

А не без скобок. Такое правило позволяет избежать ошибок, особенно в длинных логических выражениях. Аналогично эквивалентность и исключающее ИЛИ в сложных формулах удобно заключать в скобки:

(A == B)
(A != B)

Для школьных задач можно придерживаться простого правила: каждую импликацию, эквивалентность и исключающее ИЛИ при переводе в Python заключаем в скобки.

Например, выражение

запишется как

(x == (w or y)) or ((w <= z) and (y <= w))

Основные законы алгебры логики

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

1. Закон повторения (идемпотентности):

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

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

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

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

6. Законы де Моргана:

То есть при раскрытии отрицания над скобкой операция $\lor$ заменяется на $\land$, операция $\land$ заменяется на $\lor$, а каждое высказывание внутри скобок получает отрицание.

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

8. Действия с логическими константами:

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

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

11. Отрицание логических констант:

12. Преобразование импликации:

Это одна из самых важных формул: импликацию всегда можно заменить сочетанием отрицания и дизъюнкции.

13. Отрицание импликации:

Импликация ложна только тогда, когда $A=1$, а $B=0$, поэтому её отрицание истинно именно при $A\land\neg B$.

14. Контрапозиция:

15. Преобразование эквивалентности:

Эквивалентность истинна, когда оба значения одинаковы: либо оба равны $1$, либо оба равны $0$.

Также эквивалентность можно представить через две импликации:

16. Преобразование исключающего ИЛИ:

Также справедлива формула

17. Связь эквивалентности и исключающего ИЛИ:

18. Законы склеивания:

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

Построение таблицы истинности

Если логическая функция содержит $n$ переменных, каждая из которых может принимать два значения — $0$ или $1$, то полная таблица истинности содержит 2ⁿ наборов значений. Например, для трёх переменных получим $2^3=8$ строк, а для четырёх — $2^4=16$ строк.

В Python все наборы удобно получить вложенными циклами. Например, для четырёх переменных:

for w in 0,1: 
    for x in 0,1: 
        for y in 0,1: 
            for z in 0,1:

Каждый цикл перебирает два возможных значения своей переменной, поэтому в результате будут рассмотрены все $16$ комбинаций.

Шаблон решения типовых заданий

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

Сначала выписываем все переменные функции и создаём для каждой из них цикл по значениям $0$ и $1$. Затем внутри самого вложенного цикла записываем логическое выражение в условии if.

Если в таблице представлены строки, для которых $F=0$, ищем именно такие наборы:

print('w x y z') 
for w in 0,1: 
    for x in 0,1: 
        for y in 0,1: 
            for z in 0,1: 
                if <логическое выражение> == 0: 
                    print(w,x,y,z)

Если нужны строки, в которых функция равна $1$, условие меняется на:

if <логическое выражение> == 1:

Например, для функции

и строк, в которых $F=0$, получим:

print('w x y z') 
for w in 0,1: 
    for x in 0,1: 
        for y in 0,1: 
            for z in 0,1: 
                if ((x == (w or y)) or ((w <= z) and (y <= w))) == 0: 
                    print(w,x,y,z)

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

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

Например, если программа вывела набор

а в одной из строк исходной таблицы известно, что первый столбец содержит $1$, а третий — $0$, нужно проверить, какие из переменных могут стоять в этих столбцах. Затем аналогично рассматриваются остальные строки. Правильным будет только такое расположение переменных, которое одновременно подходит ко всему данному фрагменту таблицы.

Таким образом, общий алгоритм решения можно сформулировать так: переводим логическое выражение на язык Python; перебираем все значения переменных; оставляем строки с нужным значением функции; сопоставляем полученные наборы с данными из таблицы; записываем переменные в порядке соответствующих им столбцов. Главное при переводе выражения в Python — не менять его структуру. Скобки из исходной формулы лучше сохранять, а импликацию, записанную через <=, обязательно заключать в скобки. Это позволяет избежать ошибок из-за приоритета операций и делает программную запись максимально похожей на исходное логическое выражение.