Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000, страница 9

Операция проекции определяет построение "вертикального" под- множества отношения, т. е. множества подмножеств кортежей, получаемого выбором одних и исключением других доменов. Пример 1.4. Проекцияяр(яз/ Рз, Рз) вороидаетмнонество пар, пандая вн воторыт определяет дисциплину и экзаменатора (табл. 1.10). Таблица 1.10 Одинаковые строки в табл. 1.10 обьедннены в одну. Операция соединения по двум таблицам, имеющим общий домен, позволяет построить одну таблицу, каждая строка которой образуется соединением двух строк исходных таблиц.

Из заданных таблиц берут строки, содержащие адно и то же значение из общего дамена; общему домену сопоставляется один столбец. Пример 1 5. Нейдем ко двум ваданным таблицам (табл. 1 11, 1 12) результат операцпн соедннения по домену Рз (табл. 1.13). 45 Гл, 1. Основы ммоеосортныз множеств 44 1 1.6. Аксиоматике теории мнолсеств Твбпнав 1.13 Аналогично можно определить операцию соединения не только по условию "равенства", но и по другим условиям сравнения: >, >, уь, «, . 0пределим, например, операцию соединения по условию "больше, чем" (>). Соединением по условию пбольше, чем" отношения В по атрибуту Х и отношения Вь по атрибуту У (атрибуты Х и У являются атрибутами одного и того же домена, общего для отношений В, и Вь) Х > У называется множество всех кортежей л; таких, что пв — конкатенация кортежа а;, принадлежащего В„и кортежа Ь;, принадлежащего Вь, где Х вЂ” часть а1, У вЂ” часть б; и Х > У.

Запрос в реляционной базе данных будет выполнен тем быстрее, чем меньше операций над отношениями он содержит. Таким образом, представляет практический интерес рассматриваемая ниже задача упрощения представления множества через введенные операции Я 1.6). $1.6. Аксноматнка теории множеств, минимизация представления множеств Используя аксиоматический подход, формально построим теорию множеств на основании следующих аксиом.

Аксиома существования. Существует по крайней мере одно множество. Аксиома объемности (зкстенцио пал ьности). Если множество М, и Мь составлены из одних и тег же элементов, шо они совпадают (ровны): М, = Мь. А к с и о м а о б ъ е д и н е н и я. Для произв аль ныг множеств Мв и Мь существует множество, элементами кошорого являются все элементы множества М, и все элементы множества Мь и которое никаких других элементов не содержит. Из аксиом объемности и объединения следует, что для произвольных множеств М и Мь множество, удовлетворяющее условиям аксиомы объединения, единственно. Действительно, если бы имелись два таких множества, М„и М,, то они содержали бы одни и те же элементы (все элементы, принадлежащие множеству М, и все элементы множества Мь), и поэтому согласно аксиоме объемности М„= М,, = М,.

Назовем это единственное множество М, объединением множеств М, и Мь и будем писать М, = = Мв 11Мь. Аксиома разности. Для произвольныг множеств М и Мь существует множество, элементами которого являются те и только те элементы множество М, которые не являются элементами множества Мь. Аналогична, из аксиом объемности и разности заключаем, что для произвольных множеств М, и Мь существует в точности одно множество, содержащее элементы множества Мв, не принадлежащие множеству Мь. Назовем это множество М, разностью множеств М, и Мь: Мв = М 1 Мь. Аксиома степени.

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

Пересечение множеств М, и Мь определяется формулой М, г1 М =М, ~(М, ~мь). Можно показать, что элементами пересечения М, Г1 Мь являются те и только те элементы, которые принадлежат как множеству М„ так и множеству Мь. Дополнение М множества М определяется формулой М= 11М. 4Т Гл. 1. Основы многосо тных множеств 46 8 1.6. Аксиоматико теории множеств Симметрическая разность множесхв М, и Мь определяется формулой Ма>1 Мь = (М 1,мь) 0 (Мь 1>м ) На основании введенной аксиомахики можно доказать справед- ливость как приведенных выше законов, определяющих свойсхва сигнатуры алгебры множеств (законы идемпотенхносхи, комму- хахивности, ассоциахивности, дистрибутивносхи, действия с кон- схантами, двойного дополнения, законы де Моргана), хак и сле- дующих законов: закон дистрибутивности пересечения отпносительно разно- стпи Ма П (Мь >1 Мс) = Ма П Мь >1 Ма П Ме~ закон коммутпативности симметрической разностпи Ма >> М6 = Мь >> Ма> закон ассоциативности симметрической разности М ~ (Мь 1 М) = (М ~ Мь) 1 Мб закон дистрибутивности пересечения отпносительно сим- метрической разносп>и М.П(мь~'и,) еем.ПМЬ~'М.ПМ;, законы склеивания Ма П М6 О Ма П МЬ = Ма> (Ма О М6) П~ (Ма О Мь) = Ма> законы поглощения м, ом,пм = м„м, и (М,ОМЬ) = и,; законы Порецкого Ма О Ма П МЬ >«Ма и М6> Ма П (Ма О МЬ) = Ма П| М6.

Используя эхи законы, рассмотрим задачу минимизации пред- схавления множества М с помощью операций О, П, Под сложностпью представления множесхва М будем понимахь число символов М., М; в задающем его выражении. Пусть з пространстве 1 = (М>, Мз, Мз) задано миоиество вида М(М>, Мз, Мз) = )ЬУ й )Из й Льз О М> П Из й Мз О М> й Мз й Мз О О М, п Лгз г> И, и М, и Мз пауз О М> п М, и Мз. На основании вазонов идемпотеитностн, поммутвтявносги и ассопивтнзносги объединения получаем М(М>, Мз, Мз) «(М> й Мз й Мз О М> П Мз П Мз) О (М> П Мз П М О О М> П Мз П Мз) О (М> П )(тз П Мз О М> П Мз й Й:з) О (М> П туз П )(1 О О М> й Мз П Мз) О (М> й Мз П Мз О М> П Мз П Из). Сотасио авионам поммугативиости обьединения и пересечения и вазону сплеиваншт получаем М(М>, Мз, Мз) «М, П Мз О Мз О Мз П Мз О М> й Мз.

Согласно запалам помззутвтивиостн пересечения и поглошения имеем М(М>, Мз, Мз) = Щи Мз и Мз О М> П Мз. Слоииость представления заданного мноиества уменьшилась с 18 до $. Последовательность применения законов будем называть стратегией преобразования. Сложносхь предсхавления множества, получаемого в резульхахе применения эхих законов (важдый нз кохорых определяет эквивалентное преобразование), зависит ох используемой стратегии. Найдем схратегию, всегда порождающую минимальное выражение заданного множества. Рассмотрим алгебру А = (В(1), О, П, ) и определим множества, которые могут быхь порождены (образованы) из произвольных подмиожесхв'М1, Мт» ...

М„называемых порождающими или образующими проспзранство 1 с помощью операций О, П, Множесхво (М;, аз=1, )М =0 ° > а> в дальнейшем будем называть первичным термам. Множеспю вида и () Мо' = Ма' Пмз'з П...Пма", >т; = 0> 1, > 1 т назовем конститпуентпой. Общее число различных консхитуенх не превышаех 2". Каждой консхихуенхе можно сопосхавнхь двоичный набор длины и; число этих наборов равно 2". Если некоторые консхитуенхы равны»з, хо общее количество констихуент меньше 2", при эхом среди подмножеств найдутся хохя бы два таких, которые можно выразихь одно через другое, т. е. зависимые.

Например, если и = 2 и Мз = М1, хо сущесхвуюх холько две отличные ох к1 констихуенхы: вези;Пит ааи11ПМЗ1, С =И ПМ', С =И'ПМ. Л ем м а 1.1. Пересечение двух различных констпитпуентп пустпо. н а Действительно, если констихуенты С, = Й Ма' и Сь = П М; ' >«1 ° «1 различны, то аь ф аь по крайней мере для одного >с, >с ( п. Но тогда Мье» П Мь" — ю и, следовательно, С, П Сь = Э. 48 Гл. 1. Основы мнсгссортпных множестве г 1.6. Аксиоматике тпеории множеств Лемма 1.2. Объединение всех констпитуентп равно 1. и Представим 1 в виде 1 = П (Мо 0 М1), и, раскрыв скобки, в 1=1 правой части равенства получим объединение всех конституент. Лемма 1.3.

Множестпво М; равно объединению конститпуент, каждая из которых содержит М1. гВ Согласно лемме 1.2 1 = С1 0 Сг 0... 0 Сг = 0 С;, гле С;, гю1 1 = 1, 2, ..., 2", — конституенты. Определим пересечение левой и правой частей этого выражения с М;. Имеем М; = (М П С1) 0 (М П Сг) 0... 0 (М П С ) 0 ...

Если С содержит в качестве аргумента пересечения Ма, то М; П С = Я. Если же Су содержит М1, то Су П М; = С.. Следовательно, М; — объединение тех конституент, которые содержат 1 М; в качестве сомножителя; число этих конституент равно 2" 1. Теорема 1.5. Каждое непустпое множество, образованное из множеств М1, Мг,..., М„с помощью операииб 0, П,, является объединением некопюрого числа консгпитпуент. Согласно лемме 1.3 теорема справедлива для множеств М1, Мг, ..., М„. Следовательно, достаточна показать, что если произвольные множества М, и Мь представимы в виде объединения некоторого числа конституент, та и множества М, 0 Мь, М, П Мь и М, если они не пустые, также можно представить в виде объединения конституент.

Пусть множества М и Мь представимы в виде объединения ионституент Мь = С„0Сь,0...0Сьь и Мь = Сь,0Сь,0 . 0Сь,. Тогда множество М 0 Мь, очевидно, можно представить в виде объединения конституент. По закону дистрибутивности М, П Мь = (Сьг П Сь,) 0... ... 0 (Сь П Сь„); прн этом если С = Сь„, то согласно лемме 1.1 Сь, П Сья — — Э, в противном случае С,, = Сья. Следовательно, пересечение М, П Мь либо пусто, либо представимо в виде объединения конституент. Докажем, чта множество М также представимо в виде объединения конституент, если М = С1 0 Сг 0... 0 С». Согласно закону де Моргана П=С сС с...сС~=СЙС Й...сС~= Мвы П М '* П... П М~г" П Мвы П М~ы П...

П М '" П... и 1 г " и ...ПМ"'ПМ' П...ПМ""=(М "0М' 0...0М'")П г ° ° ° в = ( 1 г ° ° ° и П (М1 " 0 Мгвы 0... 0 Мп'") П... П (М1 ы 0 Мг гп 0... 0 М,,"") . Расирывая скобки и используя соотношения М П М = го, М 0 М = 1, а также добавляя в те пересечения, в которых отсутствует нижний индекс 11, сомножитель Мд 0Мгг, получаем, чта множество М также представимо в виде объединения канституепт. Теорема 1.6. Изп множеств в алгебре А = (В(1),0,П, ) гн можно образовать не более чем 2 множсстпв. Каждое множества М согласно теореме 1.5 является объединением конституент, число которых не превышает 2"; следовательно, г" число различных объединений не превышает 2 .