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

Элементарной конъюнкцией называется конъюнкция переменных или их отрицаний, в которой каждая переменная встречается не более одного раза.

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

Совершенная ДНФ – это ДНФ, каждая элементарная конъюнкция, которой включает все переменные с отрицанием или без.

 

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

Для каждой выделенной строки составляется конъюнкция всех входных переменных, причем сомножитель записывают со знаком инверсии, если переменная принимает в этой строке нулевое значение.

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

 

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

 

КНФ также называется совершенной, если каждая элементарная сумма содержит все переменные с инверсией или без.

 

КНФ может быть получена из таблицы истинности: для каждого набора аргументов на котором функция равна «0» составляют элементарную сумму, причем переменные, значение которых равно «1», записываются с отрицанием.

Пример 8: Составим СДНФ для функции из примера 6.

Рассмотрим алгоритм составления СДНФ:

1. Построить таблицу истинности

2. Выбрать все строки таблицы, в которых f=1.

3. Каждой такой строке поставить в соответствие конъюнкцию всех аргументов.

· При этом аргумент, принимающий значение 0, берем с отрицанием, а значение 1 – без отрицания.

4. Образуем дизъюнкцию всех полученных функций. Количество элементов должно совпадать с количеством единиц логической функции.

 

Таблицу истинности мы ранее построили, теперь выберем нужные строки и запишем конъюнкции:

 

x	y	z	F	Конъюнкция
				-
0
				-
0
1
				-
				-
				-

 

Образуем СДНФ:

Синтез логических схем

Задача синтеза:

· По заданной функции f требуется построить схему, реализующую данную функцию

 

Этапы синтеза:

1. Составляется таблица истинности;

2. По таблице истинности составляется совершенная дизъюнктивная нормальная форма;

3. Используя карты Карно функция (если возможно) упрощается;

4. Составляем и зарисовываем логическую схему

Пример 9: Составить логическую схему, реализующую функцию из примера 6

Изначально у нас была функция , которую мы упростили до вида при помощи карты Карно .

Для начала определим количество входов логической схемы, число входов определяет число переменных. В нашем случае - 3

Теперь определим количество блоков с схеме:

1. Блок f – дизъюнкция функций f1 и f2

2. Блок f1- конъюнкция переменной z и блока инверсии переменной x

3. Блок f2 – конъюнкция переменной х и блоков инверсии переменной y и переменной z

 

Анализ логических схем

Задача анализа:

• По заданной схеме требуется определить функцию f, реализующуюся данной схемой.

 

Этапы анализа:

1. Разбиваем схему на ярусы.

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

3. Записываем выходные функции каждого элемента в виде формул в соответствии с введенными обозначениями.

4. Производим подстановку одних выходных функций через другие, используя входные переменные.

5. Записываем получившуюся булеву функцию через входные переменные.

 

Пример 10: По заданной логической схеме составить булеву функцию.

Этапы 1и 2. Согласно приведённой выше последовательности действий, произведём разбиение схемы на ярусы. Пронумеровав получившиеся ярусы, введём обозначения для каждой выходной функции:

Этап 3. Запишем все функции, начиная с 1-го яруса:

Этап 4: Теперь запишем все функции, подставляя входные переменные x ₁,..., x ₄:

В итоге, получим выходную функцию:

Этап 5: