В.И. Игошин - Задачи и упражнения по математической логике и теории алгоритмов - 2007 (1019105), страница 24
Текст из файла (страница 24)
Это и означает, что рассмотренная функция такова, что большему набору значений аргументов соответствует большее значение функции. Следовательно, данная функция действительно монотонна. 5.49. Найдите все монотонные булевы функции от одного аргумента. Найдите все монотонные булевы функции от двух аргументов. Р е ш е н и е.
Ясно, что монотонными булевыми функциями от одного аргумента будут функции О, х, 1. Для нахождения всех монотонных булевых функций от двух аргументов сначала укажем порядок на множестве упорядоченных пар, составленных из 0 и 1: 00 < 01, 00 < 10, 00 < 11, 01 < 11, 1О < 11, пары 01 и 10 несравнимы. Теперь воспроизведем таблицу значений всех функций от двух аргументов и выделим полужирным шрифтом для каждой функции те ее значения, для которых нарушается монотонность: Следовательно, монотонными будут функции: йа(х, У) = О, й,(х, у) = ху, 8з(х„у) = х й(х у) = у л7(х у) = х ~ у, ам(х, у) = 1.
115 5.50. Найдите все монотонные булевы функции от трех аргументов. Сколько имеется таких функций? 5.51. Приведите пример монотонной булевой функции от четырех аргументов. 5.52. Выясните, какие из следующих булевых функций монотонны: а) худ; б) (х+ у)~+ (х+ ~)', в) (хмуч~)(х'чуч фхчуч~') г) ху~+ х~; д) х'у '~'ч х'у~' ч ~у'~' ~ ху~'ч ху~; е) ху(~+1)+ ~; ж) х'у~' ч ху'~ г (х'у'+ х'+ у); з) х'(у + ~) ~ ((х' м у ч ~) -+ лу~) ч х((у — э ~) + 1); и) (х'науч я)(х '4уч 2)(ха/у ч я )(х очу ч ~); к) ху~+ ху+ хх+ у~+ х+ у+ ~; л) (х ~у')(х"чу'дч х'у~ч ху'~'. Р е ш е н и е. л) Прежде всего составим таблицу значений данной функции: Из таблицы видно, что, например, для наборов (1, О, 0) и (1, О, 1) имеет место неравенство: (1, О, 0) ( (1, О, 1), а для соответствующих значений функции выполняется противоположное неравенство: 1 = у(1, О, 0) > у(1, О, 1) = О.
Следовательно, данная функция не монотонна. Для обозрения всех случаев нарушения монотонности можно также воспользоваться наглядным методом диаграмм, описанным при решении задачи 5.48. Диаграммы для данной функции имеют следующий вид: 116 но ощ ооо 5.53. Проверьте монотонность конъюнкции от л аргументов и монотонность дизъюнкции от л аргументов. 5.54. Функция большинства (или мажоритарная функция) от л аргументов — зто такая булева функция, которая принимает значение 1 на таких и только на таких наборах (ан ..., а„) значений аргументов, в которых большинство аргументов принимают значение 1.
Докажите, что функция большинства монотонна. 5.55. Докажите, что суперпозиция монотонных функций есть функция монотонная. Р е ш е н и е. Целесообразно пояснить идею доказательства этого утверждения на примере функций от небольшого числа аргументов. Так, если Я~(х, у), 6(хь х2), Я~(хп х2) — монотонные булевы функции и (ап аа) < (~ь ~)з), т.е.
а~ < Ць аг < 'ръ то рассмотрим функцию фхп х2) = ЯЯх~, х2), Яхн х2)), являющуюся су" перпозицией данных. В силу монотонности Я, и Я, имеем Яаь о2) ~ Л(Р~ Р2) и Уз(аь аз) «,6(Рп ~)г), а в силу монотонности я имеем $(<~о «~) =ЛЧ~(<~ь <~з) ~з(пь «2)) ~ ХЧ2(Д~ Д2)*~зФ~ Д2)) = а(р! Р2) 5.56. Докажите, что для всякой монотонной булевой функции ,7; не являющейся константой, справедливо следующее разложение: 7(хо ..., х„ь х„) = ~р(хь ..., х„,)х„«у(хь ..., х„,), где д, Ч~ — монотонные функции. Решение. Найдем для Уее СДН-форму и вынесем из всех конъюнктивных одночленов с одной стороны переменную х„, а с другой — х„'.
Получим разложение Яхь ..., х„„х„) = ~р(хь ..., х„,) . х„~ у(х„..., х„,)х„', где ~р(хь ..., х„,) = 7(х,, ..., х„„1), ч~(хь -> хп-~) =.7(хь " э «л-о О). Функции ч и у монотонны в силу предыдущей задачи как суперпозиции монотонных функций 7'и 1, О (константы — монотонные функции). Покажем, что в данном случае имеет место более сильное представление: Яхь ..., х„н х„) = <р(хь ..., х„~)х„ч у(хь ..., х„,).
(ь) Для этого докажем, что справедливо равенство х„~р ~х„'у =х„~р ~ и у. В самом деле, сравним множества наборов, на которых обра- 117 щаются в нуль левая и правая части этого равенства. Если на некотором наборе (аь ..., а„ь а„) обратилась в нуль правая часть, то ад(ап..., а„~) = 0 и у(аь..., а„) = О. Но тогда а„'у(аь..., а„,) = = О, и левая часть также обращается в нуль. Обратно, пусть теперь на наборе (ап ..., а„ь а,) равна нулю левая часть.
Тогда а„у(аь ..., а„~) = О. Покажем, что ЧКаь ..., а„,) = О. В самом деле, у(а„ ..., а„~) = Яаь ..., а„ь О) < ~(ан ..., а„н а„) = 0 (неравенство — в силу монотонности функции ~). Поэтому у(ап ..., а„~) = О. Таким образом, и правая часть обращается в нуль. Следовательно, доказываемое равенство действительно имеет место, а вместе с ним справедливо и разложение (*). 5.57. Докажите, что булева функция, не являющаяся тождественной константой, будет монотонной тогда и только тогда, когда ее можно представить в виде суперпозиции конъюнкций и дизъюнкций.
Р е ш е н и е. В силу задачи 5.55 и монотонности функций коньюнкции и дизъюнкции (задача 5.49) достаточность имеет место. Доказательство необходимости проведем индукцией по числу л аргументов булевой функции. При и = 0 имеются лишь функции- константы; при л = 1 добавляется еще функция х = х ~ х, которая выражается через дизъюнкцию (как, впрочем, и через конъюнкцию). Предположим, что утверждение справедливо для монотонных функций от п — 1 аргумента. Пусть Дхп ..., х„„х„) — монотонная булева функция от л аргументов, не являющаяся константой. Тогда по предыдущей задаче справедливо разложение ~(хо ..., х„н х„) = <р(хь ..., х„~)х„ч у(хн ..., х„~). Предположим сначала, что ~р и у также не являются константами. Тогда, поскольку они монотонны и зависят от л — 1 аргумента, то по предположению индукции каждая из них представима в виде суперпозиции конъюнкций и дизъюнкций.
Из приведенного разложения видно, что этим свойством обладает и функция ~ Теперь рассмотрим случаи, когда одна или обе функции ~р и у являются константами. Заметим, что в силу монотонности )"имеем <р(хь...,х„~) = Ах„...,х„„1) > ~(хп ...,х„п О) = у(хн ...,х„~).
Поэтому если <р = О, то Ч~ = 0 и ~= О, что не так. Если у = 1, то Г"= 1, что невозможно. Если у = 0 и ~р = 1, то Яхн ..., х„) = х„. Если же у = 0 и у не является константой или у = 1, а у не является константой, то из предположения индукции и из рассматриваемого разложения также следует доказываемый результат. Ясно, что к этому результату можно прийти, используя двойственные соображения, в частности в задаче 5.56 можно получить двойственное соотношение (начав с СКН-формы для г). Проведите эти рассуждения самостоятельно.
Таким образом, в данной задаче приведено исчерпывающее описание всех монотонных функций. 118 5.58. Докажите, что функция, двойственная монотонной булевой функции, сама монотонна. Р е ш е н и е. Пусть |' — монотонная функция. Если 2 — константа, то двойственная ей функция есть другая константа (задача 5.20) и, следовательно, также монотонна. Если ~ — не константа, то по предыдущей задаче она есть суперпозиция конъюнкций и дизьюнкций. Но мы знаем (задача 5.20), что функция, двойственная для конъюнкции, есть дизъюнкция, а двойственная для дизъюнкции — конъюнкция.
Следовательно, функция, двойственная для суперпозиции конъюнкций и дизъюнкций, будет снова суперпозицией дизъюнкций и конъюнкций и потому будет также монотонной. Это утверждение можно также доказать и непосредственно, исходя из определений двойственной и монотонной функций. 5.59. Верно ли утверждение: если булева функция зависит существенно более чем от одного аргумента и линейка, то она не- монотонна? 5.60.
Существуют ли булевы функции, являющиеся одновременно линейными и монотонными? Если да, то приведите примеры таких функций и охарактеризуйте все такие функции. 5.61. Верно ли утверждение: если булева функция зависит существенно более чем от одного аргумента и монотонна, то она несамодвойственна? 5.62. Существуют ли булевы функции, являющиеся одновременно самодвойственными и монотонными? Если да, то приведите примеры таких функций и охарактеризуйте все такие функции. 5.63. Существуют ли булевы функции, являющиеся одновременно линейными, самодвойственными и монотонными? Если да, то приведите примеры. 5.64. Пусть имеется произвольная немонотонная булева функция от и аргументов (л > 3). Докажите, что, отождествив подходящим образом ее аргументы, можно получить немонотонную функцию от трех аргументов.
Р е ш е н и е. Пусть |' — немонотонная функция и наборы а = (ао ..., а„) < ~3 = (~3о ..., ~3„) таковы, что~(ао ..., а„) > Я3о ..., Д„), т.е. Яа,, ..., а„) = 1, Щ„..., )3„) = О. Разобьем переменные х„..., х„ на три группы. В первую включим такие переменные хь что а; = О, 0; = 1; во вторую — такие хь что а; = ~3; = 0; в третью — такие х;, что а;= О, = 1. (Поскольку а < р, то не может быть такого, что а;= 1, а б; = 0.) Отождествим переменные внутри каждой из этих групп: подставим вместо каждой переменной первой группы х, второй— у, третьей — Г. Тогда получим немонотонную функцию 9(х, у, Г), так как ср(0, О, 1) = 1, ср(1, О, 1) = О. 5.65.
Приведите пример немонотонной булевой функции от трех аргументов, любое отождествление аргументов которой приводит к монотонной функции. 119 Р е ш е н и е. Примером такой функции может служить следующая: х+ у+ ~. Отождествление любых двух ее переменных приводит к функции от одного аргумента, совпадающей с этим аргументом. Например, х+ у+ у = х+ 0 = х. Такая функция уже монотонна. 5.66. Показать, по суперпозицией любой немонотонной функции и констант можно получить отрицание. Решение. Если Яхь ..., х„) — любая немонотонная функция, то согласно задаче 5.64 получим из нее немонотонную функцию от трех аргументов ~р(х, у, х).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
