Классификация формул алгебры высказываний

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

Высказывание -это повествовательное предложение, о котором можно судить истинно оно или ложно.

Безличные предложения и вопросительные не являются высказываниями.

Пример: Снег чёрный – высказывание.

Два умножить на два, равно пять – высказывание.

3<9 высказывание.

Добро пожаловать! – не высказывание.

Высказывания обозначаются заглавными буквами латинского алфавита A,B,C,R,….,S.

A: “3>2”

Если высказывание истинно, то значение истинности |A|=1.

Если высказывание ложно, то |B|=0.

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

Отрицанием высказывания P называется такое высказывание, обозначаемое ⌐P (не P), которое ложно, если P- истинно, и ложно в противном случае.

Конъюнкцией высказываний P и Q называется такое высказывание, обозначаемое P^Q, которое истинно, тогда и только тогда, когда P и Q истинно одновременно.

Дизъюнкцией высказываний P и Q называется такое высказывание, обозначаемое ­PÚQ, которое ложно, тогда и только тогда, когда P и Q ложно одновременно.

Импликацией высказываний P и Q называется такое высказывание, обозначаемое P–›Q, которое ложно, тогда и только тогда, когда P истинно, а Q ложно.

Эквиваленцией высказываний P и Q называется такое высказывание, обозначаемое P‹–›Q, которое истинно, тогда и только тогда, когда P и Q принимают одинаковые значения истинности.

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

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

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

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

2. Если P и Q – это формулы алгебры высказываний, то выражения ⌐P, ­­­­­(P^Q), ­­­­­ (PÚQ), ­­­­­ (P–›Q),         (P‹–›Q) являются формулами алгебры высказываний.

3. Никаких других формул кроме перечисленных в пунктах 1 и 2 нет.

Пример:

(xÙy)Ú формула алгебры высказываний.

(xy)   не формула алгебры высказываний.

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

           Например, для формулы  таблица истинности имеет вид:

 

Классификация формул алгебры высказываний.

          Тавтологии (тождественно истинные формулы, законы алгебры высказываний)

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

   Противоречия (тождественно ложные формулы)

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

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

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

Следующие формулы являются тавтологиями

 

закон коммутативности конъюнкции,

закон ассоциативности конъюнкции,

 

закон коммутативности дизъюнкции,

закон ассоциативности дизъюнкции,

закон дистрибутивности конъюнкции относительно дизъюнкции,

закон дистрибутивности дизъюнкции относительно конъюнкции,

законы де Моргана,

 

 

закон контрапозиции,

закон двойного отрицания.

 

 

Свойства тавтологий

1. Формула А является тавтологией тогда и только тогда, когда её отрицание является противоречием.

2. Если формула А является тавтологией, А–›В тавтология, то В тавтология.

3. Если формула А(x₁,……x_n) – тождественно истинная и формулы В₁(y₁,….y_k), B₂(y₁,….y_k),…,B_n(y₁,….y_k) – тождественно истинные, то формула А*(y₁,….y_k) полученная из А, подстановкой в неё формул В₁, В₂ ,…, B_n является тождественно истинной.

Логическое следствие

Формула алгебры высказываний В называется логическим следствием совокупности формул А₁, А₂,…, A_n, если она принимает значение истина на любом наборе на котором все формулы данной совокупности одновременно истинны.

Пример: P–›Q - логическое следствие P‹–›Q, обратное логическое следование не выполняется.

Тавтология является следствием любой совокупности формул. Следствием тождественно ложной формулы является любая формула.