Главная страница

Контрольная работа. Раздел Множества


Скачать 267.44 Kb.
НазваниеКонтрольная работа. Раздел Множества
Дата20.05.2022
Размер267.44 Kb.
Формат файлаdocx
Имя файлаKontr_rab.docx
ТипКонтрольная работа
#540574
страница2 из 2
1   2

4. Раздел «Булевы функции»

Для данной формулы булевой функции:

а) найти ДНФ, КНФ, СДНФ, СКНФ методом равносильных преобразований;

б) найти СДНФ, СКНФ табличным способом (сравнить с СДНФ, СКНФ, полученными в пункте “а”);

в) указать минимальную ДНФ и соответствующую ей переключательную схему.



Для удобства знак конъюнкции (логического умножения) будем опускать, знак отрицания будем обозначать чертой над переменной, а знак импликации – стрелкой. Заданная функция:



а) Заменяем импликацию по правилу :



Используем закон де Моргана: ; в итоге получаем ДНФ -дизъюнктивную нормальную форму:



Из неё можно получить СДНФ – совершенную дизъюнктивную нормальную форму. Будем использовать закон единицы, закон исключённого третьего, закон дистрибутивности:





Теперь, учитывая каждую конъюнкцию только 1 раз, получаем СДНФ:



Чтобы получить КНФ, воспользуемся полученной ДНФ: . Используем закон , тогда (здесь используем также закон снятия двойного отрицания): . Тогда упрощённая ДНФ:



Используя закон дистрибутивности, закон противоречия и закон нуля, получаем:



Получаем:





Получили конъюнктивную нормальную форму – КНФ:



Эта же форма является СКНФ, т.к. в каждой дизъюнкции участвуют все переменные.

б) Найдём теперь СДНФ, СКНФ табличным способом.

Составляем последовательно таблицу истинности для заданной функции . Учитываем, что отрицание меняет истинность, дизъюнкция ( ) ложна только в том случае, когда оба операнда ложны, конъюнкция истинна только в том случае, когда оба операнда истинны, импликация ( ) ложна только в том случае, когда из истины следует ложь.

















0

0

0

1

0

1

0

1

0

0

1

0

0

1

0

1

0

1

0

1

1

1

0

1

0

1

1

0

1

0

0

0

1

0

0

1

1

1

0

1

1

0

1

0

1

0

0

0

1

1

0

1

1

1

0

1

1

1

1

0

1

0

1

1

Используя наборы, на которых функция принимает значение 1, составляем совершенную дизъюнктивную нормальную форму - СДНФ: в каждую конъюнкцию переменная входит с отрицанием, если в соответствующем наборе она имеет значение 0 (знак конъюнкции – логического умножения опускаем для удобства):



Получили такую же форму СДНФ, как и раньше, только с перестановкой членов (но форма одна и та же).

Используя наборы, на которых функция принимает значение 0, составляем совершенную конъюнктивную нормальную форму - СКНФ: в каждую дизъюнкцию переменная входит с отрицанием, если в соответствующем наборе она имеет значение 1:



Получили такую же форму СКНФ, как и раньше, только с перестановкой членов (форма одна и та же).

в) Ранее была получена ДНФ: . Она является минимальной, уменьшить в ней число переменных уже нельзя. Построим по этой форме переключательную схему. В этой форме – три конъюнкции, значит схема будет состоять из трёх параллельных ветвей. Каждая конъюнкция реализуется последовательным соединением элементов в ней. Получаем:
















1   2


написать администратору сайта