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

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

A×B Ú A×B ≡ A

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 - элементарная конъюнкция, называется дизъюнктивной нормальной формой (ДНФ).

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

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

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

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

Дата добавления: 2014-01-06