Построение таблицы истинности
Построение таблицы истинности — это последовательная запись всех наборов значений переменных и вычисление значения выражения для каждого набора. Такой способ позволяет полностью определить, когда логическое выражение истинно, а когда ложно.
Сколько строк и столбцов нужно
Если выражение содержит \(n\) различных переменных, таблица должна иметь \(2^n\) строк с наборами значений. Каждая переменная принимает одно из двух значений: \(0\) — ложь или \(1\) — истина. Кроме столбцов переменных обычно создают отдельный столбец для каждой промежуточной части выражения и последний столбец для всего выражения.
Алгоритм построения
- Выписать все переменные, входящие в выражение, без повторений.
- Определить число строк: \(2^n\).
- Перечислить наборы значений переменных в едином порядке, например от \(00\ldots0\) до \(11\ldots1\).
- Разбить выражение на операции и добавить столбцы для промежуточных результатов.
- Заполнить столбцы, начиная с внутренних скобок, затем выполнить отрицание, конъюнкцию, дизъюнкцию и другие операции согласно порядку действий.
- В последнем столбце записать значения всего выражения.
Для выражения \(A\land\neg B\) нужны две переменные, поэтому будет \(2^2=4\) строки. Удобно добавить промежуточный столбец \(\neg B\), а затем вычислить конъюнкцию \(A\land\neg B\). Результат равен \(1\) только при \(A=1\) и \(B=0\).
| A | B | ¬B | A ∧ ¬B |
|---|---|---|---|
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |
Число строк зависит только от количества различных переменных, а не от числа их упоминаний. В выражении \(A\lor A\land B\) переменных две — \(A\) и \(B\), поэтому строк будет төрт, а не больше из-за повторения \(A\).
Сколько строк должна содержать таблица истинности для выражения \((A\lor B)\land\neg C\)?
Главное
- Для \(n\) различных переменных таблица содержит \(2^n\) наборов значений.
- Сначала вычисляют промежуточные операции, затем значение всего выражения.
- Последний столбец показывает результат логического выражения для каждого набора.