Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132709), страница 5
Текст из файла (страница 5)
~(иы хз ..., х„) = = Д(х„, и„..., и,„) при любой подстановке .. ''' ., и > 1; /1 2 ... п1 -)' 8) если функция обращается в 1 на некотором наборе веса й (О < й < и — 1), то она равна 1 и на всяком наборе большего веса (п > 1). 22 Гл, 1. Способы задания и свобства угуикиий алгебры логики 1.7. 1) Булева функция Д(хз) определяется так. Она равна 1 только в тех случаях, когда яз = 1 либо когда выполняется следующее условие: переменные яз и яз принимают разные значения, а значение переменной яс меньше значения переменной яз, в остальных случаях функция обращается в О. Построить таблицы Т(у) и Пз з( г) функции г(хз) и выписать наборы множества Лгу. 2) Булева функция )'(х~) задается следующим образом: она равна О только на таких наборах П = (пы сгз, пз, сел), для которых справедливо неравенство 2оп + скз ) сгз + 2скл, на остальных наборах она обращается в 1. Построить таблицы Т(() и Пз з® этой функции и выписать наборы множества Яу.
3) Пусть наборы (яы хз) и (хз, ял) задают двоичные разложения чисел ис и из соответственно. Обозначим через (в(хл) 1-й разряд двоичного РазложениЯ (уз, ~с) числа ~ос — оз1 1 = 1, 2. ПостРоить прямоугольные таблицы Пз з функций ул(й ) и гз(й ). 4) Па аварийном пульте системы расположены четыре сигнальные лампочки: Вы Лз, Лз, Л4. Система выключается только в том случае, когда выполняется хотя бы одно из следующих условий: а) загорелась лампочка Вы но не загорелась лампочка Вэ; б) загорелись лампочки Вз и Вз, но не горит лампочка Вл, в) загорелась лампочка В4 и не горит лампочка Вп Построить таблицу Т(1") булевой функции 1(х~), характеризующей условия выключения системы, т.е.
Дял) = 1 тогда и только тогда, когда справедливо хотя бы одно из условий а), б), в): при этом предполагается, что х, = 1, если лампочка В, горит, и я, = О, если лампочка В, не горит. 5) Лля оценки гипотез Н1 и Нз проводятся пять разнотипных экспериментов: Аы Аз, Аз, Ал, Аз. Каждый эксперимент упорядочивает гипотезы по предпочтению относительно некоторого признака.
Гипотеза Нз принимается только в следующих случаях: а) в большинстве экспериментов предпочтение отдавалось НП б) в экспериментах А1 и Аз предпочтение отдавалось гипотезе Нз, но в эксперименте Ал предпочтение отдано гипотезе Ны Гипотеза Нз принимается в случаях, когда: в) в экспериментах Аз и Аз предпочтение отдавалось ей, а в экспериментах Ас и Ал гипотезе Нп г) в экспериментах Аг и Аз предпочтение отдавалось гипотезе Нз, а в экспериментах Аз и Ал .. гипотезе Нь Полагаем я, = О, если эксперимент А, «поддерживает» гипотезу Н„и х = 1, если в эксперименте А.
предпочтение отдано гипотезе Нз (у = 1, ..., 5). Записать в виде булевых функций ул, (тв) и Гно(ха) условия принятия гипотез Нг и Нз (1д, (сез) = 1) тогда и только тогда, когда по набору Нз принимается гипотеза Н, (1 = 1, 2). Выяснить, возможна ли такая ситуация, когда окажутся принятыми обе гипотезы. 6) Четырем членам Вы Вз, Вз, Вл некоторой комиссии сформулированы следующие условия посещения заседаний (хотя бы одно из них они должны выполнить): а) в заседании не участвует ни Вы ни Вз, но должен быть Вз, б) в заседании принимают участие Вэ и Вл, но отсутствует Вз, .в) на заседании должны присутствовать Вз и В».
у 1. Функции алгебры логики. Операция гуперпогиции 23 Выяснить, обязан ли присутствовать на заседании комиссии член Вз, если в нем не участвует Вз. 7) Проект принимается, если большинство из шести экспертов Сы ..., Св высказалось в его пользу. Кроме того, проект все же принимается, если указанное условие не выполнено, но за, принятие проекта высказались: а) либо эксперты Сы Сз, Сз, б) либо эксперты Сз, Сл, Св, .в) либо эксперты Сы Св, Св.
Записать в виде булевой функции «" (о в) условие принятия проекта, считая, что оц = 1 в том случае, когда 1-й эксперт высказывается за принятие проекта, и л; = 0 в противном случае. Выяснить, будет ли обязательно принят проект, если известно, что за его принятие высказались ровно трое из экспертов Сы Сз, С4 и Св, а кто-то один из экспертов Сз и Св высказался против. 3. Формулы. Реализация булевых функций формулами. Пример 9. Локазать, что выражения й« = 1л) — «1(1у3гг и йз = (я Ч (1 у)) — «(я оо 1 у) не являются формулами над множеством логических связок (1, 3о, Ч, — «), но что, добавляя скобки, каждое из этих выражений можно превратить в формулу над указанным множеством связок.
Р е ш е н и е. Лля доказательства того, что некоторое выражение й нг явллегпся формулой над каким-то фиксированным множеством Ф (функциональных символов и«или логических связок), достаточно выявить какое-либо свойство, присущее каждой формуле над заданным множеством Ф, но которым не обладает выражение й. Утверждение о том, что любая формула над множеством Ф обладает выявленным свойством, обосновывается обычно по индукции по «сложности» формул (например, по числу связок или по числу функциональных символов, входящих в формулы). В выражении й« вЂ” — 1 я) — «1(1 у во я нарушено несколько свойств, присущих формулам над множеством (1, йо, Ч, -«): а) обе скобки, содержащиеся в йы не имеют парных им скобок; б) отсутствуют внешние скобки; в) не отделена скобками связка — «от остальных связок.
Лобавляя скобки, выражение й«можно превратить, например, в формулу или ((1л) — «(1(1(уйг)))), или ((1 л) — «(1((1 у) 3гг))), или ((1 л) — «((1(1 у)) 3г г)). В выражении йг = (л Ч (1 у)) — «(я Уг1 и) не хватает только двух пар скобок: внешних и отделяющих связку 3о от связки 1. Формула, соответствующая выражению йз, имеет вид ((л«7(1 у)) -«(я й (1 у))). Лля обоснования того, что оба выражения й«и йз не являются формулами над множеством связок (1, 3г, ~«, — «), достаточно, например, установить справедливость такого утверждения: всякая формула над множеством связок (1, оо, 'я', — «), отличная от формул вида л, у, ...., обладает парой внешних скобок.
Показательство этого факта проведем по индукции — — по числу связок 1, ог, Н, — «в формулах. Базис индукции. Если в формуле й только одна связка, то с точностью до переименования переменных (с отождествлением) 24 Гас 1. Способы гадания и сводапва 41упкцпй алгебры логики формула й имеот один из следующих видов; й = (з х), й = (х8с у), й = (х Ч у) и й = (х — э у). Следовательно, базис индукции справедлив. Индуктивный шаг. Предположим, что доказываемое утверждение верно для формул, содержащих не более в связок (в > Ц, и установим его истинность для формул с числом связок, равным .в + 1.
Имеем или й = ( 1 З), или й = (й 8с с), или й = (З 'о' ь), или й = = (Ж вЂ” > к), причем одна из подформул З или С в формулах трех последних видов может быть (с точностью до переименования переменных) формулой, равной х. Очевидно, что индуктивный шаг также справедлив. П р и м е р 10. Построив таблицы функций, реализуемых формулами й= Их4у) — г ((уЮ (тчг)) ~ г)) и 'З = Ихчу) (х — э (у® 63 (х бс г)))), выяснить, эквивалентны ли эти формулы. Решение. Принимая во внимание тот факт, что функция т — > у обращается в 0 только на наборе (1, 0), а функция х ).
у равна 1 а б л и ц а 1 5 лишь на набоРе (О, 0), мы можем УпРостить пропедуру построения таблипы функции воя(х, у, г), реализуемой формулой й. В самом деле, угя = 0 тогда и только тогда, когда х ). у = 1 и (у Ю (х М г)) ~ г = О, т.е, когда х=у=О и (Оео(ОЧг)) ~г= = г ) г = г = О. Следовательно, сои = 0 только при х = у = 0 и г = 1 (табл.
1.5). Таблицу функции 1от(х, у, г), реализуемой формулой 21, будем строить шаг за шагом (табл. 1.6). Таблица 1.6 Сравнивая таблицы функций воя и сох, видим, что ря ф уьл. Значит, формулы й и З неэквивалентны. Пример 11. Используя основные эквивалентности (см. и. 3 после задачи 1.20), установить эквивалентность формул й = (х ). у) э (хг — э Пх ~ (у г)) Ч (х у 9 г))) В = Их -э у) ~ (х ). 1у ))) '1 у Решение.
Применяя основные эквивалентности 8,в), 9,а) и 9, б), получаем й = х Ч у Ч хгЧ (х(у г) Ч (ху 9 г)). Используя затем основные эквивалентности 7,д), 4, а), 8,б) и 8, а), имеем й = (х Ч у) Ч Ч (х Ч у) Ч ((х Ч (у Юг)) Ч ((х ~у)ся Чхуг)). Палее применяем основ- у Д фрикции алгебры логики. Оиерация едвериозиции 25 ные эквивалентности 2, 7,в), 7,д), 1, 3 и 8,а): г« = х «7д 'и' з ««уя Н1«г Ч ' ' хз Ч дз '««хр ж Накопал, воспользовавшись правилом поглощения 5, а), приходим к соотношению й = х 'о' у ««г. Преобразуем теперь к такому же виду и формулу «л«.
Имеем Ж = (х ««д)х Ч уд ««у Ч я (здесь были использованы основные эквивалентности 8, в), 9, а), 9, б) и 4, а)). Па- лее, применяя основные эквивалентности 4, а), 7,.д) и 4, б), получаем З = хр ««' х о дз Ч у ««з. С помощью закона поглощения 5, а) последнее выражение преобразуется к такому: и «7д ««ж Тем самым эквивалент- ность формул Й и З доказана. 1.8.
Выяснить., какие из нижеприводимых выражений являются формулами над множеством логических связок 8 = (1, 8е, «7, Ю, -, — «) . Проверить, можно ли некоторые из приведенных ниже выражений (и какие), не являющиеся формулами над Я, превратить в формулы, добавляя скобки: 1) х — «хц 2) х«7(1у); 3) хб«(йу); 4) (х««д) — «(х~р(1з)): 5) (х е- у); 6) (х 8е) 1 х; 7) (х В (г)): 8) 1(т †« (( 1 х) ух у)); 9) (х у) 1у; 10) ((х — «(1у)) ((хь'(у3ег))вд)); 11) (1х — «у); 12) ((х 8е (1 х)) ' ' (х 9 (х — «х)) Ч (1 х)). 1.9.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
