В.И. Игошин - Задачи и упражнения по математической логике и теории алгоритмов - 2007 (1019105), страница 26
Текст из файла (страница 26)
Р е ш е н и е. Для доказательства неполноты системы нужно найти какое-либо свойство, которым обладают все функции данной системы и которое сохраняется при суперпозиции, хотя не все булевы функции им обладают. Например, в задаче а) кюкдая из функций и ~ сохраняет О, т.е. 0 0 = 0 и 0 ч 0 = О. Следовательно, всякая суперпозиция этих 123 функций будет функцией, сохраняющей О. Ясно, что далеко не все булевы функции сохраняют О, и потому далеко не все они выразимы через и ~. В задаче л) нетрудно показать, что в виде суперпозиций функций ++ и ' могут быть представлены лишь такие функции, среди значений которых имеется одинаковое число нулей и единиц.
6.3. Исследуйте на полноту системы булевых функций: а) (+, »; б) (-+, +»; в) (-+, 1»; г) (+, Ц; д) (+,, О»; е) (+, О, 1»; ж) (, О, Ц; з) (++, ~, 0»; и) (-+,, О»; к) (+,, ++»; л) (+, ~, ++); м) (-+, Ф- », где х х~ у = (у-+ х)' = х'у. 6.4. Докажите, что каждая из следующих функций образует полную систему из одной функции (такие функции называются обобщенными функциями Шеффера): а) х'у'х', б) (х+ у+ 1)(х+ 1); в) х'у'~' ч ху'~; г) ху -+ ~', д) (х+ + 1)(у+ 1)(е+ 1); е) х'(у-+ х'); ж) х++ (у+ (хх)); з) (1+ х)(у'+ х)'; и) хт' ч уХ'; к) хуя + 1; л) ху -+ (х -+ ~').
Решение. л) Обозначим данную функцию через Г", т.е. г(х, у, я) = ху -+ (х -+ е'), и покажем, что все функции какой-нибудь полной системы функций могут быть выражены через функцию у. Положим е = у и преобразуем выражение для г'следующим образом:)(х, у, у) = ху -+ (х -+ у') = (ху)'ч (х'ч у') = х' ч у' ~~х'ч у' = = х' ~ у' = (ху)' = х» у. Таким образом, х ) у =~(х, у, у). Поскольку система (»», состоящая из функции» (штрих Шеффера), полна (см. задачу 6.1, ж) и эта функция выражается через функцию ~ то, следовательно, через функцию у'может быть выражена всякая булева функция.
Это и означает, что система (г» полна. 6.5. Исследуйте на полноту следующие системы булевых функций: а) (ху ~ у'е, О, Ц; ж) ((у-+ х)(у' -+ я), О, 1»; б) (ху ~ х~ г у~, х', Ц", з) (х+ у+ ~, х'»; в) (ху ч хе ~~ у~, х++ у, х е у»; и) (ху ~~ х~ ч у~, х'»; г) (у -+ хе, О, 1»; к) (ху + хя + у~> О, Ц; д) (х+ у+ ~, ху, х'»; л) (х+ у, О, Ц; е) (ху+ ~, (х++ у) + е, Ц; м) (ху, О, Ц. Решение. Системы а) — ж) полны. Система з) не полна, так как обе функции линейны и, следовательно, всякая их суперпозиция есть линейная функция (задача 5.14).
Аналогично в задаче и) обе функции самодвойственны, а в задаче к) все три функции системы монотонны. 6.6. Докажите, что если некоторая система булевых функций Р= Я, ..., у" » полна, то и система Р" = (Я', ..., У„'», состоящая из функций, двойственных функциям системы Г, также полна. Р е ш е н и е. Если требуется представить некоторую функцию г" в виде суперпозиции функций из Г*, то представим сначала двойственную функцию )' в виде суперпозиции функций из Г.
Переходя в этом представлении к двойственным функциям, мы 124 получим слева функцию 7; а справа суперпозицию двойственных функций к функциям из Р, т.е. суперпозицию функций из г «. Применение теоремы Поста. Напомним теорему Поста, которая формулирует критерий полноты системы булевых функций: для полноты системы булевых функций В = (Д, Я, ..., 7» ...) необходимо и достаточно, чтобы для каждого из классов Рд, Рь Я, 1„М в системе В нашлась функция 6„ему не принадлежащая, т.е. необходимо и достаточно, чтобы система В не включалась ни в один из этих классов.
Отсюда легко получается отрицание этого критерия, представляющее собой критерий неполноты системы булевых функций: система В булевых функций неполна тогда и только тогда, когда она целиком включается в один из классов Р„Рь Я, 1„М. 6.7. Решите задачу 6.1, используя теорему Поста. Р е ш е н и е. л) Для решения полезно составить таблицу, называемую таблицей Поста данной системы функций: Стоящий в таблице знак «+» означает, что указанная в данной строке функция принадлежит указанному в данном столбце классу.
Знак «-» означает непринадлежность данной функции соответствующему классу. Если в каждом из пяти последних столбцов таблицы имеется хотя бы один знак «-», то это означает, что рассматриваемая система функций полна. В противном случае, т.е. когда хотя бы в одном столбце нет ни одного знака « — », система не полна. 6.8. Используя теорему Поста, решите задачу 6.2.
6.9. Решите задачу 6.3, используя теорему Поста. 6.10. Как выглядят таблицы Поста для функций задачи 6.4? 6.11. Решите задачу 6.5, используя теорему Поста. В этой задаче выделите системы булевых функций, которые доказывали бы существенность каждого условия теоремы Поста, т.е. доказывали бы невозможность опустить ни одно условие этой теоремы без того, чтобы не нарушить формулируемый в теореме критерий.
Решение. Составим таблицу Поста для пяти последних систем функций. Из этой таблицы заключаем, что каждая из рассмотренных систем функций включается в один из классов Рд, Рн Я, 1„М. Первая система включается в класс Р«, вторая — в класс Р„третья— в класс Я, четвертая — в 1„пятая — в М. Следовательно, на основании теоремы Поста ни одна из рассмотренных систем не является полной. 125 Обсудим теперь вопрос о существенности условий теоремы Поста.
Приведенные пять систем булевых функций предоставляют нам такую возможность. Эти системы показывают, что для каждого из пяти классов Р„Ро Я, Е, М можно указать такую содержащуюся в нем систему булевых функций (а значит, неполную), в которой для каждого из остальных четырех классов имеется функция, ему не принадлежащая. Это и означает, что, отбросив условие непринадлежности функции системы хотя бы одному из классов Р„Рп Я, А, М, мы рискуем получить неполную систему булевых функций. 6.12. Выясните, является ли система Я(хо хн ..., х„), Яз(хо хп ..., х„)) булевых функций полной, если: а) 1; а Я~М,,12 а Е~~ о,Л'-+К=1; б) Л а Р ~ Е, Я а Я, Я~ -э Д = 1. 6.13.
Является ли полной система Я (хп ..., х„), Я~(хп ..., х„), Яз(хь ..., х„)) булевых функций, если Я а Х, '.~ (Р0 г~ Р~), 12 е М ~ ~ 1 Х -+ Уг = 1* А ".6 = 1. 6.14. Докажите, что функции штрих Шеффера и стрелка Пирса и только они являются булевыми функциями от двух аргументов, через каждую из которых могут быть выражены все другие булевы функции. Указание. Решение может состоять в проверке того, что все остальные булевы функции от двух аргументов, взятые по отдельности, не удовлетворяют условию теоремы Поста. 126 6.15.
Докажите, что система (г (х„хь ..., х„)), состоящая из одной функции, полна тогда и только тогда, когда эта функция не сохраняет О, не сохраняет 1 и не является самодвойственной. 6.16. Докажите, что среди булевых функций от и аргументов имеется ровно 2'" ' — 2'" ' ' таких, каждая из которых образует полную систему функций. Функционально замкнутые классы булевых функций. Всякая совокупность Т функций алгебры логики, замкнутая относительно суперпозиции (т.е. такая, что суперпозиция функций из Т снова принадлежит Т), называется фулкциональло замкнутым классом. 6.17. Какие из указанных классов функций являются функционально замкнутыми классами: а) функции от одной переменной; б) функции от двух переменных; в) все функции алгебры логики; г) линейные функции; д) самодвойственные функции; е) монотонные функции; ж) монотонно убывающие функции; з) функции, сохраняющие нуль; и) функции, сохраняющие единицу; к) функции, сохраняющие и нуль, и единицу; л) функции, сохраняющие нуль, но не сохраняющие единицу.
Решение. л) Нужно показать, замкнута или нет данная совокупность относительно суперпозиции. В данном случае можно привести пример, доказывающий, что совокупность — не функционально замкнутый класс. Например, функция х+ у сохраняет О, но не сохраняет 1, а ее суперпозиция х+ (у+ х) сохраняет 1. 6.18. Докажите, что ни один. из классов Р,, Рп Ю, Е, М не содержится в другом, т.е.: а) Р, не включается в Р„Р, не включается в Р„ б) Р, не включается в Я, 5 не включается в Р;, в) Р, не включается в Ь, Е не включается в Р;, г) Р, не включается в М Мне включается в Р6 д) Р, не включается в Я, Я не включается в Р,; е) Р, не включается в Е, А не включается в Р,; ж) Р, не включается в М, Мне включается в Р,; з) Я не включается в А, .(, не включается в Я; н) Ю не включается в М Мне включается в Ю; к) Е не включается в М, Мне включается в Е.
У к а з а н и е. В каждом случае привести примеры двух конкретных функций: одна из них должна принадлежать первому классу, но не принадлежать второму„а другая принадлежать второму и не принадлежать первому. 6.19. Докажите, что всякий функционально замкнутый класс, не совпадающий с классом всех булевых функций, содерхсится в одном из классов Р„Рп Я, А, М. Р е ш е н и е. Допустим, что некоторый функционально замкнутый класс Хне содержится ни в одном из классов Рм Ро Я„Е, М. Следовательно, в нем есть функции, не принадлежащие каждому из этих классов. Тогда, по теореме Поста, всякая булева функция 127 представима в виде суперпозиции таких функций. Но в силу функ- циональной замкнутости класса К эта суперпозиция снова при- надлежит классу К.
Таким образом, всякая булева функция нахо- дится в К, что противоречит условию, согласно которому К не совпадает с классом всех булевых функций. Получили противоре- чие, которое и доказывает, что К содержится в одном из классов Рм Рь о, Т,> М. 6.20. Докажите, что функционально замкнутые классы ЄЄ Ю, А, М максимальны, т.е.
не существует функционально замкну- тых классов, отличных от класса всех булевых функций и содер- жащих какой-либо из перечисленных классов. 6.21. Докажите, что кроме классов Р„Рь Я, 1„Мне существу- ет других максимальных (см. задачу 6.20) функционально замкну- тых классов. Р е ш е н и е. Утверждения двух последних задач непосредствен- но следуют из утверждения задачи 6.19. Базисы булевых функций. Минимальная полная система функ- ций (т.е. такая полная система функций, удаление из которой любой функции делает систему неполной) называется базисом. Булева функция, представляющая собой базис из одного элемента, называется обобщеннойфункцией Шеффера.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
