Контрольная работа. Раздел Множества
Скачать 267.44 Kb.
|
1 2 4. Раздел «Булевы функции» Для данной формулы булевой функции: а) найти ДНФ, КНФ, СДНФ, СКНФ методом равносильных преобразований; б) найти СДНФ, СКНФ табличным способом (сравнить с СДНФ, СКНФ, полученными в пункте “а”); в) указать минимальную ДНФ и соответствующую ей переключательную схему. Для удобства знак конъюнкции (логического умножения) будем опускать, знак отрицания будем обозначать чертой над переменной, а знак импликации – стрелкой. Заданная функция: а) Заменяем импликацию по правилу : Используем закон де Моргана: ; в итоге получаем ДНФ -дизъюнктивную нормальную форму: Из неё можно получить СДНФ – совершенную дизъюнктивную нормальную форму. Будем использовать закон единицы, закон исключённого третьего, закон дистрибутивности: Теперь, учитывая каждую конъюнкцию только 1 раз, получаем СДНФ: Чтобы получить КНФ, воспользуемся полученной ДНФ: . Используем закон , тогда (здесь используем также закон снятия двойного отрицания): . Тогда упрощённая ДНФ: Используя закон дистрибутивности, закон противоречия и закон нуля, получаем: Получаем: Получили конъюнктивную нормальную форму – КНФ: Эта же форма является СКНФ, т.к. в каждой дизъюнкции участвуют все переменные. б) Найдём теперь СДНФ, СКНФ табличным способом. Составляем последовательно таблицу истинности для заданной функции . Учитываем, что отрицание меняет истинность, дизъюнкция ( ) ложна только в том случае, когда оба операнда ложны, конъюнкция истинна только в том случае, когда оба операнда истинны, импликация ( ) ложна только в том случае, когда из истины следует ложь.
Используя наборы, на которых функция принимает значение 1, составляем совершенную дизъюнктивную нормальную форму - СДНФ: в каждую конъюнкцию переменная входит с отрицанием, если в соответствующем наборе она имеет значение 0 (знак конъюнкции – логического умножения опускаем для удобства): Получили такую же форму СДНФ, как и раньше, только с перестановкой членов (но форма одна и та же). Используя наборы, на которых функция принимает значение 0, составляем совершенную конъюнктивную нормальную форму - СКНФ: в каждую дизъюнкцию переменная входит с отрицанием, если в соответствующем наборе она имеет значение 1: Получили такую же форму СКНФ, как и раньше, только с перестановкой членов (форма одна и та же). в) Ранее была получена ДНФ: . Она является минимальной, уменьшить в ней число переменных уже нельзя. Построим по этой форме переключательную схему. В этой форме – три конъюнкции, значит схема будет состоять из трёх параллельных ветвей. Каждая конъюнкция реализуется последовательным соединением элементов в ней. Получаем: 1 2 |