XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 61
Текст из файла (страница 61)
Рассмотрим некоторые примеры булевых функций, которые будем задавать посредством таблиц. При и = 1 имеем четыре булевы функции (табл. 6.2). Таблица 6.6 Функцию,~~ называют тождестпеенной функцией, а функцию у4 — отрицанием. Функции уз и ~з являются функциями (от одного переменного), принимающими постоянное значение (О и 1 соответственно). Их также зачастую называют константой О и константой 1. Постоянные функции, разумеется, могут быть определены и при любом (большем 1) числе переменных. В табл. 6.3 указаны семь (из 2~ = 16) наиболее важных для дальнейшего изложения булевых функций от двух переменных. 385 6.2. 7аблилы булевых фувклвв Таблица б.ое Поскольку каждая булева функция от двух переменных есть одновременно и бинарная операция на множестве (О, Ц, то естественно для таких функций использовать запись, принятую для бинарных операций: хюу вместо ь1(х,у). Для функций, записанных в табл.
6.3, принимаютсл следующие обозначения: Функцию у1 называют дизъюнкцией, уг — кокъюнкцией, уз — слоэкением по модулю 2 (шод 2), у4 — импликацией; ув — эквиваленьпностпью, ув — штприхом Ше4фера, Уг — сьпрелкой Пирса. Дизъюнкция и конъюнкция, как видно, — это операции двухэлементной булевой алзебры — объединение и пересечение соответственно (тогда как функция отрицания есть не что иное, как дополнение в этой булевой алгебре). В то же время дизъюнкция и конъюнкция — это не что иное, как одноименные логические операции, введенные в 1.1 (в свете логической интерпретации булевой функции, см.
6.1). Очевидным образом с логическими связками, помимо отрицания, соотносятся импликация и эквивалентность (хотя их обозначения как булевых ЯХ1,хг) = х1 Ь(Х1,хг) =* Ь(Х1,хг) = * г4(х1,хг) = х1 гз(х1)х2) = х1 ув(Х1,хг) = Х1 Уг(Х1,Х2) = Х1 1~ хг, х2 (или У2(х11хг) = х1 Лхг)~ 9Х2, "+ Хг~ ' Хг~ ~ Х2, 1Хг. 386 б. БУЛЕВЫ ФУНКЦИИ функций несколько отличаются от введенных в 1.1). Таблицы для введенных булевых функций являются тогда не чем иным, как формой представления шаблиц ис~иинносши. Далее, можно заметить, что сложение по модулю 2 совпадает с операцией сложения кольца вычешов Е2 по модулю 2, штрих Шеффера есть отрицание конъюнкции, а стрелка Пирса — отрицание дизъюнкции, т.е.
Ж~ ~ Ж2 =Х1 ° Х2, Х1.~,Х2 =ЖГ 7Х2. Приведем для примера таблицу булевой функции от трех переменных (табл. 6.4). Таблица 6.4 Эта функция называется мажоригпарной функцией или функцией еолосоеани,я. Заметим, что в первом столбце табл. 6.4 для каждого набора из (О, Ц указан его номер, т.е. '3 число, двоичным кодом которого служит данный набор. Теоретически таблицей можно задать любую булеву функцию, но при большом числе переменных этот способ практически не применим.
Далее (см. 6.4) мы рассмотрим способ задания булевых функций в виде формул, аналогичный аналитическому заданию элементарных функций в анализе ~1]. С точки зрения логической интерпретации булевой функции ее 387 Э.г. таелвл~ы мяу е фу 1 а таблица есть таблица истинности некоторого сложного высказывания Переменными функции являются входящие в сложное высказывание простые высказывания. Кроме того, полезно иметь в виду, что, записывая таблицу булевой функции от и переменных, нет необходимости каждый раэ перечислять все наборы длины и — достаточно записать вант~ар значений булевой функции, понимал, что е-л компонента этого вектора есть значение функции на 1-м наборе (двоичном коде числа 1).
Тогда мажоритарная функция у может быть задана так: ~ = (0,0,0,1,0,1,1,1). Можно также перечислить номера тех наборов, на которых функция принимает значение 1: У=(3 5 6 7). Обобщением понятия булевой функцни служит понятие булева оператора. Булев оператор — зто произвольное отображение вида (6.3) у. Ве Ет для произвольных н, 1п Е М0 (О). Булез оператор (6.3) может быть задан посредством семейства булевых функций в виде (6.4) Функции 71 в (6.4) будем называть координатными функция ни булева оператпора (6.3).
Если ввести векторы переменных у=(ум ..., у,з) и х =(х1, ..., х„), то булез оператор (6.3), заданный семейством координатных функций (6.4), можно записать в таком виде: (6.5) 388 б. БУЛЕВЫ ФУНКЦИИ 6.3, Фиктивные переменные. Равенство булевых функций Ключевым понятием в теории булевых функций является понятие равных булевых функций. Для функций от одного и того же числа переменных н нет необходимости рассматривать какое-то специальное определение равенства, ибо такие функции равны, если они совпадают как ошобрахсенил булева куба В" в В. Проблема состоит в том, чтобы определить равенство булевых функций независимо от числа переменных. Пример 6.4.
Рассмотрим булевы функции Дх,у) = х Ч у и д(х,у,г) =ххЧхУЧулууУ. Можно заметить, используя тождества булевое алгебры, что д(х,у>х) = (хЧу)(лЧУ), а поскольку г Ч У = 1, то д(х,у>л) = (х Чу) = Дх,у), и функции ~ и д естественно рассматривать как равные, несмотря на то что они зависят от разного числа переменных. В примере 6.4 функция д определена как функция от трех переменных, но значение переменного г не влияет на значение функции. Обобщая ситуацию примера, можно ввести понятие фиктивного переменного булевой функции. Определение 6.1. Переменное х; называют фннпьнвным нерелвеннын булевой функции у(хм...,х„), если значе.
ние функции не зависит от значения этого переменного, т.е. если для любых значений переменных хы ..., х; и х;+и ..., х„ ~(х1»...х; 1>0>х;,1»...хв) =,~(х1>".>х>-1>1>х>+1>" >ха) Будем называть переменное х, не являющееся фиктивным переменным функции у, существенным нерельеннььн данной функции и говорить, что функция у существенно зависит от переменного х.
б.э. Фивтиввые вереыевиые. Рввеветво булевых фувввив 389 Пусть дана булеза функция у = у(хм...,хв) от н переменных. Пусть существенными переменными этой функции являются переменные х;„..., х;„, где т < н и 1 < е1 « ... ет < н. Присваивая каждому фиктивному переменному функции у произвольное значение, получим функцию ~, такую, что она есть функция от г переменных, т.е. есть отображение из В' в В, и для любого набора а;„..., а;, значений переменных х;„..., х,, имеет место равенство независимо от значений фиктивных переменных функции у (т.е.
переменных, отличных от х;„..., х;,). Тем самым функция у оказывается уже функцией, определенной на некоторой г-мерной грани булева куба В". Договопимся только что описанный переход от функции у к функции у, уже не имеющей фиктивных переменных, называть удалением фиктивных переменных (функции у). Замечание 6.2. В качестве упомянутой вьппе г-мерной грани может быть взята любая грань с направлением, заданным номерами фиктивных переменных. Фиксация грани означает фиксацию конкретного набора значений фиктивных переменных.
Тогда соответствующая этой грани функция,~ получается из исходной функции у в результате подстановки вместо каждого фиктивного переменного того конкретного значения, которое задано указанным вьппе набором. Вернемсв к примеру 6.4. Удаляя фиктивное переменное в, вместо функции д получим либо функцию д(х,у,О), которая определена на (двумерной) грани В„' булеза куба Вз, либо функцию д(х,у,1), определенную на грани В ' .
Направлением з,з каждой нз этих граней будет однокомпонентный кортеж (3), определенный номером фиктивного переменного е. С использованием понятий фиктивного и существенного пе. Ременного можно дать следующее определение равных булевых функций. 390 6. ВУЛЕВЫ ФУНКЦИИ Определение 6.2, Булевы функции у и д называют равными, если их существенные переменные соответственно равны и на каждом наборе значений этих переменных функции у и д принимают равные значения. Чтобы распознать по таблице булевой функции, является ли переменное я; фиктивным, нужно рассмотреть все наборы с фиксированным значением 1-й компоненты (один раз фиксирован это значение как О, другой раз — как 1). Из определения 6.1 ясно, что переменное х; фиктивно тогда и только тогда, когда для любых двух наборов, отличающихся только значением 4ьй компоненты, функция принимает равные значения.
Пример 6.5. а. Из табл. 6.4 следует, что мажорип4арная фдикцил не имеет фиктивных переменных, так как, например, у(0,0,1) = О, а у(1,0,1) = 1, т.е. переменное х1 существенное. Далее, У(1,0,0) = О, но У(1,1,0) = 1, что означает существенность переменного хз, для яз имеем ~(1,0, 0) = О, но у(1,0, 1) = 1, что означает существенность и этого переменного. б. Ниже приведена таблица функции д от четырех переменных (табл.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
