Нахождение кратчайших путей

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ

Бийский технологический институт (филиал)

федерального государственного бюджетного образовательного учреждения высшего профессионального образования

«Алтайский государственный технический университет им. И.И. Ползунова»

Т.М. Тушкина О.Д. Ростова, Л.П. Кувшинова

ДИСКРЕТНАЯ МАТЕМАТИКА

Методические рекомендации с вариантами заданий

к типовому расчету для студентов направлений подготовки

230400.62 «Информационные системы и технологии», 080500.62 «Бизнес-информатика»

Бийск

Издательство Алтайского государственного технического университета им. И.И. Ползунова

УДК 519.1(0.76)

Рецензент: к. т. н., доцент кафедры МСИиА Гареева Р.Г.

Тушкина, Т.М.

Дискретная математика: Методические рекомендации с вариантами заданий к типовому расчету для студентов направлений подготовки 230400.62 «Информационные системы и технологии», 080500.62 «Бизнес-информатика» / Т.М. Тушкина, О.Д. Ростова, Л.П. Кувшинова; Алт. гос. техн. ун-т, БТИ. - Бийск: Изд-во Алт. гос. техн. ун-та, 2014. - 62 с.

В методических рекомендациях приведены программа курса «Дискретная математика», основные понятия и формулы по каждому модулю курса, примеры решения задач и варианты расчетных заданий для изучающих данный курс.

УДК 519.1(0.76)

	Рассмотрены и одобрены на заседании кафедры высшей математики и математической физики. Протокол № 6 от 23.05.14 г.
© Т.М. Тушкина, О.Д. Ростова, Л.П. Кувшинова, 2014 © БТИ АлтГТУ, 2014

ВВЕДЕНИЕ

На современном этапе исследование, моделирование и проектирование, особенно автоматизированное, в науке и технике практически невозможно без применения математических методов.

В высшей школе базовой математической дисциплиной является «Высшая математика». Однако при анализе и синтезе сложных систем, например, таких как химико-технологические, создание и эксплуатация ЭВМ, автоматизированных систем проектирования и управления, знаний только высшей математики недостаточно. Поэтому в учебные планы многих специальностей введена дисциплина «Дискретная математика».

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

Данная методическая разработка предназначена для студентов направлений подготовки 230400.62 «Информационные системы и технологии», 080500.62 «Бизнес-информатика», изучающих дисциплину «Дискретная математика». Для выполнения заданий типового расчета необходимо изучить вопросы, указанные ниже:

1. Множества.

2. Способы задания множеств.

3. Пустое множество.

4. Интуитивный принцип объемности.

5. Основные операции над множествами (объединение, пересечение, разность, дополнение, симметрическая разность).

6. Диаграммы Эйлера – Венна.

7. Свойства операции объединения множеств.

8. Свойства операции пересечения множеств.

9. Мощность множества.

10. Подмножество.

11. Свойства подмножеств.

12. Булеан множества.

13. Мощность булеана конечного множества.

14. Равномощные множества.

15. Счетные множества. Континуальные множества.

16. Декартово произведение множеств.

17. Степень множества.

18. Бинарное отношение.

19. Способы задания бинарных отношений.

20. Матрица бинарного отношения.

21. Область определения, область значений отношения.

22. Композиция отношений.

23. Степень отношения.

24. Свойства бинарных отношений (рефлексивность, антирефлексивность, симметричность, транзитивность, связность).

25. Признаки свойств бинарных отношений.

26. Транзитивное замыкание отношения.

27. Рефлексиное транзитивное замыкание отношения.

28. Основные комбинаторные правила (правило сложения, правило умножения).

29. Перестановки, размещения, сочетания.

30. Размещения с повторениями и без повторений.

31. Сочетания с повторениями и без повторений.

32. Перестановки с повторениями и без повторений.

33. Разбиения.

34. Бином Ньютона.

35. Полиномиальная формула.

36. Свойства биномиальных коэффициентов.

37. Формула включений-исключений.

38. Формулы алгебры логики.

39. Таблицы истинности.

40. Функции алгебры логики.

41. Логические константы.

42. Равносильность функций алгебры логики.

43. Нормальные логические формы (ДНФ, КНФ).

44. Совершенные нормальные формы (СДНФ, СКНФ).

45. Упрощение нормальных форм.

46. Логические схемы.

47. Линейные булевы функции.

48. Многочлен Жегалкина.

49. Монотонные булевы функции.

50. Самодвойственные булевы функции.

51. Классы Поста.

52. Полные системы булевых функций.

53. Базис.

54. Предикат.

55. Кванторы общности и существования.

56. Формулы логики предикатов.

57. Раносильные формулы логики предикатов.

58. Определение графов и орграфов.

59. Цепи и циклы.

60. Простые цепи и простые циклы.

61. Матрица смежности.

62. Матрица инцидентности.

63. Матрица достижимости.

64. Матрица связности (сильной связности).

65. Компонента связности (сильной связности).

66. Алгоритм определения компонент связности (сильной связности).

67. Взвешенный орграф.

68. Уравнения Форда-Беллмана.

69. Алгоритм Форда-Беллмана нахождения минимального пути во взвешенном орграфе.

70. Сети..

71. Поток в сети.

72. Источник и сток.

73. Алгоритм определения критического пути в сети.

Основы теории множеств

Основные понятия и операции

Множество - это любая определенная совокупность объектов, которые называются элементами множества. Элементы множества различны и отличимы друг от друга.

Приняты следующие обозначения. Если a - элемент множества А, то пишут: а А. В противном случае: а А или а А.

Два множества А и В равны, если они содержат одни и те же элементы: А=В.

Множество А всех элементов, обладающих свойством Н(x), обозначается А= или А= .

Множество, не содержащее ни одного элемента, называется пустым и обозначается Æ.

Если все элементы множества В являются элементами множества А, то это обозначают В А или А В (В содержится в А или А содержит В). Множество В называется подмножеством множества А. Если В А, то В называется собственным подмножеством множества и обозначается: В А. Считается, что Æ является подмножеством любого множества.

Отношения и называются включением и собственным включением.

Объединение множеств А и В обозначается А В и представляет собой множество элементов, принадлежащих или множеству А, или множеству В.

Пересечение множеств А и В обозначается А В и представляет собой множество элементов, принадлежащих и множеству А, и множеству В (их общая часть).

Если множества А и В не имеют общих элементов, то есть их пересечение есть пустое множество: А В=Æ, то они называются непересекающимися или дизъюнктными.

Справедливы следующие соотношения:

;

;

;

, ;

;

Æ=А, Æ=Æ.

Разность множеств А и В обозначается А\В, это есть множество элементов множества А, которые не принадлежат множеству В.

Симметрическая разность АDВ множеств А и В представляет собой множество, состоящее из элементов, принадлежащих в точности одному из множеств А и В: АDВ=(А\В)È(В\А).

Если А U, то дополнение множества А относительно множества U определяется как =U\А.

Для более наглядного представления операций над множествами и их свойств применяют диаграммы Эйлера - Венна (рисунок 1). Каждое множество предсталяется множестом точек на плоскости.

\

Рисунок 1 – Диаграммы Эйлера – Венна

Приняты следующие обозначения для числовых множеств:

N – множество натуральных чисел;

Z – множество целых чисел;

R – множество действительных чисел;

Q – множество рациональных чисел;

С – множество комплексных чисел.

Множества А и В называются эквивалентными или равномощными (А~В), если между ними можно установить взаимно однозначное соответствие.

Множество А является бесконечным, если оно эквивалентно некоторому собственному подмножеству.

Всякое бесконечное множество, эквивалентное множеству натуральных чисел N, называется счетным.

Всякое бесконечное множество, эквивалентное множеству действительных чисел Q, называется множеством мощности континуума. Мощность континуума обозначается через .

Множество А, состоящее из конечного числа n элементов, называется конечным. Мощность конечного множества А равна: |А|=n.

Если АÇВ¹Æ, то |АÈВ|=|А|+|В| - |АÇВ|.

Для дизъюнктных множеств (АÇВ=Æ ) |АÈВ|=|А|+|В|.

Пусть A_i (i =1,2,...,n; n>1) – конечные множества. Имеет место формула включений-исключений:

|А₁ÈА₂È...ÈА_n|=(|A₁|+|A₂|+...+|A_n|) – ...

... - (|A₁ÇA₂|+|A₁ÇA₃|+...+|A_n-1ÇA_n|) +...

...+ (|A₁ÇA₂ÇA₃|+|A₁ÇA₂ÇA₄|+...+|A_n-2ÇA_n-1ÇA_n|) -- ...

...+(-1)ⁿ⁺¹|A₁ÇA₂Ç...A_n|.

Универсальным множеством U по отношению к конечному множеству А называется множество всех подмножеств множества А. Мощность универсального множества U равна |U|=2ⁿ, где n=|A|.

Примеры

Пример 1. А – множество делителей числа 15; В – множество простых чисел, меньших 10; С - множество четных чисел, меньших 9. Описать каждое множество перечислением. Найти: АÈВ, АÇС, ВÇС,

(АÈС)ÇВ, АÇВÇС.

Решение.

Исходя из условия находим А={1;3;5;15},B={2;3;5;7}, C={2;4;6;8}. Тогда AÈB={1;2;3;5;7;15}, BÇC={2}, AÇC=Æ, AÈC={1;2;3;4;5;6;8;15}, (AÈC)ÇB={2;3;5}, AÇBÇC=Æ.

Пример 2.В группе из 100 туристов 70 человек знают английский язык, 45 – французский, 25 человек знают оба языка. Сколько туристов не знают ни английского, ни французского языка?

Решение.

Пусть A – множество туристов, знающих английский язык, F – французский. По условию |А|=70, |F|=45, количество туристов, знающих оба языка, равно |AÇF|=25. Множество туристов, знающих хотя бы один язык – это следующее AÈF. Тогда по формуле находим |AÈF|=|A|+|F|-|AÇF|=70+45-25=90. Так как всего туристов 100, а из них знают хотя бы один язык 90, то не знают ни английского, ни французского языка 100-90=10 туристов.

Варианты задачи №1

Найти для вариантов 1 – 10.

1. .

2. .

3. .

4. .

5. .

6. .

7. .

8. .

9. .

10. .

Изобразить на координатной плоскости множества для вариантов 11 – 26.

Условие, которому удовлетворяют координаты точек, принадлежащих множеству
	А	В
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.

Найти для вариантов 27 – 30.

27. U – множество целых чисел, A – множество четных чисел, B – множество чисел, которые кратны 4.

28. U – множество натуральных чисел, A – множество нечетных чисел, B – множество корней уравнения .

29. , А – множество простых чисел, В – множество корней уравнения .

30. , А – множество составных чисел, В – множество степеней числа 2.

Варианты задачи №2

Доказать тождества

1. .

2. .

3. .

4. .

5. .

6. .

7. .

8. .

9. .

10. .

11. .

12. .

13. .

14. .

15. .

Доказать, что

16. .

17. .

18. .

19. .

20. .

21. .

22. .

23. .

24. .

25. .

26. .

27. .

28. .

29. .

30. .

ОТНОШЕНИЯ

Основные понятия и формулы

.Если а и b – объекты, то через (а, b) обозначим упорядоченную пару. Равенство упорядоченных пар определяется следующим образом:

(a, b)=(c, d) тогда и только тогда, когда a=b и c=d.

Прямым (декартовым) произведением множеств А и В называется множество упорядоченных пар

А В ={(a , b): a A, b B}.

Аналогично определяется упорядоченная n-ка эелементов и декартово произведение n множеств.

n-ой степенью множества А называется его прямое n-кратное произведение на себя и обозначается так: .

Бинарным отношением между элементами множеств A и B называется любое подмножество R множества А B. Если А=B, то отношение называется бинарным отношением на A. Вместо (x,y) R часто пишут xRy.

Областью определения бинарного отношения R называется множество

= {x: существует y такое, что (x,y) R}.

Областью значений бинарного отношения R называется множество

= {y: существует x такое, что (x,y) R}.

Для бинарных отношений определены обычным образом теоретико-множественные операции объединения, пересечения и т.д.

Дополнением бинарного отношения R между элементами A и B называется отношение =(A B) \ R.

Обратным отношением для бинарного отношения R называется отношение R ^-1={(x,y): (y,x) R}.

Композицией (произведением) отношений R₁ и R₂ называется отношение R₁ R_n ={(x,y): существует z такое, что (x,z) R₁ и (z,y) R₂}.

Пусть и множество A состоит из n элементов, пронумеруем их. Тогда элементы бинарного отношения R можно представить матрицей ||R|| порядка n n такой, что ее элементы r_ij находятся из условия:

Элементы r_ij матрицы ||R|| композиции отношений P и S, т.е. , определяются следующим образом: .

Здесь и - логические операции: дизъюнкция и конъюнкция соответственно.

Бинарное отношение R на множестве A называется рефлексивным, если

(x, x) R для всех x A,

иррефлексивным (антирефлексивным), если

(x, x) R для всех x A.

Бинарное отношение R на множестве A называется симметричным, если для всех х, у A:

из того, что <x, y> R, следует <y, x> R,

антисимметричным, если для всех х, у A :

из того, что <x, y> R и <y, x> R, следует x=y.

Бинарное отношение R на множестве A называется транзитивным, если для всех х, у, z A:

из того, что <x, y> R и <y, z> R, следует <x, z> R.

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

Бинарное отношение R на множестве A называется предпорядком на A, если оно рефлексивно и транзитивно. Рефлексивное, транзитивное и антисимметричное отношение на множестве A называется частичным порядком на A. Частичный порядок часто обозначается символом ≤ . Пишут: x<y, если x≤ y и x≠ y. Частичный порядок ≤ на множестве A называется линейным, если любые два элемента из A сравнимы по отношению ≤ , т.е. x≤ y или y≤ x для любых x, y A. Множество A с заданным на нем частичным (линейным) порядком ≤ называется частично (линейно) упорядоченным.

Транзитивным замыканием R⁺ отношения R является объединение всех его положительных степеней, т.е. R⁺= . Под n-ой степенью отношения R понимается его n-кратная композиция с самим собой, т.е. .

Примеры

Пример 1. На множестве А={1, 2, 3, 4, 5} задано отношение R ={(x; y): x < y}. Найти область определения, область значений R. Задать матричным способом R ^-1; ; . Указать свойства отношения.

Решение.

Укажем сначала все упорядоченные пары элементов множества А, которые принадлежат отношению R: R = {(1, 2), (1. 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)}.

Область определения отношения = {1, 2, 3, 4}, область значений отношения = {2, 3, 4, 5}.

={(у; х): (x; y) R }={(x; y): y<x}={(x; y): x>y}.

={(х; у): (x; y) R }={(x; y): x y}

Матрицы отношений R, R ^-1; и представлены ниже:

; ;

; .

Поясним способ определения элементов r_ij матрицы композиции отношения R с самим собой, изложенный выше в 2=.1, на нескольких примерах :

;

;

.

Аналогично определены и остальные элементы матрицы .

Отношение R является антирефлексивным, так как для любого элемента x R не выполняется условие x<x.

Отношение R - несимметрично, так как для любых x, y А из того, что x<y, не следует, что y<x.

Отношение R обладает свойством антисимметричности. Оно также и транзитивно, так как для любых x, y, z А, если x<y и y<z, значит x<z.

Пример 2. Найти транзитивное замыкание отношения R, заданного на множестве А={1, 2, 3}. Матрица отношения имеет вид

.

Решение.

Найдем матрицы положительных степеней отношения. Результаты занесем в таблицу 1.

Таблица 1 - Степени отношения R

Номер степени отношения	Матрица степени отношения	Степень отношения
Первая		R ={(1, 2), (2, 3), (3, 2)}
Вторая		R2= {(1,3), (2, 2), (3, 3)}
Третья		R3= {(1, 2), (2, 3), (3, 2)}
Четвертая		R4= {(1,3), (2, 2), (3, 3)}

Для данного отношения характерно равенство всех нечетных степеней друг другу и равенство четных степеней. Объединим степени отношения, в результате чего получим транзитивное замыкание отношения R⁺={(1, 2), (1,3), (2, 2),(2, 3), (3, 2), (3, 3)}.

Варианты задачи №3

Дано множество M={1; 2, 3; 4, 5, 6} и бинарное отношение . Найти область определения, область значений R. Задать матричным способом R ^-1; ; ^-1; ^-1 . Указать свойства (рефлексивность, антирефлексивность, симметричность, антисимметричность, транзитивность). Для нетранзитивного отношения найти транзитивное замыкание.

1. = {( a; b): a - b = 3, а, b }.
2. = {( a; b): a > 2b, а, b }.
3. = {( a; b): a + b > 5, а, b }.
4. = {( a; b): a при делении на b дает в остатке 1, а, b }.
5. = {( a; b): a делитель b, а, b }.
6. = {( a; b): a и b имеют одинаковые остатки от деления на 3, а, b }.
7. = {( a; b): a + b – четное, а, b }.
8. = {( a; b): a +b+1 M, а, b }.
9. = {( a; b): 3a b, а, b }.
10. = {( a; b): a = b² или а+3=b, а, b }.
11. = {( a; b): или a = b² , а, b }.
12. = {( a; b): |b-1| = |a-3|, а, b }.
13. = {( a; b): a делится на b без остатка и а – четно, а, b }.
14. = {( a; b): |a – b| = 3, а, b }.
15. = {( a; b): b = 2a + 1, а, b }.
16. = {( a; b): a = 3b ± 1, а, b }.
17. = {( a; b): M, а, b }.
18. = {( a; b): a+1 b, а, b }.
19. = {( a; b): a – остаток от деления b на 5, а, b }.
20. = {( a; b): a делит b или b делит a, а, b }.
21. R= {( a; b): b – остаток от деления a на 3, а, b }
22. R= {( a; b): |a – b| 3, а, b }
23. R= {( a; b): a делится на b без остатка и b – нечетно, а, b }
24. R= {( a; b): b = 2a - 1, а, b }
25. R= {( a; b): a = 3b + 1, а, b }
26. R= {( a; b): M, а, b }
27. R= {( a; b): a – остаток от деления b на 4, а, b }
28. R= {( a; b): |3 - b| < |a + 2|, а, b }
29. R= {( a; b): a – b + 2 M, а, b }
30. R= {( a; b): b = 5a - 1, а, b }

Основы комбинаторики

Основные формулы

Предполагается, что m и n натуральные числа, причем m n.

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

(принято, что ).

При больших значениях n для приближенного вычисления применяется формула Стирлинга

,

или

.

Число сочетаний из n элементов по m

.

Справедливы следующие свойства сочетаний:

1. (свойство симметрии);
2. (свойство Паскаля);
3. .

Число сочетаний из n элементов по m с повторениями определяется по формуле

.

Если среди n элементов есть одинаковые (i-тый элемент повторяется n_i раз), то число различных сочетаний равно

,

где .

Число размещений из n элементов по m определяется по формуле

,

или

.

Число размещений из n элементов по m с повторениями:

.

Бином Ньютона:

.

Принято (к+1) член бинома обозначать через Т_к, то есть

(к=0,1,2,...,n).

Полиномиальная формула

.

Примеры

Пример 1. Решить уравнение

.

Решение.

По формулам имеем

Так как ,

,

то .

Рассуждая аналогично, находим

.

Подставив в исходное уравнение выражения для и , приведя подобные члены, придем к уравнению

.

Решив это уравнение, находим: , .

Так как , то решением уравнения является .

Пример 2. На организацию соревнований выделено 760 условных денежных единиц (УДЕ). Сколько команд организаторы соревнований могут пригласить к себе, если команды встречаются между собой два раза, а на каждую игру выделяется 1 УДЕ?

Решение.

Так как команды встречаются между собой два раза, то здесь необходимо применить формулу для размещений без повторений. В данном случае получаем или n(n-1)=760.

Получили квадратное уравнение n²-n-760=0.

Решив уравнение, находим .

Так как n N, то решением задачи будет n=23.

Варианты задачи №4

1. Сколько различных слов можно составить из пяти букв «а» и не больше, чем трех букв «в»?

2. Имеется по две монеты 5; 10; 50 копеек. Сколькими способами можно выбрать две из этих шести монет?

3. Для решения задачи с помощью ЭВМ используются в определенном порядке по две программы каждого из трех типов a, b, c. В списке указаны 88 последовательностей из шести программ: aabbcc; aabcbc; aacbbc;… .Все ли такие последовательности вошли в список?

4. Сколькими способами можно распределить четырех студентов для прохождения практики в двух фирмах?

5. Сколькими способами можно обозначить треугольник, отмечая его вершины большими латинскими буквами?

6. Сколькими способами можно выбрать некоторые из семи различных книг?

7. Сколькими способами четверо юношей могут пригласить танцевать четырех из шести девушек?

8. Семь яблок и три апельсина надо положить в два пакета так, чтобы в каждом был хотя бы один апельсин, и чтобы количество фруктов в них было одинаковым. Сколькими способами это можно сделать?

9. Расписание одного дня содержит три пары. Определить количество таких расписаний при выборе из 11 предметов.

10. Комиссия состоит из председателя, его заместителя и еще пяти человек. Сколькими способами члены комиссии могут распределить между собой обязанности?

11. Тридцать человек разбиты на три группы по 10 человек в каждой. Сколько может быть различных составов групп?

12. Десять групп занимаются в десяти расположенных подряд аудиториях. Сколько существует вариантов расписания, при которых группы A и B находились бы в соседних аудиториях?

13. Восемь авторов должны написать книгу из 16 глав. Сколькими способами возможно распределение материала между авторами, если два человека напишут по три главы, четыре – по две, два – по одной главе книги?

14. Сколько четырехзначных чисел, делящихся на пять, можно составить из цифр 0, 1, 3, 5, 7, если каждое число не должно содержать одинаковых цифр?

15. Из группы в 12 человек выбирают ежедневно в течение шести дней двух дежурных. Определить количество различных списков дежурных, если каждый человек дежурит один раз.

16. На книжной полке размещается 30 томов. Сколькими способами их можно расставить, чтобы при этом первый и второй тома не стояли рядом?

17. Собрание из 80 человек выбирает председателя, секретаря и трех членов ревизионной комиссии. Сколькими способами это можно сделать?

18. Четыре стрелка должны поразить восемь мишеней (каждый по две). Сколькими способами они могут распределить мишени между собой?

19. Команда из пяти человек выступает в соревнованиях по плаванию, в которых участвуют еще 20 спортсменов. Сколькими способами могут распределиться места, занятые членами этой команды?

20. Два почтальона должны раснести 10 писем по десяти адресам. Сколькими способами они могут распределить работу?

21. Буквы азбуки Морзе состоят из символов (точек и тире). Сколько букв можно изобразить, если потребовать, чтобы каждая буква содержала не больше пяти символов?

22. Двадцать восемь костей домино распределены между четырьмя игроками. Сколько возможно различных вариантов распределения?

23. Пять студентов нужно распределить по двум параллельным группам. Сколькими способами это можно сделать?

24. Лифт останавливается на 10 этажах. Сколькими способами могут распределиться между этими остановками восемь пассажиров, находящихся в кабине лифта?

25. Из цифр 1, 2, 3, 4, 5, 6, 7, 8, 9 составляются пятизначные числа, не содержащие одинаковых цифр. Определить количество чисел, в которых присутствуют цифры 2, 4 и 5 одновременно.

26. Сколько четырехзначных чисел, составленных из цифр 0, 1, 2, 3, 4, 5, содержат цифру 3 (цифры в числах не повторяются)?

27. Сколько трехзначных чисел, делящихся на три, можно составить из цифр 0, 1, 2, 3, 4, 5, если каждое число не должно содержать одинаковых цифр?

28. Три автомашины № 1, 2, 3 должны доставить товар в шесть магазинов. Сколькими способами можно использовать машины, если грузоподъемность каждой из них позволяет взять товар сразу для всех магазинов, и если две машины в один и тот же магазин не направляются? Сколько существует вариантов маршрута, если решено использовать только машину № 1?

29. Поезд метро делает 16 остановок, на которых выходят все пассажиры. Сколькими способами могут распределиться между этими остановками 100 пассажиров, вошедших в поезд на конечной остановке?

30. Сколькими способами можно построить в одну шеренгу игроков двух футбольных команд так, чтобы при этом два футболиста одной команды не стояли рядом?

Варианты задачи №5

Решить уравнения 1 – 13:

1. .

2. .

3. .

4. .

5. .

6. .

7. .

8. .

9. .

10. .

11. .

12. .

13. .

14. Показать, что при любом k сумма есть точный квадрат.

15. Доказать тождество .

16. Доказать тождество .

17. Сумма биномиальных коэффициентов равна 256. Найти коэффициент члена бинома Ньютона , который содержит .

18. Каков наибольший коэффициент разложения , если сумма всех коэффициентов равна 4096?

19. Сумма биномиальных коэффициентов разложения равна 64. Найти слагаемое, не содержащее x.

20. Сумма биномиальных коэффициентов с нечетными номерами в разложении равна 512. Найти слагаемое, не содержащее x.

21. Определить , если пятое слагаемое разложения не зависит от x.

22. В разложении имеется член, содержащий ab. Найти этот член.

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

24. При каком значении x четвертое слагаемое разложения в 20 раз больше m, если биномиальный коэффициент четвертого слагаемого относится к биномиальному коэффициенту второго слагаемого как 5:1?

25. Сумма коэффициентов второго и третьего слагаемых разложения равна 25,5. Написать член, не содержащий x.

26. Найти наибольший полиномиальный коэффициент разложения , если произведение четвертого от начала и четвертого от конца слагаемых равно 14400?

27. Разность между третьими биномиальными коэффициентами разложений и равна 225. Найти число рациональных членов разложения .

28. Сумма третьего от начала и четвертого от конца биномиальных коэффициентов разложения равна 9900. Сколько рациональных членов содержится в этом разложении?

29. При каких значениях x четвертое слагаемое разложения больше двух соседних с ним слагаемых?

30. Найти k-й член разложения , если известно, что

1. Элементы математической логики

Основные понятия и формулы

Высказывание – это всякое утверждение, о котором имеет смысл говорить, что оно истинно или ложно.

В математической логике обычно истинность высказывания обозначается 1, ложность – 0.

Высказывания, истинные (ложные) во всех возможных ситуациях, называются абсолютно истинными (абсолютно ложными). Абсолютно истинные и абсолютно ложные высказывания называются логическими константами.

Одноместная логическая операция – отрицание: отрицание истинного ложно и наоборот (таблица 2). Отрицание - одноместная операция в том смысле, что из одного простого высказывания А строится новое высказывание `А или ØА (читается: не А).

Таблица 2 - Таблица истинности операции отрицания

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

Конъюнкция (логическое умножение): высказывание АÙВ (читается: А и В) истинно тогда и только тогда, когда истинны оба высказывания А и В (таблица 3).

Таблица 3 - Таблица истинности операции конъюнкции

		Ù

Дизъюнкция (логическое сложение) высказываний А и В - высказывание АÚВ (читается: А или В), которое истинно тогда и только тогда, когда истинно хотя бы одно из высказываний А или В (таблица 4).

Таблица 4 - Таблица истинности операции дизъюнкции