Новиков Ф.А. Дискретная математика для программистов (860615), страница 26
Текст из файла (страница 26)
Табличные представленияОбласть определения и область значений у булевой функции конечна, поэтому булева функция может быть представлена массивом. Самое бесхитростноепредставление прямо воспроизводит таблицу истинности. Если условиться, чтокортежи в таблице всегда идут в установленном порядке (см. 3.1.1), то для представления булевой функции f ( x i , . . . , х п ) достаточно хранить столбец значений:Fi : array [0..(2n - 1)] of 0..1134Глава 3. Булевы функцииПример В этом и последующих примерах рассматривается булева функцияд(х, у, z), заданная следующей таблицей истинности:X00001111У001100112 g{x,y,z)1011101000100110Fi{g) : array [0..7] of 0..1: =(1,1,1,0,0,0,1,0)Данное представление — пе самое эффективное.
В частности, если набор аргументов задан массивом х : array [l..n] of 0..1, то для вычисления значения функции /с помощью представления Fi необходимо сначала вычислить индекс d (то естьномер кортежа в установленном порядке), чтобы затем получить значение Fi[d].Индекс d нетрудно вычислить, например, с помощью следующего алгоритма.Алгоритм 3.2 Вычисление номера кортежа в установленном порядкеВход: кортеж х : array [l..n] of 0..1 значений переменных.Выход: номер d кортежа х при перечислении кортежей в установленномпорядке.d: = 0 { начальное значение индекса }for г from 1 to п dod: = d* 2 { сдвигаем код числа d влево на один разряд }if х[г] = 1 thend: — d + 1 { добавляем 1, если нужно }end ifend forЕсли рассматривать кортеж булевых значений как двоичную запись числа, то это число — номер кортежа в установленном порядке.
Значение числа d, заданного в позиционной двоичной системе счисления цифрамих\.. .хп, определяется следующим образом:ОБОСНОВАНИЕпd = х\2п~1 + ... + хп2° = J2 Х*2П~* = 2(2(... (2xi + х 2 ) . . . ) + x„_i) + х п .г=1Цикл в алгоритме непосредственно вычисляет последнюю формулу, которая является частным случаем схемы Горнера.•1353.6. Представление булевых функций в программахЗАМЕЧАНИЕПо схеме Горнера можно определить значение числа d по записи х\...
хп в любой позиционной системе счисления с основанием b: d = b(b(... (bx 1 + хг)...) + xn-1) + x n .Более эффективным представлением таблицы истинности является использование n-мерного массива:F 2 : array [0..1,..., 0..1] of 0..1В случае использования представления F2 значение функции f(x\,...даётся выражением F2[x 1 , . . . , х п ] .Пример,хп)за-Для функции д из предыдущего примераF2 : array [0..1,0..1,0..1] of 0..1 = (((1,1), (1,0)), ((0,0), (1,0)))Представления булевой функции п переменных в виде массива занимают памятьобъёмом 0(2 П ).3.6.2. Строковые представленияБулеву функцию можно представить с помощью реализующей её формулы. Существует множество способов представления формул, но наиболее удобной длячеловека является запись в виде цепочки символов на некотором формальномязыке.Как уже указывалось, для любой булевой функции существует бесконечно многоразличных реализующих её формул.
Однако булевы функции имеют нормальныеформы, в частности СДНФ (см. 3.4.2), и при установленном порядке переменныхСДНФ единственна.СДНФ булевой функции может быть построена по заданной таблице истинностис помощью следующего алгоритма.Алгоритм 3.3 Построение СДНФВход: вектор х : array [l..n] of string идентификаторов переменных,вектор F\ : array [0..2n - 1] of 0..1 значений функции при установленномпорядке кортежей.Выход: последовательность символов, образующих запись формулы СДНФ длязаданной функции./ : = false { признак присутствия левого операнда дизъюнкции }for г from 0 to 2 n - 1 doif Fi [г] = 1 thenif / thenyield ' V ' { добавление в формулу знака дизъюнкции }else/ : = true { это первое слагаемое в дизъюнкции }end if136Глава 3.
Булевы функциид: = false { признак присутствия левого операнда конъюнкции }for j from 1 to n doif g thenyield 'A' { добавление в формулу знака конъюнкции }elseд: = true { это первый сомножитель в конъюнкции }end ifv: =(i div 2 J _ 1 ) mod 2 { значение j-го разряда кортежа с номером г }if v = 0 thenyield{ добавление в формулу знака отрицания }end ifyield x[j] { добавление в формулу идентификатора переменной }end forend ifend forОБОСНОВАНИЕДанный алгоритм буквально воспроизводит словесную запись следующего правила: для каждой строки таблицы истинности, для которой значениефункции равно 1, построить дизъюнктивное слагаемое, включающее все переменные, причём те переменные, которые имеют значение 0 в этой строке, входятсо знаком отрицания. Остальное в этом алгоритме — мелкие программистские«хитрости», которые полезно один раз посмотреть, но не стоит обсуждать.•Пример Для функции д, используемой в примерах данного раздела, алгоритмпостроит строку->хЛЛV - I X Л -1 уAzV - I X Л У Л - I 2 V Х Л У Л ->2.Представление функции в виде формулы, выраженной как строка символов,совершенно необходимо при реализации интерфейса пользователя в системахкомпьютерной алгебры, но крайне неудобно при выполнении других манипуляций с формулами.
В следующем подразделе рассматривается представлениеСДНФ, более удобное, например, для вычисления значения функции.3.6.3. Алгоритм вычисления значения булевой функцииНекоторые классы формул допускают более эффективную интерпретацию посравнению с алгоритмом Eval. Рассмотрим алгоритм вычисления значения булевой функции, заданной в виде СДНФ, для заданных значений переменныхX I , . . . , х п . В этом алгоритме используется следующее представление данных.СДНФ задана массивом F 3 : array [I..к, l..n] of 0..1, где строка F3[i, *] содержитнабор значений cxi,... ,сгп, для которого /(сг ь .
. . ,сгп) = 1, i £ 1 ..к, к ^ 2п.ПримерДля функции дF3 : array [1..4,1..3] of 0..1 = ((0,0,0), (0,0,1), (0,1,0), (1,1,0)).1373.6. Представление булевых функций в программахОТСТУПЛЕНИЕБыстрое вычислеиие значения СДНФ имеет, помимо теоретического, большое практическое значение. Например, во многих современных программах с графическим интерфейсом для составления сложных логических условий используется наглядный бланкв виде таблицы: в клетках записываются условия, причём клетки одного столбца считаются соединёнными конъюнкцией, а столбцы — дизъюнкцией, то есть образуют ДНФ (илинаоборот, в таком случае получается КНФ). В частности, так устроен графический интерфейс QBE (Query-by-Example), применяемый для формулировки логических условийпри запросе к СУБД.Алгоритм 3.4 Алгоритм вычисления значения СДНФВход: массив, представляющий СДНФ: / : array [l..k, l..n] of 0..1;множество значений переменных х : array [l..n] of 0..1.Выход: 0..1 — значение булевой функции,for i from 1 to к dofor j from 1 to n doif f[i,j] ^x[j] thennext for г { x j ф Gj = > x° j = 0x\ai A ...
A xnan = 0 }end ifend forreturn 1 { X\ai к . . . к xnan = 1 = > V(<7i,...,am) XV A • • • A xnn =end forreturn 0 { все слагаемые в дизъюнкции равны нулю }1}Алгоритм основан на следующих (очевидно, верных) правилах.Можно прекратить вычисление конъюнкции, как только получен конъюнктивный сомножитель, равный 0 (вся конъюнкция имеет значение 0). Можно прекратить вычислеиие дизъюнкции, как только получено дизъюнктивное слагаемое,равное 1 (вся дизъюнкция имеет значение 1).•ОБОСНОВАНИЕЭтот алгоритм в худшем случае выполняет к • п сравнений, а в среднем — гораздо меньше.
Таким образом, он существенно эффективнее общего алгоритмаинтерпретации.3.6.4. Деревья решенийНаиболее эффективными с точки зрения экономии памяти и времени оказываются представления, которые не имеют прямой связи с «естественными» представлениями функции в виде графика (массива) или формулы (выражения), носпециально ориентированы па выполнение операций.Начнём с простого наблюдения. Таблицу истинности булевой функции п переменных можно представить в виде полного бинарного дерева высоты п + 1.138Глава 3. Булевы функцииЗАМЕЧАНИЕБинарные деревья, равно как и другие виды деревьев, а также способы их представленияв программах и соответствующая терминология, подробно рассматриваются в главе 9,Ярусы дерева соответствуют переменным, дуги дерева соответствуют значениямпеременных, скажем, левая дуга — 0, а правая — 1.
Листья дерева па последнем ярусе хранят значение функции па кортеже, соответствующем пути из корня в этот лист. Такое дерево называется деревом решений (или семантическимдеревом).ПримерНа рис. 3.2 слева представлено дерево решений для функции д.Дерево решений можно сократить, если заменить корень каждого поддерева, вселистья которого имеют одно и то же значение, этим значением.
Иногда такоесокращение значительно уменьшает объём дерева.Пример На рис. 3.2 справа представлено сокращённое дерево решений дляфункции д.(х)0 /@\ л11Ь)oXio /® \ l00 0Ь)0Д10 0Рис. 3.2. Дерево решений и сокращённое дерево решенийВычисление значения функции осуществляется проходом по дереву решений,как показано в алгоритме 3.5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
