Лабораторная работа № 12. «Представление функций в совершенной нормальной форме»

«Представление функций в совершенной нормальной форме»

Цель работы: Научиться представлять функций в совершенной нормальной форме

Образовательные результаты, заявленные во ФГОС третьего поколения:

Студент должен

уметь:

- строить логические схемы и алгоритмы;

- использовать средства операционных систем и сред для обеспечения работы вычислительной техники;

- использовать языки программирования строить логически правильные и эффективные программы;

- осваивать и использовать базовые системные программные продукты и пакеты прикладных программ.

.

знать:

- общий состав и структуру персональных ЭВМ и вычислительных систем;

- основные функции назначение и принципы работы распространенных операционных систем;

- состав, структуру, принципы реализации и функционирования информационных технологий;

- общие принципы построение алгоритмов основные алгоритмические конструкции;

- стандартные типы данных;

- базовые системные программные продукты и пакеты прикладных программ.

 

 

Краткие теоретические и учебно-методические материалы по теме практической работы:

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

Поэтому более целесообразно использовать специальные алгоритмические методы минимизации, позволяющие проводить упрощение функции более просто, быстро и безошибочно.Если все конъюнктивные термы в ДНФ являются минтермами, т. е. содержат в точности по одной все логические переменные, взятые с отрицаниями или без них, то такая форма представления функции называется совершенной дизъюнктивной нормальной формой (СДНФ) этой функции. СДНФ называется совершенной, потому что каждый терм в дизъюнкции включает все переменные; дизъюнктивной, потому что главная операция в формуле – дизъюнкция. Понятие “нормальной формы” означает однозначный способ записи формулы, реализующей заданную функцию.

Формула называется тождественно-истинной (тавтологией), если для любых наборов переменных она принимает значение И. Формула называется тождественно тождественно-ложной, если для любых наборов переменных она принимает значение Л

В алгебре высказываний используют две нормальные формы: дизъюнктивную и конъюнктивную нормальные формы формулы (ДНФ и КНФ).

Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция простых конъюнкций. Конъюнктивной нормальной формой (КНФ) формулы есть формула, равносильная исходной формуле логики высказываний и записанная в виде конъюнкции элементарных дизъюнкций переменных.

Каждая формула, не равная тождественно Л, может быть приведена СДНФ, которая является единственной с точностью до перестановки дизъюнктивных членов. Каждая формула, не равная тождественно И, может быть приведена к СКНФ, которая является единственной с точностью до перестановки конъюнктивных членов.

Совершенная дизъюнктивная нормальная форма формулы (СДНФ) это равносильная ей формула, представляющая собой дизъюнкцию элементарных конъюнкций, обладающая свойствами:

1. Каждое логическое слагаемое формулы содержит все высказывания, входящие в формулу.

2. Все логические слагаемые формулы различны

3. Ни одно логическое слагаемое не содержит высказывание и его отрицание

4. Ни одно логическое слагаемое формулы не содержит одно и то же высказывание дважды. Алгоритм получения СКНФ по таблице истинности:

1)Отметить те строки, в последнем столбце которых стоят 0:

2)Выписать для каждой отмеченной строки дизъюнкцию всех переменных следующим образом: если значение некоторой переменной в данной строке =0, то в дизъюнкцию включают саму эту переменную, если =1, то ее отрицание:

3)Все полученные дизъюнкции связать в конъюнкцию.

 

Задания для практического занятия:

Для заданной функции:

- найти двоичную форму булевой функции

-составить СДНФ функции

- минимизировать СДНФ функции

Задание

По результатам в последней колонке f(x, y, z) = (11110110)

2. Составим СДНФ функции. Функция принимает значение 1 на наборах 000, 001, 010, 011, 101, 110. Нулю соответствует переменная с отрицанием, единице – без отрицания. Получим СДНФ:

3. Минимизируем СКНФ функции, для этого:

- перегруппируем элементарные конъюнкции так чтобы между двумя членами, содержащими одинаковые переменные, вхождения которых (прямые и инверсные) совпали для всех переменных, кроме одной

- последние два члена нельзя сгруппировать, но, используя закон идемпотентности (АVA =A), продублируем подходящие коньюнкции:

- в этом случаем все переменные в паре, кроме одной, можно вынести за скобки

- а оставшееся в скобках прямое и инверсное вхождение одной переменной подвергнуть склейке

 

Варианты заданий

Контрольные вопросы:

1 Что такое дизъюнктивной нормальной формой (ДНФ)?

2 Что такое конъюктивная нормальной формой (КНФ)?

3 Свойства дизъюнкции элементарных конъюнкций?

4 Алгоритм получения СКНФ