← Вернуться к оглавлению
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 шага:
  1. Кликни по ячейке — она переключается между 0 и 1. Единицы — это строки, где F=1 (минтермы).
  2. Нажми «Минимизировать» — алгоритм найдёт максимальные прямоугольные группы единиц. Каждая группа подсвечивается своим цветом.
  3. Читай результат — каждая группа даёт один терм формулы. Чем больше группа, тем короче терм.
Ячейка = 0
Не выбрана. Функция равна 0 на этом наборе переменных.
Ячейка = 1
Выбрана (зелёная). Функция равна 1 — это минтерм СДНФ.
Рамка группы
Объединение единиц. Каждая группа → один конъюнкт в результате.
Размер группы Убирает переменных Переменных в терме Пример терма
104A∧B∧C∧D
213A∧B∧C
422A∧B
831A
16401 (всегда истина)
Правила группировки (обязательно знать для ЕГЭ):
  • Группа — только прямоугольник (с учётом «склейки» краёв)
  • Размер — только степень двойки: 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 за каждый правильный ответ.