книги / Основы дискретной математики
..pdfМИНИСТЕРСТВО ВЫСШЕГО И СРЕДНЕГО СПЕЦИАЛЬНОГО ОБРАЗОВАНИЯ РСФСР
ПЕРМСКИЙ ОРДЕНА ТРУДОВОГО КРАСНОГО ЗНАМЕНИ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ А.М.ГОРЫСОГО ПЕРМСКИЙ ПОЛИТЕХНИЧЕСКИЙ ИНСТИТУТ
А.Е. СОЛОВЬЕВ. В.С. ГАЛКИН
ОСНОВЫ ДИСКРЕТНОЙ МАТЕМАТИКИ
Учебное пособие
Пермь 1977
519.5(07)
С603
С603. А.Е.Соловьев, В.С.Галкин. Основы диыфетной «дате матики. Учебное пособие. Изд. Пермского ун-та, 1977, 80 с.
Учебное пособие предназначено для активного изучения основ ных разделов дискретной математики: теории множеств, математичес кой логики, теории автоматов, графов и алгоритмов. Оно сгруппиро вано по соответствующим главам. Многие задачи онабиены решениями и ответами. Каждая глава содержит библиографию и краткое теорети ческое введение.
Учебное пособие подготовлено кафедрой автоматизированных систем управления Пермского политехнического института.
Печатается по постановлению редакционно-издательского со вета Пермского политехнического института
519.5(07)
©Пермский политехнический институт, 1977
В В Е Д Е Н И Й
Задачи синтеза и анализа сложных систем требуют адекватного математического аппарата. Каи потребности навигации и строитель ства способствовали развитию гёометрии, успехи в механике сопро вождались бурным развитием аппарата математического анализа, тах
впотребности кибернетики стимулируют развитие целого ряда разде лов так называемо! дискретно! математики.
Вкурсе "Ооновы диокретно! математики" рассматриваются такие фундаментальные для математики в целом разделы, как теория мно жеств и математическая логика, а также теория графов, автоматов, алгоритмов, комбинаторика и др.
Аппарат дискретно! математики будет широко использоваться
вчитаемых для специальности АСУ курсах "Теория вероятностей", "Алгоритмические языки и программирование", "Цифровые вычислитель
ные машины", "Основы построения АСУ", "Исследование операций", "Теория вычислительных систем" и т.п.
Учитывая, что много места в работе системотехника занимают процедуры выявления проблем я постановка задач, в данном курсе уделяется внимание и выработке навыков вычислительного плава, а выработке навыков перехода от оодеркатеяьных представлений к формальным и наоборот.
В пособии без дополнительных ссылок наряду с новик задача ми широко использованы задачи, взятые кз литературы.
ГЛАВА I. ТЕОРИЯ Ш Ш В С Г В
Основная литература
I. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. М., "Наука", 1976.
2. ТГидисдич L L ТШжят в od p a w a g t ш п ш т у . i , •Зяуха". 1Э65.
3. Отодл Р. Множества. Логоса. Аксиоматические теории. К., "Просвещение", 1968.
4. Кофман А. Введение в прикладную комбинаторику. М., •Наука*, 1975.
5. Коршунов Ю.М. Математические основы кибернетики. М., •Энергии", 1972.
6.Бератисо А.Т. Структуры данных. Н., "Статистика*,1974.
7.Шрейдер Ю.А. Равенотво, оходотво, порядок. М., "Наука*,
1971.
Дополнительная литература
1. Александров П.С. Введение в общую теорию множеств и функций. М.-Л., Гостеивдат, 1948.
2.Вурбакж Н. Теория множеств. Ы., "Мир", 1965.
3.Глушков В.М., Цейтлин Г.В., Сщенко Е.Л. Алгебра, языки, программирование. Киев, "Наукове думка”, 1974.
4.Горбатов В.А. Теория частично упорядоченных систем. Ы., "Советское радио", 1976.
5.Кааухвжи Л.А. Введение а общую алгебру. М., "Наука",
1973.
6.КхШш С. Введение в метаматематику. М., ИЛ, 1957.
7.Коен П.Дж. Теория множеств ж кинтмнуум-гжпотеза. М.,
Пир". 1969*
8. Куратовслй К., MoctoBOKift А. Теория мвожеотв, М., "Мжр", 1970.
9.Основы кибернетик!. Математжчеокае основы кибернетики. Под ред. Пулкова К.А. М., "Высшая школа", 1974.
10.Раоева В., Сикорский Р. Математжжа метаматематика. М.,
"Наука", |
1972. |
П . |
Савельев Л Л . Комбинаторика к вероятность. Новосибирск, |
•Наука", |
1975. |
12. Успенский В.А. Лекции о шчжолмшх функциях. М,, Физ |
|
м а т а , |
I960. |
13.Фор Р.( Кофман А., Дени-Папен М. Современная математи ка, М., "Мир", 1966.
14.Френкель А,, Бар-Хиллел И. Основания теории множеств,
М.."Мир", 1966.
- 5 -
I.I. Свойства множеств. Oneрядит над множествами
Понятие "множества" относится к числу фундаментальных не определимых понятий* Множество есть объединение г одно целое объектов, хорошо различней навей интуицией или мыслы>. Объекты
мюжества называются элементами множества» |
|
|
|
|
|
|
|||||||||||
|
Запись лс е А читается |
"элемент х |
|
принадлежит множеству А ", |
|||||||||||||
ихк |
" х |
есть элемент множества |
А |
". х |
ф А |
- ":г не принадле |
|||||||||||
жит множеству/4 ". Здесь € |
- внак отношения принадлежности. |
||||||||||||||||
|
Множество может |
задаваться: |
|
|
|
|
|
|
|
|
|
||||||
|
а) |
перечислением ого элементов |
|
|
|
|
|
|
|
|
|||||||
|
|
|
A 9{%f г |
* *’* |
|
|
|
|
|
|
|
|
|
|
|
||
где |
X-L - элемент множества |
А |
; |
|
|
|
|
|
|
|
|
|
|||||
|
б) с помощью описания свойств объектов, |
по которым они |
|||||||||||||||
выделяютоя в одно множество |
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
А - { х I С ( х ) } , |
|
|
|
|
|
|
||||||
где С(зс)- характеристическое свойство, которому удовлетворяют |
|||||||||||||||||
элементы только этого множества» |
|
|
|
|
|
|
|
|
|
||||||||
|
Два множества считаются равными, если они состоят из одних |
||||||||||||||||
и тех же элементов. Запись А & |
В означает, что каждый элемент |
||||||||||||||||
множества А |
является элементом множества |
В |
, или, что |
А |
|
||||||||||||
есть подмножество В |
( А |
включено в В ). |
S |
- |
знак отношения |
||||||||||||
включения. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
Запись А с В |
читается |
" А |
строго |
|
включено |
в в |
' я озна |
|||||||||
чает, что А |
й в ' |
и |
А ф |
|
в |
. |
с |
- знак строгого |
включения. |
||||||||
|
Множество, не содержащее элементов, называется пустым и |
||||||||||||||||
обозначается |
ф • Множества обладают следующими свойствами: |
||||||||||||||||
|
а) рефлексивностью - |
А |
й |
А |
\ |
|
|
|
|
|
|
|
|
||||
|
б) |
транзитивностью - если |
А й в |
|
* |
3 |
Я С |
t то А |
с |
С I |
|||||||
|
в) интуитивным принципом объемности - если |
A Q В |
и |
3 я А . |
|||||||||||||
то |
А * В . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Н о ш е множества могут задаваться с помощью операций над |
||||||||||||||||
множествами. Объединением множеств А |
ж В |
вазывсется множество |
|||||||||||||||
|
|
|
А и |
В ~ { x f |
х |
е А |
или |
х |
€ |
В} |
* |
|
|
|
|||
Пересечением множеств А в В |
называется множество |
|
|
|
|||||||||||||
А П б = { х t х е А |
и х е В } - |
Разностью множеств А |
ж В |
- б - |
назовется шожество |
||
A \ B = { x t зс е А и х ф В } . |
||
Спметркческо! разностью множеств А и В навивается множество |
||
A A B S { * I( X € A |
ц х ф б ) жта ( х ф А и х е В ) ) , |
|
т.е. А л 6 * ( А \ б ) U ( В \ А ) . |
||
Доножненжем множества |
А |
будем навивать множество А ~ { x f x ^ A j - |
Расомвтрнвая в дальнейшем различные множества, мм будем |
||
счктать кх подмножеотвамж некоторого уннвероаяьного множества
U |
. Основой» ввжонм |
ангебрн множеств: |
||||
|
а) жошутатганнй |
А и В ^ В и А , |
А п б ^ В п А ) |
|||
|
б) асооцнатнвник |
|
|
|||
|
|
|
(А и В )и С -А и (б о С ), |
(А / )В )п С = А п (В п С ); |
||
|
в) дистрибутивный |
|
|
|||
|
|
А и (в п С )= (А и в )п (А и С ), |
Аа ( В и С ) с (а пВ) и(АпС); |
|||
|
г) адемпотентност* А и А * А , |
А п А *А * |
||||
|
д) |
оагложенжя А у ( А пВ)=А , |
А п ( А и д ) * А , |
|||
|
е) Де Моргана Л и в = А п В , |
Ап в * Хи~В , |
||||
|
ж) A u U * U t A n U •А ; |
|
||||
|
з) |
А и ф * А , |
Ап<р - ф ; |
|
||
|
ж) А иА * U , A j] А = <р i |
|
||||
|
к) |
фт*Ы , |
й*ф; |
|
|
|
|
л) |
А =А . |
|
|
|
|
|
Реаенже урашенжй алгебры м ю ввотв (о о д н ш нежзвестним) |
|||||
вжда А ( х ) = В ( х ) | где х |
- вежзвеотвое множество: |
|||||
|
1. Предотавхжвм |
А ( х ) & В ( х ) * 0 • |
||||
|
2. Используя законы ажгебрн шюжест», преобразуем уровне- |
|||||
нне к вжду |
( C n X ] u ( D n |
X ) = ф » |
||||
где |
£ |
ж ^ |
- вежоторме шожеотва, не оодержащжс множество |
|||
Xв о его дэполненже*
3.Дня .хсжомого множества шполянетоя ооотноменже
Э Я Х с С .
Нрамем обозваченжя: Z - целых чжсел, Q нмх чжоел.
I. Что можно сказать о справедливости данных выражений:
•) |
|
, ~ 7 ~ г) А б ф , |
б) { a } - { v } , |
д) A S { $ } . |
|
») |
А я ф , |
е) А е { Ф } . |
|
2. Доказать, |
что |
a)
в)
»)
а)
б)
в)
Р)
X)
а)
O f f , |
г) { * } + { { * } } . |
|
|
Д) { а . 6 . с } = { а , с , 6 } . |
|
Ф * { о } . |
в) { { u } . J } ¥ f W |
. O } , O i } - |
3. РущестБуют ли таете непустые множества /1, & и ^ .что
А п б ф Ф , А а С - ф , ( А п В ) \ С = ф ;
А п 6 £ АЛ С и С £ 3 ; А £ С \ В и А л бп С £ А ;
А п З ф ф , |
д п С ф ф , А А С ф ф ; |
А и 3 с А п 5 ; |
|
А и б £ А и С, А о С Я С п А , А п З = * ф -
4.Изобразить на диаграмм ЭЙлера-Венна множества:
а)
б)
»)
г)
X)
е)
(А \ В )б (A \ J> ); |
ж) А а З а С ; |
||
d |
\ |
d |
8) А п В п С ; |
дП (A U 3)и (A a D); |
м) Л Т а л £ \ Р ; |
||
(А п (В з С ))\3 > ; |
К) А п б п ё п Р |
||
A n |
( ( В а С ) \ J> )i |
л) (Са а В)\ С) а 2>; |
|
ы) (AflB и А п Ь) и (Ап Ь * В п С ) и А п С .
5. Записать аналитически множества, представленные на Хааграммах Эйжера-Венна (рис. I.I - 1.6).
Рко. 1 Л |
Рас. 1.2. |
Рис. 1.3. |
х*ис* 1.4. |
Рис. 1.5. |
*-6. |
- 8 -
6, Доказать равенство множеств, используя принцип объем ности:
а) А п ( б п С ) * ( А п В ) п С ; б) А и ( в и С ) * ( А и б ) и С -
В) |
А и В - В и А ; |
г) |
А п & = s О А ; |
Д) |
А о (В п С) s (Аи 6) П (А и С); |
е) Ап ( 8 и С ) * ( А п В ) и ( А п С ) :
ж) |
(АиВ)пА = (А п В) и А - А ; |
|
з) |
А и А = Ал А = А ; |
|
и) |
А и д - А п В ; |
|
к) |
Ап |
6 = А о В ; |
л) |
А й |
в * 3 ДА ; |
м) А * А ; н) А л ( В \ А ) = Ф ;
o)А й Ф - А ; п) А й А = ф ;
p)А п А * ф ;
с) |
A n U -А ; |
Т) |
А д и */; |
У) |
А и А - И , |
ф) |
A u U ~ U ; |
X) |
ф = U . |
7. Доказать равенство множеств, преобразуя множества к оди наковому виду с помощью основных законов алгебры множеств:
а) |
А \ ( А \ В) * A n d ; |
б) |
А и & = А и ( 8 \ А ) , |
в) |
(А п в ) и ( 3 \ А ) и ( С \ в)= 6 и С ; |
г) А \ д = А \ (А п в ) ; |
|
Л) |
(А п б ) и (С р $ ) = ( А а С ) п ( в и С ) п (А а 1>)п ( B u D ) i |
е) |
А \ ( в \ С ) = ( А \ В ) и ( А п С ) ; |
ж) |
( A n B n C j u (Ап 3 П ? ) * [ А \ ( & п С ) ] \ [ А \ . ( в и с ) 3 ; |
з) |
(Ап В)и ( А п В ) - (А и В ) п (А и В ) ; |
и) |
( А и В ) \ С * ( А \ С ) и ( 3 \ С ) ; |
к) |
А и В и С * ( С \ А )п ( С \ б ) ; |
л) |
А и (ВО С )* А и В о (А п £ ) |
м) |
А и В * ( А й З ) и (А п В ) , |
н) |
( А \ В ) Д В = А л 6 ; |
о) |
А и В г ( А \ В ) д 8 ; |
п) |
А \ В * А й (А п В). |
8. Доказать равенство множеств, преобразуя .множества к оди наковому виду с помощью основных законов алгебры множеств:
а) |
(Ап во С) д [(АйС)\ В]* (А п В а С )о (А п И )и (А п В )о (В р С ) |
б) А \ ( 5 и с ) = ( А \ Ь ) \ С , |
|
в) |
А п (В \ С )* (А п в ) \ ( А п С); |
г) ( А \ В ) и С = Д Ы п S T ? ; |
|
Д) |
[(Ап В) и (Ал В ) ) * (А \ 8 )й /й Т а ); |
г) А п ( в \ С ) * ( C \ A ) \ Q ; |
|
ж) (А \ 6 ) \ С Z |
( А \ С ) \ ( В \ с ) ; |
з) А \ ( В \ С )* |
( А \ 8 ) о (а \ С ) ; |
■)
К)
Л)
м)
н)
о)
п)
р)
С)
т)
у)
ф)
х)
Ц)
а)
б)
в)
г)
д)
в)
S)
3)
и)
а)
б)
в)
г)
д)
в)
*)
з)
а)
б)
в)
г)
д)
_________ |
- 9 - |
(А и В о С)* |
(A flB )\[(A o C j r f B h |
А\ (ВиС)ш (А\В)п (А\С): /4\ (bnC) = (A\B)U(A\ С ),
А и В и С * (АЛ&)\ [(Ап С)\ 5 ].
(А\В)а&= (АлЬ)и(А\В) .
(АпВ)л С - (ХоВоС)пС(АпВ)оС],
Ал(ВдС)* ( А л б ) л С ; Ап (ВдС) - (Ап в) 4 (а п с ) ; (А л 6)4 (Ап д) = а и В) ;
Ал В г А а 6 ; ( А л Ь ) \ С - ( А й Ь ) и С ;
Ал (А л В ) - 0, ( В \ А ) = и ;
Аи В - А Л (В л (А п В ))-
9.Решить уравнение относительно х :
X и А = В. X и А ■ В, X п 8 = А.
Хп А = 8,
А\ Х * В:
Х\ A = 6 i
А\ X = В ;
Г Г З - С; X Л А* В;
к ) |
X п А ~ А и В , |
л) |
X и А * А \ 6 - |
м) |
Л \ B - A \ B ; |
н) |
X UA = X и В , |
о) |
А пХ s 3/f X ; |
п) |
X и А = X л В ; |
р) |
X п А * X п В ; |
с) |
А \ X * £ \ х . |
10. Решить уравнение относительно х :
( В о х ) \ А * в ; в) Ап ( В и Х ) * Аи В,
^\ а ; \ С г *д!
*d А - В ;
(х\В)\ С*С;
( к п А ) л 8 s А; X \ ( A \ B j - A ; ( Х и А ) п В = С ;
(Хд 6 ) \ С =В ;
к )
л)
м)
н)
0)
п)
р)
(А п б )\ ( х и A J : B ,
А л б * б и х ;
(Xл А ) \ В ~ ф
(X и А ) \ ( X п В ) - ф ,
( Х о А ) \ ( Х и в ) =Ф ‘ ( Х и А ) \ ( x o B ) - U . ( Х и А ) \ ( х п В)=и .
IX. НаДти вое подмножества множеств
{*},{/}.{/.г}, {i.t.s};
{*12* Х4 V ; |
Х € /V} , |
{xfx - положительная оценка } ; |
|
{xix - входит |
в треугольник учебно* группы } : |
{xix*- х - 0} ,
|
|
|
|
|
|
- |
10 - |
|
|
|
|
|
||
е) { л , а . О ) Л 1 0 , П 7 , О з ; |
|
|
|
|
|
|
||||||||
ж) |
U |
J \ г\ |
,/) * |
|
|
|
|
|
|
|
|
|||
|
12. Доказать, что для любых |
а |
, 6 |
* с |
и d |
а=с в ё - d |
||||||||
тогда в только тогда, |
когда |
{ ( а У , ( а .6 |
У ) |
s ( |
i c |
|||||||||
|
13. Привести содержательные примеры для предложений: |
|||||||||||||
а) |
если |
А € в |
и |
5 е С |
, то |
А |
€ |
С |
; |
|
|
|
||
0) если |
А е з |
в |
В е |
С |
, то а |
4 |
С |
; |
|
|
|
|||
в) если |
А с 5 |
И |
с |
f |
, to А |
с |
f |
; |
|
|
|
|||
г) если |
A i 5 |
в |
б € |
С |
, то А |
е |
С . |
|
|
|
||||
|
14. |
Доказать, что для произвольных множеств А, 5 и С |
||||||||||||
справедливы утверждения: |
|
|
|
|
|
|
|
|
|
|||||
а) если |
А с |
5 |
и £ С £ |
, то |
А и С |
С |
б |
|
; |
|
||||
б) если |
5 С А |
и в £ £ , т о |
|
в |
с |
А о |
С |
• |
|
|||||
|
15. |
Разрешить относительно |
х |
системы: |
|
|
||||||||
а)
б)
в)
г)
д)
е)
( А \ Х ) и & = А п Х , |
ж) |
М л х = 5 , |
|
4, |
|
|
\АиА - С , |
(С и Х ) \ А = Ф , |
|
||
\А пХ - & \ X , |
з) Ы \ Х * х \ в , |
||
[ С и * - X \ А ; * |
|
\ х \ А “ С \ Х , |
|
fAn X - Ф > |
и) |
Гх иА = Х и в, |
|
[ з л я = <Р ; |
|
[X \ С = А \ С , |
|
f.A^X - S , |
к) |
| Х иА = 6, |
|
[х \ А * с ; |
|
[X \ В = с , |
|
< А и Х * З л х , |
л) |
Гх и 3 = А п X , |
|
[Ап |
х - С и Х , |
|
\& Л С = С и Х . |
А \ Х |
= 6> |
|
|
А и X - С ,
1.2.ГраЬики. соответствия, отношения
Упорядоченная последовательность элементов вида |
|
" * х п > называется кортежем» |
а сами элементы - |
компонентами гортежа. Кортеж» состоящий из двух компонентов |
|
<*/> Х^> * называется парой, |
тройкой, |
£Xj tXj t ■•■гХ^ У — /I -КОЙ• |
пар. Пара <,c,d> называется |
|
Графиком называется |
множество |
|
инверсией пары < а , В > , |
если С = 6 |
и d - а , График л 1 |
называется инверсией графика Р , если его элементы является