§ 5. Решетка и булевы алгебры

Булева алгебра является одним из математических объектов, с которыми мы уже сталкивались во введении. Мы покажем, что существует не одна булева алгебра, а много. Следовательно, любое преждевременное исполь­зование этого объекта может привести к недоразумению. Тем не менее мы начнем изучение с введения более общей структуры, называемой решеткой.

Некоторые из решеток имеют важное значение в аб­страктной теории вычислений, возникшей из понятия ап­проксимации. Одна программа аппроксимирует другую, если она осуществляет те же самые вычисления на под­множестве данных, доступных той программе. Если же рассматривать результат работы программы как множе­ство, то одна программа аппроксимирует другую, когда для некоторых входных данных она выдает' в качестве результата подмножество В ⊆ А, где А — множество вы­ходных данных второй программы. Это достаточно про­стые и, вероятно, очевидные способы аппроксимации про­грамм. При этом возникает множество элементов, свя­занных некоторым отношением порядка.

Вычисление является результатом выполнения про­граммы (на некоторых данных), которая написана на ка­ком-либо языке (см. гл. 8). Для общности рассмотрений свойства вычислений падо выводить не в терминах рас­сматриваемой программы, а в терминах языка, используе­мого для записи программы. В то же время мы должпы быть в состоянии определить результат выполнения про­граммы «язык X» с помощью формального определения. К сожалению, количество деталей, требующихся для описания даже простых примеров, достаточно велико и, следовательно, ничего не определяет. Однако в п. 5.1 мы дадим теоретические обоснования некоторых ключевых результатов. Это будет следовать (п. 5.2) из формаль­ного использования булевой алгебры, а затем (п. 5.3) из краткого рассмотрения некоторых общих приложений.

5.1. Решетки. Напомним! что бинарное отношение р на множестве S является частично упорядоченным от­ношением, если оно рефлексивно, транзитивно и анти­симметрично. Следовательно, (S, ρ) — частично упорядо­ченное множество, и, если не возникает двусмысленно­сти, р можно записать как ≤, а (S, ≤) обозначить про­сто через s. Частично упорядоченное множество называ­ется линейно упорядоченным (или цепью), если для любых х, у ∊ S или х ≤ у, или у ≤ х, или же выполнены оба эти отношения. На самом деле любой частичный порядок можно представить в виде объединения линей­ных порядков. Поэтому возникает естественный и по­лезный способ изображения отношений порядка.

Заметим, что любое конечное, линейно упорядоченное множество (А, ≤) можно представить следующим об­разом:

а₁ ≤ а₂ ≤... ≤ а_n,

здесь рефлективность и транзитивность не требуют дока­зательств. Легко видеть, что рис. 5.7 является «очевид­ным» представлением (A, ≤). Другими словами, мы за­писываем А как (а₁, а₂, ... , а_n)

Предложение. Частичное упорядочение на ко­нечном множестве может быть представлено как объеди­нение линейных порядков на некоторых подмножествах.

20

Рис. 5.8

Рис. 5.7

Доказательство этого факта оставляем в качестве уп­ражнения. //

Используя этот результат, можно представить любой частичный порядок (конечный или бесконечный, однако бесконечные отношения сложно изобразить на конечных листах бумаги за конечное время!) изображением мно­жества соответствующей цепей. Полученная диаграмма называется диаграммой Хасса.

Пример 5.1. Отношение ρ = {(х, у): х — множи­тель у}, определенное на множестве (1, 2, 3, 4, б, 10, 12, 20), дает диаграмму Хасса (изображенную на рис. 5.8) и может быть разбито на линейно упорядоченные под­ множества {(1, 2, 4, 12), (1, 3, 6, 12), (2, 6), (4, 20), (2, 10, 20)}. Этому разбиению эквивалентно следующее множество линейных порядков: {(2, 6, 12), (1, 3, 6), (1, 2, 10, 20), (2, 4, 20), (4, 12)}. Заметим, что по срав­нению с отношениями, изображенными на диаграммах в § 2 гл. 2, хотя 1ρх для всех х ∊ {1, 2, 3, 4,6,10,12, 20}. па этом рисунке отсутствуют восемь стрел, выходящих из 1. Это достигается неявным представлением свойств рефлективности и транзитивности. //

Пусть дано (А, ≤) и В ⊆ А. Разумно задать вопрос: будет ли В ограничено сверху (снизу) элементами мно­жества А? Далее мы можем искать наименьшую верх­нюю грань (наибольшую нижнюю грань), которая обо­значается sup (inf) (читается супремум (инфимум)). Эти понятия были полностью определены в § 5 гл. 2. Будем их использовать для характеристики решетки.

Определение. Решеткой называется частично упорядоченное множество (A, ≤), в котором каждая па­ра элементов имеет супремум и инфимум. Для заданных x, y ∊ A эти грани будем записывать следующим об­разом:

x /\ у = inf ({x, y}), х \/ у = sup ({x, у}). //

Не всякое частично упорядоченное множество явля­ется решеткой. Например, частично упорядоченное мно­жество из примера 5.1 но является решеткой, поскольку 12V20 не определено.

Определив операции Д и V между парами элементов в частично упорядочеппом лшожестве, расширим это по­нятие естественным образом. Положим

/\X = /\_х∊Х х = inf X, \/X = \/ _х∊Х х = sup X,

Это обозначает sup X и inf X конечного непустого мно­жества X.

Легко показать, что существует много специальных видов решеток, в которых можно производить различные операции. Ограничимся рассмотрением трех таких типов.

Определение. Решетка L, обозначаемая (L, /\, \/), дистрибутивна, если она подчиняется дистрибутив­ным законам

для всех х, у, z е Г,. S

Не все решетки являются дистрибутивными,

Пример 5.2. Решетка, изображенная на рис. 5.9, не является дистрибутивной, поскольку

b /\ (d \/ c) = b /\ e = b,

тогда как

(b /\ d) \/ (b/\c) = a \/ a=a. //

Предложение. Пусть в дистрибутивной решетке (L, /\, \/) выполнены соотношения

x \/ y = x \/ z x /\ y = x /\ z

Тогда у = z.

Доказательство. Сначала заметим, что из определения inf и sup

а ) а/\b = b/\а, a\/b = b\/a;

б) а/\b ≤ а ≤ а\/b;

в) (a/\b) \/c

Поэтому

//

Определение. Предположим, что (L, /\, \/) — решетка и 0, 1 ∊ L такие, что 0 ≤ х ≤ 1 для всех (об элементах 0 и 1 скажем немного позже). Тогда

X \/ 1=*1, х /\ 1 = х, х /\ 0 = 0, х \/ 0 = х

для любого х ∊ L. Такая решетка называется решеткой с дополнениями, если для любого х ∊ Z, существует х ∊ L в такой, что

х /\ = 0, х \/ = 1

( называют дополнением х). /

Предложение. Если (L, /\, \/)— дистрибутивная решетка с дополнениями, го дополнения единственны.

Доказательство. Предположим, что х, у, z ∊ L и

х \/ у = х \/ z(=1), х /\ y = х /\ z(=0).

Тогда из предыдущего предложения следует, что y = z.//

Третий, и последний специальный тип решеток, кото­рый мы определим, необычен в том смысле, что он не дает нам ничего нового для конечных решеток. Чтобы подчерк­нуть ключевой момент исследования, дадим другое опре­деление решетки в форме предложения.

Предложение. L является решеткой тогда и толь­ко тогда, когда \/Х и /\Х существуют для любого непу­стого конечного подмножества X из L.

(Этот факт можно доказать индукцией по числу эле­ментов множества X; оставляем его в качестве упраж­нения,) //

Если L — решетка и в ней определен элемент /\L, то он обозначается символом 0 и называется наименьшим элементом L. Аналогично, если в L существует элемент \/L, то он обозначается символом 1 и называется наи­большим элементом L; по определению /\ = 0.

Определение. Решетка L называется полной, если \/X и /\Х существуют для всех подмножеств X из L. //

Все конечные решетки являются полными. Рассмот­рим, однако, множество Q с обычным отношением по­рядка ≤ и бесконечное множество аппроксимаций числа π, каждое из которых имеет на один десятичный внак больше. Верхняя грань этой последовательности, очевид­но, есть π, однако π ∊ R\Q, и, следовательно, (Q, ≤) не является полной решеткой. Решетка (R, является полной, и Q ⊆ R,

Можно показать, что любая решетка может быть рас­ширена до полной решетки, однако мы не будем зани­маться этим вопросом.

5.2. Булевы алгебры. Мы уже интенсивно занимались алгеброй множеств и упоминали об относительно «логич­ной» арифметике. Сейчас дадим формальное определение общей булевой алгебры, названной так в честь матема­тика XIX в. Дж. Буля. Алгебра множеств — это част­ный случай булевой алгебры, и, хотя различные булевы алгебры структурyно подобны, следует заметить, что не все они включают в себя множества обычным образом.

Определение. Булевой алгеброй называют мно­жество B вместе с тремя операциями \/, /\ и ^- (\/ на­зывают операцией или, /\ — операцией или, — опера­цией дополнения или же операцией не; кроме того, пер­вые две операции часто называют дизъюнкцией и конъ­юнкцией соответственно). Бинарные операторы \/ и /\ и унарный оператор ^- (обычно записывается над операн­дом, например ) вместе с двумя различными элемента­ми B, которые обозначаются символами 0 и 1, удовлет­воряют следующим аксиомам.

Для произвольных элементов а, b и с в B:

a) a \/ b = b \/ a;

б) a \/ (b \/ с) = (а \/ b) \/ с;

в) a \/ 0 = а;

г) a \/ = 1; д) а /\ b = b /\ а; е) a /\ (b /\ с) = (а /\ b) /\ с;

ж) а /\ 1=а; з) а /\ а = 0; и) а /\ (b\/с) = (а /\ b) \/ (а /\ с);

к) a \/ (b/\ c) = (a \/ b) /\ (a \/ c).

Таким образом, и и или коммутативны, ассоциативны и дистрибутивны одна по отношению к другой. Каждая из этих операций имеет единичный элемент, и, когда элемент комбинируется вместе со своим дополнением посредством и/или, в результате получается единица по отношению к или/и соответственно.

Названия операторов, использованные выше, являют­ся именами, которые непосредственно связаны с компь­ютерной логикой, используемой при построении схем. В других булевых алгебрах может быть более подходя­щим читать \/ как объединение, наименьшая верхняя грань или supremum, а /\ как пересечение, наибольшая нижняя грань или infimum. (Иногда операцию /\ обо­значают также &). //

Булеву алгебру можно определить как дистрибутив­ную решетку с дополнением. Поэтому по аналогии с бу­левой алгеброй (ρ(X), , , ') для данного непустого множества X из результатов предыдущего параграфа можно вывести ряд следствий. Доказательства некоторых из них оставлены в качестве упражнений. Наиболее важ­ными из этих следствий являются следующие.

Инволютивный закон (или закон двойно­го отрицания). Дополнение дополнения х, x ∊ B (т. е. в рассматриваемой булевой алгебре), есть х.

Закон поглощения. Для любых а, b ∊ В спра­ведливы соотношения

a /\ (a\/b) = a, a \/ (a/\b) = а.

Закон идемпотентности. Любой элемент B идемпотентен по отношению к операциям Д и V.

Законы де Моргана. Для любых а, b ∊ В спра­ведливы соотношения

Из инволютивного закона и законов Моргана следу­ет, что если мы берем булеву алгебру B (более точно (B, /\, \/, ^-)) и образуем новую систему или путем отображения каждого х ∊ B в , или использованием операций /\ и \/, то (B, /\, \/, ^-) также булева алгебра. Этот факт известен как принцип двойственности. Дей­ствительно, каждый из законов Моргана может быть получен из других путем отображения каждого элемента в его дополнение.

Сейчас мы выведем теорему, которая показывает, в какой стандартной форме могут записываться булевы выражения; непосредственным следствием этого является утверждение, что достаточно двух операторов, чтобы описать все бинарпые функции. Как всегда, введем вна­чале необходимую терминологию.

Определим две общеупотребительные логические связ­ки следующим образом. Говорят, что булевы формулы А и В эквивалентны (записывается в виде А В или А В), если они выражают одну и ту же функцию. В простейшем случае это — отношение эквивалентности.

Таблица 5.3

А	В	А В
0	0	1
0	1	1
1	0	0
1	1	1

Аналогично говорят, что формула А имплицирует фор­мулу В (записывается*) А → В), если имеют место ус­ловия, изображенные в табл. 5.3. (Таблицы такого тана часто называют таблицами истинности.)

Заметим, что стрелки используются во многих различ­ных контекстах. Поэтому надо обращать особое внима­ние на расшифровку их значения. Таким образом, А → В это то же самое, что и (⌐А) \/ В это то же самое, что и (А → В) /\ (B → A). Логически А → В означает «если А, то В» (т. е. если А справедливо, то В также справедливо и обычно так и читается. Дру­гие названия для символов → и это условный и без­условный операторы соответственно.

Обычно вводят операции, которые обозначают отрицания бинарных связок, такие, как

А В=⌐(А В), А В = ⌐(А /\ В),

А В=⌐(А В), А В = ⌐(А \/ В),

Сейчас можно описать все бинарные операции {0, 1}² → {0, 1} (здесь стрелка находится между двумя множе­ствами и, следовательно, обозначает множества, которые являются областью определения и множеством значений; не следует путать с логическим оператором -»-) в крат­кой форме, как показано в табл. 5.4. Более того, мы

Таблица 5.4

А	0 1 0	1	Функция	А	0 1 0	1	Функция
В	0 0 1	1		В	0 0 1	1

f8		0	0	0	0	0	f8	1	0	0	0	А В
f9		0	0	0	1	A /\ B	f9	1	0	0	1	А В
f10		0	0	1	0	В ↛ А	f10	1	0	1	0	⌐А
f11		0	0	1	1	В	f11	1	0	1	1	А → В
f12		0	1	0	0	А ↛В	f12	1	1	0	0	⌐B
f13		0	1	0	1	А	f13	1	1	0	1	В → А
f14		0	1	1	0	А≢В	f14	1	1	1	0	A В
f15		0	1	1	1	А \/ В	f15	1	1	1	1	1

можем описать все отображения из {0, 1}² в {0, 1}, ис­пользуя только или только (первая из них называ­ется штрихом Шеффера и обозначается «|»; в вычисли­тельном контексте t называют «не и», а называют *) «не или»). Заметим, что операции и являются удоб­ными сокращениями, но они, например, неассоциативны. Следовательно, по определению A В С есть ((A /\ B)' /\ С)', а, например, не ((А/\В)'/\С)'. Говорят, что множества операторов { } и { } адекватны. Сейчас мы сформулируем теорему и дадим ее конструктивное дока­зательство, т. е. не только докажем справедливость ут­верждения теоремы, но и дадим метод получения резуль­тата.

Теорема. Любое отображение {0, 1}² → {0, 1} мо­жет быть представлено в виде формулы, содержащей только оператор или только оператор .

Пример 5.3. Получим представление для функции f, используя только операцию ; таблица истинности функции f дана в виде табл. 5.5.

Таблица 5.5

x	y	z	f	x	y	z	f
0	0	0	0	1	0	0	1
0	0	1	1	1	0	1	1
0	1	0	1	1	1	0	0
0	1	1	0	1	1	1	1

5.3. Некоторые приложения булевой алгебры. Суще­ствует ряд проблем, например в комбинаторике, которые можно решить наилучшим образом в подходящей буле­вой алгебре. Другой путь применения булевой алгебры заключается в моделировании реальной ситуации, или, другими словами, в интерпретации булевой алгебры в терминах, относящихся к рассматриваемой задаче.

Э тот метод может быть применен в областях, которые так широко распространены, что у них отсутствует клас­сификация. Мы рассмотрим только одно приложение, а именно комбинационные и переключательные схемы). Другие области приложений будут представлены в виде отдельно выбранных.С этой точки зрения необходимо подчеркнуть, что мы занимаемся только некоторыми вопросами построения и преобразования схем; формальное исследование лежит за пределами этой книги. Сначала давайте посмотрим, как выражения булевой алгебры могут быть использованы для описания и определения схемы, состоящей из про­водников и переключателей. Схема, изображенная па рис. 5.10, состоит из пяти переключателей, источника питания, лампы и соединяющих проводников. Из диа­граммы нетрудно видеть, что ток течет по замкнутой цепи тогда и только тогда, когда переключатель А зам­кнут и (или) переключатели В и С оба замкнуты

или переключатели D и Е оба замкнуты. Алгебраически это можно записать в виде

.

П еред тем как продолжить изложение, сделаем не­сколько замечаний о представлены элементов электри­ческих схем с переключателями в виде диаграмм. Един­ственный сегмент схемы, в котором будет отличие между рассматриваемыми примерами,— это верхняя часть схе­мы, содержащая переключатели; следовательно, можно не изображать остальной части схемы. Внутри схемы не­которые переключатели могут быть взаимосвязаны (рпс. 5.11, а) и, возможно, могут работать так, что когда один переключатель включен, то другой должен быть выключен и наоборот (рис. 5.11, в). Основные методы расположения переключателей — это последовательный (рис. 5.11, с), что соответствует связке и (т. е. A /\ B), и параллельный (рис. 5.11, d), что соответствует связке или (т. е. А \/ В), Отметим, наконец, что на диаграмме есть совершенно лишние переключатели, и их для удоб­ства можно обозначать теми же «именами» (рпс. 5.11, е).

Таким образом, любую операцию в булевой алгебре можно представить при помощи схемы и наоборот. Сле­довательно, для получения эквивалентных схем надо перейти от первоначальной схемы к соответствующему ей выражению в булевой алгебре, затем к «более про­стому» (или более желаемому) выражению и, наконец, к схеме, соответствующей этому выражению.

Пример 5.4. Упростить схему, изображенную на рис. 5.12. Этой схеме соответствует следующее выражение:

М ы уже уделили достаточно внимания схемам с пе­реключателями. Перейдем теперь к комбинационным схемам. Основные компоненты таких схем — элементы. В наиболее общей форме элемент является устройством, имеющим n входов и m выходов (m, n ∊ N), На каждый вход может подаваться один из двух бинарных сигналов; представим их как 0 и 1, однако любая другая система из двух различных значений также нам подходит. В ре­альной ситуации обычно мы имеем сигналы в окрестно­сти 0 вольт (например, от 0 до 0,8 вольта), которые представляются нулем, и в другой окрестности — в рай­оне 4 вольт (скажем, между 3 и 5 вольтами), которые представляются единицей. Отсюда определяются выход­ные значения (0 и 1). Можно ожидать, что нам понадо­бится достаточно много различных элементов, чтобы представить все возможные функции {0, 1}² → {0, 1}, однако, как мы увидим далее, это не так. Схемам, не име­ющим временных задержек (в дальнейшем только такие схемы мы и будем рассматривать), соответствует един­ственный тип элементов. Однако это не очевидно. Струк­тура схем станет более ясной, если вначале мы рассмотрим три типа элементов, изображенных на рис. 5.14. Самым

Р ис. 5.14

простым является элемент не; его действие определяется тождеством

с = ⌐ а (с = не a), определяемым табл. 5.6.

Таблица 5.6

INPUT(a)	OUTPUT(c)
0 1	1 0

Элементы и и или могут также иметь несколько вхо­дов; в этом случае они определяются аналогично, т. е. выходной сигнал элемента и равен 1 тогда и только тогда, когда на всех входах сигнал равен 1, и выходной сигнал элемента или равен 1 тогда и только тогда, когда какой-либо из входных сигналов равен 1. Алгебраически выходной сигнал элемента не имеет вид: (входной сигнал), выходной сигнал элемента о имеет вид: ⌐ (сиг­нал первого входа) ∧ (сигнал второго входа) ∧… и, наконец, выходной сигнал элемента или имеет вид: (сиг­нал первого входа) ∨ (сигнал второго входа) ∨… Чтобы представить более сложные функции, элементы мож­но «соединять» различными способами.

Пример 5.5. Рассмотрим схему (более точно, часть схемы, которая нас интересует), изображенную на

Рис. 5.15

рис. 5.15. Возвращаясь «назад» от выходов схемы, по­лучаем

х = ((a∨(a ∧ b’))∧(y)) ’,

y = (b ∧ c) ’

Поэтому

x = (((a ∨ a) ∧ (a ∨ b’)) ∧ (b ∧ c)’)’ = ((a ∧ (a ∨ b’)) ∧ (b ∧ c)’)’ = (a∧(b∧c)’)’

(по закону поглощения). Таким образом, одно из возможных упрощений схемы изображено на рис. 5.16. //

Рис. 5.16

Следовательно, мы можем использовать булевы вы­ражения для анализа и упрощения сложных схем. Рас­смотренный пример показывает, как можно осуществлять такие операции.

Существуют также устройства, которые реализуют другие логические операции. Наиболее важными явля­ются элементы ие и и не или; опи изображены на рис. 5.17. Используя множество таких элементов, при помощи булевых выражений можно получить требуемую схему непосредственно по таблице истинности.

Пример 5.5 (продолжение). Не останавливаясь на формальностях, заметим, что каждое выражение в скоб­ках в окончательной форме f (см. выше) представляет вход для последнего элемента на рис. 5.18 и может быть вычислено с помощью элементов предшествующего ряда

Р ис. 5.17

(Части схемы, обведенные штриховыми линиями, практи­чески не требуются, поскольку для многих электрических элементов дополнение к выходу также доступно из вспомогательного выхода.) Отметим, что полученная схе­ма в общем случае не будет минимальной в смысле чис­ла используемых элементов. //

В завершение рассмотрим два примера, которые пока­зывают, как булева алгебра может быть использована в задачах иного рода.

Рис. 5.18

Пример 5.6. Предположим, что справедливы следу­ющие утверждения:

а) знание структур данных необходимо для совер­шенствования дисциплины ума;

б) только опыт программирования может создать дис­циплинированный ум;

в) для того чтобы написать компилятор, надо иметь возможность анализировать задачи;

г) недисциплинированный ум не может анализиро­вать задачи;

д) всякий, кто писал структурные программы, может рассматриваться как опытный программист.

Можно ли из этих предположений определить спра­ведливость нижеследующих утверждений:

а') опыт написания структурных программ необхо­дим для того, чтобы быть в состоянии написать ком­пилятор;

б') знание структур данных является частью опыта программирования;

в ) анализ задач невозможен теми, кто игнорирует структуры данных;

г') опытный программист, который писал структур­ные программы, в состоянии анализировать задачи и имеет дисциплинированный ум, является программистом, который мог бы написать компилятор?

Чтобы ответить на эти вопросы, мы могли бы иссле­довать логические следствия утверждений, однаки для того, чтобы проиллюстрировать используемую техпику в более сложных ситуациях, воспользуемся нашим знани­ем булевой алгебры. Сначала необходимо закодировать наши утверждения. Пусть

E— множество всех программистов,

U — те из них, кто знает структуры данных,

V—те из них, кто имеет дисциплинированный ум,

W — те из них, кто является опытными программи­стами,

X — те из них, кто мог бы написать компилятор,

Y — те из них, кто может анализировать задачи,

Z — те из них, кто может писать структурные про­граммы. Тогда имеем

a) U б) W ; в) X ;

г) V ⊇ Y; д) W Z;

a') Z ⊇ X; б') U ⊇ W; в') U;

г') W∩Z∩Y∩V⊇X.

Теперь видно, что а') непосредственно следует из в), г), б) и д) до транзитивности; аналогично в') следует из г) и а). Также

W∩Z∩Y∩V = W∩Y∩V = Y∩V = Y⊇ X

Таким образом, г') также справедливо. Утверждение б') не может быть выведено из а)—д), поскольку мы только внаем, что W Z, и цепочка на этом заканчивается. //

Пример 5.7. Алиса сказала, что Барбара и Клара говорят правду, а Клара сказала, что Элспет и Фиона или обе говорят правду, или обе лгут. С другой стороны, Деби считает, что по крайней мере или Алиса, или Бар­бара говорят правду, тогда как Барбара утверждает, что только одна из двух — Алиса или Фиона — была правди­вой. Элспет считает, что Алиса и Барбара всегда говорят правду, однако Фиона уверена, что Барбара и Клара обе не могли сказать правду. Кому мы должны верить?

Рассмотрим множество утверждений вида «Алиса (не) говорит правду», «Барбара (не) говорит правду»,

в пусть А содержит только те утверждения, в которых Алиса говорит правду. Пусть В, С, D, Е и F определены аналогично. Тогда, если S — непустое множество пересе­чений таких, что

S ⊆ A ∩ B’ ∩ C,

то S включает утверждения, в которых

«Алиса говорит правду», «Барбара лжет»,

«Клара говорит правду».

Из первого утверждения следует, что можно вывести следующий факт: если Алиса говорит правду, то же самое делают Барбара и Клара. Это можно закодировать следующим образом:

если х ∊ А, то x ∊ B ∩ C;

следовательно,

ПРЕДИСЛОВИЕ 7

ВВЕДЕНИЕ 8

ГЛАВА 1. МНОЖЕСТВА 11

§ 1. Множества н их спецификация 11

§ 2. Простейшие операции над множествами 17

§ 3. Диаграммы Венна 24

§ 4. Подмножества и доказательства 27

§ 5. Произведения множеств 36

ГЛАВА 2. ОТНОШЕНИЯ 39

§ 1. Основные понятия 40

§ 2. Графические представления 44

§ 3. Свойства отношений 48

§ 4. Разбиения и отношения эквивалентности 50

§ 5. Отношения порядка 54

§ 6. Отношения на базах данных и структурах данных 57

§ 7. Составные отношения 65

§ 8. Замыкание отношений 68

ГЛАВА 3. Функции 71

§ 1. Функции и отображения 71

§ 2. Обратные функции и отображения 75

§ 3. Мощность множеств и счетность 76

§ 4. Некоторые специальные классы функций 86

§ 5. Аналитические свойства вещественных функций 95

§ 6. Операции 110

ГЛАВА 4. ОСНОВНЫЕ ПОНЯТИЯ АРИФМЕТИКИ 120

§ 1. «Малая» конечная арифметика 120

§ 2. «Большая» конечная арифметика 125

§ 3. Двоичная арифметика 131

§ 4. Логическая арифметика 137

ГЛАВА 5. АЛГЕБРАИЧЕСКИЕ СТРУКТУРЫ 141

§ 1. Алгебраические структуры и подструктуры 142

§ 2. Простейшие операционные структуры 145

§ 3. Кольца и поля 148

§ 4. Линейная алгебра 160

§ 5. Решетка и булевы алгебры 180

§ 6. Замкнутые полукольца 202

ГЛАВА 6. МАТРИЦЫ 205

§ 1. Матрицы и бинарные отношения на конечных множествах 205

§ 2. Матрицы над другими алгебраическими структурами 212

§ 3. Матрицы и векторные пространства 216

Глава 7. Теория графов 227

§ 1. Вводные понятия 227

§ 2. Маршруты, циклы и связанность. 236

§ 3. Планарные графы 241

§ 4. Структуры данных для представления графа 248

§ 5. Обход графа 252

§ 6. Ориентированные графы 257

ГЛАВА 8. ЯЗЫКИ И ГРАММАТИКИ 273

§ 1. Основные понятия 273

§ 2. Грамматики с фразовой структурой 281

§ 3. Контекстно-свободные языки 292

§ 4. Понятия грамматического разбора и грамматических модификаций 298

§ 5. Грамматики операторного предшествования 314

ГЛАВА 9. КОНЕЧНЫЕ АВТОМАТЫ 318

§ 1. Общие понятия 319

§ 2. Конечные автоматы 337

§ 3. Регулярная алгебра 349

ГЛАВА 10.КОМПЬЮТЕРНАЯ ГЕОМЕТРИЯ 358

§ 1. Системы координат для подмножеств R³ 360

§ 2. Преобразования 366

§ 3. Кривые и поверхности 387

Как и раньше, А = и Е = , и поэтому Алиса и Элепет никогда не говорят правду. Из (2а), (4а) и (6а) следует, что F = E. Таким образом, из (За) и (4а) получаем D = В = F = E, откуда с помощью подстановки в (2а) сле­дует С = .

Отсюда следует, что возможно только одно утвержде­ние такое, что

х∊ ' ;

это означает, что Алиса, Клара и Элспет лгут, а Барба­ра, Деби и Фиона говорят правду. //

Упражнение 5.5.

1. Показать, что в булевой алгебре (B, *, +, ') для х, у, z ∊ B справедливы соотношения:

а) (х + y) * (х'+у)*=у;

б) (z + x) * (z' + y) = (z * y) + (z' * x);

в) ((x * z) + (y * z')) ' = (x' * z) + (y' * z');

2. Доказать, что если в (B, *, +, ') выполняются со­отношения х * у = х * z и х + у = х + z, то у = z.

3. Из схем, изображенных на рис. 5.19 и 5.20, полу­чить «простые» схемы, эквивалентные исходным.

4. Получить алгебраическое представление схемы, изо­браженной на рис. 5.21, и дать табличное представление выходов х и у в зависимости от значений а и b на входе. Использовать две такие схемы для построения схемы,

соответствующей функции, определяемой табл. 5.8. Свя­зать это с арифметикой из § 3 гл. 4.

5. Построить схему, реализующую операцию не и, ко­торая имеет четыре входа и выдает на выходе 1 тогда и

Рис. 5.21

только тогда, когда все входы равны 0.

6. Пусть выполнены указанные здесь условия:

а) все гонщики импульсивны;

б) все хорошие программисты меланхоличны;

в) никто не может быть и импульсивным и меланхо­личным;

г) читатель меланхоличен.

Таблица 5.8

	Входы		Выходы			Входы			Выходы
P	Q	R	S	T	P		Q	R	S T
0	0	0	0	0	1		0	0	0 1
0	0	1	0	1	1		0	1	1 0
0	1	0	0	1	1		1	0	1 0
0	1	1	1	0	1		1	1	1 1

Является ли читатель хорошим программистом и/или гонщиком?

7. Организаторы международной конференции по компьютерам решили, что для того, чтобы на встрече не доминировали коммерческие интересы, будет только один магазин, которым будут пользоваться вместе все произ­водители компьютеров. Сами производители будут ответ­ственны за определение того, кто принимает участие в представительстве. Десять компаний — пять европей­ских и пять американских — дали знать, что они хотят принять участие в конференции. (Обозна­чим эти компании через А, В, С, D, Е и F, G, Н, I, J соответственно.) Однако из-за обязательств цо контрактам и торговой политики должны появиться раз­личные ограничения. Европейские предписания требуют, чтобы G и I не могли одновременно принимать участие в конференции; аналогично не могут одновременно принять участие F, G и Л Ограничения американских производи­телей исключают участие А и D, пока G не примет уча­стия; аналогично исключаются С и D. Если Е присутст­вует на конференции, то должно присутствовать и J, од­нако если они принимают участие вдвоем, то В не может быть там. И наконец, В и С не могут вместе принимать участие в конференции.

Может ли быть достигнуто соглашение, по которому по три компании из каждой группы могут собраться вме­сте, не нарушая условий? Если так, то кто именно примет участие?