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

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

← Вернуться к оглавлению
Alterna · глава 28 · страница 28.1
ДНФ: дизъюнктивная нормальная форма
Минтермы, конструктор, визуализация по таблице истинности.
ДНФ
— это дизъюнкция (∨) конъюнкций (∧) литералов. Каждая конъюнкция называется
минтермом
. ДНФ читается так: «F=1, если выполнен хотя бы один минтерм».
ФГОС
ФОП
ЕГЭ №2
углубл.
Связь с предыдущим.
В
главе 28 «Главная»
мы познакомились с понятиями нормальных форм. Здесь подробно разбираем
ДНФ
— первую из них — через минтермы и конструктор.
01
Что такое ДНФ
ДНФ
(дизъюнктивная нормальная форма) — формула вида:
F = (K₁) ∨ (K₂) ∨ … ∨ (Kₙ)
где каждое
Kᵢ
— конъюнкция (∧) литералов.
Литерал
— переменная или её отрицание.
Примеры ДНФ:
F = A ∨ ¬B ∨ C
— ДНФ из одиночных литералов (частный случай)
F = (A∧¬B) ∨ (¬A∧C)
— ДНФ из двух конъюнкций
F = A∧B∧C
— ДНФ из одной конъюнкции
F = (A∨B) ∧ C
— НЕ ДНФ: сверху конъюнкция с дизъюнкцией внутри
Алгоритм приведения к ДНФ:
1. Раскрыть двойные отрицания (¬¬A = A)
2. Применить де Моргана (¬(A∧B) = ¬A∨¬B, ¬(A∨B) = ¬A∧¬B)
3. Раскрыть скобки через дистрибутивность (A∧(B∨C) = (A∧B)∨(A∧C))
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₇
Для n переменных существует ровно 2ⁿ различных минтермов.
03
Конструктор ДНФ
🔨
Построй ДНФ по таблице истинности
Выбери количество переменных и отметь строки, где F=1. Нажми «Построить ДНФ».
Переменных:
Выбери строки (F=1) и нажми «Построить ДНФ».
04
Визуализатор: какой минтерм истинен?
💡
Введи значения переменных — увидь какие минтермы = 1
Введи значения A, B, C (0 или 1) и нажми «Проверить». Таблица подсветит единственный истинный минтерм.
A:
B:
C:
05
Проверь формулу на ДНФ
🔍
Является ли введённая формула ДНФ?
Введи логическое выражение. Используй: ∧ или &, ∨ или |, ¬ или !. Пример:
A∧¬B∨C
Введите формулу и нажмите «Проверить».
🎯
Мини-тест: 5 вопросов по ДНФ
XP: 0
🧩
Тест по теме ДНФ
5 вопросов, 20 XP за каждый правильный ответ.