Дискретная математика (998286), страница 14
Текст из файла (страница 14)
Определим отношение < на упорядоченном поле следующим образом: а < Ь: =Ь вЂ” а е Р. Доказать, что < является отношением порядка на Р. 2.6. Доказать, что в решетке из взаимного поглощения следует идемпотентность обеих операций. 2.?. Доказать, что семейство 3 с 2к является базой некоторого матроида над Е тогда и только тогда, когда 1сс Вт, Вз Е 3 е Е Вт ~ Вэ =~ Э з б Вэ 'т Вт (Вс 'т (е) 0 (с )) 6 с. ГЛАВА 3 Булевы функции Данная глава имеет двойное назначение. С одной стороны, это развернутый пример к предыдущей главе в том смысле, что здесь демонстрируются эффективность и действенность алгебраических методов. Помимо основных фактов из теории булевых функций здесь затрагиваются весьма общие понятия, такие как реализация функций формулами, нормальные формы, двойственность, полнота.
Этн понятия затруднительно описать исчерпывающим образом на выбранном элементарном уровне изложения, но знакомство с ними необходимо. Поэтому рассматриваются частные случаи указанных понятий на простейшем примере булевых функций. С другой стороны, материал этой главы служит для «накопления фактов», которые должны создать у читателя необходимый эффект «узнавания знакомого» при изучении довольно абстрактного и формального материала следующей главы, 3.1. Элементарные булавы функции Подобно тому как в классической математике знакомство с основами анализа начинают с изучения элементарных функций (зш, 1оя и т, д.), так и изложение теории булевых функций естественно начать с выделения, идентификации и изучения элементарных булевых функций (дизъюнкция, конъюнкция и т. д.).
3.1.1. Фумкции алгегбрй! лог!яки Функции г: Е~ -» Его где Ез. =(О, Ц, называются функциями алгебры логики, или булевыми функциями, по имени Дж. Буля'. Множество булевых функций от и переменных обозначим Р„, Р„: =(У ) У: Ез -» Ез).
Булеву функцию от и переменных можно задать таблиц«и истинности: гб. воо!е (1815 — гзв«) 80 Глава 3. Булввы функщли Если число переменных и, то в таблице истинности имеется 2" строк, соответствующих всем различным комбинациям значений переменных, которым можно сопоставить 2з различных столбцов, соответствующих различным функциям. Таким образом, число булевых функций от и переменных с ростом и растет весьма быстро: 3.1.2. Существенные и несущественные переменные Вулева функция У Б Р„существенно зависит от переменной хо если существует такой набор значений аы..., а; у, авен..., а„, что Дам,а; 1,0,а+о,в ) ф Г(ам...,а,. м1,а+м,а„).
В этом случае х; называют существенной переменной, в противном случае х, называют несущественной (фиктивной) переменной. Пример Пусть булевы функции ~1(хм ха) и Гз(хмхз) заданы сведующей таблицей ис- тинности: Для этих функций переменная х1 — существенная, а переменная хз несущественная. По определению булевы функции равны, если одна из другой получается введением (или удалением) несущественных переменных.
Всюду в дальнейшем булевы функции рассматриваются с точностью до несущественных переменных. Это позволяет считать, что все булевы функции (в данной системе функций) зависят зт одних н тех же переменных. 81 3.1.3. Булевы функции одной переменной 3.1.4. Булевы функции двух переменных 3.2. Формулы В атом разделе обсуждается целый ряд важных понятий, которые часто считаются самоочевидными, а потому их объяснение опускается. Такими понятиями являются, в частности, реализация функций формулами, интерпретация формул для вычисления значений функций, равносильность формул, подстановка и замена в формулах.
Между тем программная реализация работы с формулами требует учета некоторых тонкостей, связанных с данными понятиями, которые целесообразно явно указать и обсудить. Глава 3. Булавы функции 3.2.1. Реализация Функций формулами Пусть р = (Л,...,У ) — множество булевых функций. Формулой нвд лдяазы- вается выражение вида ~%=У(гм ",г ) где У Б Р и гг либо пеРеменнаЯ, либо фоРмУла над Р. Множество Р называетсЯ базисом, функция у называется главной (внеиивй) операцией (функцией), а г; называются подформулами. ЗАМЕЧАНИЕ Обычно для злементарных булевых функций используется ннфнксная форма;записи, устанавливается приоритет (, й, ч, -ь) и лишние скобки опускаются Всякой формуле У однозначно соответствует некоторая функция У.
Это соответствие задается алгоритмом интерпретации, который позволяет вычнсчмть.значение формулы при заданных значениях переменных. Алгоритм 3.1. Алгоритм интерпретации формул — рекурсивная функция Еча( Вход: формула У, множество функций базиса Р, значения переменных зп, .., з„. Выход: значение формулы У на значениях зп...,хч, или значение га11, если значение не может быть определено. 1Т У- 'кчз йеп геспгп ач ( значение переменной задано ) епй К 11 У - 'Дг„..., г )' йгеп К у й р тЬеп гесшп га11 ( функция не входит в базис ) епа 1г (ог г Б (гм..., Г ) йо у;:= Еча! (внР,хм...,з„) ( значениег-го аргумента ) епа )ог гетпгп у(ум..., у„) ( значение главной операции, примененной к значениям аргументов ) епп 1г гетега га11 ( зто не формула ) ОТСТУПЛЕНИЕ Некоторые программистские замечания по поводу процедуры Еча1.
1. При программной реализации алгоритма интерпретации формул важно учитывать. чго в общем случае результат вычисления значения формулы может быть не определен (1п)1). Это имеет место, если формула построена синтаксически неправильно или если в ней используются функции (операцни), способ вычисления которых не задан, то есть они не входят а базис. Таким образом, необходимо либо проверять правильность формулы до начала работы алгоритма интерпретации, либо предусматривать невозможность вычисления значения в самом алгоритме. З.з, Шоп тлы 2. Это не единственный возможный алгоритм вычисления значения формулы, более того, он пе самый лучший.
Для конкретных классов формул, например, для некоторых классов формул, реализующих булевы функции, известны более эффективные алгоритмы. 3. Сама идея этого алгоритма: »сначала вычисляются значения аргументов, а потом значение функции», пе является догмой. Например, можно построить такой алгоритм интерпретации, который вычисляет значения только некоторых аргументов, а потом вычисляет значение формулы, в результате чего получается новая формула, реализующая функцию, которая зависит от меньшего числа аргументов.
Такой алгоритм интерпретации называется снешапвыми еычислекшини. 4. Порядок вычисления аргументов считается неопределенным, то есть предполагается, что базисные функции пе имеют побочных згрфеииов. Если же базисные функции имеют побочные эффекты, то результат вычисления значения функции может зависеть от порядка вычисления значений аргументов. Если формула У и базис Г заданы (причем У является правильно построенной формулой над базисом Р), то процедура Еча!(У, Р, хы..., х„) является некоторой булевой функций у переменных хы..., х„. В этом случае говорят, что формула 3 реализует функцию У: ЗАМЕЧАНИЕ Для обозначения реализуемости применяют и другие приемы.
Выбранное обозначение обладает тем достоинством, что не путается с другими обозначениями в книге. Зная таблицы истинности для функций базиса, можно вычислить таблицу истинности той функции, которую реализует данная формула. Прмигер 1. Р~ . =(хг Г1 хз) '~ Цхг д хз) 'ч (хг д хз)) Таким образом, формула Гг реализует дизъюнкцию. 2. Рз . =(х, л хз) -+ хг Глава 3. Булавы функции 84 Таким образом, формула гв реализует константу 1. 3, Га:=((х1Лха) +х1)+ха Таким образом, формула гз также реализует дизъюнкцию. 3.2.2.
Равносильные формулы Одна функция может иметь множество реализаций (над данным базисом). Формулы, реализующие одну и ту же функцию, называются равносильными; 91 = 92 . "= гцпсэ1 = / вс(цпсиз = /. Отношение равносильности формул является эквивалентностью. Имеют место следующие равносильности: 1. аЧа=а„ 2. а~/6 = Ь|(а, 3. аЧ(Ь|/с) = (а 1/Ь) ~/с, '4. (а Л Ь) Ч а = а, 5. а Ч (Ь Л с) = (а Ч Ь) Л (а Ч с), 6. аМ1=1, 7. а ~/ 0 = а, 8. а=а; 9.. (а Л Ь) = а ~/ - Ь, 10. аЧ-а=1, аЛа=а; аЛЬ=ЬЛа; аЛ(ЬЛс) = (а ЛЬ) Лс; (а Ч Ь) Л а = а; аЛ(Ь~/с) = (аЛЬ) Ч (а Лс); алО =0; ал1=а; -(аЧЬ) =-аЛ-Ь; ал.
а=б. Все они могут быть проверены построением соответствующих таблиц истинно- сти. Таким образом, (Еа, '/, л, ) — булеза алгебра. 3.2.3. Подстановка и замена Если в формулу в входит переменная х, то это обстоятельство обозначается так: 9(... х... ). Соответственно, запись 9'(... 9... ) обозначает, что в формулу 9 входит подформула 9.
Вместо подформулы (в частности, вместо переменной) в формулу можно подставить другую формулу (в частности, переменную), в результате чего получится новая правильно построенная формула. Если подстановка производится вместо всех вхождений заменяемой переменной (или подформулы), то результат подстановки обозначается следующим образом: й(... х... )(90х). 85 3.2. Формулы Если же подстановка производится вместо некоторых вхождений (в том числе вместо одного), то результат подстановки обозначается следующим образом: У( "9г" )(9г/91) Пример 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
