← Вернуться к оглавлению
Alterna · глава 18 · страница 18.2

СДНФ и карты Карно: от таблицы к формуле

Алгоритм СДНФ. Кликни по строкам F=1 — программа построит формулу.

СДНФ (совершенная дизъюнктивная нормальная форма) — способ записать любую логическую функцию в виде дизъюнкции минтермов. ЕГЭ №2 часто даёт таблицу и просит построить СДНФ.

ФГОСФОПЕГЭ №2,15
📌 Связь с главой 17

Логические функции — это надёжность системы (дублирование, проверка чётности). Каждый вентиль — узел графа с булевым значением. Таблица истинности — частный случай ориентированного ациклического графа (ДАГ).

00

Модельные примеры

Минтерм

A ∧ B Конъюнкция 1

Если A=1, B=1 → минтерм истинен

СДНФ из трёх строк

¬A∧B A∧¬B A∧B ∨ СДНФ

Три минтерма соединены дизъюнкцией

Карта Карно 2×2

00 01 11 10 A↓B→ A→B↓

Группировка соседних клеток даёт импликанту

СКНФ — дизъюнкция в макстерме

A ∨ ¬B Макстерм ¬A ∨ B Макстерм ∧ СКНФ

Конъюнкция макстермов = СКНФ

01

Алгоритм построения СДНФ

  1. Найти все строки таблицы, где F = 1.
  2. Для каждой такой строки записать конъюнкцию всех переменных:
    • Если переменная в этой строке = 1, пишем её как есть.
    • Если = 0, пишем её с отрицанием (¬).
  3. Все полученные конъюнкции соединить через дизъюнкцию ∨.
Пример В таблице (A, B, F): (0,1,1), (1,0,1), (1,1,1) — три строки с F=1.
Минтермы: (¬A∧B), (A∧¬B), (A∧B).
СДНФ: (¬A∧B)∨(A∧¬B)∨(A∧B).
02

СКНФ (для полноты)

  1. Найти все строки, где F = 0.
  2. Для каждой записать дизъюнкцию переменных (если 0 — без отрицания, если 1 — с отрицанием).
  3. Соединить через конъюнкцию ∧.

Для того же примера (A, B, F): F=0 только в строке (0,0,0). СКНФ: (A∨B).

03

Интерактивный СДНФ-строитель

Кликни по строкам, где F=1

🔨СДНФ-строитель: задай строки
Выбери строки с F=1 и нажми «Построить СДНФ».
04

Карта Карно

Визуальное упрощение: кликни клетки F=1 → карта покажет группы и упрощённую форму

🗺Карта Карно (ЕГЭ №15)
Кликни клетки где F=1, затем нажми «Упростить».
05

Мини-тест

📝 СДНФ и карты Карно
Вопрос 1 из 5
0 XP
Ур: Новичок · 50 XP