Новиков Ф.А. Дискретная математика для программистов (860615), страница 21
Текст из файла (страница 21)
Во всех таблицах истинности в этом учебнике переменные всегда перечисляютсяв лексикографическом порядке, а кортежи булевых значений — в порядке возрастанияцелых чисел, задаваемых кортежами как двоичными шкалами (см. алгоритм 1.1), чтосовпадает с лексикографическим порядком на кортежах.
Такой порядок мы называемустановленным.Если к > 2п (что, как показывает предыдущая формула, не редкость), то таблицу истинности можно «транспонировать», выписывая наборы значений в столбцах, а значенияфункций — в строках:XI01Хп01h/ i ( 0 , . . .,0).fkЛ ( о , . . .,0). •• ,1)Л ( 1...• ,1)Именно такой способ записи таблицы истинности использовал в подразделах 3.1.3 и 3.1.4.3.1.
Элементарные булевы функции1093.1.2. Существенные и несущественные переменныеБулева функция / е Рп существенно зависит, от переменной xi, если существуеттакой набор значений a i , . . . , a j - i , a , + i , . . . , а п , что/ ( a i , . . . , a j _ i , 0, aj+i? • • • > а п,1, О-г+1, • • • J «тг)-В этом случае Хг называют существенной переменной, в противном случае Xiназывают несущественной (фиктивной) переменной.Примерности:XI0011Пусть булевы функции / i ( x i , x 2 ) и / 2 ( x i , x 2 ) заданы таблицей истинХ20101/10011/21100Для этих функций переменная х\ — существенная, а переменная х 2 — несущественная.Пусть заданы две булевы функции / i ( x i , . . .
, x n _ i ) и / 2 ( х i , . . . , x n _ i , x n ) и пустьпеременная х п — несущественная для функции / 2 , а при одинаковых значенияхостальных переменных значения функций совпадают:Vai,... ,a„_i,an (/i(ai,... ,on_i) = /2(ai,... ,an_i,an)).В таком случае говорят, что / 2 получается из / i введением несущественной переменной хп, а fi получается из / 2 удалением несущественной переменной хп.ЗАМЕЧАНИЕПроцедурно введение и удаление несущественных переменных выполняются достаточно просто. Чтобы ввести несущественную переменную, нужно продублировать каждуюстроку таблицы истинности, добавить новый столбец и заполнить этот столбец чередующимися значениями 0 и 1 (или 1 и 0, что несущественно).
Удаление несущественной переменной выполняется аналогично: нужно отсортировать таблицу истинности так, чтобыона состояла из пар строк, различающихся только в разряде несущественной переменной,после чего удалить столбец несущественной переменной и удалить каждую вторую строкутаблицы.Всюду в дальнейшем булевы функции рассматриваются с точностью до несущественных переменных. Это позволяет считать, что все булевы функции (вданной системе функций) зависят от одних и тех же переменных. Для этого вдайной системе булевых функций можно сначала удалить все несущественныепеременные, а потом добавить несущественные переменные так, чтобы уравнятьколичество переменных у всех функций.110Глава 3. Булевы функции3.1.3.
Булевы функции одной переменнойВ следующей таблице собраны все булевы функции одной переменной. Две изних, фактически, являются константами, поскольку их значения не зависят отзначения аргумента.Переменная хНазваниеОтрицание100ОбозначениеНульТождественная00НесущественныеXX 0 1—IX, х, х', ~ X 1 0Единица111X3.1.4. Булевы функции двух переменныхВ следующей таблице собраны все булевы функции двух переменных.
Из нихдве являются константами, четыре зависят от одной переменной и только десятьсущественно зависят от обеих переменных.НазваниеПеременная х0011Переменная у010100000Л000100100011010001010110ОбозначениеНульКонъюнкцияСложение по модулю 2•,+ . +2. ф,АНесущественныеСтрелка Пирса 1V 0 1 1 11 1 0 0 0Эквивалентность=Дизъюнкция1001101010111100101Ш т р и х Шеффера 2э 11 1110Единица1111Импликация—,1х, уУXXУх, уЗАМЕЧАНИЕПустоты в столбцах «Название» и «Обозначение» в предыдущей таблице означают, чтобулева функция редко используется, а потому не имеет специального названия и обозначения.12Чарльз Сандерс Пирс (1839-1914).Генри М. Шеффер (1882-1964).1113.2.
Формулы3.2. ФормулыВ этом разделе обсуждается целый ряд важных понятий, которые часто считаются самоочевидными, а потому их объяснение опускается. Такими понятиямиявляются, в частности, реализация функций формулами, интерпретация формул для вычисления значений функций, равносильность формул, подстановка изамена в формулах. Между тем программная реализация работы с формуламитребует учёта некоторых тонкостей, связанных с данными понятиями, которыецелесообразно явно указать и обсудить.3.2.1.
Реализация функций формуламиНачнём обсуждение с привычного понятия формулы. Вообще говоря, формула —это цепочка символов, имеющих заранее оговорённый смысл. Обычно формулы строятся по определённым правилам из обозначений объектов и вспомогательных символов — разделителей. Применительно к рассматриваемому случаюобъектами являются переменные и булевы функции, перечисленные в таблицах подразделов 3.1.3 и 3.1.4, а разделителями — скобки «(», «)» и запятая «,».Мы считаем, что обозначения всех объектов заранее определены и синтаксически отличимы друг от друга и от разделителей, а правила составления формулобщеизвестны.ЗАМЕЧАНИЕДля обозначения объектов используются как отдельные символы, так и группы символов,в том числе со специальным начертанием: верхние и нижние индексы, наклон шрифта и т.
п. Допущение о синтаксической различимости остаётся в силе для всех такихособенностей.Пример Операцию сложения вещественных чисел принято обозначать знаком«+», 4 - : l x R - > l , a функцию «синус» — словом «sin», которое записываетсяпрямым шрифтом и считается одним символом, sin: М —• R.ОТСТУПЛЕНИЕВ математических текстах часто используется нелинейная форма записи формул, прикоторой формула не является цепочкой символов. Примерами могут служить дроби, радикалы, суммы, интегралы. Подобные нелинейные формы записи формул привычны иудобны. Использование нелинейной записи формул не является принципиальным расширением языка формул. Можно ограничиться только линейными цепочками символов,что блестяще подтверждает система Т^Х, с помощью которой подготовлена эта книга.Пусть F = { Д , .
. . , fm} — некоторое множество булевых функций от п переменных. Формулой 7 над F называется выражение (цепочка символов) вида= / ( < ! , . . . , tn),112Глава 3. Булевы функциигде / е F nti — либо переменная, либо формула над F. Множество F называетсябазисом, функция / называется главной (внешней) операцией (функцией), a Uназываются подформулами. Если базис F ясен из контекста, то его обозначениеопускают.ЗАМЕЧАНИЕОбычно при записи формул, составленных из элементарных булевых функций, обозначения бинарных булевых функций записываются как знаки операций в инфиксной форме,отрицание записывается как знак унарной операции в префиксной форме, тождественные функции записываются как константы 0 и 1.
Кроме того, устанавливается приоритетопераций (->, &, V, —•) и лишние скобки опускаются.Всякой формуле 7 однозначно соответствует некоторая функция / . Это соответствие задается алгоритмом интерпретации, который позволяет вычислитьзначение формулы J при заданных значениях переменных.Алгоритм 3.1 Интерпретация формул — рекурсивная функция EvalВход: формуламножество F функций базиса,значения переменных х\,...,хп.Выход: значение формулы 7 на значениях xi,...,xnили значение fail, еслизначение формулы не может быть определено,if J = 'х^ thenreturn xi { значение переменной задано }end ifif J = ' f{t\,...,tn)' thenif / g F thenreturn fail { функция не входит в базис }end iffor t e {ti,..., tn} doUi: = Eval (U, F, x\,..., xn) { значение г-го аргумента }if yi = fail then return fail end ifend forreturn f(yi,...
,yn) { вычисленное значение главной операции }end ifreturn fail { это не формула }ОТСТУПЛЕНИЕНекоторые программистские замечания по поводу процедуры Eval.1. При программной реализации алгоритма интерпретации формул важно учитывать, чтов общем случае результат вычисления значения формулы может быть не определён(fail). Это имеет место, если формула построена синтаксически неправильно или если в пей используются функции (операции), способ вычисления которых не задан,то есть они пе входят в базис. Таким образом, необходимо либо проверять правильность формулы до начала работы алгоритма интерпретации, либо предусматриватьневозможность вычисления значения в самом алгоритме.1133.2.
Формулы2. Это не единственный возможный алгоритм вычисления значения формулы, более того,он не самый лучший. Для конкретных классов формул, например, для некоторых классов формул, реализующих булевы функции, известны более эффективные алгоритмы(например, алгоритм 3.4).3. Сама идея этого алгоритма: «сначала вычисляются значения аргументов, а потом значение функции»,— не является догмой. Например, можно построить такой алгоритминтерпретации, который вычисляет значения только некоторых аргументов, а потомвычисляет значение формулы, в результате чего получается новая формула, реализующая функцию, которая зависит от меньшего числа аргументов. Такой алгоритминтерпретации называется смешанными вычислениями.А. Порядок вычислеиия аргументов считается неопределённым, то есть предполагается,что базисные функции не имеют побочных эффектов.
Если же базисные функции имеют побочные эффекты, то результат вычисления значения функции может зависеть отпорядка вычисления значений аргументов. Побочные эффекты могут иметь различныепричины. Наиболее частая: использование глобальных переменных. Например, еслиf(x) = f а: — а + 1; return х + а,д(х) = f а: = а * 2; return х * а,причём переменная а глобальна, то (если а Ф 6)/(2) +^(3) фд(3) + /(2).Если формула 7 и базис F заданы (причём 7 является правильно построеннойформулой над базисом F), то процедура E v a l ( J , F, х\,...,хп) является некоторойбулевой функцией / переменных х\,... ,хп.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
