Высказывания, логические операции и таблицы истинности

Язык, на котором рассуждают и компьютеры, и математики: от «истина/ложь» к таблицам истинности.

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

Зачем это нужно

Каждое условие в программе (if x > 0 and y < 10), каждый поисковый запрос («Python И не Java»), каждая логическая схема внутри процессора — это математическая логика. Она же — целый блок заданий ЕГЭ. Освоив её, вы перестанете гадать, когда сложное условие истинно, и научитесь упрощать запутанные проверки. А главное — увидите, что мышление компьютера строится на нескольких простых операциях.

Математическая логика появилась задолго до компьютеров. В середине XIX века английский математик Джордж Буль предложил описывать рассуждения алгеброй, где переменные принимают всего два значения — «истина» и «ложь», а связки «и», «или», «не» становятся операциями. Почти столетие это считалось красивой абстракцией без практической пользы. Всё изменилось в 1930-х, когда Клод Шеннон заметил: булева алгебра идеально описывает работу электрических переключателей — замкнут контакт или разомкнут. Так логика Буля стала фундаментом цифровой техники. Поэтому, изучая таблицы истинности, вы не просто готовитесь к экзамену — вы осваиваете тот самый язык, на котором спроектирован каждый процессор в мире.

Что считается высказыванием

«Москва — столица России» — высказывание (истинно). «2 + 2 = 5» — тоже высказывание (ложно). А вот «Который час?» или «Реши уравнение» высказываниями не являются: им нельзя приписать истину или ложь. В логике значения обозначают 1 (истина) и 0 (ложь) — и это снова возвращает нас к двоичной системе.

Пять базовых операций

Из простых высказываний строят сложные с помощью логических операций. Вот они в порядке приоритета (от высшего к низшему):

Операция	Обозначение	Читается	Истинна, когда
отрицание	¬A, НЕ A	«не A»	A ложно
конъюнкция	A ∧ B, A И B	«A и B»	оба истинны
дизъюнкция	A ∨ B, A ИЛИ B	«A или B»	хотя бы один истинен
импликация	A → B	«если A, то B»	ложна только при A=1, B=0
эквивалентность	A ↔ B	«A равносильно B»	значения совпадают

Самая коварная — импликация. «Если пойдёт дождь, я возьму зонт» — это обещание нарушено только в одном случае: дождь пошёл (A=1), а зонт не взят (B=0). Во всех остальных случаях обещание считается выполненным, в том числе когда дождя не было. Отсюда правило: импликация ложна лишь когда из истины следует ложь.

Таблица истинности своими руками

Таблица истинности перечисляет все комбинации значений переменных и результат выражения для каждой. Для n переменных строк ровно 2ⁿ. Построим таблицу для всех пяти операций сразу. В Python отрицание — not, конъюнкция — and, дизъюнкция — or; импликацию и эквивалентность выразим формулами:

def impl(a, b):     # импликация A → B  равна  (not A) or B
    return (not a) or b

def equ(a, b):      # эквивалентность A ↔ B
    return a == b

print("A B | not-A  A-and-B  A-or-B  A-impl-B  A-equ-B")
print("-" * 46)
for a in (0, 1):
    for b in (0, 1):
        row = (
            int(not a), int(a and b), int(a or b),
            int(impl(a, b)), int(equ(a, b)),
        )
        print(f"{a} {b} |   {row[0]}      {row[1]}        {row[2]}       {row[3]}        {row[4]}")

Вывод:

A B | not-A  A-and-B  A-or-B  A-impl-B  A-equ-B
----------------------------------------------
0 0 |   1      0        0       1        1
0 1 |   1      0        1       1        0
1 0 |   0      0        1       0        0
1 1 |   0      1        1       1        1

Вглядитесь в столбец импликации: единственный 0 стоит в строке A=1, B=0 — ровно как мы рассуждали про зонт.

Вычисление сложного выражения

Когда операций несколько, важен приоритет: сначала ¬, затем ∧, затем ∨, потом → и ↔. Скобки, как в арифметике, меняют порядок. Посчитаем выражение (A ∨ B) ∧ ¬C для всех восьми комбинаций трёх переменных — и пусть Python проверит нас:

print("A B C | (A or B) and not C")
print("-" * 30)
for a in (0, 1):
    for b in (0, 1):
        for c in (0, 1):
            value = (a or b) and (not c)
            print(f"{a} {b} {c} |        {int(value)}")

Вывод:

A B C | (A or B) and not C
------------------------------
0 0 0 |        0
0 0 1 |        0
0 1 0 |        1
0 1 1 |        0
1 0 0 |        1
1 0 1 |        0
1 1 0 |        1
1 1 1 |        0

Выражение истинно там, где хотя бы одна из A, B истинна И при этом C ложна. Таблица — надёжный способ не ошибиться в сложном условии.

Попробуй сам

Сравним два выражения по их таблицам истинности. Если все строки совпали — выражения равносильны. Проверим, правда ли, что ¬(A ∧ B) равно ¬A ∨ ¬B (один из законов де Моргана, к которым вернёмся в следующем уроке):

def left(a, b):
    return not (a and b)

def right(a, b):
    return (not a) or (not b)

same = True
for a in (0, 1):
    for b in (0, 1):
        l, r = left(a, b), right(a, b)
        print(f"A={a} B={b}: {int(l)} vs {int(r)}")
        if l != r:
            same = False
print("Выражения равносильны?", same)

Вывод:

A=0 B=0: 1 vs 1
A=0 B=1: 1 vs 1
A=1 B=0: 1 vs 1
A=1 B=1: 0 vs 0
Выражения равносильны? True

Частые ошибки

Считают импликацию «симметричной». A → B и B → A — разные выражения; путаница с этим стоит баллов на ЕГЭ.
Забывают приоритет. Без скобок A ∨ B ∧ C читается как A ∨ (B ∧ C), потому что ∧ старше ∨.
Думают, что «или» исключающее. Логическое ИЛИ (дизъюнкция) истинно и когда оба истинны; «либо-либо» — это уже XOR.
Путают «истинно всегда» и «истинно при данных значениях». Тождественно истинное выражение (тавтология) истинно при любых значениях переменных.

Итоги

Высказывание — это утверждение, которому можно приписать 1 (истина) или 0 (ложь).
Базовых операций пять: ¬, ∧, ∨, →, ↔; приоритет именно в этом порядке.
Импликация A → B ложна только при A=1, B=0 и равна ¬A ∨ B.
Таблица истинности перечисляет все 2ⁿ комбинаций — это безотказный инструмент проверки.