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

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

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

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

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

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

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

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

4. Де Моргана.

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

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

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

A Ú A ≡ A A×A ≡ A

6. Поглощения.

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

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

A̅ Ú A ≡ 1 A̅×A ≡ 0

A Ú 1 ≡ 1 A×1 ≡ A

A Ú 0 ≡ A A×0 ≡ 0

0̅ ≡ 1 не1 ≡ 0

A̅̅ ≡ A

8. Следование

A ® B ≡ A̅ Ú B

9. Эквивалентность(равнозначность)

A «B ≡ A×B Ú A̅×B̅

10. Неравнозначность

A Å B ≡ A×B̅ Ú A̅×B

11. Штрих Шеффера (И-НЕ)

A | B ≡ ̅(A×B) ≡ A̅ Ú B̅

12. Стрелка пирса (ИЛИ-НЕ)

A ¯ B ≡ ̅(A Ú B) ≡ A̅×B̅

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

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

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

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

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

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

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

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

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

17. Переход от одной формы представления к другой.

18. Минимизация методом Квайна.

19. Минимизация методом Вейча.