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

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, обратное логическое следование не выполняется.

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