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

Логическое выражение → таблица истинности и тип выражения

Переменные — латинские буквы A–D; ¬ (не, !, not), ∧ (и, &, *), ∨ (или, |, +), → (->, imp), ≡ (~, =, eq)

Выключите, чтобы оставить только наборы, где F = 1

Нашли ошибку или хотите предложить улучшение?

Улучшить калькулятор «Таблица истинности»

Теория

Логическое выражение состоит из переменных (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, и никакие операции на это не влияют.

Пример с решением

  1. Условие. Построить таблицу истинности для выражения \(F = A \land B \lor \neg C\).
  2. Переменные. В выражении три переменные, значит строк \(2^3 = 8\).
  3. Порядок действий. Сначала \(A \land B\) и \(\neg C\), только потом дизъюнкция.
  4. Первая строка. \(A = 0\), \(B = 0\), \(C = 0\): \(A \land B = 0\), \(\neg C = 1\), поэтому \(F = 0 \lor 1 = 1\).
  5. Вторая строка. \(A = 0\), \(B = 0\), \(C = 1\): \(A \land B = 0\), \(\neg C = 0\), поэтому \(F = 0 \lor 0 = 0\).
  6. Последняя строка. \(A = 1\), \(B = 1\), \(C = 1\): \(A \land B = 1\), \(\neg C = 0\), поэтому \(F = 1 \lor 0 = 1\).
  7. Ответ. \(F = 1\) в пяти строках из восьми, значит выражение выполнимое. Калькулятор с выражением \(A \land B \lor \neg C\) выдаст ту же таблицу, тот же вывод и подскажет, какие именно наборы дают \(F = 1\).

Главное

  • Строк в таблице — \(2^n\), где \(n\) — число различных переменных выражения.
  • Порядок действий: скобки и \(\neg\), затем \(\land\), затем \(\lor\), затем \(\to\), затем \(\equiv\).
  • Тип выражения читается по столбцу F: тавтология, противоречие или выполнимое.
  • Наборы перебирают двоичным счётом — тогда ни одна комбинация не потеряется.