Гаврилов Г.П., Сапоженко А.А. - Задачи и упражнения по дискретной математике, страница 2

Поэтому полезно бывает знать основные принципы и методы комбинаторного анализа. В главу згП1 включен не только традиционный комбинаторный материал (перестановки, сочетания, свойства биномиадьных коэффициентов, принцип включения-исключения, возвратные последовательности, рекуррентные соотношения, производящие функции), но и современные разделы комбинаторной математики (теория Пойа, асимптотические оценки и неравенства). В главе 1Х затронуты вопросы, относящиеся к минимизации булевых функций. Здесь представлены задачи о свойствах булева куба, характеризациях дизъюнктивных нормальных форм, алгоритмах на множествах д.н.ф. Глава Х содержит задачи по реализации булевых функций схемами из функциональных элементов, контактными схемами и формулами.

Для удобства читателя авторы сочли целесообразным поместить в каждом параграфе необходимые теоретические справки. Многие задачи снабжены ответами и указаниями. К сожалению, ограниченный объем не позволил включить подготовленные нами подробные указания и решения задач среднего и высокого уровней трудности. По происхождению материал, включенный в задачник, весьма разнообразен. Есть и «фольклорные» задачи., есть задачи, возникшие при обработке журнальных статей, отдельные задачи заимствованы из других руководств. Основная часть задач придумана авторами при подготовке к семинарским занятиям и проведению экзаменов по дискретной математике, а также при написании данного пособия и ранее вышедшего сборника задач.

При написании настоящего пособия мы пытались учесть все замечания, которые были высказаны нам коллегами и читателями, приславшими свои отзывы о содержании «Сборника задач по дискретной математике». Всем им мы выражаем искреннюю бла|юдарность. В заключение отметим, что работа над пособием распределялась следующим образом: главы 1, П1-У, а также у 1, 2 главы У1 и ответы ко всем этим главам и параграфам написаны Г.П. Гавриловым, главы П, Ъ'П Х, а также з 3 главы Ъ'1 и ответы к ним написаны А. А.

Сапоженко. Г. П. Гаврилов, А. А. Сапоженко Глана 1 СПОСОБЫ ЗАДАНИЯ И ПРОСТЕЙШИЕ СВОЙСТВА ФУНКЦИЙ АЛГЕБРЫ ЛОГИКИ З 1. Функции алгебры логики и способы их задания. Операция суперпозиции 1. Основные понятия и факты, связанные с булевым кубом и булевыми функциями. Набор (а!, оз, ..., оп), где о! Е (О, Ц, 1 < ! < и, называется булевым или двоичным набором (вектором). Элементы набора часто называют компонентами или координатами. Кратко набор 1аз, ав, ..., ов) обозначают через а" или а. Число и называется длиной набора а". Весом (или нормой) набора б" (обозначение йб" (~) называют число его координат, рави ных 1, т.е.

йб" (! = 2 аь !=! Множество всех двоичных наборов длины и образует и-мерный йулее 1или двоичный) куб, который называют также единичным п-мерным кубом и обычно обозначают В~ (а иногда Езв). Применяя геометрическую терминологию, наборы а" е В" называют вершинами куба В". Множество всех вершин куба В", имеющих вес к, называется к-м слоем кдйа В" (обозначение Вг). Каждому двоичи ному набору а" можно сопоставить число и1а") = 2 о, 2"' ' !=1 номер набора а". Набор о" является двоичным разложением своего номера и(а"). Расстоянием (Хэмминга) между вершинами а и В куба В" па.- в зывается число р(о, !э) = 2 )а! — В!); оно равно числу координат, в г=! которых наборы а и 11 отличаются друг от друга. Расстояние Хэннинга являотся метрикой, а куб В" метрическим пространством. Наборы а = 1аз, аз, ..., а„) и,З = (В!, Вз,...,,9„) из В" называются соседними, если р(а, В) = 1, и протиеоиолоэкными, если р1Н,,З) = п, т.е.

соседние наборы различаются только в одной координате, а противоположные во всех координатах. Говорят, что 1О Гл. 1. Способы задания и свойства функций алгебры логики 1111 111 1110 110 011 11 10 01 00 0011 001 100 0001 000 В4 вг Рис. 1.1 порядком на множестве В". На рис. 1Л приведены диаграммы частично упорядоченных множеств В, В и В . Функция У'(ты ..., т„), определенная на множестве В" = 10, 1)" и принимающая значения из множества 10, 1), называется функцией алгебры логики (а также булевой или булевской функцией). Набор символов переменных (ты ..., т„) будет обозначаться также через й" или х, а множество тех же символов переменных через Х". Множество всех булевых функций, зависящих от переменных ть, ..., та, будем обозначать через Рд(Ха). При этом обычно полагают, что н > О. Нульместными булевыми функциями (т.е.

соответствующими и = 0) являются константы 0 и 1. Булеву функцию 1" 1й") при и > 1 можно задать таблицей Т(Г) (табл. 1.1)., в которой наборы Н = (оы ог, ..., о„ы о ) выписываТаблица 1.1 ются в порядке возрастания их номеров (сверху вниз). Имея в виду такое стандартное расположение наборов, булеву функцию у(ть) набор Н" предшествует набору )3" (или не больше набора Вл), и применяют обозначение Н" 4 В", если сн < Д для всех 1 = 1,..., и. Если 5„4 р„и Н" ~ Д", то говорят, что набор На строго предшесгпвует набору 13" (или строго меньше, или меньше набора )3"), и используют обозначение Н" -~ В". Наборы Н" и Д" называются сравнимыми, если либо На < р'ь, либо Дь 4 Н". В случае, когда ни одно из этих отношений не выполняется, наборы Н" и 13" называются несравнимыми.

Говорят, что набор На непосредственно иредиьествувт набору Д", если Н" -~ Д" и р(о", Д") = 1. Отношение 4 (его часто называют отношением нрвдшествования) является частным у 1. Функции алгебры логики. Операцию суперпогиции удобно задавать вектором ее значений: й~~ = (ое, оы ..., ог г), где координата о, равна значения> функции 1(х") на наборе й, имеющем номер 1 (1 = О, 1,..., 2" — 1). Символом Ху обозначают множество (й" ~ (й" Е В") аг (1(й") = = 1)), т.е. множество всех наборов йп из В", на которых функция 1" (х") обращается в 1.

Булеза функция 1(хп) при п > 2 может быть задана прямоугольной таблицей Пап ь(() (табл. 1.2), в которой значение Дом ..., оя, Таблица 1.2 хй»1 хь-;-г функции у(х") помещается на пересечении «строки» (оы ..., оь) и «столбца» (овьы ..., оп), 1 ( к < п.

Булевы функции, задаваемые табл. 1.3 и табл. 1.4, будут считаться элементарными. Таблица 1.4 Т аблица 1.3 Приведем обозначения и названия этих функций. 1. Функции О и 1 называются соответственно (пюждественнььм) нулем и (тождественной) единицей. 2. Функция ~г называется тождественной функцией и обозначается через х. З.Функция уг называется огприцанием х, обозначается х или Зх (читается «не х»).

4.Функция (з называется коньюнкцией хг и хг, обозначается хг аг хг или хг хг, или хгхг, или шш (хы тг) (читается «хг и хг»). 12 Гл, 1. Способы задания и ввойсгпва функций алгебры логики 5. Функция Д называется дизъюнкцией хз и хг, обозначается хг М хг или хз + хг, или щах(хы хг) (читается «хг или хг»). 6. Функция 1ь называется суммой по модулю 2 хз и хг, обозначается хз Ю тг или хз + хг (читается «хг плюс хг»). 7. Функция 1в называется эквнваленцией (или эквивалентностью) хз и хг, Обозначается хз хг или хз = хг, или хз (-) тг (читается «хг эквивалентно хг»).

8. Функция 1г называется импликацией хз и хг, обознютется хг — э хг или хз Э хг (читается «хз имплицирует хг» или «из хг следует хг»). 9. Функция гв называется штрихом Шеффера хз а хг, обозначается хз ~ хг (читается «не хг или не хг» или «хз и хг не совместны»). В технической литературе функция хг ~ хг называется обычно анти- конъюнкцией или «нс — и». 10. Функция 1э называется стрелкой Пирса хз и хг, обозначается хз «хг (читается «ни хы ни хг» или «не хг и не хг»). В технической литературе функция хг ь хг обычно называется антидизъюнкцией или «не — али» (а также функцией Даеевра и функцией Бебба).

Функции 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 должны быть формулами над бм Обычно принимаются следующие соглашения для сокращения записи формул над множеством связок б: а) внешние скобки у формул опускаются; б) формула (1 й) записывается в виде й; в) формула (й ее Цз) записывается в виде (Й 21) или (Й'.о); г) считается, что связка 1 сильнее любой двухместной связки из множества б; д) связка Й считается сильнее, чем любая другая двухместная связка из множества б. Эти соглазпения позволязот, например, записать формулу ((((1 х) 9 9 у) (е г) -+ Их Й (1 у))у г)) в вице (х 9 у)г — з (ху у з). Употребляется также «смешанная» запись формул, например, х 9 ~У, г) или хзф(хг, О, хз) З хам(х,, хг, 1) Пусть каждому функциональному символу 1~ * из множества Ф = (Гзш, Д "", ...