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

1. Форма А1 Ú А2 Ú… Ú Аn, где Аi, — элементарное высказывание или отрицание элементарного высказывания (литерал), называется элементарной дизъюнкцией.

2. Форма B1 × B2 ×… × Bn, где Bi — литерал, называется элементарной конъюнкцией.

3. Форма D1 × D2 ×… × Dn, где Dj — элементарная дизъюнкция, называется конъюнктивной нормальной формой (КНФ).

4. Форма K1 Ú K2 Ú… Ú Kn, где Kj — элементарная конъюнкция, называется дизъюнктивной нормальной формой (ДНФ).

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

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

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

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