Что такое ДНФ и СДНФ

Элементарная конъюнкция — это формула вида $a_1 ∧ a_2 ∧ ... ∧ a_n$, где каждая $a_i$ — это переменная или отрицание переменной. Каждая переменная входит в неё не более одного раза.

ДНФ — это формула 0 (вырожденный случай) или формула вида $K_1 ∨ K_2 ∨ ... ∨ K_n$ — дизъюнкция попарно различных конъюнкций.

СДНФ — это ДНФ, у которой каждая элементарная конъюнкция содержит все переменные. Формула 0 тоже СДНФ.

Построение ДНФ

1. Используем законы Де-Моргана и двойное отрицание: двойное отрицание переменной есть сама переменная;
2. Все скобки раскрываем через дистрибутивный закон: 𝑥 (𝑦 ∨ 𝑧) = 𝑥𝑦 ∨ 𝑥𝑧
3. Избавляемся по-максимуму от лишнего: законы идемпотентности, контстант, поглощения и т.д. (𝑥 ⋅ 𝑥 = 𝑥 ∨ 𝑥 = x, 𝑥 ⋅ 𝑥^0 = 0, 𝑥 ⋅ 0 = 0, …)

Построение СДНФ

1. Построить ДНФ;
2. В каждом слагаемом каких переменных нет, те мы дописываем как единицу в таком виде: $(x_i \text{ ∨ } \overline{x_i})$

Пример:

Получили ДНФ x1x2 v x3 = [в СДНФ] = x1x2^(x3 v ¬x3) v x3^(x2 v ¬x2)^(x1 v ¬x1) = [раскрываем скобки, убираем повторы]