Облако знаний. Канонические формы логических выражений. Информатика. 10 класс

Логическая формула от k переменных называется совершенной дизъюнктивной нормальной формой (СДНФ), если она является дизъюнкцией неповторяющихся конъюнкций k переменных х₁, х₂, …, х_k, причём на i-м месте каждой конъюнкции стоит либо переменная х_i, либо её отрицание.
Логическая формула от k переменных называется совершенной конъюнктивной нормальной формой (СКНФ), если она является конъюнкцией неповторяющихся дизъюнкций k переменных х₁, х₂, …, х_k, причём на i-м месте каждой дизъюнкции стоит либо переменная х_i, либо её отрицание.
Примеры.

СДНФ: $(𝑥_{1} \land 𝑥_{2} \land \bar{𝑥_{3}}) \lor (\bar{𝑥_{1}} \land \bar{𝑥_{2}} \land 𝑥_{3})$

СКНФ: $(𝑥_{1} \lor \bar{𝑥_{2}} \lor \bar{𝑥_{3}}) \land (𝑥_{1} \lor \bar{𝑥_{2}} \lor 𝑥_{3}) \land (\bar{𝑥_{1}} \lor \bar{𝑥_{2}} \lor 𝑥_{3})$

Алгоритм построения СДНФ по таблице истинности.
1. Выбрать строки таблицы, в которых значение функции равно 1.
2. Для каждой такой строки записать конъюнкцию всех переменных следующим образом: если значение некоторой переменной в этом наборе равно 1, то в конъюнкцию включаем саму переменную, в противном случае — её отрицание.
3. Все полученные конъюнкции связать операциями дизъюнкции.
Алгоритм построения СКНФ по таблице истинности аналогичен алгоритму построения СДНФ.