5659.Учебная работа .Тема:Дизъюнктивные нормальные формы

1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд (3 оценок, среднее: 4,67 из 5)
Загрузка...

Тема:Дизъюнктивные нормальные формы»,»

Тема

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

Понятие ДНФ

Пусть задан алфавит переменных {x1, …, xn}.

Выражение вида

& & … & ()

называется элементарной конъюнкцией. Здесь ?j = {0, 1} и переменная xij входит в конъюнкцию с отрицанием, если ?j = 0, и без отрицания, если ?j = 1.

Число r называется рангом элементарной конъюнкции. По определению считаем константу 1 элементарной конъюнкцией ранга 0.

Выражение вида

()

где Ki (i = 1, …, s) элементарная конъюнкция ранга ri, называется дизъюнктивной нормальной формой (д.н.ф.).

Пример.

D1 = (a) V (¬a & c) V (¬b & c) это днф2 = (¬x1 & ¬x2 & x3) V (x1 & ¬x2 & x3) V (x1 & x2 & ¬x3) V (x1 & x2 & x3) это днф

Контрпример:

X = (a V b)&(b V c) это не днф

Представление булевой функции в виде дизъюнктивной нормальной формы бывает крайне удобным для доказательства некоторых теорем, а также для исследования функции и её визуализации.

Отметим, что любая функция может быть представлена в виде ДНФ, вообще говоря, не единственным образом. Пример:1 = (a&b) V (a&¬b).

Простым перебором убеждаемся, что данная ДНФ может быть записана как

D2 = a.

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

Построение ДНФ

Алгоритм построения ДНФ путём замены операций в выражении.

Пусть требуется привести произвольную формулу к виду днф. Алгоритм состоит в следующем:

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

A>B¬A V BA<>B(A & B) V (¬A & ¬B)A+B(¬A & B) V (A & ¬B)A|B¬A V ¬BA?B¬A & ¬B

2) Заменить знак отрицания, относящийся ко всему выражению, знаками отрицания, относящимися к отдельным переменным высказываниям на основании формул

¬(A V B)¬A & ¬B¬(A & B)¬A V ¬B

3) Избавиться от знаков двойного отрицания.

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

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

Пример.

Приведем к ДНФ формулу

F = ((X > Y) ? ¬ (Y > Z))

1)F = ((¬X V Y) ? ¬(¬Y V Z)) = ¬((¬X V Y) V ¬(¬Y V Z))

2)В полученной формуле перенесем отрицание к переменным:

F = ¬((¬X V Y) V ¬(¬Y V Z)) = (¬¬X & ¬Y) & (¬Y V Z)

3)сократим двойные отрицания

F = (X & ¬Y) & (¬Y V Z)

)Используя закон дистрибутивности, приводим формулу к ДНФ

F = (X & ¬Y) V (X & ¬Y & Z)

Алгоритм построения СДНФ по таблице истинности

Пусть имеется таблица истинности для функции n переменных.

x1…xnf0…0?10…1?2…………1…0?(2^n)11…1?2^n

Для каждого набора {?1, …, ?n}, такого, что f(?1, …, ?n) = 1, выписать элементарную конъюнкцию, в которую переменная xi входит со знаком отрицания, если ?i = 0, и без него, если ?i = 1. Дизъюнкция всех таких элементарных конъюнкций и будет СДНФ, реализующей данную функцию.

Пример.

Пусть дана таблица истинности для функции трёх переменных.

x1x2x3f00000011010001101000101111011111

Здесь f(0,0,1) = 1, значит, в ДНФ включаем конъюнкцию ¬x1 & ¬x2 & x3

Аналогично, включаем x1 & ¬x2 & x3, x1 & x2 & ¬x3 и x1 & x2 & x3.

Получаем: f(x1, x2, x3) = (¬x1 & ¬x2 & x3) V (x1 & ¬x2 & x3) V (x1 & x2 & ¬x3) V (x1 & x2 & x3).

Аналогично строится КНФ: для каждого набора {?1, …, ?n}, такого, что f(?1, …, ?n) = 0, выписать элементарную дизъюнкцию, в которую переменная xi входит со знаком отрицания, если ?i = 0, и без него, если ?i = 1. Конъюнкция всех таких дизъюнкций образует КНФ выражение вида

( V V … V ) & ( V V … V ) & … & ( V V … V ).

Упрощение ДНФ

Рассмотрим задачу упрощения ДНФ сокращения количества слагаемых, входящих в формулу, а также количества переменных, входящих в каждое слагаемое. Эта задача называется проблемой минимизации булевых функций. Заметим сразу, что эта проблема допускает тривиальное решение: поскольку количество всех возможных ДНФ от n переменных конечно (их ), можно построить их все, и выбирать среди них подходящие.

)Построим все ДНФ над переменными x1, x2, … , xn:

D1, D2, … ,

)Выберем среди них те, которые реализуют заданную функцию f:

D1, D2, … ,

)Наконец, выберем среди них минимальные.

Данный алгоритм весьма трудоёмок с точки зрения реализации, так как он основан на переборе всех днф. Им нельзя воспользоваться на практике начиная уже с n=3, а для более высоких n алгоритм вовсе неприменим. В связи с этим появилась необходимость искать другие пути решения этой задачи. Далее будет рассказано о некоторых практических алгоритмах минимизации.

Алгоритм Блейка

Идея алгоритма в том, чтобы получить сокращенную ДНФ из произвольной путём выполнения операций обобщённого склеивания и поглощения конъюнкций.

Закон поглощения: x&y V x = x.

Закон обобщенного склеивания: x&y V ¬y&z = x&y V ¬y&z V x&z

Рассмотрим конъюнкции заданной ДНФ слева направо:

) Пусть выбрана конъюнкция Ki. Проверяем её на возможность обобщённого склеивания с предшествующими конъюнкциями. При этом для очередной Ki, Kj, j < i возможны следующие ситуации:

а) результат обобщенного склеивания поглощается рассматриваемой ДНФ. Тогда и переходим к шагу 2.

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

2) Увеличиваем j. Если i j переходим к шагу 1, увеличивая i и полагая j = 1, иначе увеличиваем j.

Разберём этот алгоритм на примере.

Пример. Пусть дана произвольная ДНФ:

D = x&y V ¬x&z V ¬y&z.

К первой и второй конъюнкции можно применить закон обобщённого склеивания:

x&y V ¬x&z = x&y V ¬x&z V y&z

Слагаемое y&z не поглощается ни одной из конъюнкций ДНФ, значит, приписываем его в конец формулы.

D = x&y V ¬x&z V ¬y&z V y&z.

Применим закон обобщённого склеивания к первой и третьей конъюнкции, припишем полученную конъюнкцию справа:

D = x&y V ¬x&z V ¬y&z V y&z V x&z

Применим закон обобщённого склеивания к третьему и четвёртому слагаемому:

¬y&z V y&z = ¬y&z V y&z V z

Припишем z в конец выражения:

D = x&y V ¬x&z V ¬y&z V y&z V x&z V z

Легко заметить, что z поглощает все конъюнкции, содержащие переменную z, то есть все кроме первого:

D = x&y V z.

Минимальная ДНФ построена.

Карты Карно

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

Карты Карно были изобретены в 1952 Эдвардом В. Вейчем и усовершенствованы в 1953 Морисом Карно, физиком из «Bell Labs», и были призваны помочь упростить цифровые электронные схемы.

Возможность поглощения следует из очевидных равенств:

A V ¬A = 1; A&(¬A) = 0.

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

Разберём минимизацию СДНФ с помощью карт Карно на примере.

Пример.

Пусть дана таблица истинности для функции трёх переменных.

x1x2x3f00000011010001101000101111011111

Соответствующая ей СДНФ: (¬x1 & ¬x2 & x3) V (x1 & ¬x2 & x3) V (x1 & x2 & ¬x3) V (x1 & x2 & x3).

Сначала необходимо построить прямоугольное поле с количеством клеток 2n. В этом случае стороны прямоугольника также будут степенью двойки (0, 1, 2, 4, …). Для трёх переменных количество клеток будет 23 = 8.

Построим поле 2×4

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

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

Далее, нужно пометить единицей клетки, соответствующие конъюнкции которых присутствуют в формуле: f(?1, ?2, ?3) = 1. В нашем случае таких конъюнкций четыре. Им соответствуют клетки:

Далее, необходимо выделить области по следующим правилам:

·Склейку клеток карты Карно можно осуществлять по единицам.

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

·Область, которая подвергается склейке, должна содержать только единицы.

·Крайние клетки каждой горизонтали и каждой вертикали также граничат между собой (топологически карта Карно для четырёх переменных представляет собой тор) и могут объединяться в прямоугольники. Следствием этого правила является смежность всех четырёх угловых ячеек карты Карно для N=4. Если во всех четырёх угловых ячейках стоят единицы, они могут быть объединены в квадрат.

·Все единицы (нули) должны попасть в какуюлибо область.

·С точки зрения минимальности ДНФ <#»»left»»>В нашем случае, можно выделить две области 1×2 и 2×1

Затем, выписываем конъюнкции, соответствующие данным областям.

Левая область отвечает конъюнкции, куда входит переменная x3 и ¬x2, а от переменной x1 эта область не зависит (не меняется от замены x1 на ¬x1), поэтому её туда не включаем. Получаем: ¬x2&x3. Аналогично получаем вторую конъюнкцию: x1&x2. В итоге, ДНФ упростилась до дизъюнкции двух конъюнкций:

(¬x1 & ¬x2 & x3) V (x1 & ¬x2 & x3) V (x1 & x2 & ¬x3) V (x1 & x2 & x3) = (x1&x2) V (¬x2&x3)

Ещё один, более простой пример. Пусть дана ДНФ: (a&b) V (a&¬b). Соответствующая карта Карно будет полем 2х2

Вносим единицы в соответствующие клетки

Объединяем их в одну область

Выписываем конъюнкцию, соответствующую данной области:

f(a, b) = a

Это и будет упрощенная ДНФ данной функции. Таким образом, функция не зависит от переменной b.

Постановка задачи в геометрической форме

Аналогично картам Карно, искать кратчайшие покрытия функции f(x1, x2, …, xn) можно на гранях nмерного куба (где n количество входящих в функцию переменных).

Обозначим через En множество всех наборов (?1, …, ?n) из 0 и 1. Его можно рассматривать как множество всех вершин nмерного куба. Поскольку никаких других, кроме упомянутых, точек мы не рассматриваем, постольку множество En будем называть nмерным кубом, а наборы (?1, …, ?n) вершинами куба.

Примеры проекций 3мерного, 4мерного, 5мерного и 6мерного кубов на плоскость:

На рисунке 4 не наборы, а соответствующие им натуральные числа.

Определение. Пусть фиксированная система чисел из 0 и 1 такая, что

i1 i2 ir n. Множество всех вершин (1, 2, …, n,) куба En таких, что

, , …, , называется (n r)мерной гранью.

Очевидно, что (n r)мерная грань является (n r)мерным подкубом куба En.

Пусть f(x1, x2, …, xn) произвольная функция алгебры логики. Сопоставим ей подмножество Nf вершин куба En так, что

(1, 2, …, n,) Nf тогда и только тогда, когда когда f(1, 2, …, n,) = 1.

Ясно, что по подмножеству Nf функция восстанавливается единственным образом.

Пример.

f = (¬x1 & ¬x2 & ¬x3) V (x1 & ¬x2 & ¬x3) V (x1 & ¬x2 & x3) V (x1 & x2 & ¬x3) V (x1 & x2 & x3)

Функции f, подмножество Nf которой задаётся как Nf = {(0, 0, 0), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1)},

соответствует множество, изображенное на рисунке 5:

Выберем в качестве покрытия следующие два подмножества: x1 (правая квадратная грань) и ¬x2 & ¬x3 (переднее нижнее ребро). Получим: D = x1 V (¬x2 & ¬x3)

Возьмём в качестве исходной функции элементарную конъюнкцию K ранга r, где

& & … &

Легко видеть, что множество Nk, соответствующие конъюнкции K, образует (n r)мерную грань.

Число r будем называть рангом этой грани.

В нашем примере, конъюнкции K1 = (¬x1 & ¬x2 & ¬x3) соответствует множество NK1 = (0, 0, 0) ранга 3 и куб размерности 3 3 = 0 (точка);

конъюнкции K2 = (x1 & ¬x2) соответствует множество NK2 = {(1, 0, 0), (1, 0, 1)} ранга 2 и куб размерности 3 2 = 1 (ребро);

конъюнкции K3 = (x1) соответствует множество NK3 = {(1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1)} ранга 1 и куб размерности 3 1 = 2 (квадратная грань); И так далее.

Итак, пусть ri обозначает ранг грани NKi (он равен рангу конъюнкции Ki). Число r, где

r = ,

будем называть рангом покрытия. Теперь мы можем дать формулировку задачи в геометрической форме, эквивалентной задачи о минимизации булевой функции:

Найти для данного множества Nf такое покрытие гранями, принадлежащими Nf,

Nf = NK1 U NK2 U … U NKs,

Чтобы его ранг был наименьшим.

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

булевой функция операция дизъюнктивный

Список источников

·С. В. Яблонский Введение в дискретную математику (6е изд, 2010 г.)

·Самофалов, А.М. Романкевич, В.Н. Валуйский «»Прикладная теория цифровых автоматов»» Киев «»Вища Школа»» 1987