ДНФ, КНФ, СДНФ, СКНФ

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

← Вернуться к оглавлению
Alterna · глава 28
ДНФ, КНФ, СДНФ, СКНФ
Нормальные формы, минтермы, макстермы, карты Карно, минимизация.
Любая логическая функция записывается в двух стандартных формах:
ДНФ
(дизъюнкция конъюнкций) и
КНФ
(конъюнкция дизъюнкций). Совершенные формы СДНФ и СКНФ строятся прямо по таблице истинности, а карта Карно позволяет их минимизировать.
ФГОС
ФОП
ЕГЭ №2,15
углубл.
Связь с предыдущей главой.
В
главе 27 «Измерение информации»
мы изучили алфавитный подход, энтропию Шеннона и формулу Хартли. Здесь мы переходим к логике: по таблице истинности строим
нормальные формы
— ДНФ, КНФ, СДНФ, СКНФ — и минимизируем функции картами Карно. Это фундамент
главы 29 «Алгебра логики»
и всего программирования.
01
СДНФ
СДНФ
(совершенная дизъюнктивная нормальная форма) — дизъюнкция минтермов (строк, где F=1).
Минтерм
— конъюнкция всех переменных (=1 → без отрицания, =0 → с отрицанием).
Пример: по таблице истинности → СДНФ
A
B
C
F
0
0
0
0
0
0
1
1
0
1
0
0
0
1
1
1
1
0
0
0
1
0
1
1
1
1
0
0
1
1
1
1
Строки где F=1:
001, 011, 101, 111
Минтермы:
¬A∧¬B∧C
,
¬A∧B∧C
,
A∧¬B∧C
,
A∧B∧C
СДНФ = (¬A∧¬B∧C) ∨ (¬A∧B∧C) ∨ (A∧¬B∧C) ∨ (A∧B∧C)
Каждая 1 в F даёт один минтерм: переменная без ¬ если=1, с ¬ если=0.
02
СКНФ
СКНФ
— конъюнкция макстермов (строк, где F=0).
Макстерм
— дизъюнкция всех переменных (=0 → без отрицания, =1 → с отрицанием).
Пример: по таблице истинности → СКНФ
A
B
C
F
0
0
0
0
0
0
1
1
0
1
0
0
0
1
1
1
1
0
0
0
1
0
1
1
1
1
0
0
1
1
1
1
Строки где F=0:
000, 010, 100, 110
Макстермы:
A∨B∨C
,
A∨¬B∨C
,
¬A∨B∨C
,
¬A∨¬B∨C
СКНФ = (A∨B∨C) ∧ (A∨¬B∨C) ∧ (¬A∨B∨C) ∧ (¬A∨¬B∨C)
Каждая 0 в F даёт один макстерм: переменная с ¬ если=1, без ¬ если=0.
03
Карта Карно: минимизация
🗺
Карта Карно (4 переменные, 4×4)
Кликни по ячейкам (F=1). Кнопка «Минимизировать» найдёт группы 2, 4, 8 клеток и выделит их цветом.
Введи 1 в ячейки, нажми «Минимизировать».
Как работает:
Карта использует серый код — соседние ячейки отличаются в 1 бит. Группы 2, 4, 8 клеток дают термы с 3, 2, 1 литералом. Жадный алгоритм ищет сначала группы по 8, потом по 4, потом по 2.
🎯
Мини-тест: 5 вопросов
XP: 0
🧩
Быстрый тест по теме
Проверь себя! 5 вопросов, 20 XP за каждый правильный ответ.