Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 4
Текст из файла (страница 4)
Ргфлексивное и транзитивное замыкание отношения Р на множестве А обозначается через Я" и определяется следующим образом: (1) аР'а для всех аЕ А; (21 аР*Ь, если аР'б; (3) в Р' нет ничего другого, кроме того, что содержится там в силу (1) или (2). Если определить Р', сказав, что аР'Ь тогда и только тогда, когда а=Ь, то аР*Ь тогда и только тогда, когда аРГЬ для некоторого | ~ О. Единственное различие между Р' и Р" состоит в том, что аР'а истинно для всех аЕ А, но аР'а может быть, а может и не быть истинным.
Р" — это наименьшее рефлексивное и транзитивное отношение, включшощее Р. В равд. 0.5.8 мы изучим методы эффективного построения рефлексивного и транзитивного замыкания отношения. Л здесь докажем, что Р'" и Р' — наименьшие надмножества отношения Я, обладающие нужными свойствами. Теорема 0.2. Если Р' и Р* — сооа|ветственно транзитивное и рефлексивно-транзитивное замыкание санси|ения Р, то (а) Р+ транзигаивно и если Р' — любое транзитивное отношение, для которого Р.= Р', то Р" с:- Р'1 (б) Р' рефлексивно и транзитивно и если Я' — л|обое рефлгксивное и транзитивное отношение, для которого Ры Р', то Р*=- Р'.
Д о к а з а т е л ь с т в о. Докажем только (а); утверждение (б) оставим в качестве упражнения. Во-первых, чтобы показать, что Р+ транзитивно, нужно показать, что если аР ьЬ и ЬР'с, то аР~с, Так как аР" Ь, существует такая последовательность элементов до ..., сГ„, что д,Рд„..., с(„ГРд„, где Г(, =-а и Г(„=ь. так как ЬР+с, то можно найти такие е„..., е,„, что е,Ре„..., е ГРе, где е, =Ь=с|, и е =с. Отсюда, используя определение Р", заключаел|, что аР'с. Теперь покажем, что Р+ — наименьшее транзитивное отношение, включающее Р. Пусть Р' — любое транзитивное отношение, для которого Р ~ Р'. Надо показать, что Р': — Р'.
Пусть (а, Ь) Е Р ', т. е. аЯ Ь. Тогда существует такая последовательность с„..., с„, что а =- с„б =- с„и с;Рс,, для 1:. | < а. Так как Р ~ Р', получаем с|Р'с|„, для 1:.!< а, Так как Р' травзитивио, повторное применение определения транзитивности дает 19 гл. о. ппадввпитнльныз млтвмлтичнские сваднния с,)с'с„, т. е. а)с'Ь. Поскольку (а, Ь) — произвольный элемент из )с+, мы показали, что каждый элемент из Й' принадлежит сс'. Таким образом, )с~:= )с', что и требовалось доказать.
Д ОАЛ. Откошанкя порядка Важный класс отношений образуют отношения порядка. Вообще говоря, порядок на множестве А — это любое транзитивиое отношение на А, При изучении алгоритмов важную роль играет специальный тип порядка, называемый частичным. Множество, на котором задан какой-нибудь порядок, называется упорядоченным, Определение.
Частичным порядком па множестве А называется отношение )с, определенное на А и такое, что (1) )с транзитивяо, (2) для всех а Е А утверждение асса ложно '), т. е. отношение )с ир ресйлекси он о. Из свойств (1) и (2) следует, что если а)сЬ истинно, то Ь)са ложно. Это свойство называется асимметричностью. Пример О.о. Примером частичного порядка служит собственное включение множеств. Например, пусть 5 ==. (е„..., е„)-- множество, состоящее из и элементов, и пусть А =У(5). Поло~Ь жим аДЬ для любых а, Ь из А тогда и только тогда, когда а Ь. Отношение )с является частичным порядком.
ол. основныв понятия твопии множвств В литературе частичным порядком иногда называют то, что мы называем рефлексивным частичным порядком. Определение. Рефлексивным чаапичным порядком на А пазы- вается отношение )с, обладающее слсдующими свойствами: (1) Й транзитивно, (2) )с рефлексивно, (3) если а)сЬ и Ь)са, то а=Ь.
Последнее свойство называют антисимметричнсстью. Примером рефлексивного частичного порядка служит (не обязательно собственное) включение множеств. В равд. О.б мы покажем, что каждый частичный порядок можно представить графически в виде структуры, называемой ориентированным ациклическим графом. Важный частный случай частичного порядка — линейный порядок. Определение. Линейный порядок )с на множестве А — это такой частичный порядок, что если а и Ь принадлежат А, то либо айЬ, либо Ыа, либо а=-Ь. Если А — конечное множество, то линейный порядок )с удобно представлять себе, считая все элементы множества А расположенными в виде последовательности а„а„..., а„, для которой аЯа тогда и только тогда, когда 1С1 Аналогично можно определить рефлексивный линейный порядок, а именно Я вЂ” рефлексивный линейный порядок на А, если )с' — такой рефлексивный частичный порядок, что а)сЬ или Ьйа для всех а и Ь из А.
Например, отношение < (меньше), определенное па множестве неотрицательных целых чисел, является линейным порядком. Примером рефлексивного линейного порядка может служить отношение (. Рнс. 0.4. Честннный порядок На рнс, 0,4 графически изображен этот частичный порядок для случая 5 = (О, 1, 2). Множество 5, собственно включает 5, то. да и только тогда, когда существует направленный вниз путь, ведущий из 5, в 5,. ') Под „айЬ ложно" понимается, что (а, Ь) ( й.
20 ОА.6. Отображения Важный класс отношений, которым мы будем пользоваться, образуют отображения. Определение. Отображением (а также функцней или преобразованием) М множества А в множество В называется такое отношение из А в В, что если (а, Ь) и (а, с) принадлежат М, то Ь= с. Если (а, Ь)ЕМ, то обычно пишут М(а)=Ь. Говорят, что М(а) определено, если существует такое ЬЕВ, что (а, Ь)ЕМ.
Если М (а) определено для всех аЕА, то говорят, что М всюду определено. Если хотят подчеркнуть, что М может быть опреде- гл е ПРедзАРительные математичрские сведения УПРАЖНЕНИЯ лена не для всех аЕ А, то говорят, что М вЂ” частичное отображение (функция) множества А в множество В. В любом случае пишут М: А В. Множества А и В называются соответственно областью определения и множеством знаеенш1 М. Если отображение М: А — В таково, что для каждого Ь ЕВ существует не более одного такого иЕА, что М (а) =Ь, то М называется инъективным (взаимно однозначным).
Если отображение М всюду определено на А и для каждого Ь ЕВ существует точно одно такое аЕА, что М(а)= — Ь, то М называется биективным. Если отображение М: А — В инъективное, то можно найти обратное отображение М '.  — А, для которого М '(Ь)=а тогда и только тогда, когда М (а) =Ь. Если существует Ь Е В, для которого в А не найдется такого а, что М(а) ==-Ь, то М ' будет частичной функцией. Понятие биективного отображения используется для определения мощности множества, которая, говоря неформально, означает число элементов этого множества.
Определение. Два множества А и В называются равномощными, если существует биективное отображение из А в В. Пример 0.9. Множества (О, 1, 2) и (а, Ь, с) равиомощны. Для доказательства этого утверждения можно взять, например, биективпое отображение М = ((О, а), (1, Ь), (2, с)). Множество целых чисел имеет ту же мощность, что и множество четных чисел, хотя последнее является собственным подмножеством первого.
Это легко доказать с помощью биективного отображения ((а, 21) ) ~'-— целое число). Теперь можно точно определить, что мы понимаем под конечным множеством и бесконечным множеством '). Определение. Множество В конечно, если оно равномощно множеству (1, 2, ..., п) для некоторого целого числа п. Множество бесконечно, если опо равномощно некоторому своему собственному подмножеству. Множество счеапно, если оно равно- мощно множеству положительных целых чисел.
(Из примера 0,9 следует, что каждое счетное множество бесконечно.) Бесконечное множество, которое не является счетным, называется несчетным, Примеры счетных множеств: (1) Множество всех положительных и отрицательных целых чисел. ') Ранее мы употреблялн атн термины, предполагая, разумеется, что нх ннтунтнаныз смысл ясен. Однако целесообразно дать формальные определения.
22 (2) Множество четных чисел (3) ((а, ЬИа и Ь целые). Примеры несчетных множеств: (1) Множество вещественных чисел. (2) Множество всех отображений целых чисел в целые. (3) Множество всех подмножеств множества положительных целых чисел. УПРАЖНЕНИЯ ' О.1.1, Пусть А =(О, 1, 2, 3, 4, 5, б). Запишите множества, определяемые следующими предикатами: (а) (Х(Х принадлежит А и Х четно), (б) (Х!Х принадлежат А и является квадратом), (в) (Х)Х принадлежит А и Х' Е Ха+1). 0.1.2. Пусть А = (О, 1, 2) и  — (О, 3, 4).
Запишите множества (а) АОВ, (б) А ПВ, (в) А — В, (г) Ар (А), (д) Ахв. 0.1.3. Покажите, что если А — множество, состоящее из п элементов, то У (А) состоит из 2' элементов. 0.1.4. Пусть А и  †множест, а (7--некоторое универ- сальное множество, по отношению к которому берутся допол- нения. Покажите, что (а) А 0В=А ПВ, (б) А АО В = А О В. Эти тождества называются законами де Моргана. 0.1.3.
Покажите, что не существует такого множества (7, что А Е (7 для всех множеств А. Указание: Рассмотрите парадокс Рассела. 0.1.6, Дайте пример отношения, которое (а) рефлексивно, но не симметрично и не трапзитивно; (б) симметрично, по не рефлексивно и не траизитивно; (з) транзнтивно, но не рефлексивно и не симметрично, В каждом случае укажите множество, на котором определено отношение. 0.1.7. Приведите пример отношения на множестве, когорое (а) рефлексивно и симметрично, но не транзитивно; (б) рефлексивно и транзитивпо, по не симметрично; (в) симметрично и траизитивно, но пе рефлексивно.
2З гл. в. првавхрительнын млтамлтичвскиа свндвния нпрлжнсния Предостерезсение: Вы заблуждаетесь, если считаете, что сим- метричное и транзитивное отношение обязано быть рефлексив- ным (так как а)?Ь и Ьйа влечет а)?а). 0.1.8. Покажите, что следующие отношения являются отно- шениями эквивалентности: (а) ((а, а))а~А), (б) отношение конгруэнтности, заданное ка множестве тре- угольников. 0.1.9. > !усть Д вЂ” отношение эквивалентности на множестве А. Пусть а и Ь вЂ” элементы из А. Покажите, что (а) [а1=[Ь1 тогда н только тогда, когда а)?Ь, (б) [а1!) [Ь)=)с> тогда н только тогда, когда а)?Ь ложно.
0.1.10. Пусть А — конечное множество. Какие отношения эк- вивалентности порождают наибольшее н наименьшее число клас- сов эквивалентности? 0.1.11. Пусть А =(О, 1, 2) и )? =((О, 1), (1, 2)). Найдите )?* и )?+. 0.1.12, Докажите теорему 0.2(б). 0.1.13. Пусть )? — отношение на А. Покажите„что сущест- вует такое единственное отношение )?„что (1) )?а)?„ (2) Я,-- отношение эквивалентности на А, (3) если Я' — какое-то отношение эквивалентности на А и )?~ )?', то )?„с= )?', )?, назызается наив>еньшилс отношением эквивалентности, содер- жащим )?. Определение.
Полным порядков> на А называется ча>сой ре- флексивный частичный порядок на А, что для каждого пепустого подмножества В = А сущестнует такое ЬЕ В, что Ыа для всех а ~ В (т. е. каждое непустое подмножество содержит наименьший элемент). Множество А называется тогда вполнг упорядоченным, 0.1.!4. Покажите, что отношение «(меньше или равно) яв- ляется полным порядком на множестве положительных целых чисел. Определение. Пусть А †множест.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
