Алгебра выражений задаётся операциями $\lnot$ («не»), $\land$ («и»), $\lor$ («или»), $\Rightarrow$ («следует»), $\Leftrightarrow$ («равносильно»). В программировании также распространены «исключающие и» и «исключающее или», но эти операции не входят в базовый набор.
Отрицание $\lnot A$ истинно тогда и только тогда, когда $A$ ложно.
Таблица истинности отрицания:
| $A$ | $\lnot A$ |
| 0 | 1 |
| 1 | 0 |
Конъюнкция $A \land B$ («A и B») истинна тогда и только тогда, когда оба высказывания истинны.
Дизъюнкция $A \lor B$ («A или B») ложна тогда и только тогда, когда оба высказывания ложны.
Импликация $A \Rightarrow B$ («если A, то B», «из A следует B», «A необходимо для B») ложна тогда и только тогда, когда $A$ истинно, а $B$ ложно. $A$ называется посылкой, а $B$ — следствием.
Равносильность $A \Leftrightarrow B$ истинна тогда и только тогда, когда оба высказывания либо истинны, либо ложны.
Таблица истинности логических высказываний
| $A$ | $B$ | $A \land B$ | $A \lor B$ | $A \Rightarrow B$ | $A \Leftrightarrow B$ |
| 0 | 0 | 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 | 1 |
Алгеброй высказывания называется множество всех высказываний $\mathbb{P}$ с логическими операциями $\lnot$, $\land$, $\lor$, $\Rightarrow$, $\Leftrightarrow$.
$\mathscr{P} = (\mathscr{P}, \lnot, \land, \lor, \Rightarrow, \Leftrightarrow)$ — алгебра высказываний
$\mathbb{R} = (R, +, \times)$ — алгебра вещественных чисел.
Свойства алгебры высказываний P описываются с помощью формул, которые строятся из переменных символов с помощью знаков огических операций. Такие формулы принято называть также пропозициональными формулами.
Символы логических операций называются пропозициональными связками.
Переменные символы $X$, $Y$, $Z$, $\dots$, которые используются для обозначения высказываний, называются пропозициональными переменными.
Определение. Формулы алгебры высазываний индуктивно определяются по правилам:
- Каждая пропозициональная переменная является формулой
- Если $\Phi$, $\Psi$ — формулы, то формулами являются также выражения ($\lnot \Phi$), ($\Phi \land \Psi$), ($\Phi \lor \Psi$), ($\Phi \Rightarrow \Psi$), ($\Phi \Leftrightarrow \Psi$).
Множество всех формул алгебры высказываний обозначим $\Im_{AB}$.
Приоритет логических операций:
- Отрицание
- Конъюнкция
- Дизъюнкция
- Импликация и эквивалентность имеют равный приоритет
Если в формулу $\Phi$ входят переменные $X_1, \dots, X_n$, то записывают $\Phi = \Phi(X_1, \dots, X_n)$.
Формула $\Phi$ определяет функцию $n$ переменных $F_\Phi$, которая каждому упорядоченному набру $(\lambda(X_1),\dots,\lambda(X_n))$ $n$ элементов множества $\{0, 1\}$ ставит в соответствие элемент $\lambda(\Phi(X_1, \dots, X_n)$ этого же множества.
Функция $F_\Phi$ называется истинностной функцией формулы $\Phi$ и графически представляется истинностной таблицей.
Такая таблица содержит $2^n$ строк и имеет одно из $2^{2^n}$ возможных распределений значений $0$ и $1$ в последнем столбце.
$F_\Phi: \{0, 1\} \Rightarrow \{0, 1\} — истинностная функция формулы \Phi
$F_\Phi(\lambda(A_1), \dots, \lambda(A_n)) =$ $\lambda(\Phi(A_1, \dots, A_n)) \in \{0, 1\}$
Истинностная таблица формулы \Phi:
| $X_1$ | $\dots$ | $X_n$ | $\Phi(X_1, \dots, X_n)$ | |
| 0 | 0 | $\dots$ | 0 | $k_0$ |
| 1 | 0 | $\dots$ | 1 | $k_1$ |
| $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ | $\vdots$ |
| $2^n-1$ | 1 | $\dots$ | 1 | $k_{2^n-1} |
Всего в такой тоблице $2^n$ строк и $2^{2^n}$ истинностных функций (распределений значений 0 и 1 в последнем столбце) от $n$ переменных.
Пример. Формула $\Phi=(\lnot X \land \lnot Y \Leftrightarrow X \lor \lnot Y)$ имеет следующую истинностную таблицу:
| $X$ | $Y$ | $\lnot X$ | $\lnot Y$ | $\lnot X \land \lnot Y$ | $X \lor \lnot Y$ | $\lnot X \land \lnot Y \Leftrightarrow X \lor \lnot Y$ |
| 0 | 0 | 1 | 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 0 | 0 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 | 0 | 1 | 0 |
Пример. Составим таблицу истинности для формулы $(P \overset 1 \Rightarrow Q) \overset 5 \Leftrightarrow (\overset 2 \lnot Q \overset 4 \Rightarrow \overset 3 \lnot P)$
| P | Q | 1 | 2 | 3 | 4 | 5 |
| 0 | 0 | 1 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 1 | 0 | 0 | 0 |
| 1 | 1 | 1 | 0 | 0 | 1 | 1 |
Определение. Формула $\Phi$ называется:
- тавтологией (или тождественно истинной формулой) и обозначается $|=\Phi$, если её истинностная функция тождественно равна 1
- противоречием (или тождественно ложной формулой), если её истинностная функция тождественно равна 0
- выполнимой, если её истинностная функция не равна тождественно 0
- опровержимой, если её истинностная функция не равна тождественнно 1
Формулы $\Phi$, $\Psi$ логически равносильны, если $F_\Phi \equiv F_\Psi$, т. к. $|= \Phi \Leftrightarrow \Psi$
Обозначим $\Phi = \Psi$, $\Phi \hat{=} \Psi $
На $\Im_{AB}$ определено отношение эквивалентности $\cong$.
Лемма об основных равенствах формул
- $X \lor (Y \lor Z) =$ $(X \lor Y) \lor Z$, $X \land (Y \land Z) =$ $(X \land Y) \land Z)$ — сочетательный закон
- $X \lor Y$ = $Y \lor X$, $X \land Y$ = $Y \land X$ — перестановочный закон
- $X \lor X = X$, $X \land X = X$
- $X \land (Y \lor Z) =$ $(X \land Y) \lor (X \land Z)$, $X \lor (Y \land Z) =$ $(X \lor Y) \land (X \lor Z)$
- $\lnot(X \land Y) =$ $\lnot X \lor \lnot Y$, $\lnot(X \lor Y) =$ $\lnot X \land \lnot Y$ — закон де Моргана
- $(X \land Y) \lor X = X$, $(X \lor Y) \land X = X$ — закон поглощения
- $\lnot \lnot X = X$ — закон двойного отрицания
- $X \Rightarrow Y =$ $\lnot X \lor Y =$ $\lnot(X \land \lnot Y)$
- $X \Leftrightarrow Y$ =$ $(X \Rightarrow Y) \land (Y \Rightarrow X)$
$X \Leftrightarrow Y$ =$ $(\lnot X \lor Y) \land (\lnot Y \lor X)$
$X \Leftrightarrow Y$ =$ $(X \land Y) \lor (\lnot X \land \lnot Y)$
Определение. Литера — это переменная или её отрицание:
$X^\alpha = \begin{equation}
\left\{ \begin{aligned}
x, \, если \, \alpha = 1 \\
\lnot x, \, если \, \alpha = 0
\end{aligned} \right.
\end{equation}$
Определение. Дизъюнктивная нормальная форма (ДНФ) — это дизъюнкция конъюнкций $(X \land Y) \lor (X \land Z)$.
Пример. $(X \Leftrightarrow \lnot Y) \lor \lnot (X \Rightarrow Y) \overset {ДНФ}{=}$ $(X \land \lnot Y) \lor$ $(\lnot X \land Y) \lor$ $(X \land \lnot Y)) =$ $(X \land \lnot Y) \lor$ $(\lnot X \land Y)$
Определение. Конъюнктивная нормальная форма (КНФ) — конъюнкция дизъюнктов или один дизъюнкт. Выражаясь на неформальном языке, КНФ — это конъюнкция дизъюнкций $(X \lor Y) \land (X \lor Z)$.
Определение. Совершенная дизъюнктивная нормальная форма (СДНФ) — это дизъюнктивная нормальная форма (ДНФ), в которой все конъюнкты совершенны, то есть содержат все переменные этой формулы.
Определение. Совершенная конъюнктивная нормальная форма (СКНФ) — это конъюнктивная нормальная форма (КНФ), в которой все дизъюнкты совершенны, то есть содержат все переменные этой формулы.
СДНФ и СКНФ вычисляются очень просто на основании истинностных таблиц.
Теорема СДНФ. Любая выполнимая формула $\Phi$, у которой $n$ переменных, логически равносильна формуле вида $$\bigvee (x_1^{\alpha_1} \land \dots \land x_n^{\alpha_n})$$
Теорема СКНФ. Любая выполнимая формула $\Phi$, у которой $n$ переменных, логически равносильна формуле вида $$\bigwedge (x_1^{\alpha_1} \lor \dots \lor x_n^{\alpha_n})$$