Совершенные нормальные формы алгебры логики

3.3.1 Дизъюнктивная нормальная форма и совершенная дизъюнктивная нормальная форма (ДНФ и СДНФ)

Определение 1. Элементарной конъюнкцией n переменных называется конъюнкция переменных или их отрицаний.

Определение 2. Дизъюнктивной нормальной формой (ДНФ) формулы А называется равносильная ей формула, представляющая собой дизъюнкцию элементарных конъюнкций.

Определение 3. Совершенной дизъюнктивной нормальной формой (СДНФ) формулы А называется ДНФ А, обладающая свойствами (С).

 

 

СДНФ А можно получить двумя способами:

1) с помощью таблицы истинности (см. п.3.2);

2) с помощью равносильных преобразований.