Переменные вместо которых можно подставлять высказывания называют переменными
Обновлено: 04.11.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%%
В курсе математической логики дается следующее определение формулы алгебры высказываний:
- Переменные являются формулами.
- Если %%A%% и %%B%% — формулы, то выражения $$ \overline, A \land B, A \lor B, A \rightarrow B, A \leftrightarrow B $$ являются формулами.
- Всякая формула есть либо переменная или образуется из переменных последовательным применением правила %%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%% — выполнимая формула.
Читайте также: