сднф как составить — есть таблица истинности, надо построить выражение, ничего не понимаю
Дана таблица истинности, и нужно по ней восстановить логическое выражение в СДНФ. Учитель показал на доске, но я списать не успел и теперь сижу как баран.
Вот моя таблица для функции F(A,B):
| A | B | F |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Как из этого собрать формулу? Что вообще такое эти «совершенные» дизъюнкции и где там отрицания ставить?
2 ответа
СДНФ строится по строкам, где F = 1. Алгоритм такой:
- Берёшь каждую строку с F=1.
- Для неё пишешь конъюнкцию (И) всех переменных: если переменная в этой строке = 1, берёшь её как есть, если = 0 — берёшь с отрицанием (НЕ).
- Все такие конъюнкции соединяешь через ИЛИ.
У тебя F=1 в двух строках:
- строка A=0, B=0 → оба нуля, значит оба с отрицанием:
НЕ A И НЕ B - строка A=1, B=0 → A=1 (как есть), B=0 (с отрицанием):
A И НЕ B
Соединяем через ИЛИ:
F = (НЕ A И НЕ B) ИЛИ (A И НЕ B)
Это и есть СДНФ. Можно даже упростить (вынести НЕ B): F = НЕ B И (НЕ A ИЛИ A) = НЕ B. Логично — посмотри в таблицу, F=1 ровно там, где B=0.
Запомни кричалку: «единица — И-строчка; ноль у переменной → ставим НЕ; строки соединяем ИЛИ». По нулям строки не трогаем вообще (это уже для СКНФ, другая тема).
Главное не перепутать: СДНФ — собираем по единицам, внутри одного набора всё через И, между наборами через ИЛИ. Ноль у переменной = отрицание этой переменной.
Количество скобок в СДНФ = сколько единиц в столбце F. У тебя две единицы → две скобки, всё сходится.
