Дизъюнктивные нормальные формы
Представление булевой функции в виде дизъюнктивной нормальной формы. Выражение всех логических операции в формуле через конъюнкции, дизъюнкции и отрицания. Сокращение количества слагаемых, входящих в формулу и количества переменных, входящих в слагаемое.
| Рубрика | Математика |
| Вид | контрольная работа |
| Язык | русский |
| Дата добавления | 06.05.2013 |
| Размер файла | 1,3 M |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Тема
Дизъюнктивные нормальные формы
Понятие ДНФ
Пусть задан алфавит переменных {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) - это днф
D2 = (¬x1 & ¬x2 & x3) V (x1 & ¬x2 & x3) V (x1 & x2 & ¬x3) V (x1 & x2 & x3) - это днф
Контрпример:
X = (a V b)&(b V c) - это не днф
Представление булевой функции в виде дизъюнктивной нормальной формы бывает крайне удобным для доказательства некоторых теорем, а также для исследования функции и её визуализации.
Отметим, что любая функция может быть представлена в виде ДНФ, вообще говоря, не единственным образом. Пример:
D1 = (a&b) V (a&¬b).
Простым перебором убеждаемся, что данная ДНФ может быть записана как
D2 = a.
Отыскание наиболее простой формы представления заданной функции в виде ДНФ является одной из важнейших задач дискретной математики. Позже мы рассмотрим несколько способов решения этой задачи.
Построение ДНФ
Алгоритм построения ДНФ путём замены операций в выражении.
Пусть требуется привести произвольную формулу к виду днф. Алгоритм состоит в следующем:
1) Выразить все логические операции в формуле через конъюнкции, дизъюнкции и отрицания. Это можно сделать, используя равносильные формулы
|
A->B |
¬A V B |
|
|
A<->B |
(A & B) V (¬A & ¬B) |
|
|
A+B |
(¬A & B) V (A & ¬B) |
|
|
A|B |
¬A V ¬B |
|
|
AvB |
¬A & ¬B |
2) Заменить знак отрицания, относящийся ко всему выражению, знаками отрицания, относящимися к отдельным переменным высказываниям на основании формул
|
¬(A V B) |
¬A & ¬B |
|
|
¬(A & B) |
¬A V ¬B |
3) Избавиться от знаков двойного отрицания.
4) Применить, если нужно, к операциям конъюнкции и дизъюнкции свойства дистрибутивности и формулы поглощения.
Таким образом, для функции, заданной аналитически, можно построить ДНФ, превратив её в дизъюнкцию простых конъюнкций. Полученная формула будет удовлетворять определению дизъюнктивной нормальной формы.
Пример.
Приведем к ДНФ формулу
F = ((X -> Y) v ¬ (Y -> Z))
1) F = ((¬X V Y) v ¬(¬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)
4) Используя закон дистрибутивности, приводим формулу к ДНФ
F = (X & ¬Y) V (X & ¬Y & Z)
Алгоритм построения СДНФ по таблице истинности
Пусть имеется таблица истинности для функции n переменных.
|
x1 |
… |
xn |
f |
|
|
0 |
… |
0 |
м1 |
|
|
0 |
… |
1 |
м2 |
|
|
… |
… |
… |
… |
|
|
1 |
… |
0 |
м(2^n)-1 |
|
|
1 |
… |
1 |
м2^n |
Для каждого набора {у1, …, уn}, такого, что f(у1, …, уn) = 1, выписать элементарную конъюнкцию, в которую переменная xi входит со знаком отрицания, если уi = 0, и без него, если уi = 1. Дизъюнкция всех таких элементарных конъюнкций и будет СДНФ, реализующей данную функцию.
Пример.
Пусть дана таблица истинности для функции трёх переменных.
|
x1 |
x2 |
x3 |
f |
|
|
0 |
0 |
0 |
0 |
|
|
0 |
0 |
1 |
1 |
|
|
0 |
1 |
0 |
0 |
|
|
0 |
1 |
1 |
0 |
|
|
1 |
0 |
0 |
0 |
|
|
1 |
0 |
1 |
1 |
|
|
1 |
1 |
0 |
1 |
|
|
1 |
1 |
1 |
1 |
Здесь 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 переменных конечно (их ), можно построить их все, и выбирать среди них подходящие.
1) Построим все ДНФ над переменными x1, x2, … , xn:
D1, D2, … ,
2) Выберем среди них те, которые реализуют заданную функцию f:
D1, D2, … ,
3) Наконец, выберем среди них минимальные.
Данный алгоритм весьма трудоёмок с точки зрения реализации, так как он основан на переборе всех днф. Им нельзя воспользоваться на практике начиная уже с n=3, а для более высоких n алгоритм вовсе неприменим. В связи с этим появилась необходимость искать другие пути решения этой задачи. Далее будет рассказано о некоторых практических алгоритмах минимизации.
Алгоритм Блейка
Идея алгоритма в том, чтобы получить сокращенную ДНФ из произвольной путём выполнения операций обобщённого склеивания и поглощения конъюнкций.
Закон поглощения: x&y V x = x.
Закон обобщенного склеивания: x&y V ¬y&z = x&y V ¬y&z V x&z
Рассмотрим конъюнкции заданной ДНФ слева направо:
1) Пусть выбрана конъюнкция 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.
Таким образом, главной задачей при минимизации СДНФ и СКНФ является поиск термов, пригодных к склейке с последующим поглощением, что для больших форм может оказаться достаточно сложной задачей. Карты Карно предоставляют наглядный способ отыскания таких термов.
Разберём минимизацию СДНФ с помощью карт Карно на примере.
Пример.
Пусть дана таблица истинности для функции трёх переменных.
|
x1 |
x2 |
x3 |
f |
|
|
0 |
0 |
0 |
0 |
|
|
0 |
0 |
1 |
1 |
|
|
0 |
1 |
0 |
0 |
|
|
0 |
1 |
1 |
0 |
|
|
1 |
0 |
0 |
0 |
|
|
1 |
0 |
1 |
1 |
|
|
1 |
1 |
0 |
1 |
|
|
1 |
1 |
1 |
1 |
Соответствующая ей СДНФ: (¬x1 & ¬x2 & x3) V (x1 & ¬x2 & x3) V (x1 & x2 & ¬x3) V (x1 & x2 & x3).
Сначала необходимо построить прямоугольное поле с количеством клеток 2n. В этом случае стороны прямоугольника также будут степенью двойки (0, 1, 2, 4, …). Для трёх переменных количество клеток будет 23 = 8.
Построим поле 2x4
Каждой клетки этого поля будет соответствовать возможная элементарная конъюнкция формулы. Чтобы это обеспечить, необходимо обозначить для каждой переменной области, где она входит со знаком отрицания и без него. Сделать это можно, например, следующим образом
Первая (верхняя) строка будет соответствовать тем конъюнкциям, в которые x1 входит с отрицанием, нижняя - без. Аналогично, левая половина поля отвечает тем конъюнкциям, где x3 входит без отрицания, правая - с отрицанием. Несложно убедиться, что при таком разбиении присутствуют клетки для каждой возможной элементарной конъюнкции.
Далее, нужно пометить единицей клетки, соответствующие конъюнкции которых присутствуют в формуле: f(у1, у2, у3) = 1. В нашем случае таких конъюнкций четыре. Им соответствуют клетки:
Далее, необходимо выделить области по следующим правилам:
· Склейку клеток карты Карно можно осуществлять по единицам.
· Склеивать можно только прямоугольные области с числом единиц (нулей) 2n, где n -- целое число. Для карт Карно с числом переменных более четырёх могут получаться более сложные области, о чём будет сказано в следующих разделах.
· Область, которая подвергается склейке, должна содержать только единицы.
· Крайние клетки каждой горизонтали и каждой вертикали также граничат между собой (топологически карта Карно для четырёх переменных представляет собой тор) и могут объединяться в прямоугольники. Следствием этого правила является смежность всех четырёх угловых ячеек карты Карно для N=4. Если во всех четырёх угловых ячейках стоят единицы, они могут быть объединены в квадрат.
· Все единицы (нули) должны попасть в какую-либо область.
· С точки зрения минимальности ДНФ число областей должно быть как можно меньше (каждая область представляет собой терм), а число клеток в области должно быть как можно больше (чем больше клеток в области, тем меньше переменных содержит терм. Терм размером 2n ячеек содержит N-n переменных).
· Одна ячейка карты Карно может входить сразу в несколько областей. Это следует из очевидного свойства булевых функций: повторение уже существующего слагаемого (сомножителя) не влияет на функцию: A V A = A, A&A = A.
В нашем случае, можно выделить две области 1x2 и 2x1
Затем, выписываем конъюнкции, соответствующие данным областям.
Левая область отвечает конъюнкции, куда входит переменная 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 такая, что
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
Размещено на Allbest.ru
Подобные документы
Сокращенные, тупиковые дизъюнктивные нормальные формы. Полные системы булевых функций. Алгоритм Квайна, Мак-Класки минимизации булевой функции. Геометрическое представление логических функций. Геометрический метод минимизации булевых функций. Карты Карно.
курсовая работа [278,1 K], добавлен 21.02.2009Нечёткие системы логического вывода. Исследование основных понятий теории нечетких множеств. Операции над нечёткими множествами. Нечёткие соответствия и отношения. Описания особенностей логических операций: конъюнкции, дизъюнкции, отрицания и импликации.
презентация [191,0 K], добавлен 29.10.2013Сущность и математическое обоснование булевой функции, ее назначение и пути решения. Порядок составления таблицы истинности для определенного количества переменных. Связь всех дизъюнкций в конъюнкцию. Разработка и листинг программы представления.
курсовая работа [837,6 K], добавлен 27.04.2011Вопросы сводимости функций. Символы логических операций: отрицания, конъюнкции, дизъюнкции, импликации. Кванторы общности и существования. Минимальные элементы верхней полурешетки m-степеней. Идеалы полурешетки m-степеней частично рекурсивных функций.
контрольная работа [120,5 K], добавлен 06.05.2009Основные понятия алгебры логики. Дизъюнктивные и конъюнктивные нормальные формы. Сущность теоремы Шеннона. Булевы функции двух переменных. Последовательное и параллельное соединение двух выключателей. Свойства элементарных функций алгебры логики.
контрольная работа [345,3 K], добавлен 29.11.2010Понятие нечеткого множества и свойства его элементов. Определение логических операций: отрицания, конъюнкции, дизъюнкции. Основные этапы нечеткого вывода, метод центра тяжести. Оценка состояния повреждения объекта на основе теории нечетких множеств.
курсовая работа [316,8 K], добавлен 22.07.2011Основы формальной логики Аристотеля. Понятия инверсии, конъюнкции и дизъюнкции. Основные законы алгебры логики. Основные законы, позволяющие производить тождественные преобразования логических выражений. Равносильные преобразования логических формул.
презентация [67,8 K], добавлен 23.12.2012Основные формы мышления: понятия, суждения, умозаключения. Сочинение Джорджа Буля, в котором подробно исследовалась логическая алгебра. Значение истинности (т.е. истинность или ложность) высказывания. Логические операции инверсии (отрицания) и конъюнкции.
презентация [399,6 K], добавлен 14.12.2016Изучение булевых функций. Алгоритм представления булевых функций в виде полинома Жегалкина. Система функций множества. Алгебраические преобразования, метод неопределенных коэффициентов. Таблица истинности для определенного количества переменных.
курсовая работа [701,9 K], добавлен 27.04.2011Определение констант нуля и установление эквивалентности линейных функций при помощи таблицы истинности. Нахождение минимальной дизъюнктивной нормальной формы функции с помощью метода неопределенных коэффициентов. Преобразование функции методом Квайна.
контрольная работа [335,2 K], добавлен 05.07.2014
