WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     || 2 | 3 | 4 |
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ Нижегородский государственный университет им. Н.И. Лобачевского В.Е. Алексеев Л.Г. Киселева Т.Г. Смирнова СБОРНИК ЗАДАЧ ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ Задачник Рекомендовано методической комиссией факультета вычислительной математики и кибернетики для студентов ННГУ, обучающихся по направлениям подготовки 010500 «Прикладная математика и информатика», 010400 «Информационные технологии» Нижний Новгород 2010 УДК 519.95 ББК 518 А - 47 А - 47 Алексеев В.Е., Киселева Л.Г., Смирнова Т.Г. СБОРНИК ЗАДАЧ ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ: Задачник. – Нижний Новгород: Нижегородский госуниверситет, 2010. – 53 с.

Рецензент: к. ф.-м. н., доц. А.В. Баркалов В сборнике задач содержится краткий теоретический материал и предлагаются задачи по важным разделам курса “Дискретная математика”: теории множеств, бинарным отношениям, комбинаторике и теории графов. Раздел "Контрольные задания" представлен контрольными работами по теории множеств и комбинаторике.

Задачник предназначен для студентов первого курса дневного и вечернего отделений факультета ВМК, обучающихся по направлениям подготовки «Прикладная математика и информатика» и «Информационные технологии».

Ответственный за выпуск:

председатель методической комиссии ф-та ВМК ННГУ д. ф.-м. н., проф. Л.П. Жильцова УДК 519.95 ББК 518 © Нижегородский государственный Университет им. Н.И. Лобачевского, 2010 2 1. Множества и операции над ними Терминология и обозначения {a1,a2,...,an } – множество, состоящее из n элементов a1,a2,...,an.

{x | P(x)} – множество, состоящее из таких элементов x, которые обладают свойством P.

x A – элемент x принадлежит множеству A.

x A – элемент x не принадлежит множеству A.

– пустое множество (не содержащее ни одного элемента).

U – универсальное множество (универс), т. е. множество всех элементов.

A B – множество A является подмножеством множества B ( A включено в B, A содержится в B ), это означает, что каждый элемент множества A является элементом множества B.

A B означает, что A B и A B, т.е. A является собственным подмножеством B.

A 2 {X | X A} — множество всех подмножеств A.

A U A — дополнение множества A.

A B {x | x A или x B} – объединение множеств A и B.

A B A B {x | x A и x B} – пересечение множеств A и B.

A B {x | x A и x B} – разность множеств A и B.

A B ( A B) (B A) – симметрическая разность множеств A и B.

Некоторые свойства операций над множествами 1. A A ; A ;

2. A U U ; A U A;

3. A A A; A A A;

4. A A U ; A A ;

A 5. A;

6. коммутативные законы:

A B B A; AB BA;

7. ассоциативные законы:

A (B C) ( A B) C ; A(BC) ( AB)C ;

8. дистрибутивные законы:

A(B C) ( AB) ( AC); A (BC) ( A B)( A C);

9. законы де Моргана:

A B A B ; A B A B ;

10. A B A B.

Операцию пересечения считаем более сильной, чем другие. Это означает, что при отсутствии скобок она выполняется первой. Например, формула ( AB C) CD эквивалентна (( A B) C) (C D).

1.1. Какие из следующих утверждений верны:

b {a,b}; b {a,{b}}; {};

1) 5) 9) b {a,b}; b {a,{b}}; {};

2) 6) 10) {b} {a,b}; {b} {a,{b}};

3) 7) 11) ;

{b}{a,b}; {b}{a,{b}}; 4) 8) 12) 1.2. Сколько элементов в каждом из множеств:

1, 2,3,1, 2,3;

1) 4) ;

{1,{1},2,{1,{2,3}},};,;

2) 5), 3) ; 6) 1.3. Известно, что A B и a A. Какие из следующих утверждений верны:

1) a B ; 6) a A B ;

2) a B ; 7) a A B ;

a A;

3) A B ; 8) 4) a A B ; 9) a A;

5) a A B ; 10) a B 1.4. Известно, что B A C, a A и a B. Какие из следующих утверждений верны:

1) a С ; 9) a A С ;

2) a C ; 10) a A C ;

3) a A B ; 11) a A C ;

4) a A B ; 12) a A B С ;

5) a A B ; 13) a A B C ;

6) a B A; 14) a B C A;

7) a A B ; 15) a A B C ;

8) a A C ; 16) a B A C 1.5. Дан универс U {1,2,3,4,5,6,7,8} и его подмножества A {x | 2 x 6}, B {x | x четно}, C {x | x 4}, D {1,2,4}. Найдите множества A B, CD, B C, A (BD), ( A B) (C D),, A B C A D 2 2B, 2 2B.

1.6. Дан универс U {1,2,3,4,5,6,7,8} и его подмножества A {x | x четно}, B {x | x кратно четырем}, C {x | x простое}, D {1,3,5}. Найдите множества A B, CD, A B, AB C D, C D, A D ( A B) (C D),, C A D, 2 2B, 2 2C.

A B 1.7. Пусть M, M, M обозначают подмножества универса, состоящие 2 3 соответственно из всех чисел, кратных 2, 3, 5. С помощью операций над множествами выразите через них множества всех чисел:

1) делящихся на 6;

2) делящихся на 30;

3) взаимно простых с 30;

4) делящихся на 10, но не делящихся на 3.

Используя теоретико-множественную символику, запишите утверждения:

1) 45 делится на 15;

2) 42 делится на 6, но не делится на 10;

3) каждое число из множества {8, 9, 10} делится хотя бы на одно из чисел 2, 3, 5, но не делится на 6.

1.8. Для каждого i 1,2,...,n даны множества Ai {(i, j) | j 1,2,...,n} и Bi {( j,i) | j 1,2,...,n}.

Выразите через них с помощью операций,,– множества:

1) {(i, j) |1 i k, 1 j k, k n};

2) {(i,i) | i 1,2,...,n};

3) {(i, j) |1 i j n}.

1.9. Выясните, обладают ли операции –, свойствами коммутативности и ассоциативности.

1.10. Выясните, какие из следующих дистрибутивных законов справедливы для любых множеств A, B,C :

1) A (B C) ( A B) ( A C);

2) A (B C) ( A B) ( A C);

3) A (B C) ( A B) ( A C) ;

4) A B C ( A B)( A C) ;



5) A (B C) ( A B) ( A C);

6) A B C ( A B)( A C) ;

7) A (B C) ( A B) ( A C) ;

8) A(B C) A B AC ;

9) A (B C) ( A B) ( A C) ;

10) A (B C) A B AC ;

11) A (B C) ( A B) ( A C) 1.11. Докажите тождества:

1) A A B A;

10) A B A B A B ;

2) A( A B) A; 11) A ( A B) B ;

12) A B A A B ;

3) A A B A B ;

13) A B ( A B) A B ;

4) A( A B) A B ;

5) A ( A B) A B;

14) A B A B A B U ;

6) A A B A B ;

15) A B A B A B ;

7) A(B A) ;

16) A B A B A B ( A B) ;

8) A (B A) A B ;

17) A A B A A B B A B ;

18) A (B C) ( A B)( A C) ;

9) AB AB A;

19) ( A B) C ( A C) (B C) A (B C);

20) A (B C) ( A B) AC ( A B) ( A C);

21) ( A B) C ( A C) (B C);

22) A B C ( A B) (B C) (C A) ABC ;

23) A BC ( A B) ( A C) A BC A;

24) A(B C) A B C A B C A B ;

25) ( AB A) (BC C) ( AB BC) ( A C);

26) ( A B) (B C) ( A C) B ( AB BC) ( A C).

1.12. Выразите:

1) через, ;

2) через, ;

3) и через, –.

1.13. Решите уравнение:

16) A X B X A ;

1) A X B ;

2) A X B; 17) A X B ( X A) B ;

3) A X B ; 18) A X B X ;

19) X A B ( X A) ;

4) A X B ;

20) ( A X ) B B X A;

5) A X B X ;

21) X A B ( X A) ;

6) A X B X ;

22) ( A X ) X X B ;

7) A X X B ;

8) ( A X ) B X B ;

23) A X A ( X B) B ;

9) A X ( X B) A;

24) ( A X ) B A B X ;

25) A ( X B) B X ;

10) X A ( X B) A;

26) B X ( A X ) X ;

11) ( A X ) B X B ;

27) A X B X A ;

12) ( A X ) B B X ;

28) ( X B) A A X ;

13) ( X A) B A X ;

14) ( X A) B B X ; 29) A X B A X ;

15) A X B B X ; 30) X A (B X ) A.

1.14. Найдите множество X, удовлетворяющее системе уравнений, где A, B,C – данные множества, B A C :

A X B A X B 1) ; 2).

A X C A X C 1.15. Решите систему уравнений:

( A X )(B X ) C X A B X X C 1) ; 4) ;

AX B AX C BX C AX AX B A X B 5) ;

2) X C ;

B A X C CX A B AX B X C A X BX 3) ; 6).

AX C X BX A X C 2. Бинарные отношения Терминология и обозначения A B {(a,b) | a A,b B} – (множество всех упорядоченных пар) прямое (декартово) произведение множеств A и B.

Любое R A B называется бинарным отношением, определенным на паре множеств А и В (далее просто отношением).

A2 A A (декартов квадрат множества А). Если R A2, то R называется отношением на множестве А.

x R y означает, что (x, y) R ( x и y находятся в отношении R).

R1 {(a,b) | (b,a) R} – отношение, обратное к R.

R1 R2 – произведение отношений R1 и R2 : если R1 A B, R2 B C, то R R1 R2 A C и xR y существует такой z B, что xR1z и zR2 y.

Важнейшие свойства отношений Отношение R на множестве A называется (1) рефлексивным, если для любого x A справедливо xR x ;

(2) симметричным, если из xR y следует yR x ;

(3) антисимметричным, если из xR y и yR x следует x y ;

(4) транзитивным, если из xR y и yR z следует xR z.

Рефлексивное, симметричное и транзитивное отношение называется отношением эквивалентности (или просто эквивалентностью).

Рефлексивное, антисимметричное и транзитивное отношение называется отношением порядка (или просто порядком). Порядок R на множестве A называют линейным, если для любых x, y A имеет место xR y или yR x.

2.1. Пусть A {1, 2,3} и B {a,b}. Определите A B, A A, B A, B B, A A, 2, 2B, B 2B.

2.2. Пусть A, B {} и C {,{}}. Определите A B, A C, B C, A B B, C C, 2, 2B, 2C, B 2B, B 2C, C 2B.

2.3. Выясните, какие из следующих равенств справедливы для любых множеств A, B, C, D :

1) A B B A;

2) ( A B)C ( AC) (B C) ;

3) ( A B) (C D) ( AC) (B D);

4) ( A B) (C D) ( AC) (B D);

5) ( A B)C ( AC) (B C) 2.4. Определите, какими из свойств (1) – (4) обладают следующие отношения на множестве {1, 2, 3, 4, 5}:

R1 : аR1b | a b | 1;

R2 : aR2b 0 a b 3;

R3 : aR3b a b – четное число;

R4 : aR4b a b2;

R5 : aR5b НОД(a,b) 1.

Представьте графически отношения:

1 R1 R2, R1 R2, R2, R2 R4, R4 R2, R5 R4.

2.5. Выясните, какие из следующих утверждений верны:

1) всякое отношение на множестве либо симметрично, либо антисимметрично;

2) никакое отношение не может быть одновременно симметричным и антисимметричным;

3) для любого отношения R отношения R R1 и R R1 симметричны;

4) для любого отношения R отношение R (R R ) антисимметрично;

5) если отношение R обладает одним из свойств (1)–(4), то R обладает тем же свойством;

6) для любого отношения R отношение R R симметрично;

7) для любого отношения R отношение R R рефлексивно;

8) если отношения R1 и R2 оба обладают одним из свойств (1)–(4), то R1 R2 обладает тем же свойством;

9) если R1 и R2 отношения эквивалентности, то R1 R2 отношение эквивалентности;

10) если R1 и R2 отношения эквивалентности, то R1 R2 отношение эквивалентности;

11) если R1 и R2 отношения эквивалентности, то R1 R2 отношение эквивалентности.

2.6. Какие из отношений, представленных диаграммами на рис.1, являются отношениями эквивалентности 1 1 2 1 3 1.

2. 3.

1 2 1 1 3 4. 6.

5.

1 2 1 1 9.

7.

8.

Рис.1. К задаче 2.2.7. Найдите все отношения на двухэлементном множестве a,b. Укажите среди них:





1) все рефлексивные; 4) все транзитивные;

2) все симметричные; 5) все эквивалентности;

3) все антисимметричные; 6) все отношения порядка.

2.8. Выясните, какие из следующих перечисленных отношений на множестве {0,1,...,9} являются отношениями эквивалентности. Найдите классы эквивалентности.

R1 : aR1b a b(mod3) ;

R2 : aR2b a2 b2 (mod10) ;

R3 : aR3b ab 0 (mod 2);

R4 : aR4b | 2a 2b | 16;

R5 : aR5b | 2a 2b | 16;

R6 : aR6b НОД(a,b) 1.

2.9. – множество целых чисел. На множестве определено отношение R : xR y x y2. Является ли какое-нибудь из отношений R R1, R1 R эквивалентностью 2.10. Определите, какие из следующих отношений на 2 являются отношениями эквивалентности:

R1 : (x1, y1 )R1 (x2, y2 ) x1 x2 ;

R2 : (x1, y1 )R2 (x2, y2 ) x1 x2 или y1 y2 ;

R3 : (x1, y1 )R3 (x2, y2 ) x1 y1 x2 y2 ;

R4 : (x1, y1 )R4 (x2, y2 ) x1 y2 y1 x2 ;

R5 : (x1, y1 )R5 (x2, y2 ) x1 x2 или x1 x2, y1 y2 Найдите для них классы эквивалентности.

2.11. Сколько различных отношений эквивалентности можно определить на множестве из n элементов при n 1,2,3,4 2.12. Какие из диаграмм на рис.1 представляют отношения порядка 2.13. Какие из следующих отношений на являются отношениями порядка:

R1 : xR1y x y ;

R2 : xR2 y x y ;

R3 : xR3 y x y ;

R4 : xR4 y x2 y2 ;

R5 : xR5 y x y ;

R6 : xR6 y x делится на y ;

R7 : xR7 y НОД(x, y) 1 2.14. Постройте диаграмму непосредственных предшествований отношения делимости на множестве {2,3, 4,6,8,9,12,18, 24,36}.

2.15. На множестве 2 определено отношение R : (x1, y1 )R(x2, y2 ) x1 x2, y1 y2. Докажите, что это отношение порядка.

Найдите все минимальные и максимальные относительно R элементы в множествах:

A1 {( x, y) | x 3, y 4};

A2 {( x, y) | 2 x y 4};

A3 {(x, y) | x2 y2 4}.

2.16. Дан конечный универс U. Выясните, какие из следующих отношений на 2U являются отношениями эквивалентности или порядка:

1) AR1B A B ;

2) AR2B A B ;

3) AR3B A B B A ;

4) AR4 B | A | | B | 2.17. Сколько различных отношений порядка можно определить на множестве из трех элементов Сколько среди них линейных 3. Элементы комбинаторики Терминология и обозначения Пусть A и B – множества, тогда отображение f : A B есть:

1) инъекция, если любые два различных элемента из A отображаются в различные элементы множества B ;

2) сюръекция, если для любого элемента y B существует такой элемент x A, что f x y ;

3) биекция (взаимно-однозначное отображение), если оно инъективно и сюръективно.

A – число элементов конечного множества A (мощность множества).

Правило равенства: если между конечными множествами A и B существует взаимно-однозначное соответствие, то A B.

Правило суммы: если A и B – непересекающиеся конечные множества, то A B A B.

Правило произведения: для любых конечных множеств A и B имеет место равенство A B A B. В более общем виде, если элемент a можно выбрать k способами, и после этого, независимо от того, какой элемент a был выбран, элемент b можно выбрать n способами, то упорядоченную пару (a,b) можно выбрать k n способами.

Пусть A a1,...,an — конечное множество, набор элементов (ai1,...,aik ) из A называется n,k-выборкой. Выборка называется упорядоченной, если в ней задан порядок следования элементов, в противном случае выборка называется неупорядоченной.

Упорядоченная n,k-выборка с повторениями называется n,kперестановкой с повторениями.

Число всех n,k–перестановок с повторениями равно nk.

Упорядоченная n,k-выборка без повторений называется n,kперестановкой.

n! Число всех n,k–перестановок Pn,k.

n k! n, n-перестановка называется перестановкой из n элементов.

Число всех перестановок из n элементов равно n!.

Неупорядоченная n,k-выборка без повторений называется n,kсочетанием.

n n! Число всех n, k –сочетаний.

k n k !k! Неупорядоченная n, k -выборка с повторениями называется n, k сочетанием с повторениями.

Число всех n, k –сочетаний с повторениями равно n k n k 1!.

k k!n 1! n n Бином Ньютона: x yn ynk.

xk k k Разбиением множества A называется семейство его подмножеств A1,..., Ak, если выполнены условия:

k 1) Ai Aj при i j ; 2) Ai A.

iЧисло упорядоченных разбиений множества мощности n на k подмножеств n n! мощностей n1,n2,,nk равно =.

n1, n2,...,nk n1!n2!...nk ! Формула включений и исключений для n множеств:

n n (1)k A Ai... Ai.

i 1 k i1 k 1 {,..., }{1,2,...,n} i i 1 k 3.1. Имеется n1 книг одного автора, n2 – второго, n3 – третьего. Каким числом способов можно выбрать 1) одну книгу;

2) две книги разных авторов;

3) три книги разных авторов.

3.2. Каким числом способов можно заполнить анкету, содержащую n вопросов, если на каждый вопрос можно ответить 1) `да` или `нет`;

2) `да`, `нет`, `не знаю` 3.3. Сколько палиндромов (слов, читающихся одинаково слева направо и справа налево) длины n можно составить, если в алфавите k букв 3.4. Сколько матриц с m строками и n столбцами можно составить из элементов 0 и 1 3.5. Сколько бинарных отношений можно задать на множестве из n элементов Сколько среди них:

1) рефлексивных 2) симметричных 3) антисимметричных 3.6. Дано множество U из n элементов и в нем подмножество A из k элементов. Определите число подмножеств B U, удовлетворяющих условию:

1) B A; 4) A B ;

2) B A; 5) | B A | 1;

3) A B ; 6) | B A | 2.

Pages:     || 2 | 3 | 4 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.