Макстермы, конструктор КНФ по таблице истинности.
КНФ — это конъюнкция (∧) дизъюнкций (∨) литералов. Каждая дизъюнкция называется макстермом. КНФ читается так: «F=1, только если все макстермы истинны».
КНФ (конъюнктивная нормальная форма) — формула вида:
где каждое Dᵢ — дизъюнкция (∨) литералов.
Примеры КНФ:
| ДНФ | ∨(∧ литералов) | строки F=1 → минтермы |
| КНФ | ∧(∨ литералов) | строки F=0 → макстермы |
Макстерм — дизъюнкция, в которую входят все переменные функции (каждая ровно один раз).
Для F(A,B,C) макстерм строки A=1, B=0, C=1:
Правило: переменная с ¬ если её значение = 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₇ |
Заметь: макстерм для набора ABC — это отрицание минтерма для того же набора (де Морган).
Выбери переменных и отметь строки где F=0 (нули дают макстермы для КНФ). Нажми «Построить КНФ».
Задай произвольную функцию от 3 переменных — увидь её ДНФ и КНФ одновременно.
5 вопросов, 20 XP за каждый правильный ответ.