В.И. Игошин - Задачи и упражнения по математической логике и теории алгоритмов - 2007 (1019105), страница 23
Текст из файла (страница 23)
имеют виды (ао ..., а„) и (а'„..., а„'). Следовательно, самодвойственная булева функция на противоположных наборах принимает разные значения, т.е. ее таблица значений антисимметрична относительно средней линии. Тогда из функций, приведенных в задаче 5.29, самодвойственными будут лишь функции в), е), и). 110 5.31. Сколько существует самодвойственных булевых функций от трех аргументов? Найдите все такие функции.
Сколько из них существенно зависят от всех своих аргументов? 5.32. Приведите примеры самодвойственных булевых функций от четырех аргументов. У к а з а н и е. Здесь следует воспользоваться результатом задачи 5.30 о строении таблицы значений самодвойственной функции: составить таблицу значений какой-нибудь самодвойственной булевой функции от четырех аргументов, а затем, используя нормальные формы, найти выражение для этой функции.
5.33. Сколько существует самодвойственных булевых функций от и аргументов? Р е ш е н и е. Воспользовавшись результатом задачи 5.30 о строении таблицы значений самодвойственной функции, обратите внимание на то, что самодвойственная функция полностью определяется заданием значений, принимаемых ею на половине всех наборов.
Причем значения ее на наборах этой половины могут быть заданы произвольно. Таким образом, поскольку всего двоичных наборов длины л имеется 2" штук, то половина их составляет 2"-' штук, а самодвойственных функций будет столько, сколько имеется двоичных наборов длины 2" ', т.е. 2'" ' штук. 5.34. Подсчитайте число таких булевых функций от и аргументов, двойственные функции для которых совпадают с их отрицанием. Р е ш е н и е. В силу результата задачи 5.29 двойственная функция для г" совпадает с ее отрицанием Г"', если Г" на симметричных (т.е. противоположных) наборах принимает равные значения. Таким образом, каждая такая функция определяется своими значениями на половине наборов длины и, т.е. на 2" ' наборах, а общее число таких функций 2 " '. 5.35.
Подсчитайте число самодвойственных булевых функций от л аргументов, существенно зависящих от всех своих аргументов. 5.36. Докажите, что всякая самодвойственная булева функция от л аргументов принимает одинаковое число раз (т.е. на одинаковом числе наборов значений аргументов) значения 0 и 1. Ре шеи не. Поскольку для самодвойственной булевой функции г'справедливо соотношение ~(а1, ..., а„') = (У(аь ..., а„))', то из него видно, что если?" на одном из двух наборов (а„..., а„) или (а,', ..., а„?) принимает значение О, то на другом ее значение равно 1. 5.37.
Для произвольной булевой функции ~(хь ..., х„) от и аРгУментов опРеделим фУнкцию от п + 1 аРгУментов 8(хе, х„..., х„) = = хаен ..., х„) ч хат'(х'„..., х„'). Докажите непосредственным вычислением, что функция я(х~, х„..., х„) самодвойственна. 5.38. Докажите, что множество всех определенных в задаче 5.37 функций 8 для всевозможных булевых функций?'от л аргументов 111 есть множество всех самодвойственных булевых функций от л + 1 аргументов. 5.39.
Докажите, что: а) различные булевы функции имеют различные двойствен- ные функции: ~~ я ~,1'" ~ я*; б) ~-+ я = 1 тогда и только тогда, когда я* -+ У* = 1; в) (,1'")* =~; г) (.1')* = (~); д) (1 я)~ =1~ ч К*," е) (~+ 4)~ = ~'" ++ а~; ж) (У а)* =У*+ а*; з) (~-+ я)' = у*- и) (г" ~ й)' = ~*,1 4', к) (У4 а)* =У*! а*' л) (.1 ч Ю)* =У~ ' Ю~. Р е ш е н и е. а) Вытекает из результата задачи 5.29 о получении столбца значений функции~, исходя из столбца значений функ- ции ~. б) Докажем сначала, что (~-+ «)' = (й" -+ ~*)'. Вычисляем двой- ственную функцию: (гахн ..., х„) -+ я(хн ..., х„))' = (г(х,', ..., х„') -+ я(х,', ..., х„'))' = = (1'(х,', ..., х„') ч я(х1, ..., х„'))' =г""(х(, ..., х„')я'(х1, ..., х„') = = (~'"(х„..., х„))'я*(хн ..., х„) = (~(хн ..., х„) ч (я*(хь ..., х„)) )' = = (я'(х„..., х„) -+ ~'(хь ..., х„))'.
Тогда из )"-+ я = 1 следует, что (я" — ~ ~")' = 1' = О, откуда я' -+ -+ ~'" = 1. в), г) Проверяются непосредственными вычислениями. л) Вычисляем двойственную функцию: (Дхо ..., х„) ч л(хн ..., х„))* = (г(х,', ..., х„') ч я(х1, ..., х„'))' = ~'(х1, ..., х„') . л'(х1, .-, х„') = ~'"(хь ..., х„) . я*(хн ..., х„).
5.40. Докажите, что если булевы функции Дхн ..., х„) и я(хн ..., х„) самодвойственны и г(1, х„..., х„) = 4(1, х„..., х„), то г"= я. Решение. Покажем, что Дан иц ..., а„) = я(ин ин ..., а„) для любого набора (ан ан ..., а„). Если а~ = 1, то зто верно по условию. Пусть и, = О. Тогда ЯО, а„..., а„) = г'(1, аг, ..., а'„) = = й'(1, а1, ..., а„) = я(О, ан ..., а„). следовательно, ~= я. 5.41. Докажите, что функция, двойственная линейной, также линейна. 5.42.
Докажите, что функции, двойственные булевой функции второй или третьей степени, есть функции той же самой степени. 5.43. Докажите, что переход к двойственной булевой функции не меняет степени функции. 5.44. Существуют ли булевы функции, одновременно являю- щиеся самодвойственными и линейными? Если да, то охаракте- ризуйте все такие функции. 112 5.45. В произвольной несамодвойственной булевой функции так отождествите ее аргументы, чтобы получилась несамодвойственная функция от возможно меньшего числа аргументов.
Каким может быть это число? Покажите, что всегда можно получить несамодвойственную функцию от двух аргументов. Дальнейшее уменьшение числа переменных, вообще говоря, невозможно. Р е ш е н и е. ПустьЯх„..., х„) — несамодвойственная функция. Это означает, что найдется такой набор (а„..., а„), для которого Лаь ..., а„) =Да[, ..., а„'). Разобьем переменные х„..., х„на две группы. В первую включим те переменные хь для которых а; = 1, во вторую — те переменные хь для которых а; = О. Отождествим между собой все переменные первой группы, переименовав их в у„а также все переменные второй группы, переименовав их в уь Получим функцию от двух аргументов ф(уь уз) (она может оказаться функцией от одного аргумента, если (а„..., а„) — нулевой или единичный набор).
Ясно, что ф(1, 0) = )(ао ..., а„), ф(0, 1) =г(а1, ..., а„'). Поэтому ф(1, 0) = ф(0, 1), а значит, ф(ун у1) — несамодвойственная функция. Может оказаться, что дальнейшее отождествление переменных с сохранением несамодвойственности невозможно. Примером служит несамодвойственная функция ху, единственно возможное отождествление переменных в которой приводит к само- двойственной функции х.
5.4б. Докажите, что из суперпозиций произвольных несамодвойственных функций и отрицания можно получить константы 0 и 1. Р е ш е н и е. В силу предыдущей задачи 5.45 можно ограничиться случаем несамодвойственной функции от двух аргументов ф(х, у). Пусть ф(а, р) = ф(а', Р'). Рассмотрим тогда функцию ч~(х, у) = = ф (х", у ), где х = х, если а = 1, и х" = х', если а = О, т.е. ф есть суперпозиция функции ф и отрицания х'.
Поскольку а" = О Р = 1, то ф(1, 1) = ф(0, 0). Отождествим у функции ф(х, у) переменные х, у получим функцию от одного аргумента т(х) = ф(х, х). Для нее имеем т(1) = т(0), т.е. т(х) — константа (О или 1). Подставляя эту константу в х', получаем другую константу (1 или соответственно О). Монотонные булевы функции. Упорядочим множество (О, 1), полагая 0 < 1. Поскольку нам придется иметь дело с функциями от нескольких переменных, введем отношение частичного порядка в множестве двоичных наборов одной и той же длины.
Пусть а = (ао ..., а„) и б = ((3ь ..., 0„) — двоичные наборы. Тогда а меньше ~3 (обозначение: а < О), если а; «О; для всех 1, причем по крайней мере для одного )имеет место строгое неравенство. Будем писать а «р, если а < ~3 или наборы а и О совпадают. Булева функция?(хп ..., х„) называется монотонной, если для всяких наборов а = (а„..., а„) и О = (Ць ..., ~3„), таких, что а «О, имеем,г"(аь ..., а„) «Я~31 " 0 ).
113 5.47. Выясните, сравнимы ли два данных набора, и если сравнимы, то какой из них меньший? а) (О, 1, 0), (1, О, 0); ж) (О, 1, О, 0), (О, 1, О, 1); б) (О, 1, 1, 0), (О, 1, О, 1); з) (1, О, О, 1, 0), (1, О, 1 ,1, 0); в) (1, О, О, 1), (1, О, 1, 1); и) (О, 1, О, О, 1), (О, 1, О, 1, 0); г) (1, 1, 0), (1, О, 0); к) (1, О, 1), (1, О, 0); д) (О, 1), (1, 0); л) (О, 1, 1, 1), (О, 1, О, 0). е) (1, О, 0), (1, О, 1); Р е ш е н и е.
л) Сравним первые элементы данных наборов: 0 = О. Сравним вторые: 1 = 1, третьи: 1 > О, наконец, четвертые: 1 > О. Так как каждый элемент первого набора больше или равен соответствующему элементу второго набора (причем есть неравные элементы), то имеем (О, 1, 1, 1) > (О, 1, О, 0). 5.48. Докажите монотонность следующих булевых функций: а) худ чх'угч худ', б) худ + ху + х~; в) хучх~чуг; г) (хчучг)(хну'чг)(хчучг')' д) хуг+х+уг; е) худ ч (худ + ху); ж)(хчуч~)(х 'чучг)(хчу 'че)(хчуч ~)(х'чу'чг)(хчу'ч г); 3) хугчхуе чхугчхуя; и) хугчх~чу~; к) ху+ (х+у); л) (хчуч4~(х ч уч ~)(хчу ч г).
Решение. л) Сначала составим таблицу значений данной функции: Теперь посмотрим, каково отношение порядка на множестве упорядоченных троек, составленных из нулей и единиц: 000 < < 001, 000 < 101, 000 < 010, 000 < 110, 000 < 011, 000 < 100, 000 < 111, 001 < < 011, 001 < 101, 001 < 111, 010 < 110, 010 < 111, 010 < 011, 011 < < 111, 100 < 101, 100 < 110, 100 < 111, 101 < 111, 110 < 111, 011 < 111.
114 Данное отношение порядка удобно изобразить с помощью диаграммы (слева), на которой меньшая тройка изображена соответствующей точкой ниже большей, и от нее к большей тройке (точке диаграммы) идет восходящая линия: 11в 1 шо На параллельной такой же диаграмме (справа) в узлах изображены значения данной функции при соответствующем этому узлу наборе значений аргументов. Видно, что ни в какой части полученной диаграммы 1 не оказалась расположенной ниже О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
