🔀 Дискретка

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

Q: Сколько строк в таблице истинности для 5 переменных?

$2^5 = 32$. Число строк растёт экспоненциально: для 10 переменных их уже 1024. Поэтому большие формулы упрощают не таблицей, а эквивалентными преобразованиями и законами алгебры логики.

Q: Можно ли строить таблицу для трёх и более переменных?

Можно, схема та же: $2^3 = 8$ строк для трёх переменных, столбцы промежуточных операций по приоритетам. Меняется только объём работы — механика построения от $n$ не зависит, поэтому её легко доверить и программе.

англ. Truth table

Полный протокол испытаний логической формулы: все комбинации нулей и единиц входов и ответ на каждую. 2ⁿ строк — и никакое спорное утверждение не спрячется.

Таблица истинности — полный протокол поведения логической формулы: для каждой комбинации значений переменных (истина/ложь, 1/0) записано значение всей формулы. Переменных две — строк четыре, переменных $n$ — строк $2^{n}$ : никаких «обычно» и «почти всегда», формула либо выдерживает все строки, либо нет. Базовые операции — НЕ ( $\neg$ ), И ( $\land$ ), ИЛИ ( $\lor$ ), импликация ( $\to$ ) — задаются таблицами на 2 и 4 строки; разбор каждой — в уроке логика высказываний.

(A \to B) \leftrightarrow (\neg A \lor B)

классическая проверка таблицей: столбцы совпадают во всех 2² = 4 строках, значит формула — тавтология

Строится таблица по жёсткому рецепту. Слева — столбцы переменных: все комбинации 0 и 1, удобно перечислять их как двоичный счётчик (00, 01, 10, 11), чтобы ничего не потерять. Дальше — столбцы промежуточных подформул слева направо по приоритету операций: сначала НЕ, потом И, затем ИЛИ, импликация и эквивалентность — последними. Последний столбец — вся формула. Для $(A \to B)$ четыре строки дают 1, 1, 0, 1: единственный ноль — при $A = 1, B = 0$ , «из истины не следует ложь».

Конструктор логических операций

Щёлкай переключатели!

Логика в компьютере — это всего лишь нули и единицы. Переключайте A и B и смотрите, как меняются результаты всех восьми базовых операций. Развёрнутая таблица истинности раскрывается по клику.

A	B	A ⊕ B
0	0	0
0	1	1
1	0	1
1	1	0

Импликация A→B ложна только в одном случае: из истины не может следовать ложь.

Зачем таблицы за пределами семинара? Тавтологии — формулы с одними единицами в итоговом столбце — превращаются в законы логики, на которых стоит упрощение формул: полный арсенал — в уроке булева алгебра. По таблице же формула переводится в СДНФ и СКНФ — нормальные формы, по которым строятся цифровые схемы: каждая строка с единицей становится конъюнкцией-«строчкой памяти» вентиля. На кванторы таблица не натягивается напрямую — там вступает логика предикатов, но принцип «проверить всё» остаётся.

Частые вопросы

Сколько строк в таблице истинности для 5 переменных?

$2^{5} = 32$ . Число строк растёт экспоненциально: для 10 переменных их уже 1024. Поэтому большие формулы упрощают не таблицей, а эквивалентными преобразованиями и законами алгебры логики.

Как по таблице понять, что формула — тавтология или противоречие?

Тавтология: в итоговом столбце одни единицы при любых входах (пример — $A \lor \neg A$ ). Противоречие: одни нули ( $A \land \neg A$ ). Всё остальное — выполнимая формула: истина хотя бы в одной строке.

Можно ли строить таблицу для трёх и более переменных?

Можно, схема та же: $2^{3} = 8$ строк для трёх переменных, столбцы промежуточных операций по приоритетам. Меняется только объём работы — механика построения от $n$ не зависит, поэтому её легко доверить и программе.