Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132701), страница 3
Текст из файла (страница 3)
Функции 0 и 1 иногда рассматриваются как нульместные, т.е. зависящие от пустого множества переменных. Символы З, вв, у, еЗ, и т.д., участвующие в обозначениях элементарных функций, называя>тся лоеическима связками (или просто связками). Зафиксируем некоторый алфавит переменных Х (конечный или счетно-бесконечный). Пусть Ф = (у "', уг1"', ... ) множество функциональных символов, где верхние индексы указывают «местность» (арность) символов. Иногда верхние индексы опускаются, но при этом арности предполагаются известными. Определение 1. Формулой над,множеством Ф называется всякое (и только такое) выражение вида: 1) 1"ь и Л(хп, х„, ..., х,„), где 1'ь нульмсстный, а и-местный (и ) 1) функциональные символы и х... х;„..., х,„ переменные из множества Х; 2) 1ы(яч, йг,..., Й,), где 1"„, - - в-местный (в ) 1) функциональный символ и 21, либо формула над Ф, либо переменная из Х.
Зля подчеркивания того факта, что в формуле л' используются только переменные из Х (не обязательно все) или только функциональные символы из Ф (тоже не обязательно все), будем писать соответственно л(Х) и й~Ф]. Иногда формулу вида 1'(х, у) записывают либо как (х1"у), либо как хуу, а формулу г(х) как (ух) или ух. При этом символы у называют связками. В алгебре логики обычно в качестве связок употребляют символы из множества б = (1, Й, Н, Ф,, — э, ~, Ц. Определение 2. Формулой над Ь называется всякое (и только такое) выражение вида: 1) х любая переменная из множества Х; у а Функции алгебры логики.
Операцию еуперпозиции 2) (1й), (йй21), (й~(Ж), (Й921), (й З), (й з З), (Й ~ З)., (Й З аз), где й и яз —. формулы над б. Замечание. Аналогично определяется понятие формулы над любым нспустым подмножеством бз множества 9; п. 1) из определения 2 надо оставить неизменным, а и. 2) видоизменить естественным образом: берутся только связки из Ям и формулы й и З должны быть формулами над бм Обычно принимаются следующие соглашения для сокращения записи формул над множеством связок б: а) внешние скобки у формул опускаются; б) формула (1 й) записывается в виде й; в) формула (й ее Цз) записывается в виде (Й 21) или (Й'.о); г) считается, что связка 1 сильнее любой двухместной связки из множества б; д) связка Й считается сильнее, чем любая другая двухместная связка из множества б.
Эти соглазпения позволязот, например, записать формулу ((((1 х) 9 9 у) (е г) -+ Их Й (1 у))у г)) в вице (х 9 у)г — з (ху у з). Употребляется также «смешанная» запись формул, например, х 9 ~У, г) или хзф(хг, О, хз) З хам(х,, хг, 1) Пусть каждому функциональному символу 1~ * из множества Ф = (Гзш, Д "", ... ) сопоставленанекотоРаафУнкциЯ г,: Вп* — Р— р В = (О, 1). Понятие функции ези, реализуемой формулой й над .множеством Ф, определяется (как и понятие формулы) по индукции: 1) если й = Дуь (х,,:е „ ..., х ), то для всякого набора (оы Оь1 оз, ..., оп,) значений переменных х,, х,, ..., х „значение функции ~ри равно г';(пы оз, ..., оп,); 2) если й = й(уы ..., Уя) = ф(йы йз, ..., Йт), где.
ф 9 Ф и й~ либо формула над Ф, либо переменная из Х, то уи(оы ..., оь) = = Е(А, )дг, ...,. р1т), где Г функция, сопоставленная функциональному символу З", и ~3р ". значение функции еои, (р = 1, 2, ..., тп), причем ыю если Йр — — ую )др = ~ри„(ор,, ..., ор,), если Йр — — йр(ур,,...., ур,) (здесь в зависит, естественно, от р). Если й = у",и* (х,, х:„..., х „), то функция ~ри, реализуемая (пд формулой й, обычно обозначается через У';(х,, х „..., х.„). Если же й = Дйм Йз, ..., Й,„), то ези обозначается через Р(ези, (ум, Узз Уме)' ляг (У21 У22 ° Узег) Фи, (Утз Утз ° Уте ))~ 14 Гл, й Способы задания и свойс1пва функций алгебры логики здесь Р функция, сопоставленная функциональному символу 1, а 1ри (у,1, у,з, ..., у„) — функция, реализуемая формулой й, (1 = =1,2, ..., .т).
Понятие функции дги, ре лизувмой формулой й над множеством связок Ь, вводится (также по индукции) следующим образом; 1) формуле й = х, где х Е Х, сопоставляется тождественная функция дгн(х) = х; 2) ЕСЛИ й = (З 22) ИЛИ й = (Ж л К), Гдс л Е 1 Й, Ч', Ю, -, -Л, /, Ц, то соответственно д1и = 1ов, и 1ои = 01в лвгс (здесь символ л надо понимать уже как обозначение для соответствующей элементарной булевой функции: см.
табл. 1.3 и табл. 1.4). Пусть Й = й(Х1,, ..., х,,), 22 = З(Х1,, ..., х,) и (Х1, хг, ... ..., Хп) МНОжЕСтВО тЕХ ПЕРЕМЕННЫХ, КОТОРЫЕ ВСтРЕЧангтСЯ ХОТЯ бы в ОДНОЙ из формул Й и З, Т.е. (Х1, х2, . ° Хп) — 1хн .. ° Хм) ~-~ 0(Х1,, ..., хд). Формулы й и Ж называются эквивалентными (обозначение; й = З или й = 22), если на всяком наборе (О1, Ог, ...
..., О„) значений пероменных х1, хз, ..., х„значения функций д2и и д1в, реализуемых соответственно формулами й и З, совпадают, т.е. ц1и(оп,..., о;„) = ~р~(О1,, ..., Оз). Пусть Ф множество функциональных символов или логических связок, а Р множество соответствующих им функций. Суперпозицией над,инооквством Р называется всякая функция Е, которую можно реализовать формулой над множеством Ф. Пусть й = й[~~"'1,..., ~~"'1) и 22 = З~д~п'1, ..., д~"'1). Говорят, что формулы й и З имеют одинаковое строение, если формула й может быть получена из формулы З путем замены каждого вхождения функционального символа д, * на символ (1 = 1, ..., в).
Строение формулы отражает индуктивный процесс ее порождения в соответствии с определением формулы (см. определения 1 и 2). Строение формулы можно естественным образом характеризовать диаграммой (специальным графом, являющимся обычно ориентированным графом), вершинам которой приписаны функциональные символы (или логические связки) и символы переменных. Например, если формулы й у(21( (21( й~11( )) 121(( Й ) ф(01)) щ ~ (01 с — д~ 1(х, х), З вЂ” 1"1 1(1о~ ~1(АХ Ч у) 1В 2), у, й1 1(х Й 2)) рассматриваются над некоторым множеством Ф, содержащим логические связки Й, М, ~3 и функциональные символы ~~~1, д1~1, пр1, д11~1 и фу1щ1 (и, возможно, что-то еще), то их строение описывается диаграммами, изображенными на рис.
1.2. у д Функции алгебры логики. Оиерацин суиериозиции 15 у<2) 12) А, Рис. 1.2 Если нужно обратить внимание именно на строение формулы 21 = = 'о[11, ..., Я, то используют запись Ж = С[21, ..., Я. 2. Элементы булева куба. Первичные представления о булевых функциях. Пример 1. Найти номер двоичного набора зо раз т раз т раз Решение. Плина данного набора равна Зт+ 1, а его 1-я компонента равна 1 при 1 = 1, ..., т, пз + 2, ..., 2ьч + 1 и равна 0 в противном случае. Следовательно, З З-1 зо 2т-~-1 ~, ' 2з з-1 — зо ~ 22 з-1 — 1+ ~~, 2з з-1 — 1 з=1 з.=1 У=за-~-2 22елз.
1 [2ззз 1) + 2ы [2ы 1) 2оз [22оз 1-1 2оз 1) Пример 2. Найти двоичный набор, являющийся разложением числа 325 (первая слева цифра в наборе должна быть равна 1). и Решение. Так как р(Н) = 2 оз 2" ', то для нахождения ком- з=1 понент набора а, имеющего номер р(а), можно применить процедуру «последовательного деления с остатком на число 2»: а) ДЕЛИМ у[а) На 2, ОетатОК ЕетЬ аа, а ЧаСтНОЕ З11 = а1 2" 2+...
... + 11, — 2 2+ аи 1,. б) частное д1 делим на 2з остаток равен ао 1, частное 112 = = а1 2и + ... + а„ з делим на 2, остаток равен а„ 2 и т.д. 16 Гл. 1. Способы задания и сводсзпва узуикиий алгебры логики до тех пор, пока на некотором ((и — 1)-м) шаге нс получим частное уи 1 — — о1 и остаток оз. В нашем случае р(Н) = 325. Используем описанную процедуру: 1) делим 325 на 2, находим частное 91 и остаток о„; 91 — — 162, ои = 1: 2) делим 162 на 2, частное равно 81, в остатке О, т. е, ои 1 — — О, 92 =81; 3) делим 81 на 2, за = 40, оо 2 = 1; 4)делим40на2, 94=20, ои з=О; 5) делим 20 на 2, 93 —— 10, ои 4 = 0; 6)делим10на2, с73=5, ои;=0; 7) делим 5 на 2, с12 = 2з ои — в 1; 8) делим 2 на 2, частное равно 1, в остатке О, т.е, о„г — — 0 и оа 3=аз — — 1.
Следовательно, и = 9 и Н = (1з Оз 1, О, О, О, 1, О, 1). зз Замеч анно. Из формулы р(Н) = 2 оз 2" ' видно, что для з=1 получения координаты о, набора Н можно поступать следующим образом: а) используя неравенство 2" 1 < р(Н) < 2",находим и; б) делим р(сз) на 2" 141 и получаем остаток и, = о,.2" ' + + о,41 . 2" ' 1 +...
+ ои 1 2+ ои; в) делим р(Н) на 2"' 1 и получаем остаток г,.е1 = о,4.1 2" ' 1 4-... ..,+пи 1 2+па; г) вычисляем разность т, — гзл 1 и делим ее на 2" Полученное частное и есть значение координаты оо Например, если р(о) = 325 и нужно найти оз (см. пример 2), то имеем; а)2и 1(325<2",значит, п=9,таккак 2 =256<325<2 = 512; б) делим 325 на 23 за1 = 22 = 128, получаем остаток, равный 69; в) делим 325 на 2о 3 = 23 = 64 и получаем в остатке 5; г) гз — гз — — 64, и поэтому оз = 64/64 = 1. Пример 3. Найти двоичный набор длины т, являющийся разложением числа 2'" 1 — 2 (т ) 3).
Решение. Представим число 2и' 1 — 2 в виде суммы степеней двойки: 2т — 1 2 2риз — 2 ц 2(2зи — 3+2т — 4+ +2+1) -2+2 — з+ +22+2 Значит, соответствующий числу 2 1 — 2 двоичный набор длины т таков: (01 ... 10). ш — 2 раз Пример 4. На множестве наборов и — 2 раз и — 3 раз и — 3 раз и — 3 раз и — 3 раз у 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
