Как найти днф: Учебник по дискретной математике ДНФ, СДНФ, КНФ, СКНФ

Содержание

Учебник по дискретной математике ДНФ, СДНФ, КНФ, СКНФ

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

Например, является простой конъюнкцией,

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

Например, выражение является ДНФ.

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

сами, либо их отрицания), причем в одном и том жепорядке.

Например, выражение является ДНФ, но не СДНФ. Выражение является СДНФ.

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

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

Конъюнктивной нормальной формой (КНФ) называется конъюнкция

простых дизъюнкций (например выражение – КНФ).

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

Например, выражение является СКНФ.

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

а) переход от ДНФ к КНФ

Алгоритм этого перехода следующий: ставим над ДНФ два отрицания и с помощью правил де Моргана (не трогая верхнее отрицание) приводим отрицание ДНФ снова к ДНФ. При этом приходится раскрывать скобки с использованием правила поглощения (или правила Блейка). Отрицание (верхнее) полученной ДНФ (снова по правилу де Моргана) сразу дает нам КНФ:

Заметим, что КНФ можно получить и из первоначального выражения, если вынести у за скобки;

б) переход от КНФ к ДНФ

Этот переход осуществляется простым раскрытием скобок (при этом опять-таки используется правило поглощения)

Таким образом, получили ДНФ.

Обратный переход (от СДНФ к ДНФ) связан с проблемой минимизации ДНФ. Подробнее об этом будет рассказано в разд. 5, здесь же мы покажем, как упростить ДНФ (или СДНФ) по правилу Блейка. Такая ДНФ называется сокращенной ДНФ;

в) сокращение ДНФ (или СДНФ) по правилу Блейка

Применение этого правила состоит из двух частей:

— если среди дизъюнктных слагаемых в ДНФ имеются слагаемые , то ко всей дизъюнкции добавляем слагаемое К₁К

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

— если добавляемое слагаемое уже содержалось в ДНФ, то его можно отбросить совсем, например,

или

Разумеется, сокращенная ДНФ не определяется единственным образом, но все они содержат одинаковое число букв (например, имеется ДНФ , после применения к ней правила Блейка можно прийти к ДНФ, равносильной данной):

в) переход от ДНФ к СДНФ

Если в какой-то простой конъюнкции недостает переменной, например, z, вставляем в нее выражение ,после чего раскрываем скобки (при этом повторяющиеся дизъюнктные слагаемые не пишем). (Xv ךYv ךZ) Таким образом, из КНФ получена СКНФ.

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

Соверше́нная конъюнкти́вная норма́льная фо́рма (СКНФ) — это такая конъюнктивная нормальная форма, которая удовлетворяет трём условиям:

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

в каждой дизъюнкции нет одинаковых пропозициональных переменных

каждая элементарная дизъюнкция содержит каждую пропозициональную букву из входящих в данную КНФ пропозициональных букв.

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

Например, следующая формула записана в 2-КНФ:

Соверше́нная дизъюнкти́вная норма́льная фо́рма (СДНФ) — это такая ДНФ, которая удовлетворяет трём условиям:

в ней нет одинаковых элементарных конъюнкций

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

каждая элементарная конъюнкция содержит каждую пропозициональную букву из входящих в данную

ДНФ пропозициональных букв, причём в одинаковом порядке.

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

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


0	0	0	1
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	0
1	0	1	0
1	1	0	1
1	1	1	0

Совершенная ДНФэтой функции:

Тема 6 Минимизация булевых функций

1 Сокращенная и тупиковая ДНФ

6.2 Метод импликантных матриц

Цель данного раздела – изложение основных методов построения минимальных дизъюнктивно нормальных форм.

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

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

Заметим, что если некоторый символ в формуле, скажем , встречается, например, два раза, то при подсчете числа символов в формуле он учитывается два раза.

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

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

Число различных ДНФ, составленных из переменных , равно .

Прежде чем доказать данное утверждение, приведем следующее определение.

Конъюнкция называется Элементарной, если при .

Число R называется Рангом элементарной конъюнкции.

В случае r=0 конъюнкция называется Пустой и Полагается равной 1.

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

Рассмотрим геометрическую интерпретацию задачи минимизации булевых функций.

Обозначим через множество всех точек , где . Ясно, что — множество всех вершин единичного n-мерного куба.

Сопоставим каждой булевой функции Подмножество Из , определенное следующим образом:

Например, функции

X	Y	Z
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

Соответствует подмножество

Вершин трехмерного единичного куба

Данное соответствие является взаимно однозначным и обладает следующими свойствами:

1) булевой функции Соответствует подмножество ;

2) булевой функции соответствует подмножество ;

3) булевой функции соответствует подмножество .

Докажем утверждение 2. Пусть

Отсюда .

Тогда .

А это значит, что .

Отсюда .

Пусть ДНФ, где — элементарные конъюнкции. Подмножество называется интервалом R-го ранга, если оно соответствует элементарной конъюнкции К R-го ранга. Как показано выше, . Итак, с каждой ДНФ функции F связано покрытие такими интервалами , что .

Пусть — ранг интервала . Тогда совпадает с числом букв в ДНФ функции .

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

Интервал , содержащий , называется Максимальным для булевой функции, если не существует интервала , такого, что .

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

Очевидно, что каждый интервал из содержится в некотором максимальном интервале. Если — список всех максимальных интервалов подмножества , то нетрудно видеть, что .

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

Ясно, что сокращенная ДНФ для любой булевой функции f определяется однозначно.

Пример 1. Пусть . Обозначим , , . Найдем соответствующие этим конъюнкциям интервалы , , .

Изобразим эти интервалы

Очевидно, что и — все максимальные интервалы. Интервал не является максимальным, ибо . Следовательно, покрытию подмножества соответствует сокращенная ДНФ функции , равная .

Данный геометрический подход дает и метод построения сокращенной ДНФ.

Теперь рассмотрим аналитический метод построения сокращенной ДНФ – метод Блейка. Этот метод основан на следующей теореме.

Теорема 1. Если в произвольной ДНФ булевой функции F произвести все возможные обобщения склеивания и устранить затем все элементарные поглощения, то в результате получиться сокращенная ДНФ функции F.

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

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

Затем правило поглощения и находим сокращенную ДНФ: .

Рассмотрим еще один метод построения сокращенной ДНФ – метод Нельсона. Этот метод основан на следующей теореме.

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

Пример 3. Найти сокращенную ДНФ для функции

После раскрытия скобок с помощью дистрибутивного закона, получаем:

Так как , , то имеем:

Далее, применяя правило поглощения, получаем сокращенную ДНФ:

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

Минимизирующие карты для булевых функций от трех и от четырех переменных изображены на следующих таблицах.

Z X y	0	1
00
01
11
10

X4 X3 X1 X2	0 0	0 1	1 1	1 0
0 0
0 1
1 1
1 0

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

Пример 4. Найти сокращенную ДНФ для функции, заданной следующей таблицей.

X4 X3 X1 X2	0 0	0 1	1 1	1 0
0 0	1	1	0	1
0 1	0	1	1	0
1 1	1	1	1	0
1 0	0	1	0	0

В данной таблице объединены клетки в максимальные интервалы

Этим интервалам соответствуют элементарные конъюнкции

, , , ,

Следовательно, сокращенная ДНФ для данной функции имеет вид:

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

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

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

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

Теорема 4. Сокращенная ДНФ монотонной булевой функции не содержит отрицаний переменных и является минимальной ДНФ этой функции.

Пусть К – элементарная конъюнкция, входящая в сокращенную ДНФ. Предположим, что К содержит отрицание переменных. Обозначим через произведение всех переменных, входящих в К без отрицания. Пусть – набор переменных, в которых всем переменным, входящим в , приписано значение 1, а всем остальным – значение 0. Ясно, что при этом наборе значение функции Равно 1. Элементарная конъюнкция обращается в 1 при всех наборах . Очевидно, что при этих наборах значение функции также равно 1. Следовательно, .

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

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

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

Элементарная конъюнкция поглощается дизъюнкцией остальных элементарных конъюнкций, т. е. .

Ввиду этого введем следующее определение.

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

Теорема 5. Всякая минимальная ДНФ является тупиковой.

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

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

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

1. Выделяются все максимальные интервалы, и строится сокращенная ДНФ.

2. Строятся все тупиковые ДНФ.

3. Среди всех тупиковых ДНФ выделяются все минимальные ДНФ.

Рассмотрим алгоритм построения всех тупиковых ДНФ. Суть данного алгоритма состоит в следующем:

1) для булевой функции строим сокращенную ДНФ;

2) для каждой вершины из выделяем в сокращенной ДНФ функции F все такие элементарные конъюнкции , что ;

3) составляем выражение вида

(*)

4) применяем к выражению вида (*) законы дистрибутивности и поглощения. В результате получаем .

Теперь каждая ДНФ является тупиковой ДНФ функции .

Рассмотрим работу данного алгоритма на следующем примере.

Пример 5. Рассмотрим булеву функцию, заданную следующей таблицей:

X	Y	Z
0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	1
1	0	0	1
1	0	1	1
1	1	0	1
1	1	1	0

Найдем сокращенную ДНФ данной функции по методу Нельсона. Для этого составим КНФ данной функции .

Применяя законы дистрибутивности, получаем:

Обозначим , , , , , .

Составляем выражение (*)

Преобразуем данное выражение к виду

= =.

Таким образом, имеет шесть тупиковых ДНФ:

Две из них и являются минимальными.

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

	…		…


…
		+
…

Для каждой находим набор такой, что .

Клетку импликантной матрицы, образованную пересечением I-строки и J-столбца отметим крестиком.

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

Пример 6. Найти минимальные ДНФ для функции

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

Строим импликантную матрицу

(0,0,1)	(0,1,0)	(0,1,1)	(1,0,0)	(1,0,1)	(1,1,0)
			+	+
			+		+
	+	+
	+				+
+		+
+				+

Отсюда видно, что данная функция имеет два минимальные ДНФ:

; .

Вопросы для самоконтроля.

1. Дайте определение основных логических операций булевой алгебры.

2. Дайте определение булевой функции.

3. Что такое таблицы истинности булевой функции?

4. Каково число булевых функций от переменных?

5. Какие булевы функции называются элементарными?

6. Дайте определение формулы алгебры логики.

7. Какие формулы алгебры логики называются равносильными?

8. Сформулируйте законы алгебры логики.

9. Какая формула алгебры логики называется двойственной к данной формуле алгебры логики?

10. Сформулируйте принцип двойственности.

11. Сформулируйте теорему о разложении и следствие из нее.

12. Дайте определение СДНФ.

13. Приведите алгоритмы построения СДНФ.

14. Дайте определение СКНФ.

15. Приведите алгоритмы построения СКНФ.

16. Дайте определение ДНФ.

17. Как найти ДНФ?

18. Дайте определение КНФ.

19. Как найти КНФ?

20. Какая формула алгебры логики называется тождественно истинной?

21. Какая формула алгебры логики называется тождественно ложной?

22. Какая формула алгебры логики называется выполнимой?

23. Что называется проблемой разрешимости?

24. Сформулируйте методы решения проблемы разрешения.

25. Что называется алгеброй Жегалкина?

26. Сформулируйте законы алгебры Жегалкина.

27. Что называется полиномом Жегалкина?

28. Сформулируйте алгоритмы построения полиномов Жегалкина.

29. Какая система булевых функций называется полной?

30. Что называется замыканием множества булевых функций?

31. Какой класс булевых функций называется замкнутым?

32. Дайте определение пяти важнейших замкнутых классов.

33. Сформулируйте теорему о полноте.

34. Сформулируйте алгоритм Поста.

35. Какая система булевых функций называется несократимой?

36. Каково максимальное возможное число функций в несократимой полной системе булевых функций?

37. Что такое релейно-контактная схема?

38. Почему любую булеву функцию можно изобразить в виде релейно-контактной схемы?

39. В чем состоит проблема анализа релейно-контактных схем?

40. В чем состоит проблема синтеза релейно-контактных схем?

41. Что такое логические элементы?

42. Приведите геометрическое изображение логических элементов.

43. Что такое логическая схема?

44. Что Вы понимаете под двоичным сумматором?

45. Какая ДНФ называется минимальной?

46. Чему равно число всех ДНФ от переменных?

47. Сформулируйте тривиальный алгоритм построения МДНФ?

48. Что такое элементарная конъюнкция?

49. Что такое ранг элементарной конъюнкции?

50. Что называется интервалом элементарной конъюнкции?

51. Какой интервал называется максимальным?

52. Что называется областью истинности булевой функции?

53. Сформулируйте теорему об области истинности булевой функции.

54. Что называется покрытием области истинности булевой функции?

55. Какое число элементов содержится в интервале?

56. Какая ДНФ называется сокращенной?

57. В чем состоит геометрическая интерпретация задачи минимизации булевой функции?

58. Сформулируйте геометрический метод построения сокращенной ДНФ.

59. Сформулируйте метод Нельсона построения сокращенной ДНФ.

60. Сформулируйте метод Блейка построения сокращенной ДНФ.

61. Сформулируйте метод карт Карно построения сокращенной ДНФ.

62. Какая связь между МДНФ и сокращенной ДНФ?

63. Какое покрытие области истинности булевой функции называется неприводимым.

64. Какая ДНФ называется тупиковой?

65. Какая связь между МДНФ и тупиковой ДНФ?

66. Сформулируйте алгоритм построения всех тупиковых ДНФ.

67. Как строится импликантная матрица?

68. Сформулируйте алгоритм нахождения МДНФ методом импликантных матриц.

< Предыдущая		Следующая >

Нормальные формы: ДНФ, КНФ, СДНФ, СКНФ

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

Алгоритм построения ДНФ:

1. Перейти к булевым операциям.

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

3. Раскрыть скобки.

4. Повторяющейся слагаемые взять по одному разу.

5. Применить законы поглощения и полупоглощения.

Пример.Найти ДНФ формулы

►

◄

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

Пример.Найти КНФ формулы

► ~ ~

.◄

Совершенную дизъюнктивную нормальную форму СДНФ можно строить, используя следующий алгоритм:

1. = 1. алгоритма ДНФ

2. = 2. алгоритма ДНФ

3. = 3. алгоритма ДНФ

4. = 4. алгоритма ДНФ

5. Опустить тождественно ложные слагаемые, т. е. слагаемые вида

6. Пополнить оставшиеся слагаемые недостающими переменными

7. Повторить пункт 4.

Пример.Найти СДНФ формулы.

► ~

.◄

Для построения СКНФ можно пользоваться следующей схемой:

Пример.Найти СДНФ формулы.

► ~

.◄

Известно (теоремы 2.11, 2.12), что СДНФ и СКНФ определены формулой однозначно и, значит, их можно строить по таблице истинности формулы [1].

►Схема построения СДНФ и СКНФ по таблице истинности приведена ниже, для формулы ~ :

2.2. Задание.

2.2.1 Ниже приведены логические выражения. Максимально упростите выражения своего варианта, воспользовавшись законами логики Буля. Затем с помощью таблиц истинности сравните ваше упрощенное выражение с исходным.

2.2.2. Выяснить вопрос о равносильности f₁ и f ₂ путем сведения их к СДНФ (табл. 1).

2.2.3. Найти двойственную функцию для f₃ по обобщенному и булевому принципу (табл.1). Сравнить полученные результаты.

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

2.3.1. Дайте определение высказывания.

2.3.2. Перечислите основные операции над высказыванием.

2.3.3. Что такое таблица истинности?

2.3.4. Составить таблицы истинности для следующих формул:

~ ~ ;

~ ;

~ ~ ~ ;

~ ~ ~ ~ .

2.3.5. Учитывая соглашения о порядке выполнения операций, опустить «лишние» скобки и знак « » в формулах:

;

~ .

2.3.6. Применяя равносильные преобразования, доказать тождественную истинность формул:

;

2.3.7.Найти двойственные формулы:

)

2.3.8. Привести к совершенной ДНФ (СДНФ) форме следующие формулы:

2.3.9. Привести к совершенной КНФ (СКНФ) форме следующие формулы:

Лабораторная работа № 3

Тема: «Минимизация булевых функций. Логические схемы»

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

3.1. Теоретические сведения [1].

Минимальные формы

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

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

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

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

Пусть, например, функция задана в совершенной нормальной дизъюнктивной форме:

Группируя члены и применяя операцию склеивания, имеем .

При другом способе группировки получим:

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

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

Многомерный куб

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

Рис.3.1 Отображение на трехмерном кубе функции, представленной в СДНФ

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

Минитерм ( -1)-го ранга можно рассматривать как результат склеивания двух минитермов -го ранга (конституент единицы), т.е. , На -мерном кубе это соответствует замене двух вершин, которые отличаются только значениями координаты , соединяющим эти вершины, ребром (говорят, что ребро покрывает инцидентные ему вершины). Таким образом, минитермам ( -1)-го порядка соответствуют ребра -мерного куба. Аналогично устанавливается соответствие минитермов ( -2)-го порядка — граням -мерного куба, каждая из которых покрывает четыре вершины (и четыре ребра).

Элементы -мерного куба, характеризующиеся измерениями, называют -кубами. Так, вершины являются 0-кубами, ребра – 1-кубами, грани – 2-кубами и т.д. Обобщая приведенные рассуждения, можно считать, что минитерм ( )-го ранга в дизъюнктивной нормальной форме для функции переменных отображается -кубом, причем каждый -куб покрывает все те -кубы низшей размерности, которые связаны с его вершинами. В качестве примера на рис. 3.2 дано отображение функции трех переменных. Здесь минитермы и соответствуют 1-кубам ( ), а минитерм отображается 2-кубом ( ).

Рис.3.2 Покрытие функции

Итак, любая дизъюнктивная нормальная форма отображается на -мерном кубе совокупностью -кубов, которые покрывают все вершины, соответствующие конституентам единицы (0-кубы). Справедливо и обратное утверждение: если некоторая совокупность -кубов покрывает множество всех вершин, соответствующих единичным значениям функции, то дизъюнкция соответствующих этим -кубам минитермов является выражение данной функции в дизъюнктивной нормальной форме. Говорят, что такая совокупность -кубов (или соответствующих им минитермов) образует покрытие функции.

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

Рис. 3.3 Покрытия функции .

слева – ; справа –

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

Рис. 3.4 Отображение функции на четырехмерном кубе

Карты Карно

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

Рис. 3.5 Карты Карно для двух, трех и четырех переменных

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

а б

Рис. 3.6 Отображение на карте Карно функции четырех переменных

(а) и ее минимального покрытия (б)

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

Считывание минитермов с карты Карно осуществляется по простому правилу. Клетки, образующие s-куб, дают минитер (n–s)-го ранга, в который входят те (n–s) переменные, которые сохраняют одинаковые значения на этом s-кубе, причем значении 1 соответствуют сами переменные, а значениям 0 – их отрицания. Переменные, которые не сохраняют свои значения на s-кубе, в минитерме отсутствуют. Различные способы считывания приводят к различным представлениям функции в дизъюнктивной нормальной форме (крайняя правая является минимальной) (рис. 3.7).

Рис. 3.7 Способы считывания с карты Карно дизъюнктивной нормальной формы булевой функции (слева направо: ; ;

Пример.Получить минимальные формы для функции

Пример.Получить минимальную форму для функции, заданной на карте.

Использование карт Карно требует более простых построений по сравнению с отображением на n-мерном кубе, особенно в случае четырех переменных. Для отображения функций пяти переменных используется две карты Карно на четыре переменные, а для функции шести переменных – четыре таких карты. При дальнейшем увеличении числа переменных карты Карно становятся практически непригодными.

Известные в литературе карты Вейча отличаются только другим порядком следования наборов значений переменных и обладают теми же свойствами, что и карты Карно.

Комплекс кубов

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

Комплекс кубов К(у) функции определяется как объединение множеств К^s(у) всех ее s-кубов (s=0.1,…,n), т. е. , причем некоторые из К^s(у) могут быть пустыми. Для записи s-кубов и минитермов функции от n переменных используются слова длины n, буквы которых соответствуют всем n переменным. Входящие в минитерм переменные называются связанными и представляются значениями, при которых минитерм равен единице (1 для и 0 для ). Не входящие в минитерм переменные являются свободными и обозначаются через . Например, 2-куб функции пяти переменных, соответствующий минитерму запишем как ( ). 0-кубы, соответствующие конституентам единицы, представляются наборами значений переменных, на которых функция равна единице. Очевидно, в записи s-куба всегда имеется s свободных переменных. Если все n переменных свободны, что соответствует n-кубу, то это означает тождественность единице рассматриваемой функции. Таким образом, для функций, не равных тождественно единице Ø.

Множество всех s-кубов записывается как совокупность слов, соответствующих каждому s-кубу. Для удобства будем располагать слова s-кубов в столбцы, а их совокупность заключать в фигурные скобки. Например, комплекс кубов, соответствующий представлению функции на трехмерном кубе (рис. 3,10а), выражается как , где

; ; .

Для сравнения на рис. 3.8 изображен комплекс кубов в принятых обозначениях.

Рис. 3.8 Комплекс кубов функции трех переменных (а) и его символическое представление (б)

Комплекс кубов образует максимальное покрытие функции. Исключая из него все те s-кубы, которые покрываются кубами высшей размерности, получаем покрытия, соответствующие тупиковым формам. Так, для рассматриваемого примера (рис. 3.8) имеем тупиковое покрытие

которое соответствует функции . В данном случае это покрытие является и минимальным.

Для двух булевых функций операция дизъюнкции соответствует объединению их комплексов кубов , а операция конъюнкции — пересечению комплексов кубов . Отрицанию функции соответствует дополнение комплекса кубов, т. е. , причем определяется всеми вершинами, на которых функция принимает значение 0. Таким образом, имеет место взаимно-однозначное соответствие (изоморфизм) между алгеброй булевых функций и булевых множеств, представляющих комплексы кубов.

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

Минимизация булевых функций

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

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

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

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

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

Рис. 3.9 Сокращенное ( ) и минимальные покрытия ( , ) функции (а – сокращенное, б, в — минимальные)

Сокращенная форма представляет собой дизъюнкцию четырех простых импликант, т. е. Экстремалями являются простые импликанты и ,которым соответствуют 1-кубы (

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:

Булевы функции

1. Булева функция $g\left(x_1,x_2,x_3\right)=\left(x_1{\overline{x}}_2x_3\vee x_2\vee x_3\right)\to \left(x_1\bigoplus x_3\right)$ задана формулой. Построить таблицу истинности.
2. Построить для функции $g\left(x_1,x_2,x_3\right)$ ДНФ, КНФ, СДНФ, СКНФ методом тождественных преобразований.
3. Найти многочлен Жегалкина для функции $g\left(x_1,x_2,x_3\right)$:
а) методом неопределенных коэффициентов;
б) методом тождественных преобразований.

Поступил ответ 2 Марта 2017 от Викиматика

2. Построить для функции $g\left(x_1,x_2,x_3\right)$ ДНФ, КНФ, СДНФ, СКНФ методом тождественных преобразований.

3. Найти многочлен Жегалкина для функции $g\left(x_1,x_2,x_3\right)$:

а) методом неопределенных коэффициентов;

б) методом тождественных преобразований.3=8$.

$\begin{array}{|c|c|}
\hline
x_1 & x_2 & x_3 & x_1{\overline{x}}_2x_3 & x_2\vee x_3 & x_1{\overline{x}}_2x_3\vee x_2\vee x_3 & x_1\bigoplus x_3 & g\left(x_1,x_2,x_3\right)=\left(x_1{\overline{x}}_2x_3\vee x_2\vee x_3\right)\to \left(x_1\bigoplus x_3\right) \\
\hline
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\
\hline
0 & 0 & 1 & 0 & 1 & 1 & 1 & 1 \\
\hline
0 & 1 & 0 & 0 & 1 & 1 & 0 & 0 \\
\hline
0 & 1 & 1 & 0 & 1 & 1 & 1 & 1 \\
\hline
1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\
\hline
1 & 0 & 1 & 1 & 1 & 1 & 0 & 0 \\
\hline
1 & 1 & 0 & 0 & 1 & 1 & 1 & 1 \\
\hline
1 & 1 & 1 & 0 & 1 & 1 & 0 & 0 \\
\hline
\end{array}$

2. Используя тождественные преобразования, приведем данную булеву функцию $g\left(x_1,x_2,x_3\right)$ к ДНФ.

$g\left(x_1,x_2,x_3\right)=\left(\underbrace{x_1{\overline{x}}_2x_3}_{поглощается\ x_3}\vee x_2\vee x_3\right)\to \left(x_1\bigoplus x_3\right)=\left(x_2\vee x_3\right)\to \left(x_1\bigoplus x_3\right)=$ «используем равносильности $x\to y=\overline{x}\vee y$, $x\bigoplus y=\overline{x}y\vee x\overline{y}$» $=\overline{x_2\vee x_3}\vee {\overline{x}}_1x_3\vee x_1{\overline{x}}_3=$ «используем закон де Моргана $\overline{x\vee y}=\overline{x}\ \overline{y}$» $={\overline{x}}_2{\overline{x}}_3\vee {\overline{x}}_1x_3\vee x_1{\overline{x}}_3$ — ДНФ.

Перейдем от ДНФ к КНФ, для этого ставим над ДНФ два отрицания и с помощью правил де Моргана (не трогая верхнее отрицание) приводим отрицание ДНФ снова к ДНФ. При этом приходится раскрывать скобки с использованием правила поглощения (или правила Блейка). Отрицание (верхнее) полученной ДНФ (снова по правилу де Моргана) сразу дает нам КНФ:

$g\left(x_1,x_2,x_3\right)={\overline{x}}_2{\overline{x}}_3\vee {\overline{x}}_1x_3\vee x_1{\overline{x}}_3=\overline{\overline{{\overline{x}}_2{\overline{x}}_3\vee {\overline{x}}_1x_3\vee x_1{\overline{x}}_3}}=\overline{\left(x_2\vee x_3\right)\left(x_1\vee {\overline{x}}_3\right)\left({\overline{x}}_1\vee x_3\right)}=$ «используем закон дистрибутивности для 1-го и 2-го множителей $\left(x\vee y\right)\left(y\vee z\right)=y\vee xz$» $=\overline{\left(x_3\vee {\overline{x}}_1x_2\right)\left(x_1\vee {\overline{x}}_3\right)}=\overline{x_1x_3\vee {\overline{x}}_1x_2{\overline{x}}_3}=\left({\overline{x}}_1\vee {\overline{x}}_3\right)\left(x_1\vee {\overline{x}}_2\vee x_3\right)$ — КНФ.

Переход от ДНФ к СДНФ. С этой целью добавляем в каждую элементарную конъюнкцию недостающие переменные вида $x_i\vee {\overline{x}}_i$, затем применяем закон дистрибутивности.

$g\left(x_1,x_2,x_3\right)={\overline{x}}_2{\overline{x}}_3\vee {\overline{x}}_1x_3\vee x_1{\overline{x}}_3={\overline{x}}_2{\overline{x}}_3\left(x_1\vee {\overline{x}}_1\right)\vee {\overline{x}}_1x_3\left(x_2\vee {\overline{x}}_2\right)\vee x_1{\overline{x}}_3\left(x_2\vee {\overline{x}}_2\right)=x_1{\overline{x}}_2{\overline{x}}_3\vee {\overline{x}}_1{\overline{x}}_2{\overline{x}}_3\vee {\overline{x}}_1x_2x_3\vee {\overline{x}}_1{\overline{x}}_2x_3\vee x_1x_2{\overline{x}}_3\vee x_1{\overline{x}}_2{\overline{x}}_3=x_1{\overline{x}}_2{\overline{x}}_3\vee {\overline{x}}_1{\overline{x}}_2{\overline{x}}_3\vee {\overline{x}}_1x_2x_3\vee {\overline{x}}_1{\overline{x}}_2x_3\vee x_1x_2{\overline{x}}_3$ — СДНФ.

Переход от КНФ к СКНФ. С этой целью добавляем в каждую элементарную дизъюнкцию недостающие переменные вида $x_i{\overline{x}}_i$, затем применяем закон дистрибутивности.

$g\left(x_1,x_2,x_3\right)=\left({\overline{x}}_1\vee {\overline{x}}_3\right)\left(x_1\vee {\overline{x}}_2\vee x_3\right)=\left({\overline{x}}_1\vee {\overline{x}}_3\vee x_2{\overline{x}}_2\right)\left(x_1\vee {\overline{x}}_2\vee x_3\right)=\left({\overline{x}}_1\vee x_2\vee {\overline{x}}_3\right)\left({\overline{x}}_1\vee {\overline{x}}_2\vee {\overline{x}}_3\right)\left(x_1\vee {\overline{x}}_2\vee x_3\right)$ — СКНФ.

3. Методом неопределенных коэффициентов найдем полином Жегалкина.

Пусть полином Жегалкина имеем вид: $P\left(x_1,\ x_2,x_3\right)=C_0\bigoplus C_3x_3\bigoplus C_2x_2\bigoplus C_{23}x_2x_3\bigoplus C_1x_1\bigoplus C_{13}x_1x_3\bigoplus C_{12}x_1x_2\bigoplus C_{123}x_1x_2x_3$. Будем подставлять наборы значений переменных $x_1,\ x_2,x_3$ и вычислять соответствующие коэффициенты.

$P\left(0,\ 0,\ 0\right)=C_0=1;$

$P\left(0,\ 0,\ 1\right)=C_0\bigoplus C_3=1\Rightarrow 1\bigoplus C_3=1\Rightarrow C_3=0;$

$P\left(0,\ 1,\ 0\right)=C_0\bigoplus C_2=0\Rightarrow 1\bigoplus C_2=0\Rightarrow C_2=1;$

$P\left(0,\ 1,\ 1\right)=C_0\bigoplus C_3\bigoplus C_2\bigoplus C_2C_3=1\Rightarrow 1\bigoplus 0\bigoplus 1\bigoplus C_{23}=1\Rightarrow 0\bigoplus C_{23}=1\Rightarrow C_{23}=1;$

$P\left(1,\ 0,\ 0\right)=C_0\bigoplus C_1=1\Rightarrow 1\bigoplus C_1=1\Rightarrow C_1=0;$

$P\left(1,\ 0,\ 1\right)=C_0\bigoplus C_3\bigoplus C_1\bigoplus C_{13}=0\Rightarrow 1\bigoplus 0\bigoplus 0\bigoplus C_{13}=0\Rightarrow 1\bigoplus C_{13}=0\Rightarrow C_{13}=1;$

$P\left(1,\ 1,\ 0\right)=C_0\bigoplus C_2\bigoplus C_1\bigoplus C_{12}=1\Rightarrow 1\bigoplus 1\bigoplus 0\bigoplus C_{12}=1\Rightarrow 0\bigoplus C_{12}=1\Rightarrow C_{12}=1;$

$P\left(1,\ 1,\ 1\right)=C_0\bigoplus C_3\bigoplus C_2\bigoplus C_{23}\bigoplus C_1\bigoplus C_{13}\bigoplus C_{12}\bigoplus C_{123}=0\Rightarrow 1\bigoplus 0\bigoplus 1\bigoplus 1\bigoplus 0\bigoplus 1\bigoplus 1\bigoplus C_{123}=0\Rightarrow 1\bigoplus C_{123}=0\Rightarrow C_{123}=1.$

Получаем полином Жегалкина:

$P\left(x_1,\ x_2,x_3\right)=1\bigoplus x_2\bigoplus x_2x_3\bigoplus x_1x_3\bigoplus x_1x_2\bigoplus x_1x_2x_3.$

Построим полином Жегалкина методом тождественных преобразований. Для этого возьмем ДНФ функции $g\left(x_1,x_2,x_3\right)={\overline{x}}_2{\overline{x}}_3\vee {\overline{x}}_1x_3\vee x_1{\overline{x}}_3$ и избавимся от дизъюнкции, используя закон де Моргана $x\vee y=\overline{xy}$, затем заменим каждое отрицание ${\overline{x}}_i$ по формуле ${\overline{x}}_i=1\bigoplus x_i$ и упростим полученную формулу.

$g\left(x_1,x_2,x_3\right)={\overline{x}}_2{\overline{x}}_3\vee {\overline{x}}_1x_3\vee x_1{\overline{x}}_3=\overline{\overline{{\overline{x}}_2{\overline{x}}_3}\cdot \overline{{\overline{x}}_1x_3}\cdot \overline{x_1{\overline{x}}_3}}=1\bigoplus \overline{{\overline{x}}_2{\overline{x}}_3}\cdot \overline{{\overline{x}}_1x_3}\cdot \overline{x_1{\overline{x}}_3}=1\bigoplus \left(1\bigoplus \left(1\bigoplus x_2\right)\left(1\bigoplus x_3\right)\right)\left(1\bigoplus x_3\left(1\bigoplus x_1\right)\right)\left(1\bigoplus x_1\left(1\bigoplus x_3\right)\right)=1\bigoplus \left(1\bigoplus 1\bigoplus x_3\bigoplus x_2\bigoplus x_2x_3\right)\left(1\bigoplus x_3\bigoplus x_1x_3\right)\left(1\bigoplus x_1\bigoplus x_1x_3\right)=1\bigoplus \left(x_3\bigoplus x_2\bigoplus x_2x_3\right)\left(1\bigoplus x_3\bigoplus x_1x_3\right)\left(1\bigoplus x_1\bigoplus x_1x_3\right)=1\bigoplus \left(x_3\bigoplus x_2\bigoplus x_2x_3\right)\left(1\bigoplus x_1\bigoplus x_1x_3\bigoplus x_3\bigoplus x_1x_3\bigoplus x_1x_3\bigoplus x_1x_3\bigoplus x_1x_3\bigoplus x_1x_3\right)=1\bigoplus \left(x_3\bigoplus x_2\bigoplus x_2x_3\right)\left(1\bigoplus x_1\bigoplus x_3\right)=1\bigoplus x_3\bigoplus x_1x_3\bigoplus x_3\bigoplus x_2\bigoplus x_1x_2\bigoplus x_2x_3\bigoplus x_2x_3\bigoplus x_1x_2x_3\bigoplus x_2x_3=1\bigoplus x_2\bigoplus x_2x_3\bigoplus x_1x_3\bigoplus x_1x_2\bigoplus x_1x_2x_3.$

Прикрепленные файлы:

Программный модуль преобразования дизъюнктивных нормальных форм булевых функций в полином Жегалкина Текст научной статьи по специальности «Компьютерные и информационные науки»

УДК 004.021

ПРОГРАММНЫЙ МОДУЛЬ ПРЕОБРАЗОВАНИЯ ДИЗЪЮНКТИВНЫХ НОРМАЛЬНЫХ ФОРМ БУЛЕВЫХ ФУНКЦИЙ В ПОЛИНОМ ЖЕГАЛКИНА А.А. Акинин, С.Л. Подвальный

В данной статье предложена программная реализация преобразования дизъюнктивных нормальных форм булевых функций в полином Жегалкина с промежуточным восстановлением дизъюнктивных форм к совершенной дизъюнктивной нормальной форме

Ключевые слова: полином Жегалкина, булева функция, дизъюнктивная нормальная форма

В [1] были разработаны и исследованы модели легкодиагностируемых логических преобразователей (ЛП) на программируемых логических матрицах (ПЛМ) с перестраиваемым элементным базисом. Основу таких ПЛМ составляет базис логических функций И (AND) и ИСКЛЮЧАЮЩЕЕ ИЛИ (EXOR) [2]. Данные элементы совместно с элементом генератор логической 1 составляют элементный базис Жегалкина. Для реализации таких ЛП требуется преобразование дизъюнктивной нормальной формы (ДНФ) булевой функции (БФ) в так называемый полином Жегалкина. Вследствие того, что полином Жегалкина может быть получен только на основе совершенной дизъюнктивной нормальной формы (СДНФ) функции, то

необходимо располагать не только автоматическими средствами преобразования СДНФ в полином Жегалкина, но и средствами автоматического преобразования произвольных ДНФ БФ в СДНФ.

В [3] предложен метод преобразования ДНФ булевых функций в полином Жегалкина. Суть этого метода заключается в следующем. Метод

реализуется в два этапа: на первом этапе

производится восстановление ДНФ БФ до СДНФ, которая реализуется в табличной форме в виде таблицы истинности (ТИ). ТИ БФ, представляется в виде 2П упорядоченного компонентного вектора, элементами которого являются значения БФ на возрастающих наборах значений аргументов функции. На втором этапе метода осуществляется вычисление коэффициентов полинома Жегалкина БФ, представленного в общем виде. По мере расчета коэффициентов полинома, формируется вектор размерности 2П, содержащий значения

присутствующих и отсутствующих членов полиномиальной нормальной формы (ПНФ) БФ. Формирование ПНФ функции осуществляется путём последовательного преобразования каждого минтерма СДНФ БФ в частные ПНФ (ЧПНФ) и на основе их последующей суперпозиции -формировании окончательной ПНФ БФ — полинома Жегалкина. Разработанные метод и алгоритм формирования ПНФ с использованием ЧПНФ

Акинин Андрей Александрович — ООО “Мобильные ответы”, соискатель, e-mail: [email protected] Подвальный Семен Леонидович — ВГТУ, д-р техн. наук, профессор, e-mail: [email protected]

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

В [4] было показано, что основной целью при программной реализации алгоритма восстановления СДНФ должно являться достижение оптимального соотношения между быстродействием процесса восстановления СДНФ по заданной сокращенной ДНФ и требуемым для решения этой задачи аппаратным ресурсам, в связи с чем был предложен алгоритм восстановления таблицы истинности БФ по произвольной ДНФ, который представлен на рис.

НАЧАЛО

1:-1, К:-количеств о конъюнкций в ДНФ; обнуление таблицы истинности ^ Е

4 ~~

S:- 1|1]; W:-i[I]Tt[I]; М- W

І___________________

G := ( S&M ) v а[1]

__________________L._________________

Е[0] := 1

ОСТАНОВ

Рис. 1. Схема алгоритма восстановления таблицы истинности БФ по произвольным ДНФ

Как видно из рис. 1, главным преимуществом предложенного алгоритма является то, что каждый минтерм СДНФ определяется не перебором всех возможных наборов значений аргументов БФ, а вычисляется на основе рекуррентного соотношения — в : = ( 8&М ) у а[1], в связи с чем,

данный алгоритм обладает приемлемой вычислительной сложностью по сравнению с известными идентичными алгоритмами при минимальных требованиях к ресурсу памяти ЭВМ.

Рассмотрим существо предложенного метода формирования ПНФ БФ путём последовательного преобразования каждого минтерма СДНФ функции в ЧПНФ на примере.

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

Таблица 1

1 Р q г f

0 0 0 0 1

1 0 0 1 1

2 0 1 0 1

3 0 1 1 0

4 1 0 0 0

5 1 0 1 0

6 1 1 0 1

7 1 1 1 0

той же функции. В остальных строках метками «1» отмечены те члены ПНФ, которые входят в частные ПНФ в соответствии с вычисленными выше ЧПНФ. где 7- = 07, если

известно, что (1 Ф р)(1 Ф д) = 1 Ф р Ф д Ф рд и р = 1 ® р ,

для V р, д, г е {0,1}.

/0 (0,0,0) = = (1Ф р)(1 Ф д)(1 Ф г) =

= 1 Ф р Ф д Ф г Ф рд Ф дг Ф рг Ф рдг = В0 /(0,0,1) = Удг = (1Ф р)(1Ф д)г =

= г Ф дг Ф рг Ф рдг = В1

/2 С0,1,0) = рдг =(1 Ф р)д(!Ф г) =

= д Ф рд Ф дг Ф рдг = В2

/з(0,1,1) = рдг = (1Ф р)дг = дг Ф рдг = В3

/4(1,0,0) = рдг = р(1 Ф д)(1Ф г) =

= р Ф рд Ф рг Ф рдг = В4

/5 (1,0,1) = рдг = р(1 Ф д)г = рг Ф рдг = В5

Леи0)=рдг=рд(1 ®г)=рд ® рдг=В6 /7 (1,1,1) = рдг = В7

Сведем полученные данные в табл. 2.

Таблица 2

ш ЧПНФ

1 г ч ЦТ Р Р г РЧ Р Ч г

рдг 1 1 1 1 1 1 1 1 В0

рдг 1 1 1 1 В!

рдг 1 1 1 1 в2

рдг 1 1 В3

рдг 1 1 1 1 в4

рдг 1 1 в5

рдг 1 1 Вб

рдг 1 в7

В табл. 2 в первом столбце перечислены все возможные минтермы функции f(p, q, г) — К1, а в первой строке указаны все возможные члены ПНФ

Кг ЧПНФ

1 000 г 001 010 ^ г 011 р 100 Р г 101 ка 110 Р 111 В,

рдг 0 0 0 1 1 1 1 1 1 1 1 Во

рдг 001 1 1 1 1 В!

рдг 0 1 0 1 1 1 1 в2

рдг 0 11 1 1 В3

рдг 1 0 0 1 1 1 1 В4

рдг 1 0 1 1 1 В5

рдг 110 1 1 Вб

рдг 1 1 1 1 В7

Е® 1 0 0 1 1 0 1 0 в

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

Анализ данных табл. 3 наглядно

демонстрирует следующую закономерность: разряды двоичных векторов BJ принимают единичные значения только в том случае, если единичные значения переменных в номерах строк полностью входят в двоичные номера столбцов таблицы. Исключение составляет только вектор В0, все элементы которого равны 1.

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

таблицы истинности логической функции, для формирования ПНФ достаточно иметь только таблицу минтермов данной функции.

Алгоритм формирования ПНФ с использованием ЧПНФ представлен на рис. 2.

напало

Задание сигаольнт имен аргументов

Е Ф и закрепление этих имен за разрядами да схемного п-разрядааго

_______________тает S________________

__________________*__________________

ВВОДЯТСЯ ИСХОДНЫ* данные п — число аргументов Е Ф, Е — вектор, содержащий шаненкя ТИБФ,где N=2n-1

Создание и обнуление двоичного me сив 4 В= {bü Jb|,. Ны

D. =К,

D, = D,+ l

________________Í________________

D| = D,vK, t

b[Df]-b[Df] _________________I

_________________1

Увеличение счетчика, i на. 1

——————I ~

\________________

По полученному мае шву В и переменной S формируется ПНФ ПОГРН е СЕСОИ функции Е СИМЕ ОЛЕГОМ

«Г

OCIABD0

Рис. 2. Алгоритм формирования ПНФ с использованием ЧПНФ

Исходными данными для предложенного алгоритма являются: п — число аргументов БФ, вектор Е размерности 2п, содержащий значения СДНФ БФ.

Основное достоинство алгоритма заключается в том, что ПНФ функции формируется путём преобразования каждого минтерма СДНФ в частные ПНФ (ЧПНФ) в виде их векторного представления так, как показано на рис. 3.

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

нормальной формы БФ заносятся в вектор В размерности 2п. Для корректной работы

программного модуля необходимо обнулить двоичные массивы В и Б.

На первом шаге рассматриваемого фрагмента алгоритма, необходимо получить векторное представление очередного минтерма СДНФ — К

Рис.,bN}, значение которого необходимо проинвертировать. Для этого

используем операции арифметического сложения Dj = Dj+1 и побитового сложения Dj = Dj v Kj. Повторяем вычисление и инвертирование

определенного номера бита вектора до тех пор, пока Dj < (2п-1). С помощью операции

инвертирования мы как бы добавляем следующий член ЧПНФ в итоговую ПНФ БФ, учитывая что x¡ ® x¡ = Ь а x¡ ® x¡ = 0 для V x¡ е {0,1} •

Далее переходим к следующему минтерму СДНФ БФ.

Таким образом, в векторе B по окончании цикла по j < m, где m — количество минтермов БФ, осуществляется поэлементное суммирование по модулю 2, с накоплением результата, сформированных по минтермам исходной СДНФ двоичных векторов частных ПНФ, в силу чего данный алгоритм является весьма экономичным по требуемой памяти и количеству операций, производимыми над символьными переменными.

Следует отметить также, что для эффективной программной реализации предложенных алгоритмов необходимо осуществить выбор наиболее рациональной формы хранения исходных и конечных данных программного модуля, которая позволяла бы не только хранить большой объем данных, но и производить над ними операции за минимально необходимый промежуток времени. В связи с чем, в качестве хранилища векторов B и E, размерности 2п, был выбран битовый массив dynamic_bitset из библиотеки BOOST C++. Эта библиотека представляет собой собрание множества кроссплатформенных библиотек, созданных

независимыми разработчиками и тщательно проверенными на различных платформах (№’№’№.Ь0081.0г§). Отличительными особенностями массива dyпamic_b1tset являются: возможность

динамического изменения размера массива в ходе выполнения программы, поддержка быстрого доступа по индексу к произвольному элементу массива, поддержка элементарных логических операций (регистрового сдвига, сложения, умножения, инверсии и т. д.). Размер массива dyпamic_bitset ограничен величиной 232-1, вследствие чего максимальное число аргументов исходной ДНФ БФ должно быть ограничено числом 31.

На основе предложенных алгоритмов, реализующих метод преобразования ДНФ булевых функций в полином Жегалкина, был разработан программный модуль “Преобразователь булевых функций”. На рис. 4 представлено главное окно программного модуля “Преобразователь булевых функций”.

Рис. 4. Главное окно программного модуля “Преобразователь булевых функций”

Программа написана на языке С++, для ее функционирования необходимо не менее 5 Гб на жестком диске и не менее 512 Мб оперативной памяти.

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

выходного файла, содержащего ПНФ функции, зависящей от 20 переменных, СДНФ которой состоит всего из двух минтермов, занимает 1,5 Мб жесткого диска. Размер самого программного модуля составляет всего 330 Кб.

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

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

Сформированные выходные данные программы могут быть получены как в символьном виде, так и в векторном. Это обстоятельство обусловлено тем, что при достаточно большом количестве аргументов функции анализировать БФ в символьном виде весьма сложно.

Литература

1. Акинина Ю.С. Альтернативный подход к обеспечению легкодиагностируемости двухуровневых программируемых пользователем логических матриц / Ю.С. Акинина, С.В. Тюрин // Вестник Воронеж. гос. техн. ун-та. Сер. Вычислительные и информационнотелекоммуникационные системы. — Воронеж: ВГТУ, 2003. Вып. 8.3. С. 32-35.

2. Закревский А.Д. Полиномиальная реализация частичных булевых функций и систем / А. Д. Закревский, Н. Р. Торопов. М.: Эдиториал УРСС, 2003. 217 с.

3. Акинина Ю.С. Разработка метода преобразования дизъюнктивных нормальных форм в полиномиальную нормальную форму / Ю.С. Акинина // Современные проблемы информатизации в системах моделирования, программирования и телекоммуникациях: сборник трудов IX международной открытой научной конференции. 2004. Вып. 9. С. 271.

4. Акинин А.А. О программной реализации алгоритма восстановления совершенной дизъюнктивной нормальной формы / А.А. Акинин, Ю.С. Акинина // Информационные технологии моделирования и управления. 2010, №6(65)

Воронежский государственный технический университет ООО “Мобильные ответы” (г. Воронеж)

THE MODULE PROGRAMM OF TRANSFORMATION OF SUM OF PRODUCTS OF BOOLEAN’S FUNCTION’S INTO ZHEGALKIN’S POLYNOMIAL A.A. Akinin, S.L. Podvalniy

This article considers the realization program of transformation of sum of products of Boolean’s functions into Zhegalkin’s polynomial with stage-by stage regeneration of sum of products till they reach complete sum of products

Key words: Zhegalkin’s polynomial, boolean function, sum of products

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

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

1. Пример нахождения СДНФ
Для того, чтобы получить СДНФ функции, требуется составить её таблицу истинности. К примеру, возьмём одну из таблиц истинности:
В ячейках результата f {\displaystyle fx_{1},x_{2},x_{3}} отмечаются лишь те комбинации, которые приводят логическое выражение в состояние единицы. Далее рассматриваются значения переменных, при которых функция равна 1. Если значение переменной равно 0, то она записывается с инверсией. Если значение переменной равно 1, то без инверсии.
Первая строка содержит 1 в указанном поле. Отмечаются значения всех трёх переменных, это:
x 2 = 0 {\displaystyle x_{2}=0}
x 1 = 0 {\displaystyle x_{1}=0}
x 3 = 0 {\displaystyle x_{3}=0}
Нулевые значения — тут все переменные представлены нулями — записываются в конечном выражении инверсией этой переменной. Первый член СДНФ рассматриваемой функции выглядит так: x 1 ¯ ⋅ x 2 ¯ ⋅ x 3 ¯ {\displaystyle {\overline {x_{1}}}\cdot {\overline {x_{2}}}\cdot {\overline {x_{3}}}}
Переменные второго члена:
x 1 = 0 {\displaystyle x_{1}=0}
x 3 = 1 {\displaystyle x_{3}=1}
x 2 = 0 {\displaystyle x_{2}=0}
x 3 {\displaystyle x_{3}} в этом случае будет представлен без инверсии: x 1 ¯ ⋅ x 2 ¯ ⋅ x 3 {\displaystyle {\overline {x_{1}}}\cdot {\overline {x_{2}}}\cdot x_{3}}
Таким образом анализируются все ячейки f {\displaystyle fx_{1},x_{2},x_{3}}. Совершенная ДНФ этой функции будет дизъюнкцией всех полученных членов элементарных конъюнкций.
Совершенная ДНФ этой функции:
f = x 1 ¯ ∧ x 2 ¯ ∧ x 3 ¯ ∨ x 1 ¯ ∧ x 2 ¯ ∧ x 3 ∨ x 1 ¯ ∧ x 2 ∧ x 3 ¯ ∨ x 1 ∧ x 2 ∧ x 3 ¯ {\displaystyle fx_{1},x_{2},x_{3}={\overline {x_{1}}}\land {\overline {x_{2}}}\land {\overline {x_{3}}}\vee {\overline {x_{1}}}\land {\overline {x_{2}}}\land x_{3}\vee {\overline {x_{1}}}\land x_{2}\land {\overline {x_{3}}}\vee x_{1}\land x_{2}\land {\overline {x_{3}}}}

Конъюнктивная нормальная форма Совершенная дизъюнктивная нормальная форма Совершенная конъюнктивная нормальная форма Конъюнктивный одночлен Дизъюнктивный одночлен
линейное время. Дизъюнктивная нормальная форма Совершенная дизъюнктивная нормальная форма Совершенная конъюнктивная нормальная форма Конъюнктивный одночлен
одночленов скобки не пишутся. Дизъюнктивная нормальная форма Конъюнктивная нормальная форма Дизъюнктивный одночлен Совершенный одночлен Булева алгебра Алгебра
прикладное значение выбранной системы функций. Основная статья: Дизъюнктивная нормальная форма Простой конъюнкцией или конъюнктом называется конъюнкция некоторого
предложено использовать для преобразования вектора значений совершенной дизъюнктивной нормальной формы в вектор коэффициентов полинома Жегалкина для произвольной
субстанциальности души, гипотетические антиномии — идею Вселенной как целого, дизъюнктивные идеал — идею Бога. Поскольку категорический императив — высшее предписание

темпоральность, мы нуждаемся в новом настоящем и желаем повторение и будущее. Дизъюнктивный синтез памяти тематика Бергсона присваивает настоящее и привычку
категорию, несмотря на то, что не имеют общего признака Взаимоисключающие дизъюнктивные категории имеют слишком примитивную логику для научного применения

Совершенная дизъюнктивная нормальная форма: днф онлайн, таблица истинности для 4 переменных, опишите совершенную дизъюнктивную нормальную форму, сднф и скнф, полином жегалкина, совершенная дизъюнктивная нормальная форма формулы, алгоритм построения сднф, алгоритм нахождения сднф

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

Математическая логика oнлайн с подробным объяснением. Активные и интерактивные формы: лекции, практические занятия, контрольные работы, Совершенная дизъюнктивная нормальная форма. Полином. Сднф и скнф. Построение таблицы истинности онлайн СКНФ СДНФ. ТЕМА: СОВЕРШЕННЫЕ НОРМАЛЬНЫЕ ФОРМЫ. ПЛАН: 1. Совершенная дизъюнктивная нормальная форма. 2. Совершенная конъюнктивная.

Днф онлайн.

7. Разложение булевой функции по переменным и совершенные. Основная статья: Дизъюнктивная нормальная форма Совершенной дизъюнктивной нормальной формой или СДНФ относительно некоторого. Алгоритм построения сднф. Совершенная дизъюнктивная нормальная форма. Это совершенная дизъюнктивная нормальная форма СДНФ нашей функции. Пример 24. Построим СДНФ для функции, таблица истинности которой. Таблица истинности для 4 переменных. СОВЕРШЕННАЯ НОРМАЛЬНАЯ ФОРМА это Что такое. Совершенная дизъюнктивная нормальная форма. Cтраница 4. При работе ППЗУ в качестве комбинационного цифрового устройства сигналы. Построение СКНФ и СДНФ по таблице истинности Автор24. Совершенной дизъюнктивной нормальной формой формулы А. СДНФ А называется дизъюнктивная нормальная форма формулы А.

Как найти скнф и сднф.

Пример 4 совершенная дизъюнктивная нормальная форма. Построим совершенную дизъюнктивную нормальную форму функции, заданной. Приложение 1 РИНХ. Совершенной дизъюнктивной нормальной формой СДНФ называется такая дизъюнктивная нормальная форма, у которой в каждую конъюнкцию входят. Совершенная дизъюнктивная нормальная форма. Совершенная. Представлений булевых функций: совершенная дизъюнктивная нормальная форма сднф, совершенная конъюнктивная нормальная форма скнф. Декану физического факультета ТГУ Томский политехнический. Совершенная конъюнктивная нормальная форма СКНФ это такая КНФ, которая удовлетворяет трём условиям: в ней нет одинаковых.

Конъюнктивной нормальной формой логической функции.

Совершенная дизъюнктивная нормальная форма представления булевых функций. Построение СДНФ по таблице истинности. Сокращенная. СДНФ. Теорема о представлении в виде СДНФ. Построение. Как с помощью python сделать СДНФ Совершенная дизъюнктивная нормальная форма? Что должно получиться на фото ниже. Урок 12. преобразование логических выражений Информатика. Формами являются: совершенная дизъюнктивная нормальная форма СДНФ и такая форма называется совершенной дизъюнктивной нормальной.

Совершенная дизъюнктивная нормальная форма ФАЛ здесь.

Что такое совершенная дизъюнктивная нормальная форма СДНФ?. 14. Что такое совершенная коньюктивная нормальная форма СКНФ?. 15. Какая. Результаты поиска по сднф Руконт. Дизъюнктивная нормальная форма называется совершенной дизъюнктивной нормальной формой СДНФ, если элементарные конъюнкции,. Способы представления переключательных функций. Учебный. Оно известно как представление функции в виде совершенной дизъюнктивной нормальной формы СДНФ. Тупиковые нормальные формы Любая. Программа в стадии разработки МАИ. Кафедра Высшая. Ни один множитель не содержит одну и ту же переменную дважды. КНФ, для которой выполняются свойства совершенства называется совершенной.

Ен.02 дискретная математика с элементами математической.

Совершенная дизъюнктивная нормальная форма одна из форм представления функции алгебры логики в виде логического выражения. Представляет собой частный случай ДНФ, удовлетворяющий следующим трём условиям: в ней нет одинаковых слагаемых в каждом слагаемом нет повторяющихся переменных. Программа вступительного испытания. А ДНФ – дизъюнктивная нормальная форма – это логическая сумма Совершенная конъюнктивная нормальная форма формулы СКНФ это. Учебник по дискретной математике днф, сднф, кнф, скнф. Конъюнктивная нормальная форма. КНФ и схема ее построения. Совершенные дизъюнктивная и конъюнктивная нормальные формы СДНФ и СКНФ. СПОСОБЫ ПРЕДСТАВЛЕНИЯ ФОРМУЛ БУЛЕВОЙ АЛГЕБРЫ. Совершенная дизъюнктивная нормальная форма СДНФ Формула называтся дизъюнктивной нормальной формой ДНФ, если она.

СКНФ и СДНФ Цифровая техника в радиосвязи.

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

Способы представления ФАЛ. Переход от одной формы.

Совершенная дизъюнктивная нормальная форма СДНФ представления переключательной функции – запись функции в виде дизъюнкции конъюнкций. Совершенная конъюнктивная нормальная форма с. КНФ это конъюнкция дизъюнктов. Совершенная конъюнктивная нормальная форма. 2.2 Совершенная нормальная форма. Теорема существования и единственности Совершенной дизъюнктивной нормальной формой по переменным.

Untitled.

Понятие дизъюнктивной и конъюнктивной нормальной формы ДНФ и. КНФ. Совершенная конъюнктивная нормальная форма и совершенная. Элементы математической логики ВятГУ. Совершенная дизъюнктивная нормальная форма, СДНФ англ. perfect disjunctive normal form, PDNF ДНФ, удовлетворяющая условиям: в ней нет. Булевы функции. Равносильных друг другу дизъюнктивных форм. Например: преобразованиями к совершенной конъюнктивной нормальной форме. СКНФ. Для этого.

ДНФ Викиконспекты.

8 Совершенной дизъюнктивной нормальной формой СДНФ называется такая дизъюнктивная нормальная форма, у которой в каждую конъюнкцию. Специальные представления недоопределенных частичных. Совершенная дизъюнктивная нормальная форма ФАЛ. Рассмотрим понятие конституенты единицы. Допустим, что функция двух переменных f x2, x1. Совершенная конъюнктивная нормальная форма Студопедия. Совершенная конъюнктивная нормальная форма. Пусть задана булева функция f x1, …, xn. Представим ее инверсию f x1. 99 % загружено Шаблон алгебраических формул tip mc. Совершенная дизъюнктивная нормальная форма, совершенная конъюнктивная нормальная форма и совершенная полиномиальная нормальная.

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

Например, выражение является ДНФ. Совершенной дизъюнктивной нормальной формой СДНФ называется такая дизъюнктивная нормальная форма. Министерство образования и науки Российской Федерации. Дизъюнктивная и конъюнктивная нормальная форма, совершенная дизъюнктивная нормальная форма СДНФ, совершенная конъюнктивная. Глава 1. Материала, вы узнаете о конъюнктивной и дизъюнктивной. нормальных формах. Также вы должны усвоить понятие. совершенной нормальной формы.

Микроконтроллеры PIC16F87X Реализуемые.

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

совершенная дизъюнктивная нормальная форма формулы, опишите совершенную дизъюнктивную нормальную форму, Совершенная дизъюнктивная нормальная форма, таблица истинности для 4 переменных

Дата публикации:

05-16-2020

Дата последнего обновления:

05-16-2020

Логика

— Расчет CNF и DNF без таблиц истинности

Обновление: (использовать логическую эквивалентность)

$$ p⊕q \ Equiv (p \ land \ neg q) \ lor (\ neg p \ land q) \ Equ (p \ lor q) \ land (\ neg p \ lor \ neg q) \ tag * { он же Xor} $$
$$ p ↓ q \ Equiv \ neg p \ land \ neg q \ tag * {aka Nor} $$
$$ p ↑ q \ Equiv \ neg p \ lor \ neg q \ tag * {aka Nand} $$

\ begin {align} \ varphi_6 & \ Equiv ((a ↑ b) ⊕ (a ↓ c)) \\ & \ Equiv (\ neg a \ lor \ neg b) ⊕ (\ neg a \ land \ neg c) \\ & \ Equiv ((\ neg a \ lor \ neg b) \ lor (\ neg a \ land \ neg c)) \ land (\ neg (\ neg a \ lor \ neg b) \ lor \ neg (\ neg a \ земля \ нег в)) \\ & \ Equiv (((\ neg b \ lor \ neg a) \ lor \ neg a) \ land ((\ neg a \ lor \ neg b) \ lor \ neg c) \ land (\ neg (\ neg a \ lor \ neg b) \ lor \ neg (\ neg a \ land \ neg c)) \\ & \ Equiv ((\ neg b \ lor (\ neg a \ lor \ neg a)) \ land ((\ neg a \ lor \ neg b) \ lor \ neg c) \ land (\ neg (\ neg a \ lor \ neg b) \ lor \ neg (\ neg a \ land \ neg c)) \\ & \ Equiv ((\ neg b \ lor \ neg a) \ land ((\ neg a \ lor \ neg b) \ lor \ neg c)) \ land (\ neg (\ neg a \ lor \ neg b) \ лор \ нег (\ нег а \ земля \ нег с)) \\ & \ Equiv ((\ neg a \ lor \ neg b) \ land ((\ neg a \ lor \ neg b) \ lor \ neg c)) \ land (\ neg (\ neg a \ lor \ neg b) \ лор \ нег (\ нег а \ земля \ нег с)) \\ & \ Equiv (\ neg a \ lor \ neg b) \ land (\ neg (\ neg a \ lor \ neg b) \ lor \ neg (\ neg a \ land \ neg c)) \\ & \ Equiv (\ neg a \ lor \ neg b) \ land ((a \ land b) \ lor (a \ lor c)) \\ & \ Equiv ((\ neg a \ lor \ neg b) \ land (a \ land b)) \ lor ((\ neg a \ lor \ neg b) \ land (a \ lor c)) \\ & \ Equiv (\ neg (a \ land b) \ land (a \ land b)) \ lor ((\ neg a \ lor \ neg b) \ land (a \ lor c)) \\ & \ Equiv \ bot \ lor ((\ neg a \ lor \ neg b) \ land (a \ lor c)) \\ & \ Equiv (\ neg a \ lor \ neg b) \ land (a \ lor c) \ tag * {CNF} \\ & \ Equiv (\ neg a \ land (a \ lor c)) \ lor (\ neg b \ land (a \ lor c)) \\ & \ Equiv ((\ neg a \ land a) \ lor (\ neg a \ land c))) \ lor ((\ neg b \ land a) \ lor (\ neg b \ land c))) \\ & \ Equiv (\ bot \ lor (\ neg a \ land c))) \ lor ((\ neg b \ land a) \ lor (\ neg b \ land c))) \\ & \ Equiv (\ neg a \ land c) \ lor ((\ neg b \ land a) \ lor (\ neg b \ land c))) \\ \ end {align}

И поскольку $ (\ neg a \ land c) \ lor (\ neg b \ land a) $ влечет $ (\ neg b \ land c) $, мы можем доказать, что его форма DNF — $ (\ neg a \ land c) \ lor (\ neg b \ land a) $.

Подсказки на 1-3 $: \ begin {align} \ varphi_1 & \ Equiv (\ neg a \ land b) \ to c \\ & \ Equiv a \ lor \ neg b \ lor c \ tag * {CNF & DNF} \\ \ varphi_2 & \ Equiv \ neg ((\ neg c \ lor¬a) ∧ (b \ lor¬c)) \ lor (a∨b∨c) \\ & \ Equiv (c \ land a) \ lor (\ neg b \ land c) \ lor (a \ lor b \ lor c) \\ & \ Equiv a \ lor b \ lor c \ tag * {CNF & DNF} \\ \ varphi_3 & \ Equiv (a∨¬b) ↔ (a∧c) \\ & \ Equiv (a∨¬b) \ to (a∧c) \ land (a \ land c) \ to (a \ lor \ neg b) \\ & \ Equiv ((\ neg a \ land b) \ lor (a \ land c)) \ land ((\ neg a \ lor \ neg c) \ lor (a \ lor \ neg b)) \\ & \ Equiv ((\ neg a \ land b) \ lor (a \ land c)) \ land \ top \\ & \ Equiv (\ neg a \ land b) \ lor (a \ land c) \ tag * {DNF} \\ & \ Equiv ((\ neg a \ land b) \ lor a) \ land ((\ neg a \ land b) \ lor c) \\ & \ Equiv (\ neg a \ lor a) \ land (a \ lor b) \ land (\ neg a \ lor c) \ land (b \ lor c) \\ & \ Equiv \ top \ land (a \ lor b) \ land (\ neg a \ lor c) \ land (b \ lor c) \\ & \ Equiv (a \ lor b) \ land (\ neg a \ lor c) \ land (b \ lor c) \\ \ end {align}

И поскольку $ (a \ lor b) \ land (\ neg a \ lor c) \ Equiv (\ neg a \ to b) \ land (a \ to c) $, что будет означать $ (b \ lor c) $ , что сделает его истинным в утверждении, поэтому мы можем доказать, что его CNF — это $ (a \ lor b) \ land (\ neg a \ lor c) $.

(я предлагаю для относительно подробных ответов задавать один вопрос за раз.)

дискретной математики — Найдите минимальные DNF и CNF логического выражения $ (A \ implies C) \ wedge \ neg (B \ wedge C \ wedge D). $

Я хочу найти минимальные CNF и DNF для следующего выражения: $$ (A \ подразумевает C) \ wedge \ neg (B \ wedge C \ wedge D). $$ Я создал таблицу истинности:

\ begin {array} {| c | c | c | c | c | c | c |} \ hline A & B & C & D & \ underbrace {A \ подразумевает B} _ {E} & \ underbrace {\ neg (B \ wedge C \ wedge D)} _ {F} & \ underbrace {E \ wedge F} _ {G} \\ \ hline 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ \ hline 1 & 0 & 0 & 0 & 0 & 1 & 0 \\ \ hline 0 & 1 & 0 & 0 & 1 & 1 & 1 \\ \ hline 1 & 1 & 0 & 0 & 0 & 1 & 0 \\ \ hline 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ \ hline 1 & 0 & 1 & 0 & 1 & 1 & 1 \\ \ hline 0 & 1 & 1 & 0 & 1 & 1 & 1 \\ \ hline 1 & 1 & 1 & 0 & 1 & 1 & 1 \\ \ hline 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ \ hline 1 & 0 & 0 & 1 & 0 & 1 & 0 \\ \ hline 0 & 1 & 0 & 1 & 1 & 1 & 1 \\ \ hline 1 & 1 & 0 & 1 & 0 & 1 & 0 \\ \ hline 0 & 0 & 1 & 1 & 1 & 1 & 1 \\ \ hline 1 & 0 & 1 & 1 & 1 & 1 & 1 \\ \ hline 0 & 1 & 1 & 1 & 1 & 0 & 0 \\ \ hline 1 & 1 & 1 & 1 & 1 & 0 & 0 \\ \ hline \ end {array}

DNF: $ G = (\ нег А \ клин \ нег В \ клин \ нег С \ клин \ нег D) \ vee (\ neg A \ клин B \ клин \ neg C \ клин \ neg D) \ vee (\ neg A \ клин \ neg B \ клин C \ клин \ neg D) \ vee (\ neg A \ клин B \ клин \ neg C \ клин D) \ vee (\ neg A \ клин B \ клин C \ клин \ neg D) \ vee (A \ клин B \ клин C \ клин \ neg D) \ vee (A \ клин \ neg B \ клин \ neg C \ клин D) \ vee (\ neg A \ клин B \ клин \ neg C \ клин D) \ vee (\ neg A \ клин \ neg B \ клин C \ клин \ neg D) \ vee (A \ клин B \ клин C \ клин D) $

Чтобы сократить это, я упрощу выражение, удалив повторяющиеся выражения:

$ G = (\ нег А \ клин \ нег В \ клин \ нег С \ клин \ нег D) \ vee (\ neg A \ клин B \ клин \ neg C \ клин \ neg D) \ vee (\ neg A \ клин \ neg B \ клин C \ клин \ neg D) \ vee (\ neg A \ клин B \ клин \ neg C \ клин D) \ vee (\ neg A \ клин B \ клин C \ клин \ neg D) \ vee (A \ клин B \ клин C \ клин \ neg D) \ vee (A \ клин \ neg B \ клин \ neg C \ клин D) \ vee (A \ клин B \ клин C \ клин D) $
$ \ vdots $
минимальный DNF: $ \ dots $
Та же процедура для CNF

CNF:
$ G_2 = (\ neg A \ vee B \ vee C \ vee D) \ клин (\ neg A \ vee \ neg B \ vee C \ vee D) \ клин \ точки \ клин (\ neg A \ vee \ neg B \ vee \ neg C \ vee \ neg D) $
$ \ vdots $

Как мне легче найти минимальные CNF и CNF? Я мог бы упростить эти выражения, как показано выше, но это действительно отнимает много времени.Есть ли способ сделать это более эффективным? Если да, то не могли бы вы подробно объяснить, как вы решили задачу?

дискретная математика — пример дизъюнктивной нормальной формы (ОБЕ dnf и cnf) справка

Для DNF :

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

Тус, формула:

$ (\ lnot z) \ lor y
$

находится в DNF , потому что это дизъюнкция двух «вырожденных» конъюнкций: $ \ lnot z $ и $ y $.

Для CNF у нас есть это:

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

Таким образом:

$ ((\ lnot z) \ lor y) \ земля T $

находится в CNF , потому что у нас есть дизъюнкция двух литералов: $ \ lnot z $ и $ y $, которые образуют предложение: $ (\ lnot z) \ lor y $; затем второе предложение: $ T $ («вырожденная» дизъюнкция) и две дизъюнкции объединяются в: $ ((\ lnot z) \ lor y) \ land T $.

По формуле:

$ T \ land [T \ lor (\ lnot x \ land y) \ lor (x \ land y)]
$

у нас есть три конъюнкции : $ (\ lnot x \ land y) $ и $ (x \ land y) $ и «вырожденный»: $ T $, и они разделены на:

$ T \ lor (\ lnot x \ land y) \ lor (x \ land y) $;

эта формула находится в DNF ; но добавив часть: $ T \ land \ ldots $, полученная формула будет не более DNF .

По формуле:

$ T \ land [T \ lor (\ lnot x \ land y) \ lor (x \ land y)]
$

, мы можем применить дистрибутивность к его подформуле:

$$ [(\ lnot x \ land y) \ lor (x \ land y)] \ Equiv [y \ land (x \ lor \ lnot x)] \ Equiv (y \ land T) \ Equiv y $$

, чтобы получить эквивалент:

$ [Т \ земля (Т \ лор у)] \ экв (Т \ земля Т) \ эквив Т $

, который является CNF и DNF, эквивалентными исходной формуле.

2.4: дизъюнктивная нормальная форма (DNF)

дизъюнктивная нормальная форма (DNF) — это стандартный способ написания логических функций. Его можно описать как сумму произведений, ИЛИ и ANDS ³. Чтобы понять DNF, сначала будет рассмотрена концепция minterm .

Минтерм — это строка в таблице истинности, в которой функция вывода для этого термина истинна. Например, в таблице 2.3.3 функция f1 (A, B, C) имеет минтерм, когда A = 1, B = 0 и C = 0. Мы можем записать этот minterm a AB’C ‘(A и не-B и не-C), поскольку A истинно, а B и C оба ложны.Функция f1 (A, B, C) также имеет три других термина: AB’C, ABC ‘и ABC. Таким образом, DNF для функции f1 (A, B, C) будет записан как:

f1 (A, B, C) = AB’C ‘+ AB’C + ABC’ + ABC

Обратите внимание, что эти минтермы — это числа 4, 5, 6 и 7 ⁴ в таблице, поэтому краткое обозначение DNF выглядит следующим образом:

f1 (A, B, C) = Σ (4,5,6,7)

Аналогично f2 (A, B, C) может быть записано как:

f2 (A, B, C) = A’B’C + A’BC + AB’C + ABC = Σ (1, 3, 5, 7)

Обратите внимание, что любая логическая функция может быть записана в DNF, а DNF требует только 3 типа операций: AND, OR и NOT.Вот почему AND, OR и NOT универсальны. Доказательство этого оставлено упражнениями в конце главы.

\ (\ PageIndex {1} \) Логические отношения

Следующий вопрос, который необходимо задать: можно ли написать какую-либо логическую функцию в DNF, следует ли использовать DNF для представления всех булевых функций? Ответ на этот вопрос дает инженерная схема. В какой-то момент компьютер должен реализовать логическую функцию в виде схемы. Этой схеме потребуется 1 вентиль для каждой операции.А при разработке схемы цель состоит в том, чтобы минимизировать количество необходимых вентилей.

Почему нужно минимизировать количество ворот? Когда гейт фактически включен в схему, это имеет 3 плохих эффекта:

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

Таким образом, цель любой схемы — ограничить количество вентилей в схеме. Для функции f1 (A, B, C) в таблице 2.3.3 количество элементов И равно 8, или элементов 3, а не элементов 4, или всего 15 элементов.Вопрос в том, можно ли реализовать схему менее чем на 15 вентилях.

Булева алгебра — это механизм, который используется для ответа на этот вопрос. Булева алгебра похожа на традиционную алгебру тем, что существует набор отношений, которые можно применить к функции для ее преобразования. И эти операции, как правило, в некоторой степени аналогичны операциям в традиционной алгебре, что несколько упрощает переход к булевой алгебре. Список этих отношений приведен в таблице \ (\ PageIndex {1} \).

Таблица \ (\ PageIndex {1} \)
Отношения	Правило №	Отношения	Правило №
х + 0 = х	1	х * 0 = 0	2
х + 1 = 1	3	х * 1 = х	4
х + х = х	5	х * х = х	6
x + x ’= 1	7	x * x ’= 0	8
х + у = у + х	9	xy = yx	10
х + (у + г) = (х + у) + г	11	х (yz) = (ху) z	12
x (y + z) = xy + yz	13	х + уz = (х + у) (х + г)	14
(x + y) ’= x’y’	15	(xy) ’= x’ + y ’	16
(x ’)’ = x	17

Все эти отношения, кроме 15 и 16, можно легко вывести.Отношения 15 и 16 известны как законы ДеМоргана, и их следует просто запомнить.

Применяя эти соотношения для f1 (A, B, C), мы находим следующее:

ф1 (А, В, С)

= AB’C ‘+ AB’C + ABC’ + ABC

= AB ‘(C’ + C) + AB (C ‘+ C) (правило 13)

= AB ‘(1) + AB (1) (правило 7)

= AB ‘+ AB (правило 4)

= A (B ‘+ B) (правило 13)

= A (1) (правило 7)

= A (правило 4)

Это выражение, очевидно, проще исходного, и количество вентилей, необходимых для этой схемы, было уменьшено с 15 до 0.Это сокращение, очевидно, стоило затраченных усилий.

Но как мы узнали, что нужно продолжать сокращать это выражение после «AB ‘+ AB»? Это само по себе было значительным сокращением, с 15 до 4 ворот. Поскольку теперь мы показали, что DNF не обязательно (и часто не дает) приводит к минимальному выражению, как мы можем узнать, было ли достигнуто минимальное выражение? Это тема следующего раздела этой главы.

³ Другой способ представления функции — это конъюнктивная нормальная форма (CNF).CNF можно описать как произведение сумм, операций И или ИЛИ. Использование CNF оставлено на усмотрение задач в конце главы.
⁴ Обратите внимание, что число начинается с 0, а не с 1.

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

3 Логика первого порядка

В отличие от случаев логики высказываний и элементарной геометрии, нет общей процедуры принятия решения для логики первого порядка. С другой стороны, учитывая соответствующие аксиомы в качестве предпосылок, все математические рассуждения могут быть выражены в логике первого порядка, и именно поэтому так много внимания было уделено процедурам доказательства для этой области.Исследования Сколема и Хербранда в 1920-х и начале 1930-х предоставили основные инструменты, необходимые для программ доказательства теорем для логики первого порядка [Davis 1983 c ].

В 1957 году пятинедельный Летний институт символической логики, который проводился в Корнельском университете, посетил почти каждый логик, работавший в Соединенных Штатах. Присутствовали также многие наиболее склонные к теории исследователи из близлежащих предприятий IBM; FORTRAN — принципиально новое новшество в практике программирования.После обсуждения с Гелернтером логик Абрахам Робинсон выступил с коротким докладом [Robinson 1957], в котором он указал на функции Сколема и «теорему Хербранда» как на полезные инструменты для средств доказательства теорем общего назначения. Он также сделал провокационное замечание о том, что вспомогательные точки, линии или окружности, «построенные» как часть решения геометрической задачи, можно рассматривать как элементы того, что сейчас называется вселенной Хербранда для этой проблемы.

Первые средства доказательства теорем для логики первого порядка, которые будут реализованы на основе теоремы Хербранда, использовали полностью неуправляемый поиск вселенной Хербранда.Вместо использования функций Сколема для работы с экземплярами переменные были заменены параметрами; поэтому программа должна была обеспечивать возможность отслеживания зависимостей между этими параметрами. Тесты на функциональную выполнимость истинности использовали либо простые вычисления таблицы истинности, либо расширение в дизъюнктивную нормальную форму. Неудивительно, что эти программы были способны доказывать только простейшие теоремы. Среди первых из этих программ программа Гилмора [1960] послужила особенно полезным стимулом для дальнейших исследований.

В своем более позднем комментарии Prawitz [1983 a ] объяснил, что разработка новых процедур доказательства и доказательств полноты для логики первого порядка вместе с доступностью вычислительных ресурсов побудили его принять участие в реализации такой процедуры. Он принял модифицированную форму метода семантических таблиц и сформулировал свой собственный высокоуровневый алгоритмический язык, на котором можно было бы написать процедуру. Подробная реализация была выполнена Prawitz, Prawitz и Voghera [1960].Несмотря на то, что она основана на современной логической системе, эта программа страдает теми же ограничениями, что и программа Гилмора.

Мартин Дэвис и Хилари Патнэм отметили, что программа Гилмора не удалась на некоторых довольно простых примерах из-за того, что она полагалась на расширения в дизъюнктивную нормальную форму для проверки выполнимости. Это привело их к оптимистическому (и в ретроспективе довольно наивному) выводу о том, что отсутствие эффективных методов проверки выполнимости больших формул исчисления высказываний является основным препятствием, которое необходимо преодолеть.Хотя их интерес к алгоритмам для решения проблемы выполнимости был вызван только тем, что они хотели использовать такие методы как часть процедуры проверки логики первого порядка, они заручились поддержкой Агентства национальной безопасности, чтобы потратить Летом 1958 года работал над этой проблемой. В своем неопубликованном отчете для NSA [Davis and Putnam 1958] они подчеркнули использование конъюнктивной нормальной формы для проверки выполнимости. В этом отчете представлены конкретные методы восстановления, совместное использование которых связано с именами Дэвиса-Патнэма.Это:

1.: Одно буквальное правило , также известное как правило единицы .
2.: Утвердительно-отрицательное правило , также известное как чистое буквальное правило .
3.: Правило для исключения атомарных формул
4.: Правило разделения , называемое в отчете, правило анализа случаев

The Davis-Putnam обычно цитируемая статья [Davis and Putnam 1960] была написана годом позже.Предлагаемая процедура будет принимать в качестве входных данных формулу, которая была предварительно обработана с использованием сначала функций Сколема для исключения экзистенциальных кванторов, а затем преобразования формулы в конъюнктивную нормальную форму. Многие программы доказательства теорем (в том числе очень успешные) использовали этот подход. Тестирование выполнимости должно было проводиться с использованием правил 1, 2, 3, приведенных выше, и было отмечено, что пример, ставящий программу Гилмора в тупик, можно легко выполнить с помощью ручных вычислений. Когда Джордж Логеманн и Дональд Ловленд попытались реализовать программу, они обнаружили, что правило для исключения атомных формул (позже названное наземным разрешением ), которое заменило формулу

(p∨A) ∧ (¬p∨B) ∧C

на

(A∨B) ∧C

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

A∧CB∧C

Идея заключалась в том, что стек для проверяемых формул может храниться во внешнем хранилище (фактически, на ленточном накопителе). ), чтобы формулы в ОЗУ никогда не становились слишком большими. ² Хотя проверка выполнимости была проведена очень эффективно, вскоре стало ясно, что очень интересные результаты не могут быть получены без предварительной разработки метода предотвращения генерации ложных элементов вселенной Хербранда [Davis, Logemann and Loveland 1962].

В те же годы Хао Ван пытался применить некоторые из более сложных работ, которые были проделаны в теории доказательств и над разрешимыми случаями Entscheidungsproblem Гильберта, к программам автоматического вывода. Он объявил о компьютерной программе, которая доказала все (около 400) теорем Principia Mathematica Уайтхеда и Рассела о логике первого порядка с равенством [Wang and Zhi 1998, Wang and Zhi 1998]. Однако это, по-видимому, важное достижение в автоматизации дедукции было (как указывал сам Ван) возможным только потому, что все эти теоремы могут быть приведены к предваренной форме с помощью простого префикса… ∀∃… ∃.Ван пришел к выводу, что:

Самый интересный урок из этих результатов, возможно, состоит в том, что даже в довольно богатой области фактически доказанные теоремы в большинстве своем используют очень небольшую часть доступных ресурсов области. ([Wang 1963 c ] стр. 32)

Влиятельная статья Правитца [1960] научила растущее сообщество автоматизированных дедукций, что ненужных терминов в расширении Гербранда можно избежать, используя алгоритмы, которые не генерируют элементы вселенной Гербранда до тех пор, пока нужный.Наиболее поздний прогресс был основан на этом ключевом открытии. Процедура Правица работала путем получения разложений в дизъюнктивную нормальную форму перед заменой переменных элементами вселенной Хербранда. Таким образом, алгоритм генерировал дизъюнктивные нормальные формы увеличивающейся длины, ищущие одну, обладающую тем свойством, что некоторая подстановка из вселенной Эрбранда дала бы истинно функционально невыполнимую формулу. ³ Поскольку это условие сводится к каждому дизъюнктивному предложению, включающему пару литералов вида ℓ, ¬ℓ, его можно сформулировать как потребность удовлетворить системе уравнений в параметрах разложения.⁴

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

В своей обзорной статье Дэвис [1963] предложил

… новый вид процедуры, которая стремится объединить достоинства процедуры Правитца и процедуры Дэвиса-Патнэма.

Идея, также отмеченная Данхэмом и Норт [1962], заключалась в том, что по «чистому буквальному правилу» из процедуры Дэвиса-Патнэма (Правило 2, выше) замены могут помочь сделать конъюнктивный набор дизъюнктивных предложений невыполнимым. только если им удастся преобразовать литерал из одного из этих предложений в отрицание литерала в другом предложении.Программа доказательства теорем, основанная на этих идеях, была написана Д. Макилроем из Bell Laboratories и была улучшена и исправлена Питером Хинманом. Программа включала реализацию обычного алгоритма унификации [Chinlund, Davis, Hinman and McIlroy 1964].

Само существование этого тома совершенно ясно показывает, что автоматизированное мышление — это процветающая область с огромной литературой. Выходящая раз в два месяца публикация The Journal of Automated Reasoning полностью посвящена этой области.Если одно событие может быть обозначено как знаменующее его появление как зрелого субъекта, то это будет публикация [Robinson 1965 b ], в которой Дж. Робинсон объявил принцип разрешения. [Robinson 1965 b ] была второй статьей Робинсона в этой области, и она помогает проследить его мысль, начиная с первой [Robinson 1963]. Он начал с базовой схемы Дэвиса-Патнэма: экзистенциальные кванторы исключены в пользу функций Сколема и конъюнктивной нормальной формы. Он обратил внимание на технику Правитца по избеганию ложных элементов вселенной Хербранда и обзорную статью Дэвиса.Очевидно, набросок Дэвиса предложенной им процедуры был недостаточно ясным, и Робинсон писал: ⁵

Поэтому Дэвис [1963] предложил способ использования мощной идеи Правитца, избегая при этом катастрофического использования Правитцем нормальных форм — во многом в том же духе. Таким образом, методы Дэвиса и Патнэма [1960] избегают использования нормальных форм, из-за чего программа Гилмора [1960] оказывается неспособной даже решить [простую задачу]. Из нескольких замечаний в конце [Davis 1963] пока не ясно, как будет действовать Дэвис, и можно с большим интересом ожидать его дальнейших исследований в этом направлении.

Остальная часть статьи содержит ряд интересных компьютерных доказательств, созданных с использованием правила Дэвиса-Патнэма «одного буквального предложения», и, когда это не удается, от пользователя требуется предварительно указать элементы вселенной Herbrand, необходимые для получить доказательство. Было высказано предположение, что поиск этих элементов является «действительно« творческой »частью искусства построения доказательств».

Метод разрешения Робинсона, представленный в его очень влиятельном [1965 b ], произвел революцию в этой области.Робинсон нашел единственное правило вывода, легко выполняемое компьютером, которое было полным для логики первого порядка. Использование разрешения не требует отдельной процедуры для работы с исчислением высказываний. Начиная с обычного предварительно обработанного конъюнктивного набора дизъюнктивных предложений, техника Робинсона заключалась в поиске всех возможных «унификаций», которые позволили бы выразить набор предложений как

(ℓ∨A) ∧ (¬ℓ∨B) ∧ C

, где ℓ — литерал, которого нет в C .Это дает «резольвент»

(A∨B) ∧C

, который после «умножения» ( A ∨ B ) приводит к новому набору предложений, который неприменим в случае, если исходный набор был. Это было похоже на предложение Дэвиса [Davis 1963, Chinlund et al. 1964] в поисках объединений, порождающих дополнительные литералы. Он отличается не только тем, что не требует отдельного функционального тестирования истинности, но и тем, что не требует, как часть входных данных, указания количества экземпляров каждого предложения для участия в окончательном доказательстве.[Robinson 1965 b ] поражает своей комбинаторной простотой, а также чистой математической элегантностью изложения. К сожалению, как вскоре выяснилось, метод голого разрешения мог легко произвести многие тысячи предложений, не достигнув доказательства. Поиск доказательства с использованием разрешения становится проблемой предоставления критериев для порядка, в котором следует искать разрешения. Ранними попытками сократить пространство поиска были собственное элегантное гиперразрешение Робинсона [Robinson 1965 a ], а также стратегии предпочтения единиц [Wos, Carson and Robinson 1964] и набор поддержки [Wos, Robinson and Carson 1965].

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

логических нормальных форм

Логическое выражение — это выражение, включающее переменные, каждая из который может принимать значение true или значение false .Эти переменные объединяются с помощью логических операций, таких как и . (соединение), или (дизъюнкция), а не (отрицание). Другой способ смотреть при этом каждое логическое выражение идентифицируется логическим значением функция , которая принимает определенное количество параметров, каждый из которых может быть истинным или ложным и возвращает истинный или ложный результат. Таким образом, мы также можем укажите логическую функцию, выписав таблицу истинности , которая таблица, содержащая все возможные присвоения параметров true или false и результирующий вывод функции.

Например, вот таблица истинности для X = A и B:

true false true false

A	B	A и B
false	false	false
false	true	false
true false	истина	истина

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

Например, (((не A) и B) или (A and (not B))) находится в дизъюнктивной нормальной форме (это ИЛИ двух членов), а (((не A) или (не B)) и (A или B)) находится в конъюнктивной нормальной форме (это И двух предложений). Вы заметите что они представляют одну и ту же функцию, A xor B . ( xor — это функция « исключающее ИЛИ », которая верна, если один или другой из аргументы верны, , но не оба .)

Легко доказать, что любую логическую функцию можно записать как в DNF и CNF.Хотя это не является формальным доказательством того, что это всегда работает, я предоставлю метод формирования выражений DNF и CNF логической функции. Первый, напишите таблицу истинности для функции. Чтобы сформировать представление DNF функции, мы включим термин для каждой строки таблицы истинности в что значение функции истинно. Для каждого из этих условий включите все переменные, которые являются параметрами функции. Если задана переменная значение false в строке таблицы истинности, отрицать его в термине; иначе, оставьте это неотрицательным.Таким образом, выражение DNF генерируется напрямую. из таблицы истинности, и довольно интуитивно понятно, что это работает и что это всегда можно сделать.

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

A	b	A xor B	термины	пункты
ложные	ложные	ложные		(A или B)
9018 9018 истинные ((не A) и B)
true	false	true	(A и (не B))
true	true	false		((не A) или (не B))

На практике мы обычно связываем соединение с умножением и дизъюнкция с добавлением.В самом деле, если мы отождествляем истину с 1 и ложь с 0, то {0,1} вместе с обычными определениями сложения и умножения по Галуа поле размера 2 (например, арифметический по модулю 2), затем сложение (+) и дизъюнкция (или) действительно такие же, как умножение и соединение (и). Это соглашение делает логические выражения более лаконичны для записи. Отрицание часто пишется как черта над переменная (или более крупное подвыражение) или «/», если верхняя черта недоступна.

Таким образом, запишем: A xor B = (/ A) B + A (/ B) = (/ A + / B) (A + B)

Нормальные и основные формы — GeeksforGeeks

Нормальные и основные формы

Дизъюнктивные нормальные формы (DNF):
Формула, которая эквивалентна данной формуле и состоит из суммы элементарных произведений, называется дизъюнктивной нормальной формой данной формулы.
Пример:
(P ∧ ~ Q) ∨ (Q ∧ R) ∨ (~ P ∧ Q ∧ ~ R)
- DNF формулы не уникален.
Конъюнктивная нормальная форма (CNF):
Формула, эквивалентная данной формуле и состоящая из произведения элементарных произведений, называется конъюнктивной нормальной формой данной формулы.
Пример:
(P ~ ∨ Q) ∧ (Q ∨ R) ∧ (~ P ∨ Q ∨ ~ R)
- CNF формулы не уникален.
- Если каждая элементарная сумма в КНФ является тавтологией, то данная формула также является тавтологией.
Принцип дизъюнктивной нормальной формы (PDNF):
Эквивалентная формула, состоящая только из дизъюнктивных терминов, называется основной дизъюнктивной нормальной формой формулы.
Также известна как каноническая форма суммы произведений .
Пример:
(P ∧ ~ Q ∧ ~ R) ∨ (P ∧ ~ Q ∧ R) ∨ (~ P ∧ ~ Q ∧ ~ R)
- Минтерм состоит из союзов, в которых каждая переменная оператора или его отрицание, но не оба, появляется только один раз.
- Минтермы записываются путем включения переменной, если ее значение истинности равно Т, и отрицания, если ее значение истинности равно F.
Принцип конъюнктивной нормальной формы (PCNF):
Эквивалентная формула, состоящая из соединений maxterms только называется основной конъюнктивной нормальной формой формулы.
No related posts.

Учебник по дискретной математике ДНФ, СДНФ, КНФ, СКНФ

Тема 6 Минимизация булевых функций

Нормальные формы: ДНФ, КНФ, СДНФ, СКНФ

Булевы функции

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

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

Днф онлайн.

Как найти скнф и сднф.

Конъюнктивной нормальной формой логической функции.

Совершенная дизъюнктивная нормальная форма ФАЛ здесь.

Ен.02 дискретная математика с элементами математической.

СКНФ и СДНФ Цифровая техника в радиосвязи.

Способы представления ФАЛ. Переход от одной формы.

Untitled.

ДНФ Викиконспекты.

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

Микроконтроллеры PIC16F87X Реализуемые.

Дата публикации:

Дата последнего обновления:

— Расчет CNF и DNF без таблиц истинности

дискретной математики — Найдите минимальные DNF и CNF логического выражения $ (A \ implies C) \ wedge \ neg (B \ wedge C \ wedge D). $

дискретная математика — пример дизъюнктивной нормальной формы (ОБЕ ​​dnf и cnf) справка

2.4: дизъюнктивная нормальная форма (DNF)

\ (\ PageIndex {1} \) Логические отношения

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

3 Логика первого порядка

логических нормальных форм

Нормальные и основные формы — GeeksforGeeks

Добавить комментарий Отменить ответ

дискретная математика — пример дизъюнктивной нормальной формы (ОБЕ dnf и cnf) справка