Порядок выполнения работы. Министерство образования и науки РФ
Министерство образования и науки РФ
Профессионально-педагогический колледж
Федерального государственного бюджетного образовательного учреждения
Высшего профессионального образования
«Саратовский государственный технический университет
Имени Гагарина Ю.А.»
09.02.01 Компьютерные системы и комплексы
ОТЧЕТ
по практической работе № 4
по дисциплине «Дискретная математика»
Совершенные нормальные формы булевых функций. Минимизация булевых функций
Вариант V
Выполнил студент 2 курса
группы КСК – 922
В.А. Добров ____________
Проверил преподаватель
М.А. Ястребова _________
Работа выполнена на оценку
________________________
«___» _____________ 2015 г.
Цели работы:
1) научиться представлять булеву функцию в виде совершенной ДНФ;
2) научиться представлять булеву функцию в виде совершенной КНФ;
3) научиться представлять булеву функцию (N £ 3) в виде минимальной ДНФ графическим методом.
Краткие теоретические сведения
Дизъюнкция конечного множества элементарных конъюнкций называется дизъюнктивной нормальной формой (ДНФ). Число элементарных конъюнкций, образующих дизъюнктивную нормальную форму (ДНФ)называется длиной ДНФ.ДНФ, содержащая только полные элементарные конъюнкции называется совершенной ДНФ(илиСДНФ). Любую логическую формулу А можно представить в виде ДНФ, а затем ДНФ в виде СДНФ.
Легко построить СДНФ, представляющую произвольную булеву функцию, заданную в табличной форме. Для этого достаточно выделить наборы 
, на которых функция принимает значение 1, и для каждого из них ввести в СДНФ полную элементарную конъюнкцию, где любая переменная 
присутствует с отрицанием, если 
, и без отрицания, если 
.
Конъюнкция конечного множества элементарных дизъюнкций называется конъюнктивной нормальной формой (или КНФ). Число элементарных дизъюнкций, образующих КНФ, называется длиной. КНФ, состоящая только из полных элементарных дизъюнкций, называется СКНФ. Произвольную формулу B можно представить в виде КНФ, а затем КНФ в виде СКНФ.
СКНФ, представляющую произвольную булеву функцию, так же, как ее СДНФ, легко построить по табличному заданию этой функции. Согласно формуле достаточно выделить наборы , на которых функция принимает значение 0, и для каждого из них ввести в СДНФ полную элементарную дизъюнкцию, где любая переменная присутствует с отрицанием, если , и без отрицания, если .
Наиболее эффективна минимизация булевых функций с помощью карт Карно.
Порядок выполнения работы
Задание 1.Записать формулы в виде ДНФ, КНФ и СДНФ, СКНФ.
1) 
= 
= (А 
) ( 
) = (А 
В) ( 
) = 1 – СДНФ.
СКНФ не существует.
2) 
= 
( 
) = 
) ( 
) = 
= ( 
( 
) – СДНФ.
= 
= (А 
) ( 
) 
– СКНФ.
Задание 2.Постройте совершенные ДНФ и КНФ и соответствующие минимальные формы для булевых функций, заданных таблично.
| x y z | f1 |
| 0 0 0 | |
| 0 0 1 | |
| 0 1 0 | |
| 0 1 1 | |
| 1 0 0 | |
| 1 0 1 | |
| 1 1 0 | |
| 1 1 1 |
1)
f1 (x, y, z) = ( 
( 
(x 
) (x 
) – СДНФ.
f1 (x, y, z) = (x 
z) ( 
) ( 
) – СКНФ.
2)
| x y z | f2 |
| 0 0 0 | |
| 0 0 1 | |
| 0 1 0 | |
| 0 1 1 | |
| 1 0 0 | |
| 1 0 1 | |
| 1 1 0 | |
| 1 1 1 |
f2 (x, y, z) = ( ( 
( 
) (x 
) – СДНФ.
f2 (x, y, z) = ( 
) ( 
) ( 
) ( 
) – СКНФ.
Выводы:
Совершенная дизъюнктивная нормальная форма (СДНФ) — это такая ДНФ, которая удовлетворяет трём условиям:
- в ней нет одинаковых элементарных конъюнкций
- в каждой конъюнкции нет одинаковых пропозициональных букв
- каждая элементарная конъюнкция содержит каждую пропозициональную букву из входящих в данную ДНФ пропозициональных букв, причём в одинаковом порядке.
Совершенная конъюнктивная нормальная форма (СКНФ) — это такая КНФ, которая удовлетворяет трём условиям:
· в ней нет одинаковых элементарных дизъюнкций
· в каждой дизъюнкции нет одинаковых пропозициональных переменных
· каждая элементарная дизъюнкция содержит каждую пропозициональную букву из входящих в данную КНФ пропозициональных букв.
СКНФ и СДНФ активно применяются в цифровой технике. Для реализации цифровых логических схем с произвольной таблицей истинности используется сочетание простейших логических элементов "И" "ИЛИ" "НЕ". Существует два способа синтеза цифровых схем, реализующих произвольную таблицу истинности. Это СКНФ (логическое произведение суммы входных сигналов) и СДНФ (сумма логических произведений входных сигналов).
Контрольные вопросы:
1) Что такое алгебра логики? Алгебра логики— раздел математической логики, в котором изучаются логические операции над высказываниями (истинными или ложными).
2) Назовите базовые операции булевой алгебры. Логическое отрицание, логическое умножение, логическое сложение.
3) Какие основные законы и аксиомы алгебры логики Вы знаете? Ассоциативность, коммутативность, законы поглощения, дистрибутивность, дополнительность.
4) Дайте определение булевой функции. Булевы функции — функции, которые задаются на двухэлементном множестве (0; 1) и задаются на этом же множестве.
5) Что такое СДНФ и СКНФ? СКНФ - совершенно конъюнктивная нормальная форма. СДНФ - совершенная дизъюнктивная нормальная форма. Нормальная форма логической формулы не содержит знаков импликации, эквиваленции и отрицания неэлементарных формул.
СКНФ — конъюнкция дизъюнкций, причём в каждой дизъюнкции (в каждой скобке) присутствуют все переменные, входящие в формулу, либо их отрицание, нет одинаковых дизъюнкций, в каждой дизъюнкции нет одинаковых слагаемых.
СДНФ — дизъюнкция конъюнкций, причём в каждой конъюнкции (в каждой скобке) присутствуют все переменные, входящие в формулу, либо их отрицание, нет одинаковых конъюнкций, в каждой конъюнкции нет одинаковых слагаемых.
6) Что такое таблица истинности? Таблица истинности — это таблица, описывающая логическую функцию.
7) Для чего применяют карты Карно? Картой Карно представляются высказывания в дизъюнктивной нормальной форме, т.е. выражения, представляющие собой дизъюнкции элементарных конъюнкций. С помощью карты Карно можно найти сокращенную, ядровую и все минимальные дизъюнктивные нормальные формы булевой функции, заданной вектором значений.