КНФ: конъюнктивная нормальная форма

Содержание и основные понятия

← Вернуться к оглавлению
Alterna · глава 28 · страница 28.2
КНФ: конъюнктивная нормальная форма
Макстермы, конструктор КНФ по таблице истинности.
КНФ
— это конъюнкция (∧) дизъюнкций (∨) литералов. Каждая дизъюнкция называется
макстермом
. КНФ читается так: «F=1, только если
все
макстермы истинны».
ФГОС
ФОП
ЕГЭ №2
углубл.
Связь с предыдущим.
В
28.1 «ДНФ»
мы разобрали дизъюнктивную форму через минтермы. КНФ — её «двойник»: строится по строкам F=0 через макстермы.
01
Что такое КНФ
КНФ
(конъюнктивная нормальная форма) — формула вида:
F = (D₁) ∧ (D₂) ∧ … ∧ (Dₙ)
где каждое
Dᵢ
— дизъюнкция (∨) литералов.
Примеры КНФ:
F = (A∨¬B) ∧ (¬A∨C)
— КНФ из двух дизъюнкций
F = A ∧ B ∧ C
— КНФ из одиночных переменных (частный случай)
F = (A∨B∨C)
— КНФ из одной дизъюнкции
F = (A∧B) ∨ C
— НЕ КНФ: сверху дизъюнкция с конъюнкцией внутри
Симметрия ДНФ и КНФ:
ДНФ
∨(∧ литералов)
строки F=1 → минтермы
КНФ
∧(∨ литералов)
строки F=0 → макстермы
02
Макстермы
Макстерм
— дизъюнкция, в которую входят
все
переменные функции (каждая ровно один раз).
Для F(A,B,C) макстерм строки
A=1, B=0, C=1
:
¬A ∨ B ∨ ¬C
Правило: переменная
с ¬
если её значение = 1,
без ¬
если = 0. (Противоположно минтерму!)
A
B
C
Макстерм
Обозначение
0
0
0
A∨B∨C
M₀
0
0
1
A∨B∨¬C
M₁
0
1
0
A∨¬B∨C
M₂
0
1
1
A∨¬B∨¬C
M₃
1
0
0
¬A∨B∨C
M₄
1
0
1
¬A∨B∨¬C
M₅
1
1
0
¬A∨¬B∨C
M₆
1
1
1
¬A∨¬B∨¬C
M₇
Заметь: макстерм для набора ABC — это
отрицание минтерма
для того же набора (де Морган).
03
Конструктор КНФ
🔨
Построй КНФ по таблице истинности
Выбери переменных и отметь строки где F=
0
(нули дают макстермы для КНФ). Нажми «Построить КНФ».
Переменных:
Отметь строки (F=0) и нажми «Построить КНФ».
04
Сравнение: ДНФ против КНФ
⚖️
Одна функция — две формы
Задай произвольную функцию от 3 переменных — увидь её ДНФ и КНФ одновременно.
Значения F (8 бит, слева = строка 000):
ДНФ появится здесь
КНФ появится здесь
🎯
Мини-тест: 5 вопросов по КНФ
XP: 0
🧩
Тест по теме КНФ
5 вопросов, 20 XP за каждый правильный ответ.