Формы представления высказываний

Дата добавления: 2013-12-23; просмотров: 742; Нарушение авторских прав

Операция склеивания.

Исключенного третьего. Противоречия.

Поглощения.

Идемпотентности.

Де Моргана.

Дистрибутивный.

Ассоциативный.

Коммутативный.

Алгебра высказываний

Сложные высказывания называются равносильными (f≡ g), если на одинаковых наборах значений элементарных высказываний они принимают одинаковые значения.

Законы :

A Ú B ≡ B Ú A A×B ≡ B×A

A Ú (B Ú C) ≡ A Ú B Ú C A×(B×C) ≡ A×B×C

A Ú B×C ≡ (A Ú B)×(A Ú C)

A×(B Ú C) ≡ A×B Ú A×C

A Ú B ≡ A×B A×B ≡ A Ú B

A Ú A ≡ A A×A ≡ A

A Ú (A×B) ≡ A A×(A Ú B) ≡ A

A Ú A ≡ 1 A×A ≡ 0

8. A Ú 1 ≡ 1 A×1 ≡ A

9. A Ú 0 ≡ A A×0 ≡ 0

10. 0 ≡ 1 1 ≡ 0

11. A ≡ A

12. A ® B ≡A Ú B

13. A « B ≡ A×B Ú A×B

14. A Å B ≡A×B Ú A×B

15. A | B ≡ A×B ≡ A Ú B

16. A ¯ B ≡A Ú B ≡A×B

A×B Ú A×B ≡ A

1. Форма А₁Ú А₂Ú ... Ú А_n, где А_i_, - элементарное высказывание или отрицание элементарного высказывания (литерал), называется элементарной дизъюнкцией.

2. Форма B₁× B₂× ... × B_n, где B_i - литерал, называется элементарной конъюнкцией.

3. Форма D₁× D₂× ... × D_n, где D_j - элементарная дизъюнкция, называется конъюнктивной нормальной формой (КНФ).

4. Форма K₁Ú K₂Ú ... Ú K_n, где K_j - элементарная конъюнкция, называется дизъюнктивной нормальной формой (ДНФ).

Всегда истинное (на любых наборах значений входящих в него элементарных высказываний) сложное высказывание называется тавтологией.

Всегда ложное (на любых наборах значений входящих в него элементарных высказываний) высказывание называется противоречием.

Совершенной КНФ (СКНФ) называется такая КНФ, что каждая входящая в нее элементарная дизъюнкция содержит все элементарные высказывания прямо или с инверсией строго по одному разу. Нет повторяющихся дизъюнкций. Любое сложное высказывание, кроме тавтологии, имеет единственную СКНФ.

Совершенной ДНФ (СДНФ) называется такая ДНФ, что каждая входящая в нее элементарная конъюнкция содержит все элементарные высказывания прямо или с инверсией строго по одному разу. Нет повторяющихся конъюнкций. Любое сложное высказывание, кроме противоречия, имеет единственную СДНФ.

<== предыдущая лекция	\|	следующая лекция ==>
Построение и анализ сложных высказываний	\|	Преобразование СДНФ в СКНФ и наоборот.