В.Н. Нефедов, В.А. Осипова - Курс дискретной математики, страница 10

13. Пусть формула А не содержит нккакик логических символов, кроме и -1. Доказать, что А является тождественнонстннной тогда и только тогда, когда каждая переменная н символ -1 входят в нее четкое число раз. 1.2. БУЛЕВЫ ФУНКЦИИ 1.2.1. Представление булевой функции формулой логики высказываний булевой фунщией )(Хь..., Х ) называется произвольная и-местная функция из множества (О. !) во множество (О, !). Итац как аргументы булевой функции принимают значения из множества (О, 1), так н сама функция принимает значения из этого же множества.

Всякую булеву функцию от л переменных можно задать таблицей из 2" строк. в которой в каждой строке записывают одну из оценок списка переменных, принимающих значение О нли 1. Например, для л = 3 булеву функцию можно задать табл. 1.9. Так как длина каждого столбца равна 2", а разлнчшех столб. цов нз О и ! длины 2" имеется з- та существует точно хе различных и-местных булевых 1 Нг, 1, !) функций (или булевмх функций сг л переменных). Удобно кон. станты О и 1 считать нуль-мест- О 1 1 )!О'1'1~ ными булевыми функциями. О 1 а (а!0 Пусть истинностному значе- нию И соответствует 1, а истин- О 0 а !га; а, 0 постному значению Л вЂ” О.

Тогда каждой формуле логики выскаэмваний Р можно поставить н соответствие булеву функцию ). При этом, если формуле Р, соответствует функция )ь а формуле Р, — функция ), и Рг Рт, та П = (е. Составим теперь в новых обозначениях табл. 120 для булевых функций, соответствующих основным логическим операциям. Докажем. что формулы дают нам, по сути дела, все булевы фуякцин, а именно имеет место следующая теорема. Теорема 1М (переая теорема а представлении булевой функции). Пусть )(Хь....

Хз) — й-местния булееи функция (й)!). Теазапе 1йв Если / ие Рима таждзсгаеиио О, то существует такая формула Р, заввсящая от списка леремещмщ <Хь ..., Ха> и иаюдящаягл е СДИФ атиоситслаио згоео списка, чго Р выражает собой фуиккяю /. Формула Р оирсделени однозначно с точюмтью до перестановки диэъюиктиллыэ чжвов. Докажем сначала вспомогательное утверждение.

Прн з - 1 под А' будем подразумевать формулу А, а ари з =Π— форму.ту -!А. С каждой оценкой списка персменнык <зь..., а,> будем ассоциировщь элементарную конъюнкцию Х,* й... АХ з Лемма 1.б. Конъюнкция Хз'й, „ЬХаь, ассоциированная с сменкой <зи..., зе>, обращаеггл з 1 ла одной а толька иа одной оаеикс списка лсрсмзииыз <Хь..., Х,>. а именно иа оясияз <ю,..., зь>.

В самом деле, на оценке <Яь,..,аь>фоРыУла Х~з й... ...ОХ,' принимает значение 1, так ючк каждый ее конъюнк. тнаный член Хга принвмает авачение 1. Действительно, возмож. ны два случая: либо м(1~!~й) есть 1, н тогда ХР' есть Хь либо м есть О, и тгада ХР есть -!Хь В каждом из этих овучаев Х,п иа оценке <зь..., эе> аринимает значение 1. С другой стороны, пусть оценка <!ь ° °, !а> не совпадает с оценкой <зь ..., эь>. Тогда «ри некотором !(1<1<у) 5~ чь й. Возможны даа случая: !)зг !С~ О; 2) ц О,!с=1.

В первом случае Хг* есть Хь а во втором — Хги есть -1Хг. В любом случае ХР нз оценив <й,..., га> принимает значение О, а значит, и вся элементарная конъюнкция Х,з~ Ь ... ...ОХьз" принимает значение О. Лемма доказана. Пусть теперь функция /(Хь ° ° . Хь) зютана таблицей. В». берси из таблицы все строки, соответствующие оценкам, аа но.

торна / принимает значение 1'(поскольку /чьб, то танис строки найдутся). Для оценки списка переыенных в каждой выбранной ст(юке построим ассоциированную с ней элементарную конъюнкцию и составим дизъюикцию всех таких конъюнкций. Полученная формула и будет искомой. Для этого нан нунщо доказать следующие два утверждения: 1) есин /(щ,..., зе) 1, то Р на оценке <зь ..., за> принимает значение 1; 2) если /(зь ..., щ) О, то Р на оценив <ю,..., я,> принимает значение О.

Пуща /(э, з„) 1, тогда в таблице длв / ст!юка' со е вуищ',ая оценке <зь..., за>, находится сред" вы ат бранных строк, а значит, элементарная нонъюнкпня ХР' б ... ... ОХьз» находитсЯ сРедн лнзъюнктнвных членов Р. В силУ леммы !.б конъюнкция ХР»й .. б Ха*» принимает на оценке <зь.,. зь> значение 1, а вместе с ней и вся формула. Пусть ! (зь.... зь) = О. Любой дизьюнктнвный член Р имеет вил Х~т~б... ОХь!э, пРичем оценка <!ь, !ь> каждый Раз отличаетси от оценин <з„,, з„>, так хзк строка, соответсгвуххцая оценке <зь"., зь>, не могла быть выбранной.

В силу леммы 1.8 каждая такая элементарная конъюнкция обращается в О нв оценке <зь .. э зз>, а значит, и вся формула Р обращается в О на этой оценке, что и требовалось показать. Пример 1АЗ. Для функции, заданной табл. 1.11, соответствующей формулой будет (Х~ ОХзйХз) т„т (Х~ й-)Хзб-)Хз) ~Г (-1 Х~ бХтбХз) ~I „~ (Пх,б-!Х,бх). Докажем едиасгзенлосгь. Пусть Р! и Рз — дае формулы, выражающие функцию В накопящвеся в СЛНФ относительно списка <Хь..., Хь> и существенно различные, т. е. либо в Р, есть элементарная конъюнкция, не содержащаяся в Рь либо в Рз есть элементарная конъюнкция, не содержащаяся в Рь Рассмотрим, например, нсрвый случай.

Рслн Кгщ й... О Ха*э — элементарная хоиъюннция, содержащаяся в Рь но не в Рь то онз будет ассоциирована с оценкой <зь... зь>. Любая элементарная конъюннция, содержащаяся в Р» будет ассоциирована с некоторой другой оценкой. Поэтому на оценке <ю.

.. зь> юобая такая конъюинцня примет значение О, а следовательно, и вся формула Рт примет значение О. С другой стороны, на этой оценке ХР б ... ЬХазэ примет значение 1, а поэтому и формула Р, примет значение 1. Тогда Р, и Р» будут выражать собой различные булезы функции, откуда н следует елинственпость формулы. Занечавие й!.

Из теоремы 1.8 следует доказанное ранее (см. теорему !А) утверждение, что пля любой не тождественно-ложной формулы А существует равносильная ей формула Рв СДНФ. Однако мы аоказалн тогда более сильное утвержлепие, а именно, что Р может быть получена нз А с помощью равносильных преобразований. Замечание 1.2. Теперь легно доказать утверждение о едии. ствснностн СДНФ длл некотород формулы А. В самом леле, если А выражает булеву функипю /(Х . " .

Хл), то и любая сДНФ для А золжна (в силу равносильности) выражать собой т> жс функцию. Поэтому все эти СДНФ должны сознавать с точнощъю до порялка алеммаарных конъ~онхзглгб. Аналогично можно доказать, что булеаы фуикинн представпмы формулами в СКНФ, Теорема 1.9 (аторал заорал~а о ргдстлелении булевой фузхЛии). Луста /(Хл,..., Хз) — 2-местная булеза функция (Д> П. не разлил тсждестееммо 1. Сугцестерет такал формула Р, эаалсящая от слиаю леркмснмык <Хь "., Хз) и накодящаяся в СКЛФ отноааельло этого списка, что 1' еыратсает собой /(Х,....

Хз). Форму и Р определена однозначно с точиостью до лерестамоаки «онъюиктиеямх чзелоэ. Перечислим все О]левы функции от двух переменных. Та«~гх функций существует 2" = 10. Две функции сохраняют постоянноезнвчение: /л(Х, У) 0: /з(Х. У) 1. Четыре функции существенно зависит только от одного из аргументов: /з(Х, У) = =Х; / (Х. У) =У:/з(Х, У)= !Х;/ (Х, У]=-]У. Саедующие че. тырс функции принимают значение 1 точно иа однод оценке; в СДНФ этих функцвй должна быть только одна элементарная хонъкнкцн»: /(Х, У) Хб У (оценка (1,1)); /л(Х. У) = ]ХА б У (о««н (О 1 и; /.(Х, У) = Х Д -1 У (оценка ( ! О) ); /м (Х, У) = ТХ* -]у (оценка (0,0)). Последняя фуниция называегсн иногда функцией Шеффера и обозначается Х( У. Двойственны.

ии этим четырем функция» ивляются фуикпии /э(Х, У) ХТГУ1 /е(Х, У) = -] Х ]/ У - Х ' Уг /„(Х. У] = Х'] )Чу = У Х] / (Х, У) = -1Х]/П У. Все этн фуггкиии на трек опенках принимают значение ! и только на озноб оценке — значение О, а именно: на (О 0), (1,0), (0,1), (1,1) соответственно Последняя из ник нааывается функвией Вебба я обозначастс» Х У. На«снеи, имеются две функции, существенно зависящие от калкдого нз аргументов н принимающее иа двух оценках значение 0 и на двух — значение 1: /в(Х, У] (ХАТ)ТГ(]ХО ~У) Х У ]на оценках (!.1) (0,0) функция принимает зазчеинс 1]; / (Х, У) (П ХйУ) Х) (Хй ]У) (лы оценках (0,1), (1,О) функция принимает значение 1).

Последняя функиия соответствует разделительному «клик Оиа заливается также сложением по модулю 2 н оболаачастся Х + У. Как видим, рассмотренные функции попарно различны, так 'лто наше перечисление является исчерпывающим. !.2.2. Полные системм булевмх функций Система бУлевых фУнкций (/ь..., / ) называетск полной, если -чюбая булева функция может быть выражена через функиии Д ..., / с помощью сулгрлозиций (т. е. составления сложных функций).