Теория
Логическое выражение состоит из переменных (A, B, C, D), каждая из которых принимает одно из двух значений: 0 — ложь, 1 — истина. Связывают переменные логические операции: отрицание \(\neg A\), конъюнкция \(A \land B\), дизъюнкция \(A \lor B\), импликация \(A \to B\) и эквивалентность \(A \equiv B\). Порядок действий такой же строгий, как в арифметике: сначала скобки и отрицание, затем конъюнкция, затем дизъюнкция, затем импликация, затем эквивалентность.
Таблица истинности содержит по одной строке на каждый набор значений переменных: для \(n\) переменных строк ровно \(2^n\) (для трёх переменных — 8, для четырёх — 16). Наборы удобно перебирать «по-школьному», двоичным счётом: старшая переменная меняется вдвое реже следующей, поэтому столбец A — это 00001111, столбец B — 00110011, столбец C — 01010101.
По последнему столбцу определяют тип выражения. Если \(F = 1\) во всех строках, выражение тождественно истинное (тавтология); если ни в одной строке — тождественно ложное (противоречие); если хотя бы в одной — выполнимое.
Важно: число строк таблицы зависит только от числа переменных — \(2^n\). Три переменные дают ровно 8 строк, четыре — 16, и никакие операции на это не влияют.
Пример с решением
- Условие. Построить таблицу истинности для выражения \(F = A \land B \lor \neg C\).
- Переменные. В выражении три переменные, значит строк \(2^3 = 8\).
- Порядок действий. Сначала \(A \land B\) и \(\neg C\), только потом дизъюнкция.
- Первая строка. \(A = 0\), \(B = 0\), \(C = 0\): \(A \land B = 0\), \(\neg C = 1\), поэтому \(F = 0 \lor 1 = 1\).
- Вторая строка. \(A = 0\), \(B = 0\), \(C = 1\): \(A \land B = 0\), \(\neg C = 0\), поэтому \(F = 0 \lor 0 = 0\).
- Последняя строка. \(A = 1\), \(B = 1\), \(C = 1\): \(A \land B = 1\), \(\neg C = 0\), поэтому \(F = 1 \lor 0 = 1\).
- Ответ. \(F = 1\) в пяти строках из восьми, значит выражение выполнимое. Калькулятор с выражением \(A \land B \lor \neg C\) выдаст ту же таблицу, тот же вывод и подскажет, какие именно наборы дают \(F = 1\).
Главное
- Строк в таблице — \(2^n\), где \(n\) — число различных переменных выражения.
- Порядок действий: скобки и \(\neg\), затем \(\land\), затем \(\lor\), затем \(\to\), затем \(\equiv\).
- Тип выражения читается по столбцу F: тавтология, противоречие или выполнимое.
- Наборы перебирают двоичным счётом — тогда ни одна комбинация не потеряется.