В.И. Игошин - Задачи и упражнения по математической логике и теории алгоритмов - 2007 (1019105), страница 25
Текст из файла (страница 25)
Положив в ней у = О, я = 1, придем к функции <р(х, О, 1) = х', так как <р(0, О, 1) = 1, а р(1, О, П = О. 5.67. Выясните, при каких п следующие функции монотонны: а) (х, 4 х2 ч ... ч х„) -+ (х,х2 ... х„)„' б) (х', 4 х1 4 ... 4 х„') -+ (х,х2 ... х„); в) (х, 4 ... 4х» 2 4 х„', 4 х„') -+ (х, 4 х2 4 ... 4х„); г) (х, ч ... ч х 1 ч х„', 4 х„') -+ (х, + х1 + ... + х„); д) (х, ч ... ч х„, 4 х„') -+ (х, ... х„~х„); е) (х1х1 ... х„ ~х„') -+ (х~ + х2 + ... + х„). Решение.
е) Посмотрим на вид данной функции при и = = 1: х1 -+ х1 =х1 4 х, =хо Ясно, что она монотонна. Для решения вопроса о монотонности данной функции при остальных значениях п обратим внимание на следующее обстоятельство: т.е. на наименьшем наборе (О, О, ..., 0) данная функция принимает значение 1. Поэтому если найдется такой набор значений аргументов (а он будет непременно больше нулевого набора), на котором функция принимает значение О, то функция является немонотонной. Попытаемся его найти. Искомый набор должен обратить посылку импликации х,х, ...
х„,х„' в 1, а следствие х~ + х2 + + х» в 0 Посылка х1х2 х» ~х»~ являющаяся коньюнк цией, принимает значение 1 только на одном наборе: х, =1, х, = 1, ..., х„, = 1, х„= О. Возникает вопрос: какое значение принимает следствие х, + хз + ...
+ х, ~ + х„? Оно равно сумме Жегалкина п-1 единиц: 1 + 1 +...+ 1. Если число и — 1 четно (и, значит, и— нечетно), то это значение равно О. Следовательно, данная функция принимает значение О, а это означает, что при нечетном и(п 1 1) данная функция немонотонна. Если же число п — 1 нечет- но (и, значит, и — четно), то вычисляемое значение равно 1. Значит, данная функция принимает значение 1, и это, в свою очередь, означает, что при четном п данная функция монотонна.
(Фактически при четном и данная функция равна тождественно 1.) Итак, данная функция монотонна при п = 1 и при любом четном п. Булевы функции, сохраняющие нуль и сохраняющие единицу. Булева функция)"(х„хц ..., х„) называется сохраняющей нуль, если ,г(0, О, ..., 0) = О. Булева функция Дх„х,, ..., х„) называется сохраняющей единицу, если г(1, 1, ..., 1) = 1. 120 5.68. Перечислите все булевы функции: а) от 1 аргумента, сохраняющие 0; б) от 1 аргумента, сохраняющие 1; в) от 2 аргументов, сохраняющие 0; г) от 2 аргументов, сохраняющие 1; д) от 1 аргумента, сохраняющие и 0 и 1; е) от 2 аргументов, сохраняющие и 0 и 1; ж) от 2 аргументов, сохраняющие О, но не сохраняющие 1; з) от 2 аргументов, сохраняющие 1, но не сохраняющие О.
5.69. Докажите, что: а) суперпозиция булевых функций, сохраняющих О, есть снова булева функция, сохраняющая 0; б) суперпозиция булевых функций, сохраняющих 1, есть снова булева функция, сохраняющая 1. 5.70. Докажите, что среди всех булевых функций от и аргументов число функций, сохраняющих О, равно числу функций, сохраняющих 1. Найдите это число. Р е ш е н и е. Если ~' сохраняет О, то ее отрицание г' сохраняет 1.
Число функций от л аргументов, сохраняющих О, равно числу всевозможных двоичных наборов длины 2" — 1, т.е. равно 2м-! 5.71. Докажите, что среди всех булевых функций от и аргументов число функций, сохраняющих О, но не сохраняющих 1, равно числу функций, сохраняющих 1, но не сохраняющих О. Найдите это число. Решение. Такие функции, как и соответствующие функции из предыдущей задачи, взаимно однозначно соответствуют друг другу. Поэтому их количество одинаково. Чему же оно равно? Так как здесь фиксируются значения на двух наборах, то это число равно числу всевозможных двоичных наборов длины 2" — 2, т.е.
равно 2'" ' 5.72. Докажите, что: а) если булева функция сохраняет О, то двойственная для нее функция сохраняет 1; б) функция, двойственная для функции, сохраняющей 1, сохраняет О. 5.73. Подсчитайте число самодвойственных булевых функций от и аргументов: а) сохраняющих О, но не сохраняющих 1; б) сохраняющих 1, но не сохраняющих О.
Решение. Если~(хь ..., х„) сохраняет О, то вычисляем/'"(1, " * 1) = (У(1' -, 1'))' = (У(0, ..., 0))' = 0' = 1, т.е. ~'" сохраняет 1, Отсюда вытекает, что не существует самодвойственных функций, сохраняющих О, но не сохраняющих 1, равно как и сохраняющих 1, но не сохраняющих О. 5.74. Докажите, что среди всех самодвойственных булевых функций от и аргументов число функций, сохраняющих О, равно числу функций, сохраняющих 1.
Найдите это число. Подсчитайте число самодвойственных булевых функций от и аргументов, сохраняющих хотя бы одну из констант 0 или 1. 121 Решение. Из двух предыдущих задач вытекает, что всякая самодвойственная булева функция, сохраняющая О, сохраняет также и 1, а сохраняющая 1 — сохраняет и О. Как нам известно (задачи 5.29, 5.30, 5.33), самодвойственная функция полностью определяется заданием своих значений, принимаемых ею на половине всех наборов значений аргументов. Таких наборов имеется 2" ' штук.
Если при этом функция еще и сохраняет 0 (а значит, сохраняет и 1), то еще один набор значений аргументов оказывается связанным. Это — нулевой набор. В итоге мы можем произвольным образом задать значения на 2"-' — 1 наборах значений аргументов, т.е.
получить 2'" ' ' булевых функций. 5.75. Докажите, что среди всех линейных булевых функций от и аргументов число функций, сохраняющих О, равно числу функций, сохраняющих 1. Найдите это число. 5.76. Докажите, что: а) все монотонные булевы функции, за исключением тождественно равной 1, сохраняют 0; б) все монотонные булевы функции, за исключением тождественно равной О, сохраняют 1. 5.77. Докажите, что если булева функция линейна и монотонна, то она либо не сохраняет О, либо не сохраняет 1, либо само- двойственна. 5.78. Пусть булева функция Яхь хг, хз, х4), существенно зависящая не менее чем от двух аргументов, самодвойственная, линейная, сохраняющая 0 и Я1, 1, О, 1) = 1.
Найдите функцию г"; Р е ш е н и е. Так как по условию функция линейная, то ее можно представить в виде Дхь хг хз х4) = ао + агх1 + агхг + азхз + + а,х4, и так как она самодвойственная, то у нее нечетное число коэффициентов а; = 1 (1~ 0). Значит, данная функция имеет вид ДХ, Х„Х„Х,) = а,Хг+ а, ИЛИЯХ„Х„Х„Х4) = а, Х, + а.Х. + а, Х, + а . первый вариант отйадает, так как фуйкцияь дьолжйа сущеетвенно зависеть по условию не менее чем от двух аргументов.
С учетом того, что ~(1, 1, О, 1) = 1, получаем следующие возможные варианты: Я(хь хг, хз) = а~хг + агхг + азхз' ,6(хг хг~ х4) = а~хг + агхг + а4х4,' Я(х,, хз, х4) = а,х, + азхз + а,х4', ,г4(хг, хз, х4) = агхг + азхз + а4х4 (свободный член равен О, так как функция линейна, самодвойственна и сохраняет 0 одновременно). Найдем значения этих функций на наборе (1, 1, О, 1). Получим а, + аг = 1; а, + аг + а4 = 1; а, + а4 = 1; аг + а4 = 1. Сумма Жегалкина х+ у равна 1 только в случаях„когда х = 1, у = 0 или х = О, у = 1. Значит, ни 1н ни Я~, ни ~4 не могут быть искомой функцией. Остается функциями„у которой а, = а, = а4 — — 1. Следовательно, искомая функция имеет вид: х, + х, + х„. 122 5.79. Докажите, что: а) из всякой булевой функции, не сохраняющей О, отождествив ее аргументы, можно получить функцию от одного аргумента, также не сохраняющую О, т.е.
функцию х' или функцию 1; б) из всякой булевой функции, не сохраняющей 1, отождествив ее аргументы, можно получить функцию от одного аргумента, также не сохраняющую 1, т.е. функцию х' или функцию О. Решение. а) Пусть функция~(хь ..., х„) не сохраняет О, т.е. ДО, ..., 0) = 1. Отождествив все ее аргументы, получим функцию ср(х) = г(х, ..., х). Если Я1, ..., 1) = 1, то ср(х) = 1. Если жег(1, ..., 1) = = О, то ср(х) = х'.
и 6. Полные системы и функционально замкнутые классы булевых функций Полные и неполные системы булевых функций. Система (совокупность) булевых функций Г = (Яь ..., Я называется полной, если всякая булева функция является суперпозицией функций из этой системы. В Учебнике (лемма 10.4 и теорема 10.
5) методом математической индукции доказывается полнота системы (, ~, '). 6.1. Докажите полноту следующих систем булевых функций: а) (, '); б) (~, '); в) (-+, '); г) (,4, '), где х 4' у = (х -+ у)' = = ху', д) (,4, Ц; е) (-+, 0); ж) ( ~ ); з) (4); и) (+,, Ц; к) (+, ~,Ц; л) (++, э 0). Р е ш е н и е. д) Для доказательства достаточно выразить каждую функцию из какой-нибудь полной системы функций через функции 4, 1 из данной системы. Проверьте, что справедливы следующие выражения: х' = 1х' = 1,4 х; х~ у = (х'у')' = 1,4 (х'у') = =1 4 ((1 4 х) э у);ху=ху"=х 4 у'=х 4 (1 4 у).Как известно, система (, ~, ') полна, т.е.
каждая булева функция выражается через, ~ и '. Если в этом выражении выразить далее , ~ и ' через,4 и 1 по указанным формулам, то получим выражение данной функции через,4 и 1. Так будет с каждой булевой функцией. Следовательно, система (,4, Ц полна.
л) Достаточно выразить функции полной системы (, ') через функции ++, з 0 из данной системы. Проверьте, что справедливо следующее выражение: х' = х++ О. 6.2. Докажите неполноту следующих систем булевых функций: а) (, ~); б) (-+, ); в) (-+, ч); г) (~-, '); д) (', Ц; е) (~, +); ж) (+, ++); з) (, ~, -+); и) (, ~, -+, ++); к) ('); л) (++, ').
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
