Часть I . Алгебра высказываний

ЧАСТЬ I. АЛГЕБРА ВЫСКАЗЫВАНИЙ

Понятие высказывания. Логические операции над высказываниями.

Понятие «высказывания» является основным (неопределяемым) понятием математической логики.

Под высказыванием понимают всякое повествовательное предложение, относительно которого мы можем сказать, истинно оно или ложно в данных условиях места и времени. Логическими значениями высказываний являются «истина» и «ложь».

Приведем примеры высказываний:

1) «Число  - четное»

2) «Число  делится на »

3) « < »

4) «Пифагор – математик»

5) «Самара – город на Днепре»

6) «Собака – животное»

Высказывания  - истинны, а высказывания -  ложны.

Будет обозначать конкретные высказывания начальными заглавными буквами латинского алфавита а их значения, то есть истину и ложь, соответственно И и Л или 1 и 0.

В алгебре высказываний все высказывания рассматриваются только с точки зрения их логического значения, а от их содержания отвлекаются. Считается, что любое высказывание либо истинно, либо ложно и ни одно высказывание не является одновременно истинным и ложным.

Высказывания, представляющие собой одно утверждение, принято называть простыми или элементарными. Примерами элементарных высказываний являются высказывания .

Высказывания, которые получаются из элементарных с помощью логических связок

принято называть сложными или составными.

Например:

«Число 2 – четное и число 10 делится на 5»,

«Если Пифагор – математик, то Самара – город на Днепре».

 

 

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

Определение. Переменные, вместо которых можно подставить высказывания, называются пропозиционными переменными или переменными высказываниями.

Пропозиционные переменные будем обозначать заглавными буквами конца латинского алфавита

Равносильные формулы алгебры высказываний.

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

Тот факт, что формулы и равносильны, будем обозначать        

Упражнения.

2.1. Доказать равносильность .

Используя равносильности  и  получаем:

Используя равносильность  получаем

.

Используя равносильности  получаем:

Этот результат получили, используя равносильность

2.2. Упростить формулу

Опустив знак  и используя равносильность , получаем

Используем равносильности  

По закону де Моргана и равносильности  получаем

.

Закон двойственности

Будем рассматривать формулы, содержащие только операции  . Если формула содержит операции  и  то эти операции, как показано выше, можно выразить через  и .

Определение. Операция  называется двойственной операции , а операция  двойственной операции .

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

Например, формула  двойственна формуле  а формула  двойственна формуле  

Теорема (Закон двойственности). Если формулы  и  равносильны, то и двойственные им формулы  и  также равносильны.

В приведенном выше примере  (первый дистрибутивный закон), по закону двойственности (второй дистрибутивный закон).

Основные равносильности 2-10 представляют собой пары равносильных формул и равносильных двойственных им формул.

Пример.

Выяснить, какой является формула .

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

 

Данная формула тождественно истинная.

Однако практическое использование таблицы истинности для формулы  при больших  затруднительно.

Существует другой способ, основанный на приведении формул к так называемой «нормальной форме».

Определение. Элементарной конъюнкцией называется конъюнкция переменных высказываний или их отрицаний.

Элементарными конъюнкциями являются формулы:

.

Определение. Элементарной дизъюнкцией называется дизъюнкция переменных высказываний или их отрицаний.

Элементарными дизъюнкциями являются формулы:

Теорема. (Критерий тождественной истинности элементарной дизъюнкции) Для того, чтобы элементарная дизъюнкция была тождественно истинна, необходимо и достаточно, чтобы в ней содержалась хотя бы одна пара слагаемых, из которых одно есть отрицание другого.

Например, элементарные дизъюнкции

 являются тождественно истинными, а элементарная дизъюнкция  тождественно истинной не является.

Теорема. (Критерий тождественной ложности элементарной конъюнкции) Для того, чтобы элементарная конъюнкция была тождественно ложна необходимо и достаточно, чтобы в ней содержалась хотя бы одна пара множителей, из которых один является отрицанием другого.

Например, элементарные конъюнкции  являются тождественно ложными, а элементарная конъюнкция  тождественно ложной не является.

Определение. Конъюнктивной нормальной формой (КНФ) формулы называется равносильная ей формула, представляющая собой конъюнкцию элементарных дизъюнкций.

Примерами КНФ являются формулы

Определение. Дизъюнктивной нормальной формой (ДНФ) формулы называется равносильная ей формула, представляющая собой дизъюнкцию элементарных конъюнкций.

Примерами ДНФ являются формулы

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

ЧАСТЬ I. АЛГЕБРА ВЫСКАЗЫВАНИЙ