Высказывания и операции над ними

Обновлено: 22.12.2024

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

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

Таблица истинности для формулы %%X%%

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

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

Пример

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

Подформулы

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

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

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

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

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

$$ \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 X &= \Bigg((A \leftrightarrow B) \lor \Big((A \land B) \land C\Big) \rightarrow \Big((B \lor C) \land A\Big)\Bigg) \overset\\ &\overset (A \leftrightarrow B) \lor \Big((A \land B) \land C\Big) \rightarrow \Big((B \lor C) \land A\Big) \overset\\ &\overset (A \leftrightarrow B) \lor (A \land B \land C) \rightarrow \Big((B \lor C) \land A\Big) \overset\\ &\overset (A \leftrightarrow B) \lor A \land B \land C \rightarrow \Big((B \lor C) \land A\Big) \overset\\ &\overset (A \leftrightarrow B) \lor A \land B \land C \rightarrow (B \lor C) \land A. \end $$

Виды формул

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

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

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

Рассмотрим утверждение «верно, что завтра пойдет дождь или завтра не пойдет дождь». Очевидно, что это утверждение является истинным, даже не зная погоды на завтрашний день. В данном случае мы имеем дело с утверждениями вида %%A \lor \overline%%. Так как формула %%A \lor \overline%% является тождественно истинной, то независимо от переменной %%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%% — выполнимая формула.

Читайте также: