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

Учимся говорить на языке логики: высказывания, связки и таблицы истинности — основа любого условия в коде.

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

Зачем программисту логика

Каждое if в твоём коде — это высказывание. Каждое условие в SQL-запросе, каждый фильтр, каждая проверка валидности — логика. Более того, сами цифровые схемы внутри процессора — это материализованная логика (об этом будет раздел про булеву алгебру). Логика высказываний даёт точные правила: когда сложное условие истинно, как его упростить, когда два условия эквивалентны (и можно безопасно заменить одно другим). Это спасает от багов вроде «перепутал and и or» или «неправильно вынес отрицание за скобки».

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

«Москва — столица России» — истинное высказывание. «2 + 2 = 5» — ложное высказывание. А вот «Который час?» или «Закрой дверь» — не высказывания: у них нет истинностного значения. Высказывания обозначают буквами p, q, r и приписывают им одно из двух значений: истина (1, True) или ложь (0, False). Дискретность здесь принципиальна: ровно два значения, никаких «может быть».

Логические связки

Из простых высказываний строят сложные с помощью связок. Вот пять основных.

Связка	Обозначение	Читается	Истинна, когда
Отрицание	`¬p`	не p	p ложно
Конъюнкция	`p ∧ q`	p и q	оба истинны
Дизъюнкция	`p ∨ q`	p или q	хотя бы один истинен
Импликация	`p → q`	если p, то q	ложна только при p=1, q=0
Эквивалентность	`p ↔ q`	p тогда и только тогда, когда q	значения совпадают

Самая коварная связка — импликация

«Если p, то q» сбивает с толку: импликация p → q ложна в единственном случае — когда посылка p истинна, а следствие q ложно. Во всех остальных случаях она истинна, включая случай ложной посылки! «Если 2×2=5, то я миллионер» — истинное высказывание, потому что посылка ложна. Интуиция: обещание «если сдашь экзамен — куплю телефон» нарушено только тогда, когда ты сдал, а телефон не купили. Если экзамен не сдан — обещание не нарушено независимо от телефона.

Полезнейшая эквивалентность: p → q равносильно ¬p ∨ q («не p, или q»). Через неё импликацию удобно сводить к уже знакомым «не» и «или».

Таблицы истинности

Таблица истинности перечисляет все комбинации значений переменных и показывает результат формулы для каждой. Для n переменных строк ровно 2^n (вспоминаем булеан!). Таблица — это полный «паспорт» формулы: две формулы равносильны тогда и только тогда, когда у них совпадают таблицы. Построим таблицу для основных связок прямо в Python, где True/False ведут себя как 1/0.

print("p q | p->q  p∧q  p∨q  p⊕q")
for p in (0, 1):
    for q in (0, 1):
        impl = int((not p) or q)   # импликация = ¬p ∨ q
        conj = p & q               # И
        disj = p | q               # ИЛИ
        xor  = p ^ q               # исключающее ИЛИ
        print(f"{p} {q} |  {impl}    {conj}    {disj}    {xor}")

Вывод:

p q | p->q  p∧q  p∨q  p⊕q
0 0 |  1    0    0    0
0 1 |  1    0    1    1
1 0 |  0    0    1    1
1 1 |  1    1    1    0

Смотри на столбец p->q: единственный 0 стоит в строке 1 0 — ровно как мы и говорили. А p⊕q (исключающее «или», xor) истинно, когда значения разные — это «или, но не оба». Xor вам ещё пригодится: на нём держатся контрольные суммы, простейшее шифрование и работа с битами.

Приоритет операций

Как и в арифметике, у связок есть старшинство, чтобы не ставить скобки на каждом шагу. По убыванию силы: ¬ (отрицание) → ∧ (и) → ∨ (или) → → (импликация) → ↔ (эквивалентность). То есть ¬p ∧ q ∨ r читается как ((¬p) ∧ q) ∨ r. Но в сомнительных случаях скобки лучше ставить явно — и в формуле, и в коде. «Слишком умное» условие без скобок — частый источник ошибок.

Мощность бесконечных множеств: биекция как мерило

Биекция — это не только про конечные множества. Именно ею Георг Кантор в конце XIX века научился сравнивать бесконечности. Идея смелая: два множества «равномощны», если между ними есть биекция. И тут начинаются сюрпризы. Натуральных чисел «столько же», сколько чётных — ведь n ↦ 2n это биекция, хотя чётные кажутся «вдвое реже». Целых и даже рациональных чисел тоже «столько же», сколько натуральных: все они счётны, их можно занумеровать.

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

Проверяем эквивалентность формул кодом

Из таблицы истинности следует мощная идея: две формулы равносильны, если их таблицы совпадают. Это легко проверить перебором всех наборов значений — мы фактически строим «маленький решатель». Убедимся, например, что импликация p → q действительно равна ¬p ∨ q, как мы утверждали выше.

from itertools import product

def equivalent(f, g, n):
    # совпадают ли таблицы истинности двух формул от n переменных
    return all(f(*bits) == g(*bits) for bits in product([0, 1], repeat=n))

impl = lambda p, q: int((not p) or q)       # p → q
or_form = lambda p, q: int((1 - p) or q)    # ¬p ∨ q

print("(p→q) ≡ (¬p ∨ q):", equivalent(impl, or_form, 2))
print("Таблица p→q:", [impl(p, q) for p in (0, 1) for q in (0, 1)])

Вывод:

(p→q) ≡ (¬p ∨ q): True
Таблица p→q: [1, 1, 0, 1]

Перебор подтвердил равносильность. Такой приём — «обернуть гипотезу о равенстве формул в функцию и проверить на всех наборах» — мы будем активно использовать в уроке про тавтологии. Для формул с n переменными это 2^n проверок: быстро для маленьких n, но напоминание о том, что число строк таблицы растёт экспоненциально.

Типичные ошибки

Считать импликацию ложной при ложной посылке. Нет: p → q ложна только при p=1, q=0. Ложная посылка делает импликацию истинной.
Путать дизъюнкцию и xor. Обычное «или» (∨) истинно и когда оба истинны; «исключающее или» (⊕) — только когда ровно один.
Забывать про приоритет. ¬p ∧ q — это (¬p) ∧ q, а не ¬(p ∧ q). Это совсем разные формулы.

Итог

Высказывание — предложение с однозначным значением «истина/ложь».
Пять связок: ¬, ∧, ∨, →, ↔; импликация ложна только при истинной посылке и ложном следствии.
p → q равносильна ¬p ∨ q.
Таблица истинности (2^n строк) — полный паспорт формулы и инструмент проверки равносильности.