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

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

Бывают два вида высказываний: простые и составные. Составные высказывания получаются из простых с помощью логических символов %%\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%%.

%%A%%	%%B%%	%%A \land B%%	%%A \lor B%%	%%(A \lor B) \rightarrow (A \land B)%%
%%0%%	%%0%%	%%0%%	%%0%%	%%1%%
%%0%%	%%1%%	%%0%%	%%1%%	%%0%%
%%1%%	%%0%%	%%0%%	%%1%%	%%0%%
%%1%%	%%1%%	%%1%%	%%1%%	%%1%%

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