Дискретная математика (998286), страница 16
Текст из файла (страница 16)
В этой книге переменные всегда перечисляются в лексикографическом порядке, а кортежи булевских значений — в порядке возрастания целых чисел, задаваемых кортежами как двоичными шкалами (см. алгоритм 1.1). Такой порядок далее считается устланоалеяным. 3.4.4. Алгоритм вычисления значения булевой функции Некоторые классы формул допускают более эффективную интерпретацию по сравнению с алгоритмом Еча[. Рассмотрим алгоритм вычисления значения булевой функции, заданной в виде СДНФ, для заданных значений переменных хы...,х„.
В этом алгоритме используется следующее представление данных. СДНФ задана массивом Е апау [1..)г,1..и[ оЕ 0..1, где строка 1[1,*[ содержит набор значений <гы..., а„, для которого Е(аы..., т„) = 1, ! е 1..Ь, ь < п. ОТСТУПЛЕНИЕ Быстрое вычисление значения СДНФ имеет не только теоретическое, но и большое практическое значение Например, во многих современных программах с графическим интерфейсом для составления сложных логических условий используется наглядный бланк в виде таблицы; в клетках записываются условия, причем клетки одного столбца считаются соединенными конъюнкцией, а столбцы — дизъюнкцией, то есть образуют ДНФ (или наоборот, в таком случае получается КНФ).
В частности, так устроен графический интерфейс ОВЕ (Яцегу-Ьу-Ехашр!е), применяемый для формулировки логических условий при запросе к СУБД. Алгоритм 3.3. Алгоритм вычисления СДНФ Вход: массив, представляюший СДНФ: 1: апау [1..к, 1..и[ оЕ 0..1. множество значений переменных з: аггау [1..и[ оЕ 0..1.
Выход: 0..1 — значение булевой функции. Еог ! Егош 1 Го Ь Йо Глава 3. Булевы функции 1ог У Гхош 1 го и ао 11 Лг,Я ~ х(З) ГЬеп пехс Гог 1 ( х,' = О =ь хг ' Л . Л х„" = О ) епа И епй гог гесцгп 1 ( х "' 1г...1гх„"" = 1 =в ~/< > х1' епй Гог гегш и О ( все слагаемые в дизъюнкции = О ) Лх„" 1) ЗАМЕЧАНИЕ В алгоритме использован оператор пехг, которому здесь придаегся следующая семантика: выполнение текущего цикла прерывается, а выполнение программы продоллщется со следующего шага цикла, указанного в операторе пехт. Такого рода операторы называются огиратораии структурного перехода.
Операторы структурного перехода присутствуют в некоторых реальных языках программирования (например оператор соптшце в языке С), хотя обычно имеют более ограниченную семантику по сравнению с использованным здесь оператором пехг. Этот алгоритм в худшем случае выполняет й и сравнений, а в среднем — гораздо меньше, то есть он существенно эффективнее общего алгоритма интерпретации. 3.4.5. Эквивалентные преобразования Используя уже доказанные равносильности, можно преобразовывать по правилу замены одни формулы в другие, равносильные им. Преобразование формулы в равносильную называются эквивалентным преобразованием. Пример Используя равносильности из подраздела 3.2.2, покажем, что имеет место правило склеивания/расщвплвниж х л у ч х л у = х.
Действительно: (хЛу) У(хлу) = хЛ(у1ГЕ) = хл1 = х. ЗАМЕЧАНИЕ Если равносильность из предыдущего примера применяется для уменьшения числа опе. раций, то говорят, что производится склеивание, а если наоборот, то расщепление. ТЕОРЕМА Для любых двух равносильных формул Уг и Уз существует последовательность эквивалеюпных преобразований из Уг в Уа с помощью равносильноствй, указанных в подразделе 3.2.2. Докааатвпьство Любую фоРмулу (кроме той, которая реализует 0) можно преобразовать в СДНФ с помощью равносильностей из подраздела 3.2.2 и правила расщепления из пре- дыдущего примера по следующему алгоритму. К«.
Нормальные формы Е Элиминация операций. Любая булеза функция реализуется формулой над базисом (л, ч, — ) (напрнмер, в виде СДНФ). Таким образом, любая присутствующая в формуле подформула с главной операцией, отличной от дизъюнкцни, конъюнкции и отрицания, может быть заменена на подформулу, содержащую только три базисные операции. Например, элимннация импликации выполняется с помощью равносильности х1 — » хз = . х» ц хх В результате этого шага в формуле остаются только базисные операции. 2, Протаскивание отрицаний. С помощью инволютивности отрицания и правил де Моргана операция отрицания «протаскивается» к переменным. В результате этого шага отрицания могут присутствовать в фбрмуле только непосредственно перед переменными.
3. Раскрытие скобок. По дистибутивности конъюнкции относительно дизъюнкции раскрываются все скобки, являющиеся операндами конъюнкции. В результате этого шага формула приобретает вид дизьюнктивной формы: )/(А; Л Л А.), где А» — это либо переменная, либо отрицание переменной. й Приведение подобных. С помощью идемпотентности конъюнкции удаляются повторные вхождения переменных в каждую конъюнкцию, а затем с помощью идемпотентности дизъюнкции удаляются повторные вхождения одинаковых конъюнкций в днзъюнкцию. В результате этого шага формула не содержит «лишних» переменных и «лишних» конъюнктивных слагаемых.
3. Раоцеплвнив переменных. По правилу расщепления в каждую конъюнкцию, которая содержит не все переменные, добавляются недостающие. В результате этого шага формула становится «совершенной», то есть в каждой конъюнкции содержатся все переменные. 3. Сортировка. С помощью коммутативности переменные в каждой конъюнкции, а затем конъюнкции в днзъюнкции сортируются в установленном порядке (см.
подраздел ЗА.З). В результате этого шага формула приобретает вид СДНФ. Заметим, что указанные преобразования обратимы. Таким образом, если даны ше формулы, преобразуем их в СДНФ указанным алгоритмом. Если результаты «е совпали, значит, формулы не равносильны, и эквивалентное преобразование »дной в другую невозможно. Если же результаты совпали, то, применяя обрат«ые преобразования в обратном порядке, преобразуем полученную СДНФ во вторую формулу.
Объединяя последовательность преобразований первой формулы в СДНФ и обратных преобразований СДНФ во вторую формулу, имеем «скомую последовательность преобразований. П глава 3. вулввы функции 3.5. Замкнутые классы В типичной современной цифровой вычислительной машине цифрами являются О и 1. Следовательно, команды, которые выполняет процессор, суть булевы функции. Выше показано, что любая булева функция реализуется через конъюнкцию, цизъюнкцию и отрицание. Следовательно, можно построить нужный процессор, имея в распоряжении элементы, реализующие конъюнкцию, днзыонкцию и отрицание.
Этот и следующий разделы посвящены ответу на вопрос: существуют ли (и если существуют, то какие) другие системы булевых функций, обладающих тем свойством, что с их помощью можно выразить все ~фугие функции. 3.5.1. Замыкание множества булевых функций Пусть Р = (Л,..., у ), Д Е Р„. Замыканием Р (обозначается [Р]) называется множество всех булевых функций, реализуемых формулами над Г: [Р]:=(у Е Р„[~= ЬапсУ[Щ. Свойства замыкания: 1. Рс[Г]; 2. [[ГЦ = [Р]; 3. Г, с Р, =Ф [Р,] с [Р,]; 4.
([Г]О[Рз]) с [Гу ОГг]. 3.5.2. Некоторые замкнутые классы Класс (множество) функций Р называется замкнутым, если [Р] = Р. Рассмотрим следующие классы функций: 1. Класс функций, сохраняющих О: те:=ц[у(о,...,о) =о). 2. Класс функций, сохраняющих 1: т,:=ц[у(1,...,ц = ц. 3. Класс самодвойствейных функций: Т"=(У[У=У*) 4. Класс монотонных функций: Тя . = (У [ а < 13 =ь У(а) < У(13)), где а = (ау,..., а„);,3 = (Ьы..., Ь„), ао Ь; Е Ез, а < /3: =Ч( а, < Ьь 5. Класс линейных функций: Ть: = (у [ ~ = со + с1 х1 + " + с к„), где + обозначает сложение по модулю 2, а знак конъюнкции опу|цен. ТЕОРЕМА Классы Тсн Ты Т„Т<, Ть замкнуты. З.о. Заыкнукые классы Доказательство Чтобы доказать, что некоторый класс К вЂ” замкнутый, достаточно показать, что если функция реализована в виде формулы над Р, то она принадлежит Г. Доказать, что произвольная формула обладает заданным свойством, можно с помощью индукции по структуре формулы (см.
подраздел З.З), База индукции очевидна: функции из Е реализованы как тривиальные формулы над тт. Таким образом, осталось обосновать индукционные переходы для пяти рассматриваемых классов. 1. Пусть|,Л,.:.,У„еТе иФ=Д(Яхм ..х„),...,У„(х„...,х„)). Тогда Ф(0,...,0) = 1(1г(0,...,0),...,1„(0,,,0)) = 1(0,...,О) = О. Следовательно, Ф ~ Тр: 2. Пусть У,Лы...,У„еТг и Ф = У(Яхм...,х„),...,У„(хм...,х„)). Тогда Ф(1,...,1) = У'(~~(1,...,1),...,У„(1,...,1) = У(1,...,1) =1. Следовательно, Ф е Ть 3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
