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

Как узнать, что аргумент работает ВСЕГДА, а не только в примерах, которые мы проверили? Таблицы истинности - это способ перебрать ВСЕ возможные случаи и убедиться наверняка.

• **Проектирование схем:** Каждый логический элемент компьютера — это реализация таблицы истинности в кремнии
• **Проверка контрактов:** Юристы используют логику для поиска лазеек — комбинаций условий, где контракт не работает
• **Тестирование ПО:** Таблицы решений (decision tables) — прямые потомки таблиц истинности для проверки всех веток кода

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

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

**Истоки:** Таблицы истинности формализовал Людвиг Витгенштейн в 1921 году. Они стали основой компьютерной логики - каждый транзистор реализует простейшую таблицу истинности.

**Количество строк:** Если в формуле n переменных, таблица имеет 2ⁿ строк. Две переменные - 4 строки. Три - 8. Четыре - 16. Поэтому для сложных формул таблицы становятся громоздкими.

Систематическая проверка

**Систематическая проверка** - это пошаговое вычисление сложной формулы через таблицу истинности. Мы разбиваем формулу на части и вычисляем каждую часть для всех комбинаций.

**Порядок операций:** Сначала отрицания (¬), потом конъюнкции (∧), потом дизъюнкции (∨), последними - импликации (→) и эквиваленции (↔). Скобки меняют порядок.

**Проверка аргумента через таблицу:** Аргумент валиден, если НЕ существует строки, где все посылки истинны, а вывод ложен. Достаточно найти одну такую строку - и аргумент опровергнут.

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

Тавтология

**Тавтология** - это формула, истинная при ЛЮБЫХ значениях переменных. В таблице истинности у неё все строки дают «И». Тавтологии - это законы логики, работающие всегда.

**Почему это важно:** Тавтологии - это «бесплатные» утверждения. Их истинность не зависит от фактов о мире. Они истинны по самой структуре логики.

**Тавтология и валидность:** Аргумент валиден тогда и только тогда, когда формула «(Посылка₁ ∧ Посылка₂ ∧ ... ∧ Посылкаₙ) → Вывод» является тавтологией.

Противоречие

**Противоречие** - это формула, ложная при ЛЮБЫХ значениях переменных. В таблице истинности все строки дают «Л». Это антипод тавтологии.

**Связь с тавтологией:** Формула F - противоречие ⟺ ¬F - тавтология. Отрицание противоречия всегда истинно, отрицание тавтологии всегда ложно.

**Контингентная формула** - ни тавтология, ни противоречие. Истинна при одних значениях, ложна при других. Большинство формул - контингентные. Они «зависят от обстоятельств».

**Практическое значение:** Если из твоих посылок следует противоречие - твои посылки несовместимы. Хотя бы одна из них должна быть ложной. Это основа доказательства от противного.

Ключевые идеи

• **Таблица истинности** перебирает все 2ⁿ комбинаций n переменных и вычисляет результат формулы
• **Аргумент валиден**, если нет строки, где все посылки истинны, а вывод ложен (контрпример)
• **Тавтология** — формула, истинная всегда; **Противоречие** — формула, ложная всегда
• **Контингентная формула** — истинна при одних значениях, ложна при других — зависит от фактов

Связанные темы

Таблицы истинности - основа для формальных методов:

• Отрицание — Таблица истинности показывает, как отрицание инвертирует значения
• Логическая эквивалентность — Две формулы эквивалентны, если их таблицы истинности совпадают

Вопросы для размышления

• Почему таблицы истинности работают для пропозициональной логики, но не для предикатной (с кванторами «все», «существует»)?
• При 10 переменных таблица имеет 1024 строки. Как компьютеры справляются с формулами, где сотни переменных?
• Можно ли считать законы логики (тавтологии) «открытыми» или они «изобретены»?

Связанные уроки

• comp-23-local-optimization
• ml-01