Число строк таблицы истинности
Количество строк в таблице истинности зависит только от числа различных логических переменных. Если переменных \(n\), таблица содержит \(2^n\) строк с наборами их значений.
Здесь \(N\) — число строк таблицы, а \(n\) — число различных переменных. Основание степени равно \(2\), потому что каждая переменная может иметь значение 0 или 1. Для каждой новой переменной число возможных наборов удваивается.
| Число переменных \(n\) | Число строк \(N=2^n\) |
|---|---|
| 1 | 2 |
| 2 | 4 |
| 3 | 8 |
| 4 | 16 |
| 5 | 32 |
В выражении \(A \land (B \lor C)\) содержатся три различные переменные: \(A\), \(B\) и \(C\). Поэтому таблица должна иметь \(2^3=8\) строк. В каждой строке записывается один возможный набор значений этих переменных: например, \((0,0,0)\) немесе \((1,0,1)\).
В формуле учитываются только различные логические переменные, а не количество упоминаний переменных, операций или столбцов. Например, в выражении \(A \lor A \lor B\) две различные переменные — \(A\) и \(B\), поэтому строк будет \(2^2=4\). Столбцы для промежуточных результатов и итогового выражения добавляются отдельно и число строк не изменяют.
Сколько строк должна содержать таблица истинности выражения \((A \land B) \lor \neg C\)?
Главное
- Если в выражении \(n\) различных логических переменных, число строк таблицы равно \(2^n\).
- Каждая новая переменная удваивает число возможных истинностных наборов.
- Количество операций и дополнительных столбцов не влияет на число строк.