Запись утверждений на языке алгебры высказываний. Формулы алгебры высказываний

Простые и составные высказывания

Бывают два вида высказываний: простые и составные. Составные высказывания получаются из простых с помощью логических символов $\overline, \land, \lor, \rightarrow, \leftrightarrow$. Рассмотрим высказывание «Иванов окончил школу и поступил в институт». Оно образовано из простых высказываний «Иванов окончил школу» и «Иванов поступил в институт» с помощью операции конъюнкции. Обозначим эти высказывания через $A$ и $B$ соответственно, тогда сложное высказывание «Иванов окончил школу и поступил в институт» имеет вид $A \land B$. При этом высказывания $A$ — «Иванов окончил школу» и $B$ — «Иванов поступил в институт» нельзя представить ввиде составных высказываний. Поэтому они простые (элементарные).

Пример

Дано высказывание «Если число $a$ делится на число $c$ и число $b$ делится на число $c$, то их сумма $a+b$ делится на число $c$». Обозначить буквами простые высказывания и, используя логические символы, выразить данное высказывание через простые.

Обозначим:

• $A$: «число $a$ делится на число $c$»;
• $B$: «число $b$ делится на число $c$»;
• $C$: «сумма $a+b$ делится на число $c$».

Тогда высказывание, с учетом замены, примет вид: «Если $A$ и $B$, то $C$», которое на языке алгебры высказываний выглядит $$(A \land B) \rightarrow C.$$

Формулы алгебры высказываний

Для определения понятия формулы нам необходимо понять, какие переменные используются в алгебре высказываний.

Пропозициональная переменная, или переменная для высказываний, — переменная, котороя может принимать одно из двух истинностных значений: «истина» или «ложь». Далее будем их называть просто переменными.

С помощью логических знаков ($\overline{ }, \land, \lor, \rightarrow, \leftrightarrow$) и переменных можно составлять сложные высказывания, которые и будем называть формулами алгебры высказываний.

Например, формула $X = (A \land B) \rightarrow (A \lor B)$ получена так: сначала построены формулы $A \land B$ и $A \lor B$, затем из этих двух формул получена исходная с помощью применения знака $\rightarrow$.

Вместо переменных в формулу можно подставлять произвольные значения переменных. При вычислении значения формулы неважно как сформулированы входящие в нее высказывания, важно лишь их значения: «истина» или «ложь».

Порядок построения формулы позволяет составить таблицу истинности для формулы $X$. Для этого переберем всевозможные комбинации значений переменных $A$ и $B$ (каждая строка в таблице) и найдем значение интересующей нас формулы.

В курсе математической логики дается следующее определение формулы алгебры высказываний:

1. Переменные являются формулами.
2. Если $A$ и $B$ — формулы, то выражения $$\overline{A}, A \land B, A \lor B, A \rightarrow B, A \leftrightarrow B$$ являются формулами.
3. Всякая формула есть либо переменная или образуется из переменных последовательным применением правила $2$.

Пример

Показать, что выражение $X = (A \lor B) \rightarrow ((C \land D) \leftrightarrow \overline{A})$ является формулой.

Действительно, $A, B, C, D$ — переменные, следовательно, формулы по правилу $1$. Так как $A$ — формула, то $\overline{A}$ — формула по правилу $2$. Так как $A,B,C,D$ формулы, $A \lor B$ и $C \land D$ — формулы по правилу $2$. Так как $C \land D$ и $\overline{A}$ формулы, то $(C \land D) \leftrightarrow \overline{A}$ формула по правилу $2$. Так как $A \lor B$ и $(C \land D) \leftrightarrow \overline{A}$ формулы, то $X$ — формула по правилу $2$.

Подформулы

Выражения, полученные при «сборке» формулы называются ее частями или подформулами. Например, формула $X = (A \lor B) \rightarrow ((C \land D) \leftrightarrow \overline{A})$ имеет следующие подформулы: $$A,B,C,D, \overline{A}, A \lor B, C \land D, (C \land D) \leftrightarrow \overline{A}, (A \lor B) \rightarrow ((C \land D) \leftrightarrow \overline{A})$$

Правила записи формул

При записи формул придерживаются следующих правил.

1. Внешние скобки в формуле можно опускать. Например, вместо $(A \lor B)$ пишем $A \lor B$.

2. Как и в арифметике, в алгебре высказываний у каждой операции есть свой приоритет. Приоритеты логических знаков, расположенные в порядке убывания, следующие:

   $$\overline{ }, \land, \lor, \rightarrow, \leftrightarrow.$$

   Приоритеты логических операций можно изменить, используя скобки.

Каждый предшествующий знак является «сильнее» последующего. Поэтому вместо записи $(A \land B) \lor C$ можно писать $A \land B \lor C$, вместо записи $A \leftrightarrow (B \lor C)$ — $A \leftrightarrow B \lor C$.

3. Если в формуле $X = A \land B \land C \land \ldots \land Z$ опущены скобки, то подрузамевается левосторонняя расстановка скобок и считается, что $X = \bigg(\Big((A \land B) \land C\Big) \land \ldots\bigg)\land Z$. Аналогично для подобных формул, имеющих знак $\lor$, $\rightarrow$ или $\leftrightarrow$.

Примеры

Пользуясь правилами $1-3$ восстановить скобки в формуле

$$X = A \lor B \land C \leftrightarrow A \rightarrow B \rightarrow C$$

По правилам $1-3$ имеем $X = \Bigg(\Big(A \lor (B \land C)\Big) \leftrightarrow \Big((A \rightarrow B) \rightarrow C\Big)\Bigg)$.

Пользуясь правилами $1-3$ опустить лишние скобки в формуле $$X = \Bigg((A \leftrightarrow B) \lor \Big((A \land B) \land C\Big) \rightarrow \Big((B \lor C) \land A\Big)\Bigg)$$

Решение, над знаком равно будут указаны номера правил которые применяются.

$$\begin{array}{ll} X &= \Bigg((A \leftrightarrow B) \lor \Big((A \land B) \land C\Big) \rightarrow \Big((B \lor C) \land A\Big)\Bigg) \overset{1}{=}\\ &\overset{1}{=} (A \leftrightarrow B) \lor \Big((A \land B) \land C\Big) \rightarrow \Big((B \lor C) \land A\Big) \overset{3}{=}\\ &\overset{3}{=} (A \leftrightarrow B) \lor (A \land B \land C) \rightarrow \Big((B \lor C) \land A\Big) \overset{2}{=}\\ &\overset{2}{=} (A \leftrightarrow B) \lor A \land B \land C \rightarrow \Big((B \lor C) \land A\Big) \overset{2}{=}\\ &\overset{2}{=} (A \leftrightarrow B) \lor A \land B \land C \rightarrow (B \lor C) \land A. \end{array}$$

Виды формул

Формула $X$ называется тождественно истинной (или тавтологией), если она принимает значение «истина» при любых значениях входящих в нее переменных.

Например, формула $X = (A \land B) \rightarrow (A \lor B)$ является тождественно истинной, т.к. при любых значениях $A$ и $B$ она является истинной.

Существует две причины, по которым мы считаем высказывание истинным или ложным. Первое, на основе различных свойств объекта. Например, «Москва — столица Австрии» ложно, так как она ею не является. Точно также в случае «$2 \cdot 3 = 6$» значение «истина» установлено из свойств рассматриваемых объектов. Второе, когда приписывается значение «истина» или «ложь» вне зависимости от свойств обсуждаемых объектов. Это и есть логическая истинность.

Рассмотрим утверждение «верно, что завтра пойдет дождь или завтра не пойдет дождь». Очевидно, что это утверждение является истинным, даже не зная погоды на завтрашний день. В данном случае мы имеем дело с утверждениями вида $A \lor \overline{A}$. Так как формула $A \lor \overline{A}$ является тождественно истинной, то независимо от переменной $A$, утверждение истинно.

Формула $X$ называется тождественно ложной, если она принимает значение «ложь» при любых значениях входящих в нее переменных.

Формула, не являющаяся тождественно ложной и тождественно истинной, называется выполнимой.

Пример

Определить вид (тождественно истинная, тождественно ложная, выполнимая) формулы:

$$X = A \lor B \rightarrow A \land B$$

Составим таблицу истинности для формулы $X$.

Поскольку формула не является тождественно истинной или тождественно ложной, то $X$ — выполнимая формула.