Игошин Математическая логика и теория алгоритмов (1019110), страница 27
Текст из файла (страница 27)
Это можно сделать так: х~у=х+у+х. у. Предлагается самостоятельно проверить справедливость приведенного тождества. Аналогично, для проверки полноты системы (», ') нужно выразить конъюнкцию через дизъюнкцию и отрицание. Соответствуюшее тождество известно (см. теорему 9.5, а). Полнота системы (, ') вытекает из полноты системы ( ч, и тождества теоремы 9.5, б, выражаюшего дизъюнкцию через коньюнкцию и отрицание, а полнота системы ( — », ') — из полноты системы (~», ') и тождества теоремы 9.5, в, выражаюшего дизьюнкцию через импликацию.
Наконец система ( ) ) полна, потому что каждая функция есть суперпозиция функций ~ и ', а обе эти функции могут быть выражены через функцию штрих Шеффера (см. теорему 9.5, зк, и). Аналогично, система (» ) полна, так как полна система (, ') и справедливы тождества теоремы 9.5, к„м, выражающие функции и ' через стрелку Пирса ) . Теорема доказана. С) Теперь от разрозненных и случайных примеров полных систем булевых функций перейдем к их исчерпывающему описанию. Прежде чем получить такое описание, в следующем пункте рассмотрим необходимые предварительные понятия. Специальные классы булевых функций.
Говорят, что булева функ- циЯ 1(хь хъ ..., х„) сохРанЯет О, если 1(0, О, ..., 0) = О. Обозначим 1»0 — класс всех булевых функций, сохраняюших О. Говорят, что булева функция 1(хп хз, ..., х„) сохраняет 1, если У(1, 1, „., 1) = 1. Обозначим Р, — класс всех булевых функций, сохраняющих 1. Булева функция 1'*(хь х,, ..., х„) называется двойственной функцией длЯ бУлевой фУнкции 1(хь хъ ..., х„), если Т*(хп хъ ..., х„) = = У'(х,', х,', ..., х„') для любых х„хъ ..., х„. Булева функция 1 назы- 107 вается самодвойопвенной, если г' =~ Класс всех самодвойственных булевых функций обозначим Х Введем на множестве (О, 1) отношение порядка, полагая, что 0 < О, 0 < 1, 1 < 1. Булева функция Дхп хг, ..., х„) называется монотонной, если для любых ац аг, ..., а„, 13„~3г, ..., 13„в (О, 1) из а < 13ь аг < Вг, ..., а„< 13„немедленно следует, что Яаь аг, ..., и„) <Я3„()г, ..., 0„).
Класс всех монотонных функций обозначим М. Наконец, булева функция )"(хг, хг, ..., х„) называется линейной, если ее можно представить в виде следующего выражения (называемого полиномом Жегалкина степени не выше первой): Яхь х,, ..., х„) = ае+ а,х, + агхг+ ... + а„х„, где аы а„а,, ..., а„— постоянные, равные либо О, либо 1. Символом Е обозначим класс всех линейных булевых функций. Введенные классы булевых функций Р„Рь Ю, М, Т, играют главную роль при описании полных систем булевых функций. В следующей теореме устанавливаются два важных свойства этих классов и одновременно рассматриваются примеры функций, принадлежащих и не принадлежащих каждому из них.
Класс булевых функций называется собственным, если он не пуст и не совпадает с классом всех булевых функций. Класс булевых функций называется замкнутым или классом Поста, если он вместе со всякими своими функциями содержит любую их супер- позицию. Теорема 11.3. Классы Рд, Р„Ю, М, ь' являются собственными замкнутыми классами булевых дгункций. Доказательство. Проверим сначала, что все эти классы являются собственными.
Укажем функции, которые принадлежат и не принадлежат каждому из рассматриваемых классов, предоставляя читателю проверить самостоятельно данные утверждения. Как классу Ры так и классу Р, принадлежит, например, конъюнкция и не принадлежит отрицание. Далее, конъюнкция не является самодвойственной функцией, а отрицание есть функция самодвойственная. (Проверим последнее утверждение. Пусть г(х) = х'. Тогда т' (х) =/'(х') = (Г(х'))' = (х")' = х' =у(х), т.е.
т' = г, а значит, у(х) = = х' — самодвойственная функция.) Наконец, к классу монотонных функций принадлежит конъюнкция и не принадлежит импликация, а к классу Е линейных функций принадлежит сложение по модулю два (сумма Жегалкина) и не принадлежит конъюнкция. Покажем теперь замкнутость этих классов. Пусть |~, Ыг в Ры т.е. ЯО, 0) = 6(0, 0) =);(О, 0) = О, и я(хь хг) =УХА(хо хг), Яхь х,)). Тогда я(0, 0) = ~(ЯО, 0), ЯО, 0)) =НО, 0) = О, т.е. я в Рв. Аналогично проверяется замкнутость класса Рь Пусть теперь |ь гг, Я~ в 5, т.е. 1Ди, о) = Я,(и', о'), Яхг', х,') = гг(хн хг) гг (х1, хг ) = гг(х1, хг) и 8(хь хг) г1(гг(хь хг), Яхь хг)).
Тогда Г*(хь хг) = 8'(хг', хг') = Я'(Ях|', хг') гг(х1', хг )) = ХИ'(хг', хг'), 108 Хз'(х1' хг')) =ХИ(х~ хг), 6(хн хг)) = я(хь хг), т.е. е* = е и значит ее Я. Пусть далее Х 1г, Я е Ми «~ < (3ь «г < 1)г и е(хь хг) = 1,'(1г(хь хг), Уз(хь хг)). Тогда Уг(«ь «г) <ЫЬь Рг) Уз(«ь «г) ~Уз(Рн Рг) и К(«н «г) = ХИ(«ь «г) Хз(аь «г)) < Х(6(Р1 з)г) Хз(з)1 з)г)) = Х(Р~ Рг).
Следовательно, я е М. Наконец, пусть 1ь 1г, 6 е 1„т.е., например, 1;(хь хг) = аь+ + а,х, + а,хг, Яхп х,) = Ьь+ Ь,хз + Ьгхг .Яхь хг) = се + с,х, + сгх,. Тогда я(хн хг) = 1~(Яхь хг), 1з(хп хг)) = аь + а| ',/г(х~ хг) + аг 1з(хь хг) = аь+ а, (Ьь+ Ь,х, + Ьгхг) + аг ' (со+ с,х, + сгхг) = (аь+ а,Ьь+ + а сь) + (а1Ь! + а с ) . х, + (а~Ьг+ агсг) . хг = до+ дзх1 + дгхг, т е. л е Е.
Теорема доказана. (З Заметим, что, например, функция Ях) = х принадлежит каждому из пяти классов Рь, Рн 5, М, 1.. Теорема Поста о полноте системы булевых функций. Эта теорема доказана американским математиком Э. Постом в 1921 г. Теорема 11.4 (о полноте системы булевых функций). Система булевых функций К, 1н ..., 1;, ...) является полной тогда и только тогда, когда в этой системе имеется функция, не принадлежащая классу Рь, имеется функция, не принадлежащая классу Рь имеется функция, не принадлежащая классу 5, имеется функция, не принадлежащая классу М, имеется функция, не принадлежащая классу 1,.
Доказательство. Необходимость. Пусть система булевых функций (4,1з, ..., 1,, ...) полна. Допустим, что все функции этой системы входят в класс Рь. Поскольку на основании предыдущей теоремы класс Рь замкнут, то всякая суперпозиция любых функций из данной системы есть функция из класса Р,. Но также по предыдущей теореме класс Р, не исчерпывает всех булевых функций. Поэтому найдется булева функция (не принадлежащая классу Рд), которая не является суперпозицией функций из системы (4, 1'„..., 1;, ...), что противоречит полноте этой системы.
Следовательно, в системе имеется функция, не принадлежащая классу Р,. Совершенно аналогично доказываются утверждения о наличии в системе (1ы б, ..., 1:, ...) функций, не принадлежащих клас- самРьЯ,М,1.. Достапгочность. Предположим, что среди функций системы (зь,,зь ..., Л, ...) имеются такие функции АХ* Уг Хз У4 что,гь в Ро з1 е Рь 1г е 5, 1з е М„~4 в 1,.
Покажем, что из этих пяти функций с помощью суперпозиций можно сконструировать такие функции, которые заведомо образуют полную систему. Начнем с 1ь, для которой 1ь(0„0, ..., 0) = 1. Ввелем функцию 1ь(х) =Ях, х, ..., х). Для нее имеем: гь(0) = 1, 1ь(1) = 0 или 1. Следовательно, 1ь(х) = х' или Ях) = 1.
Аналогично, из1ь для которой 1;(1, 1, ..., 1) = О, строим функцию Я(х) = 1;(х, х, ..., х). Для нее имеем: Я (1) = О, Я (0) = 1 или О. Следовательно„гз(х) = х' или Я(х) = О. 109 Таким образом, получаем одну из следующих четырех пар функций: х' и х' (1); х' и 0 (2); х' и 1 (3); 0 и 1 (4). В каждом из случаев (2) и (3) имеем тогда по три функции х', О, 1 (например, если есть функции х' и О, то константа 1 получается как 0'). Рассмотрим случай (1). Покажем, что и здесь можно получить обе константы 0 и 1. Для этого привлечем несамодвойственную функцию 6 (т.е. /~ е 5).
Для нее 6 ~,гг, т.е. ~~(аь иг, ..., а„);салаг', иг', ..., а„') для неколгорого набора и„аг, ..., а„из нулей и единиц. Следовательно, для этого наборами(аь аг, ..., а„) =Яг(а~', аг', ..., а„'). Построим теперь функцию Ях) по следуюшему правилу: Гг(х) = тг(х"',х"г,...,х'"), где х,еслиа; = О, ха, х',еслиаг =1, для 1 < !< л. Для функции имеем: гг(0) =Л(ац пг, гх~) =Уг(а,', а ', ..., а„') = Я1) . Следовательно, Уг(х) — константа. Поскольку в нашем распоряжении имеется отрицание х', то из этой константы (О или !) можно получить и другую константу (1 или 0 соответственно). Итак, в случае (1) имеем функции х', О, 1. Рассмотрим случай (4). Здесь к константам 0 и 1 необходимо получить функцию х'.
Для этого привлечем немонотонную функциюЯ (т.е.Яг а М). Ее немонотонность означает: найдутся такие наборы из нулей и единиц (аь аг, ..., а„) и (!3ь !3„..., 13„), что (аь аг, ..., а„) < < (!Зь !)г, ..., !3„), но г(аь аг, ..., а„) > Щ, !Зг, ..., !3„). Построим функцию Я (х) по следующему правилу Гг(х) = Яг(хгг, хгг ..., хь), где О, если с4 = (3; = О, х" = 1,еслиа; =(3; =1, х,еслиаг = О, !)г = 1, для 1 < ! < л. Тогда ясно, что гг(0) > Я(1) . Следовательно, должно быть 2гг(0) = 1, Яг(1) = О.
Значит, уг(х) = х'. Итак, из данной системы функций с помошью суперпозиций нами сконструированы функции х', О, 1. Рассмотрим теперь еше не использованную нами нелинейную функциюг4 (т.е.~~ а Е). Предположим, что х, — тот ее аргумент, который в разложение в полипом Жегалкина функции г4 входит нелинейно. Это означает, что г4 может быть представлена в виде 4(хь х„..., х„) = х, <р(хг, ..., х„) + г!г(хг, ..., х„), где д;~ О, <р ~ 1 (в противном случае функция г4 имела бы два различных представления полиномами Жегалкина, что невозможно).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
