СДНФ, СКНФ и карты Карно

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

← Вернуться к оглавлению
Alterna · глава 28 · страница 28.3
СДНФ, СКНФ и карты Карно
Совершенные нормальные формы, минимизация, карты Карно.
СДНФ
— особая ДНФ, где каждый минтерм содержит все переменные.
СКНФ
— особая КНФ с теми же свойствами для макстермов.
Карта Карно
— визуальный инструмент для минимизации любой из них.
ФГОС
ФОП
ЕГЭ №2,15
углубл.
Связь с предыдущим.
В
28.1 «ДНФ»
и
28.2 «КНФ»
мы строили произвольные нормальные формы. Здесь — совершенные: СДНФ (все минтермы) и СКНФ (все макстермы), плюс метод минимизации картами Карно.
01
СДНФ и СКНФ: определение
СДНФ
(совершенная ДНФ)
Строится по строкам
F=1
Каждый минтерм содержит
все
переменные
Минтермы
не повторяются
«Совершенная» = «полная» = «каноническая»
СКНФ
(совершенная КНФ)
Строится по строкам
F=0
Каждый макстерм содержит
все
переменные
Макстермы
не повторяются
«Совершенная» = «полная» = «каноническая»
Связь СДНФ и СКНФ:
число минтермов + число макстермов = 2ⁿ (общее число строк). Зная одну форму, легко восстановить другую: СКНФ строится по «оставшимся» строкам.
02
Автоматический построитель СДНФ/СКНФ
⚙️
Введи значения F → получи СДНФ и СКНФ
Введи строку из 0 и 1 (значения F в порядке возрастания наборов). Для 3 переменных — 8 символов, для 4 — 16.
СДНФ появится здесь
СКНФ появится здесь
03
Карта Карно (4 переменные)
Зачем нужна карта Карно?
СДНФ может быть очень длинной — десятки минтермов. Карта Карно позволяет
минимизировать
её: визуально объединить единицы в прямоугольные группы и убрать лишние переменные. Результат — компактная формула без лишних слагаемых.
Как пользоваться картой — 3 шага:
Кликни по ячейке
— она переключается между 0 и 1. Единицы — это строки, где F=1 (минтермы).
Нажми «Минимизировать»
— алгоритм найдёт максимальные прямоугольные группы единиц. Каждая группа подсвечивается своим цветом.
Читай результат
— каждая группа даёт один терм формулы. Чем больше группа, тем короче терм.
Ячейка = 0
Не выбрана. Функция равна 0 на этом наборе переменных.
Ячейка = 1
Выбрана (зелёная). Функция равна 1 — это минтерм СДНФ.
Рамка группы
Объединение единиц. Каждая группа → один конъюнкт в результате.
Размер группы
Убирает переменных
Переменных в терме
Пример терма
1
0
4
A∧B∧C∧D
2
1
3
A∧B∧C
4
2
2
A∧B
8
3
1
A
16
4
0
1 (всегда истина)
Правила группировки (обязательно знать для ЕГЭ):
Группа — только
прямоугольник
(с учётом «склейки» краёв)
Размер — только
степень двойки
: 1, 2, 4, 8, 16
Группы могут
перекрываться
(одна ячейка в нескольких группах — нормально)
Крайние столбцы/строки считаются
соседними
(карта «замкнута»)
Надо стремиться к
минимальному числу максимальных
групп
🗺
Интерактивная карта Карно 4×4
👆
Кликай по ячейкам
чтобы выставить 1 (минтерм). Потом нажми «Минимизировать».
Единиц:
0
из 16
|
СДНФ минтермов:
0
Строки:
AB
(00→01→11→10 — серый код) · Столбцы:
CD
(00→01→11→10)
Примеры:
Введи 1 в ячейки, нажми «Минимизировать».
Почему строки идут 00→01→11→10, а не 00→01→10→11?
Это
серый код (код Грея)
. Главное свойство: соседние строки/столбцы отличаются
ровно в 1 бит
. Это значит, что визуально соседние ячейки дают «сливаемые» минтермы — переменная, которая меняется, исключается из терма.
🎯
Мини-тест: 5 вопросов по СДНФ/СКНФ
XP: 0
🧩
Тест по теме СДНФ/СКНФ
5 вопросов, 20 XP за каждый правильный ответ.