ДИСКРЕТНАЯ МАТЕМАТИКА (1). В. А. Ломазов р рязанов, Ю. Д. Дискретная математика учеб пособие. Ю. Д. Рязанов е изд, доп. Белгород Издво бгту, 2016. 298 с
 Скачать 4.33 Mb.
|
|
Импликантная матрица Квайна 1011 1001 0000 0001 1000 2 1 1 2 1 2 2 --01 (1) + + 00-- (1, 2) + + + + 0--1 (1, 2) + + -0-0 (2) + + 1--0 (2) + --1- (2) + Импликанты --1-(2), --01(1), 00--(1,2), 1--0(2) образуют минимальное покрытие столбцов матрицы Квайна. ЭТАП 3. Выделив для функции f i импликанты с признаком, включающим, получаем минимальную ДНФ системы частично определенных булевых функций f 1 = --01 00--; f 2 = --1- 00-- 1--0 или в буквенном виде ; 6 3 4 3 5 2 4 3 6 Для минимизации системы частично определенных булевых функций можно использовать модифицированный метод минимизации систем полностью определенных булевых функций. Модификация метода заключается в том, что все функции системы на неопределенных наборах доопределяются единичным значением. Для доопределенной системы находятся все ее простые импликанты. При составлении матрицы Квайна строки отмечаются полученными простыми импликантами, а столбцы — конституентами единицы системы частично определенных булевых функций, те. строками таблицы Т 1 с учетом признаков. Из им- пликант, образующих минимальное покрытие столбцов матрицы Квайна, формируются функции минимальной ДНФ системы частично определенных булевых функций. В заключении следует отметить, что нахождение минимальной ДНФ системы частично определенных булевых функций при наличии фиктивных аргументов не является решением задачи о минимальном числе аргументов, несмотря на то, что их количество может уменьшиться. Так, если для системы функций (табл. 5.13) сразу начинать поиск минимальной ДНФ, то можно получить систему ДНФ, зависящую от четырех переменных и содержащую четыре простых импликанты. 5.10. Графовые способы представления булевых функций Графовыми представлениями булевых функций являются бинарные деревья, бинарные графы и синтаксические деревья. 5.10.1. Бинарные деревья и бинарные графы Бинарное дерево булевой функции содержит начальную вершину корень, в которую не входит ни одна дуга и выходят две дуги, множество условных вершин, в которые входит одна дуга и выходят две дуги, и множество заключительных вершин (листьев, в которые входит одна дуга и ни одна не выходит. Начальная и условные вершины на диаграмме изображаются кружочками, а заключительные — прямоугольниками. В начальной ив условных вершинах записываются аргументы функции, а в заключительных — значения функции. Дуги, выходящие изначальной и условных вершин, отмечаются нулем и единицей. На рис приведен пример бинарного дерева булевой функции четырех аргументов. Бинарное дерево булевой функции может быть построено исходя из любой рассмотренной ранее формы представления булевой функции. Алгоритм построения бинарного дерева основан на многократном разложении Шеннона булевой функции по одной переменной и заключается в следующем 1) построить корень дерева и приписать к нему булеву функцию f; 2) выбрать переменную разложения x i , записать ее в корень дерева и выполнить разложение Шеннона по этой переменной ) ,..., 1 ,..., , ( ) ,..., 0 ,..., , ( ) ,..., ,..., , ( 2 1 2 1 2 1 n i n i n i x x x f x x x x f x x x x x f 277 Рис. Бинарное дерево булевой функции Если коэффициент ) ,..., 0 ,..., , ( 2 1 n x x x f представляет собой константную функцию, то ввести лист дерева, записать в нем значение ) ,..., 0 ,..., , ( 2 1 n x x x f , соединить дугой корень дерева с введенной вершиной и отметить ее нулем. Если коэффициент ) ,..., 0 ,..., , ( 2 1 n x x x f представляет собой не константную функцию, то ввести условную вершину дерева, приписать к ней функцию ) ,..., 0 ,..., , ( 2 1 n x x x f , соединить дугой корень дерева с введенной вершиной и отметить ее нулем. Если коэффициент представляет собой константную функцию, то ввести лист дерева, записать в нем значение ) ,..., 1 ,..., , ( 2 1 n x x x f , соединить дугой корень дерева с введенной вершиной и отметить его единицей, если коэффициент ) ,..., 1 ,..., , ( 2 1 n x x x f представляет собой не константную функцию, то ввести условную вершину дерева, приписать к ней функцию ) ,..., 1 ,..., , ( 2 1 n x x x f , соединить дугой корень дерева с введенной вершиной и отметить ее единицей 3) пока существуют концевые условные вершины, для каждой из них выполнить действия, аналогичные действиям, выполненным над корнем дерева. Бинарное дерево булевой функции, зависящей от n аргументов, обладает следующими свойствами — количество условных вершин лежит в пределах от n до 2 n – 1; — количество листьев лежит в пределах от n + 1 до 2 n ; — глубина дерева лежит в пределах от ]log 2 (n + 1)[ до n. Бинарный граф булевой функции отличается от бинарного дерева тем, что он содержит только две заключительные вершины ив каждую условную и заключительную вершины входят не менее одной дуги. На рис приведен пример бинарного графа булевой функции четырех аргументов. 0 1 0 1 0 1 0 1 0 1 0 1 x 1 x 2 x 4 x 3 x 3 x 4 f=1 f=0 f=1 f=1 f=0 f=0 f=0 278 Рис. Бинарный граф булевой функции Алгоритм построения бинарного графа булевой функции следующий 1) строится начальная вершина, к которой приписывается функция f; 2) выбирается переменная разложения x i и записывается в вершине, выполняется разложение Шеннона функции f попеременной, где y 0 и y 1 – коэффициенты разложения ) ,..., 0 ,..., , ( 2 1 0 n x x x f y ; ) ,..., 1 ,..., , ( 2 1 1 n x x x f y . 3) если в графе существует условная вершина, к которой приписана функция y 0 (или y 1 ), то проводится дуга в эту вершину и отмечается нулем (единицей если в графе не существует условной вершины, к которой приписана функция y 0 (или y 1 ) и функция y 0 (или y 1 ) не является константой, то вводится новая условная вершина, к этой вершине проводится дуга, отмеченная нулем (или единицей) и к ней приписывается функция (или y 1 ); если функция y 0 (или y 1 ) является константой, то проводится дуга, отмеченая нулем (или единицей) в заключительную вершину f=y 0 (f=y 1 ), если такая существует, или, в противном случае, вводится такая заключительная вершина 4) пп. 2 и 3 выполняются для всех концевых условных вершин. Процесс построения бинарного графа функции 3 2 1 3 1 x x x x x f представлен на рис. Бинарный граф булевой функции, зависящей от n аргументов, обладает следующими свойствами — бинарный граф не содержит циклов — количество условных вершин лежит в пределах от n до 2 n – 1; — имеет две заключительные вершины — глубина графа лежит в пределах от ]log 2 (n + 1)[ до n. 4 0 1 0 1 0 1 1 1 0 0 0 1 x 1 x 2 x 3 x 2 f=1 f=0 x 4 279 Рис. Процесс построения бинарного графа Бинарный граф системы булевых функций отличается от бинарного графа одной функции тем, что он может содержать более двух заключительных вершин, в которых записаны значения всех функций системы. На рис приведен пример бинарного графа системы из трех булевых функций четырех аргументов. а 3 2 1 3 1 x x x x x f б 3 2 1 3 1 x x x x x f 1 1 0 1 y x y x f 3 2 0 x x y 0 1 3 1 x y 3 2 x x 3 x x 1 x 1 в 3 2 1 3 1 x x x x x 1 2 0 2 y x y x f 0 1 3 0 x y x 3 0 1 y 3 2 x x f x 1 где Рис. Бинарный граф системы булевых функций Алгоритм построения бинарного графа системы булевых функций аналогичен алгоритму построения бинарного графа одной функции, за исключением того, что переменная разложения выбирается для всей системы и выполняется разложение Шеннона по выбранной переменной каждой функции системы, образуя две новые системы функций, включающие в себя коэффициенты разложения всех функций. К вводимым условным вершинам приписываются новые системы функций, в которых хотя бы одна функция не является константой. Система из константных функций образует заключительную вершину графа. Бинарный граф системы из k булевых функций, зависящих от n аргументов, обладает следующими свойствами — бинарный граф не содержит циклов — количество условных вершин не зависят от количества функций в системе и лежит в пределах от n до 2 n – 1; — количество заключительных вершин зависит от количества функций в системе и лежит в пределах от 2 док глубина графа не зависит от количества функций в системе иле- жит в пределах от ]log 2 (n + 1)[ до n. Булеву функцию можно представить различными бинарными графами, которые могут различаться количеством условных вершин. Количество вершин зависит от выбора переменной разложения на каждом шаге. Количество вершин в графе вероятно будет меньше, если на каждом шаге в качестве переменной разложения будем выбирать такую переменную, которая позволяет получить коэффициенты разложения с минимальным количеством букв. 0 1 0 1 1 1 0 0 0 1 x 1 x 2 x 4 x 3 x 2 f 1 =1 f 2 =0 f 3 =0 f 1 =1 f 2 =0 f 3 =1 f 1 =0 f 2 =1 f 3 =0 281 5.10.2. Синтаксические деревья Булеву функцию, заданную формулой, например, в произвольной скобочной форме, можно представить синтаксическим деревом, в листьях которого записываются аргументы функции, а в остальных вершинах операции. Не нарушая общности, будем считать, что в формулах могут использоваться операции конъюнкция, дизъюнкция и отрицание. Построить синтаксическое дерево булевой функции по формуле Е можно последующим правилам 1. Построить вершину — корень дерева, и приписать к нему формулу Е. Построенную вершину считать необработанной. 2. Пока есть необработанные вершины, выбрать вершину для обработки, к которой приписана формула Е и обработать ее следующим образом. Если Е = x, где x — аргумент функции, то записать в вершину аргумент x и считать ее листом 2. Если формулу Е можно представить в виде ЕЕ, тов вершину записать знак конъюнкции ˄ , добавить к вершине левого и правого сына, клевому сыну приписать Е , а к правому — Е : 3. Если формулу Е можно представить в виде ЕЕ, тов вершину записать знак дизъюнкции ˅ , добавить к вершине левого и правого сына, клевому сыну приписать Е , а к правому — Е : 4. Если формулу Е можно представить в виде Е , тов вершину записать знак отрицания ¬ , добавить к вершине сына и приписать к нему ЕЕ ЕЕ ЕЕ ЕЕ ˄ ЕЕ Е x => 282 Рассмотрим пример построения синтаксического дерева булевой функции, заданной формулой ) ( 3 2 3 2 1 x x x x x . Строим корень дерева и приписываем к нему исходную формулу риса. Эту формулу можно представить как конъюнкцию Е и Е , где 1 1 x E и 3 2 3 2 2 x x x x E . В вершину записываем знак конъюнкции, к вершине пристраиваем левого и правого сына, клевому сыну приписываем x 1 , а к правому — 3 2 3 рис. 5.5, б. Обрабатываем вершину, к которой приписана формула x 1 , представляющая собой аргумент функции. Записываем в вершину x 1 (рис. 5.5, в. Обрабатываем вершину, к которой приписана формула 3 2 3 Эту формулу можно представить в виде дизъюнкции Е и Е , где 3 2 1 x x E и 3 2 2 x x E . В вершину записываем знак дизъюнкции, к вершине пристраиваем левого и правого сына, клевому сыну приписываем, а к правому — 3 рис. 5.5, г. Следующие три шага построения синтаксического дерева булевой функции представлены на рис. 5.5, д — ж, и результат — на рис. 5.5, з. Синтаксическое дерево можно преобразовать в формулу последующим правилам 1) если в вершине записан аргумент x , то приписать к вершине формулу) если в вершине записана операция дизъюнкция, клевому сыну приписана формула Е , к правому — формула Е , ток вершине приписать формулу ЕЕ) если в вершине записана операция отрицание и к сыну приписана формула Е , ток вершине приписать формулу Е ; 4) если в вершине записана операция конъюнкция, клевому сыну приписана формула Е, к правому — формула Е, ток вершине приписать формулу ЕЕ, при этом формулы Е или Е заключаются в скобки, если в вершине, к которой приписана формула Е или Е записан знак дизъюнкции (операция, меньшего приоритета, чем конъюнкция) Описанные выше правила применяются, пока в дереве есть хотя бы одна вершина, к которой не приписана формула. Формула, соответствующая синтаксическому дереву, приписана к корню дерева. 283 x 3 x 3 x 2 x 2 x 3 x 2 x 2 x 3 x 2 x 3 x 2 x 3 x 2 x 3 x 2 x 3 x 2 x 3 ˅ x 2 x 3 x 2 x 3 ˅ x 2 x 3 x 1 x 1 (x 2 x 3 ˅ x 2 x 3 ) а ˄ ˅ ˄ ˅ ¬ ˄ ˄ ˅ ˄ ¬ ˄ ¬ ˄ x 1 x 1 x 1 x 2 x 3 x 2 Рис. 5.5. Процесс построения синтаксического дерева ˄ x 1 ˄ x 1 ˅ ¬ ˄ x 1 ˅ ¬ ˄ б в г е з д ж 284 5.11. Программная реализация булевых функций Под программной реализацией булевой функции будем понимать программу, вычисляющую значение заданной булевой функции на заданном наборе значений аргументов. Пусть набор значений аргументов хранится в массиве X из n элементов и элемент X[i] содержит значение аргумента x i . Значение функции должно быть получено в переменной F. Алгоритм вычисления зависит от способа представления булевой функции. Вычисление значения булевой функции по таблице истинности Если булева функция задана таблицей истинности, то ее можно сохранить в одномерном массиве T из 2 n элементов с индексами от 0 до 2 n – 1. Элемент T[i] содержит значение функции нам наборе аргументов. Для вычисления значения функции необходимо набор значений аргументов (массив X) преобразовать в номер набора. Пусть это преобразование выполняет функция Index. Тогда значение булевой функции определяется выражением F := T[Index(x)]. Для того, чтобы избежать вычисление номера набора аргументов, значения булевой функции можно сохранить в мерном массиве T, й индекс которого соответствует аргументу x i . Тогда значение булевой функции определяется выражением F := T[X[1], X[2],…,X[n]]. 5.11.2. Вычисление значения булевой функции по ДНФ Булеву функцию, заданную в ДНФ, можно закодировать последовательностью целых чисел следующим образом. Просматриваем ДНФ слева направо. Если встречаем аргумент x i без отрицания, тов последовательность дописываем число i. Если встречаем аргумент x i с отрицанием, тов последовательность дописываем число –i. Если встречаем знак дизъюнкции, тов последовательность дописываем число 0. Знак конъюнкции пропускаем. Так, например, булева функция 4 3 3 2 4 кодируется последовательностью (–1,2,4,0,–2,3,0, 3,4). Полученную последовательность можно сохранить в массиве T и использовать для вычисления значения булевой функции последующему алгоритму. Алгоритм рис вычисления значения булевой функции по ДНФ. Вход X — набор значений аргументов T — массив, содержащий ДНФ булевой функции KT — количество элементов в массиве T. Выход F — значение булевой функции. |