Студопедия

КАТЕГОРИИ:

АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника


Совершенная дизъюнктивно нормальная формы




 

Если ДНФ функции f1(x1,x2,…,xn) от n переменных в каждой своей конъюнкции содержит все n переменных либо их отрицания, то это совершенная дизъюнктивная нормальная форма (СДНФ). Для перехода от ДНФ к СДНФ необходимо в каждый из членов, в которых представлены не все аргументы, ввести выражение вида , где xi - отсутствующий в члене аргумент. Так как , такая операция не может изменить значений функции [12].

Для перехода от табличного представления функции к алгебраическому в виде ее СДНФ каждому i-ому набору переменных ставится в соответствие минтерм (mi) (константа единицы) - конъюнкция переменных, которые входят либо в прямом виде, если значение данной переменной в наборе равно 1, либо в инверсном виде, если значение переменной равно 0. Минтерм - это простая конъюнкция, в которую входят все аргументы рассматриваемой логической функции. Простой конъюнкцией считается логическое произведение переменных, взятых с отрицаниями или без них, в котором каждая переменная встречается не более одного раза (в простую конъюнкцию не должны входить суммы переменных, отрицания функций двух или нескольких переменных).

Для n переменных составляют q=2n минтермов: m0, m1,... , mq-1.

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

, (2.2)

где fi, mi - значение функции (0 или 1) и минтерм, соответствующий i- ому набору переменных.

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

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

, (2.3.)

где fi, Mi - значение функции и макстерм, соответствующий i-ому набору переменных [13-15].

 

Пример 2.3. Дана функция . Показать переход от ДНФ к СДНФ.

Решение. Добавление в члены выражений в виде приведет к функции

На основании свойств операций конъюнкций и дизъюнкций

.

Отсюда после приведения подобных членов имеем СДНФ

.

Пусть исходная функция задана в виде таблицы истинности:

x1 x2 x3 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1
f(x1,x2,x3) 0 0 1 1 0 1 0 1

 

Для этой функции СДНФ имеет вид

Каждый член в этой таблице соответствует некоторому набору значений аргументов, при котором f(x1,x2,x3) равна 1. Каждый из наборов аргументов, при которых f(x1,x2,x3) равна 1, обращает в единицу соответствующий член полученной СДНФ, вследствие чего и вся функция оказывается равной единице.

Пример 2.4. По заданной таблице истинности построить логическое выражение и упростить его.

 

X1 X2 X3 F

Решение. 1.Выбираем строки, в которых F=1, и строим для них минтермы.

1 строка

2 строка

3 строка

1. Объединяем минтермы:


3. Упрощаем логическое выражение:

Пример 2.5. Упростить совершенную ДНФ для импликации.

Решение. Импликация может быть определена по формуле

( ) ( ) ( ).

Упростим правую часть равенства. Применяя тождества 3б, 1а, 4а, 1б, 4 г, получим

( ) ( ) ( ( )) (

)) ( ( ) (

(

.

Таким образом, искомая формула будет

.

Правая часть полученного равенства представляет конъюнкцию неполных дизъюнкций. Такие формулы называются сокращенными ДНФ. В примерах 3 и 4 был осуществлен переход от совершенных ДНФ к сокращенным.

 

Пример 2.6. Пусть функция Y задана таблицей:

Х1 X2 X3 Y Минтерм Макстерм ЗначениеYi
Y1=0
Y2=0
Y3=0
Y4=0
Y5=0
Y6=1
Y7=1
Y8=1

 

Алгебраическая форма записи данной функции:

.

Число слагаемых при использовании СДНФ равно количеству строк таблицы истинности, в которых Yi=1.

С использованием СКНФ выражение функции Y будет:

Число сомножителей в СКНФ равно числу строк, в которых Yi=0.

 

Если число строк в таблице истинности, содержащих Yi=1, меньше числа строк, содержащих Yi=0, то целесообразно использовать СДНФ, если наоборот, то СКНФ.

 

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

x1 x2 f

 

Решение.1. Для n=2 переменных составляют q = 2n = 4 минтерма и макстерма, которые вписаны соответственно в 3-ю и 4-ю графы таблицы 2.2.

 

Таблица 2.2.

x1 x2 mi Mi f

 

 

2. Алгебраическое представление логической функции в СДНФ

3. Алгебраическое представление логической функции в СКНФ

Пример 2.8. Представить в СДНФ логическую функцию пяти аргументов f(x1,x2,x3,x4,x5), равную единице на следующих четырех наборах

 

Решение. 1. Запишем четыре произведения аргументов, связанных знаком дизъюнкции, и под каждым из них - один из перечисленных наборов

x1 x2 x3 x4 x5 Ú x1 x2 x3 x4 x5 Ú x1 x2 x3 x4 x5 Ú x1 x2 x3 x4 x5
0 0 1 0 1 0 1 1 1 1 1 0 0 0 0 1 1 1 1 1

 

2. Расставляя отрицания над аргументами, равными нулю, получим СДНФ логической функции:

Ú Ú Ú

Пример 2.9. Представить в СКНФ переключательную функцию четырех аргументов f(x1,x2,x3,x4) , равную нулю на наборах

 

 

Решение.1. Запишем четыре произведения дизъюнкций всех аргументов и под каждым из них один из перечисленных наборов:

(x1 Vx2Vx3Vx4) × (x1Vx2Vx3Vx4) × (x1Vx2Vx3Vx4) × (x1Vx2Vx3Vx4)
0 0 1 1 0 1 1 1 1 0 0 0 1 1 1 1

 

2. Расставляя знаки отрицания над аргументами, равными единице, получим СКНФ логической функции:

Приведенные соотношения позволяют определить структуру логического устройства, которое осуществляет операции в соответствии с приведенной таблицей истинности. Но такая структура не является единственно возможной схемой логического устройства и не является оптимальной с точки зрения числа логических элементов. Поэтому одним из важнейших этапов синтеза логических схем является минимизация числа элементов структурной схемы, что связано минимизацией логических функций.


Поделиться:

Дата добавления: 2015-08-05; просмотров: 135; Мы поможем в написании вашей работы!; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2024 год. (0.007 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты