Изобразите геометрически множество истинности двуместного предиката A(x, y).

Электронный практикум

По дискретной математике

для студентов факультета «Прикладная информатика»

по областям

 

 

Глава 1. Элементы логики предикатов

Понятие предиката

Предикатом арности n (n-арным, или n-местным предикатом) называют функцию от n переменных Q(x₁, x₂, …,x_n), определенную на декартовом произведении множеств: X₁´X₂´ …´X_n и принимающую значения из множества {И, Л}.

Примеры выполнения заданий

1. Постройте матрицу одноместного предиката Р(x), если:

P(x) = "x кратно 2", где xÎ [1, 14)

x

P(x)

Л

И

Л

И

Л

И

Л

И

Л

И

Л

И

Л

2. Изобразите геометрически множество истинности двуместного предиката P(x,y) = 1/4x ³ 1/4y”, если x, y Î (-2, 5];

Построим график прямой: 1/4y =1/4x; y = x; x y           Проверим точку выше графика прямой y = x, например, с координатами (-1; 2). Подставим координаты в неравенство: 1/4 (-1) ³ 1/4(2) – это ложно, поэтому

Y   0 X   -2 5   -2

область истинности предиката расположена ниже прямой, включая ее точки (т.к. нестрогое неравенство).

 

Задания для самостоятельного выполнения

1.1.1. Постройте матрицу одноместного предиката Q(x), если:

0) Q (x)=”2x^2 кратно 5”, xÎ (-8, 13);	1) Q (x)=”3x^2 кратно 2”, xÎ [-5, 13);
2) Q (x)=”4x^2 кратно 5”, xÎ (-10, 11);	3) Q (x)=”3x^3 кратно 2”, xÎ[-9, 10);
4) Q (x)=”5x^2кратно 3”, xÎ (-5, 13];	5) Q (x)=”3x^3 кратно 4”,xÎ(-7, 12);
6) Q (x)=”5x^3 кратно 4”, xÎ [-6, 14];	7) Q (x)=”x^4 кратно 2”, xÎ (-11, 1];
8) Q (x)=”x^3 кратно 5”, xÎ (-9, 10);	9) Q (x)=”x^2кратно 3”, xÎ [-7, 12);

 

x

Q(x)

1.1.2. Изобразите геометрически множество истинности одноместных предикатов G(x) и P(x), если:

0) G(x) = ”8 ³ -2x > 4/3”;	P(x) = ”2 >1/5x ³ -5”;
1) G(x) = ”-9 < -3x £ 3/2”;	P(x) = ”12 > 3/4x > -3”;
2) G(x) = ”0 ³ 1/3x >-5/9”;	P(x) = ”–14 £ -7x £ 1/4”;
3) G(x) = ”1/4 < -3x £ 9”;	P(x) = ”1 ³ 1/6x > -1/2”;
4) G(x) = ”1/3 > -6x >-6”;	P(x) = ”5 ³ 1/2x ³ -1/4”;
5) G(x) = ”8 ³ -2x > 4/3”;	P(x) = ”1/10 >1/5x > -5”;
6) G(x) = ”-1 < -3x £ 3/2”;	P(x) = ”6 > 1/4x > -3”;
7) G(x) = ”0 ³ 1/2x >-3/4”;	P(x) = ”–1 £ -7x £ 1/2”;
8) G(x) = ”1/5 < -3x £ 9”;	P(x) = ”1 ³ 1/6x > -1/2”;
9) G(x) = ”1/8 > -4x>-8”;	P(x) = ”2 ³ 1/2x ³ -1/4”;

 

X

0

X

1.1.3. Изобразите геометрически множество истинности предиката P(x), решив систему неравенств:

0) P(x)=	1) P(x)=
2) P(x)=	3) P(x)=
4) P(x)=	5) P(x)=
6) P(x)=	7) P(x)=
8) P(x)=	9) P(x)=

X

0

1.1.4. Постройте матрицу двуместного предиката P(x,y) и проверьте решение геометрически:

0)P(x,y)=”3x>-1/2y”, при x, y Î(-4,4);	1)P(x, y)=”1/3x > 9y”, при x, y Î (-2,5];
2)P(x,y)=”-1/4x£2y”, при x, y Î[-1,5];	3)P(x,y)=”10x£1/2y”, при x,y Î (-4,3);
4)P(x,y)=”5x>1/2y”, при x, y Î[-6,1);	5)P(x,y)=”-4x£2/3y”, при x, y Î [-5,1];
6)P(x,y)=”-1/10x£ 5y”, при x,y Î(-1,7)	7)P(x,y)=”3x£ 5/3y”, при x, y Î [-2,4];
8)P(x, y)=”-3x<2y”, при x, y Î [-5,2);	9)P(x,y)=”1/6x>-12y”, при x,y Î[-1,6).

x y

Y X

Изобразите геометрически множество истинности двуместного предиката A(x, y).

0) A(x, y)=”1/3x > 9y”, если x, y Î (-2, 13];	1) A(x, y)=”3x > -1/2y”, если x, y Î (-5, 11);
2) A(x, y)=”-1/4x £ 2y”, если x, y Î [-4, 9];	3) A(x, y)=”10x £1/2y”, если x, y Î (-10, 5);
4) A(x, y)=”5x > 1/2y”, если x, y Î [-12, 3);	Y X
5) A(x, y)=”- 1/10x £ 5y”, если x, y Î (-1, 15);
6) A(x, y)=”3x £ 5/3y”, если x, y Î [-9, 4];
7) A(x, y)=”-3x < 2y”, если x, y Î [-10, 5);
8) A(x, y)=”1/6x >- 12y”, если x, y Î [-1, 14); 9) A(x, y)=” -4x £ 2/3y”, если x, y Î [-8, 6];

Изобразите геометрически множество истинности двуместного предиката Q(x,y).

0) Q(x, y)=”1/4x^2 <2y”, если x, yÎ(-1,6);	Y 0 X
1) Q(x, y)=”-4x^2<2y”, если x,yÎ(-4, 8];
2) Q(x, y)=”-6x^2£ 3y”,если x, y Î [-2, 7];
3) Q(x, y)=”-5x^2 £ 2y”, если x, yÎ[-3,7);
4) Q(x, y)=”3x^2<-2y”, если x, y Î (-2, 6);
5) Q(x, y)=”- 6x^2 >3y”, если x, yÎ (-4, 5];
6) Q(x, y)=”7x^2£ -3y”, если x, yÎ [-4, 5];
7) Q(x, y)=”-4x >1/ 2y”, если x, yÎ (-7,1);
8) Q(x, y)=”6x^2>- 5y”, если x, y Î [-3, 4]; 9) Q(x, y)=” 8x^2£ 1/6y”, если x, yÎ[-3, 8);

Операции над предикатами и кванторами

Все логические операции логики высказываний справедливы и для предикатов (отрицание, конъюнкция, дизъюнкция, импликация и эквиваленция). Квантор — общее название для логических операций, ограничивающих область истинности какого-либо предиката. В математической логике приписывание квантора к формуле называется связыванием, а переменную, к которой он относится, называют связанной иначе свободной. Например, в предикате "x A(x, y)Ú"z B(c, z) переменные x и z - связанные, а переменные у и z – свободные.

Чаще всего используют два вида кванторов:

 

Название	Прочтение	Обозначение
Квантор общности	«все», «всякий», «каждый», «любой»	"
Квантор существования	«существует», «найдется», «хотя бы один»	$

 

Пусть задан одноместный предикат P(x) на множестве Х = { a₁, a₂, a₃, a₄ }, тогда: "xP(x)=P(a₁)&P(a₂)&P(a₃)&P(a₄); $xP(x)=P(a₁)ÚP(a₂)ÚP(a₃)ÚP(a₄).

Говорят, что у квантора всеобщности конъюнктивная природа, а у квантора существования – дизъюнктивная. Квантор уменьшает число свободных переменных в логическом выражении и превращает трёхместный предикат в двухместный, двухместный — в одноместный, одноместный — в высказывание.

Примеры выполнения заданий

1. Пусть предикат Q(x,y) определен на конечных множествах:

X={a₁,a₂,a₃, a₄, a₅}, Y={b₁, b₂, b₃, b₄, b₅, b₆} и имеет таблицу истинности:

X	Y
b1	b2	b3	b4	b5	b6
a1	И	И	Л	Л	И	Л
a2	Л	Л	Л	И	И	Л
a3	И	И	Л	Л	И	И
a4	Л	И	Л	Л	И	И
a5	И	И	И	И	И	И

Глава 2. Комбинаторика

 

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

Размещениями из n элементов по m (m n) называются упорядоченные m -элементные выборки из данных n элементов .

Задания для самостоятельного выполнения

0) Составьте все слова из трех букв А, В, С по две буквы.

1) В классе 30 учащихся. Сколькими способами можно выбрать из класса команду из 4 учащихся для участия в олимпиаде по истории?

2) Сколькими способами можно составить двуцветный полоса­тый флаг, если имеется материал 5 различных цветов? Та же за­дача, если одна из полос должна быть красной?

3) Из состава конференции, на которой присутствует 45 чело­века, надо избрать делегацию из 6 человек. Сколькими способами это можно сделать?

4) В турнире принимают участие 8 команд. Сколько различных предположений относительно распределения трех первых мест можно сделать?

5) Сколько существует двузначных чисел, в которых цифра десятков и цифра единиц различны и нечетны?

6) Сколькими способами можно сделать трехцветный флаг с горизонтальными полосами одинаковой ширины, если имеется материя 6 различных цветов?

7) Сколько существует трехзначных чисел, в записи которых цифры 1, 2, 3 встречаются ровно по одному разу?

8) На полке стоят 5 книг. Сколькими способами можно выложить в стопку несколько из них (стопка может состоять и из одной книги)?

9) У Димы есть 5 шариков: красный, зеленый, желтый, синий и золотой. Сколькими способами он сможет украсить ими 5 елок, если на каждую требуется надеть ровно один шарик?

Размещения с повторениями

Размещениями с повторениями из n по m называются упорядоченные m-элементные выборки, в которых элементы могут повторяться.

Задания для самостоятельного выполнения

0) Сколько четырехбуквенных «слов» можно составить из букв "М" и "А"?

1) Сколькими способами можно разместить восемь пассажиров в три вагона?

2) Каждый телефонный номер состоит из семи цифр. Сколько всего телефонных номеров, не содержащих других цифр, кроме 2, 3, 5 и 7?

3) Четверо студентов сдают экзамен. Сколькими способами мо­гут быть поставлены им отметки, если известно, что никто из них не получил неудовлетворительной отметки?

4) Сколько различных трехбуквенных слов можно составить из 32 букв алфавита (со смыслом и без)?

5) В селении проживает 2000 жителей. Доказать, что, по край­ней мере, двое из них имеют одинаковые инициалы.

6) Сколькими способами можно покрасить пять елок в серебристый, зеленый и синий цвета, если количество краски неограниченно, а каждую елку можно покрасить только в один цвет?

7) Каждую клетку квадратной таблицы 2 × 2 можно покрасить в черный или белый цвет. Сколько существует различных раскрасок этой таблицы?

8) Сколькими способами можно заполнить одну карточку в лотерее «Спортпрогноз»'? Указание: в этой лотерее нужно предсказать итог тринадцати спортивных матчей. Итог каждого матча - победа одной из команд либо ничья; счет роли не играет.

9) Алфавит племени Мумбо-Юмбо состоит из трех букв А, Б и В. Словом является любая последовательность, состоящая не более, чем из 4 букв. Сколько слов в языке племени Мумбо-Юмбо? Указание: сосчитайте отдельно количества одно-, двух-, трех- и четырехбуквенных слов.

Перестановки без повторений

Перестановками из n элементов называются размещения из n элементов по n.

Пусть (a₁,a₂,…,a_n), — перестановка элементов множества {1, 2,...,n}.Пара (a_i, a_j) называется инверсией перестановки, если i < j, то a_i > a_j.

Таблицей инверсии перестановки (a₁,a₂,…,a_n) называется последовательность (d₁,d₂,…,d_n),где dj — число элементов, больших j и расположенных левее j.

 

Задания для самостоятельного выполнения

0) Сколькими способами можно расставить 7 книг на книжной полке?

1) Сколькими способами можно разложить 8 различных писем по 8 различным конвертам, если в каждый конверт кладется только одно письмо?

2) Сколько ожерелий можно составить из семи бусин раз­ных размеров?

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

4) Сколько слов можно получить, переставляя буквы в слове «градус»?

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

6) Сколько всего шестизначных четных чисел можно составить из цифр 1, 3, 4, 5, 7 и 9, если из этих чисел ни одна не повторяется?

7) Сколькими способами можно расположить на шахматной доске 8 ладей так, чтобы они не могли взять друг друга?

8) Сколько всего семизначных четных чисел можно составить из цифр 0, 2, 3, 5, 7 и 9, если из этих чисел ни одна не повторяется?

9) Как велико число различных отображений, переводящих множество из n элементов в себя?

Перестановки с повторениями

Перестановки с повторениями вычисляются по формуле:

Задания для самостоятельного выполнения

0) Сколько различных шестизначных чисел можно составить из цифр: 1, 1, 1, 5, 5, 9?

1) Сколькими способами можно расположить в ряд 2 зеленые и 4 красные лампочки?

2) Сколько всего шестизначных чисел, у каждого из которых цифра 2 встречается два раза, а цифра 3 - четыре раза?

3) Имеется 5 мест на флагштоке и 5 флагов: 2 красных и 3 белых. Сколько можно изобразить различных сигналов, если использовать все флаги одновременно?

4) Сколько различных слов можно получить, переставляя буквы в слове «молоко»? В слове «караоке»? В слове «ингредиент»?

5) В магазине игрушек имеются 7 одинаковых Чебурашек и 2 одинаковых Крокодила. Сколькими способами их можно расставить в один ряд на витрине?

6) Сколькими способами можно разделить 40 одинаковых яблок а) между 4 мальчиками; в) чтобы каждый получил, по крайней мере, 3 яблока?

7) Сколькими способами в библиотеке можно расположить на одной полке 6 экземпляров романа «Овод», 7 экземпляров сказки «Золушка» и 8 экземпляров учебника Акимова «Дискретная математика»?

8) Сколькими способами можно расставить белые фигуры (2 ладьи, 2 коня, 2 слона, ферзь и король) на первой линии шахматной доски?

9) В магазине ``Все для чая'' продается 7 чашек, 5 блюдец и 6 чайных ложек. Сколькими способами можно распределить посуду с разными названиями?

Сочетания без повторений

Сочетаниями из n элементов по m (m n) называются неупорядоченные m-элементные выборки из данных n элементов.

Задания для самостоятельного выполнения

0) Составьте все сочетания из трех букв А, В, С по две буквы.

1) У 6 взрослых и 11 детей обнаружены признаки инфекционного заболевания. Чтобы проверить заболевание, следует взять выборочный анализ у 2 взрослых и 3 детей. Сколькими способами можно это сделать?

2) Сколькими способами можно группу из 20 студентов разделить на две подгруппы так, чтобы в одной группе было 13, а в другой 7 человек?

3) На книжной полке стоят 3 книги по алгебре, 4 книги по геометрии и 5 книг по литературе. Сколькими способами можно взять с полки три книги по математике?

4) Учащийся хочет использовать для раскраски географической контурной карты 4 краски из 6, которые он имеет в своем распоряжении. Сколькими способами он может выбрать 4 краски из 6?

5) Даны две параллельные прямые. На одной из них имеется 10 точек, а на другой - 20. Сколько существует треугольников с вершинами в данных точках?

6) Сколькими способами можно распределить 28 костей домино между 4 игроками так, чтобы каждый получил 7 костей?

7) В классе 12 юношей и 13 девушек. Сколькими способами из них можно выбрать четырех учащихся для дежурства на вечере, если а) освободить девушек; б) юноши и девушки?

8) Сколькими способами абитуриент может выбрать 3 ВУЗа из 5 для подачи документов?

9) Из двух математиков и десяти экономистов надо составить комиссию в составе восьми человек. Сколькими способами может быть составлена комиссия, если в нее должен входить хотя бы один математик?

 

Сочетания с повторениями

Сочетаниями с повторениями из n по m называются неупорядоченные m-элементные выборки, в которых элементы могут повторяться.

Задания для самостоятельного выполнения

0) В почтовом отделении имеются открытки 3 видов. Сколькими способами можно купить набор из 6 открыток?

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

2) В хлебном отделе имеются булки белого и черного хлеба. Сколькими способами можно купить 8 булок хлеба?

3) Сколько имеется костей в обычной игре "домино"?

4) Сколько вариантов строения ДНК Шубуршунчика обворожительного может быть, если длина цепи 1000 нуклеотидов (нуклеотиды 4 видов: А, Т, Г, Ц)?

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

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

7) Как велико число отличных друг от друга результатов бросаний двух одинаковых кубиков?

8) Сколькими способами можно выбрать 7 крупных апельсинов из 2 имеющихся на рынке сортов?

9) В магазине продаются белые, черные и красные носки. Сколькими способами можно купить 5 пар?

 

Примеры решения сложных задач

Приведем в систему полученные формулы всех 6 видов комбинаций с повторениями и без повторений, представив алгоритм определения вида комбинации (см. рис. 1).

Задания для самостоятельного выполнения

0) Из 10 роз и 8 георгинов нужно составить букет так, чтобы в нем было 2 розы и 3 георгина. Сколькими способами это можно сделать?

1) Собрание из 40 человек избирает председателя, секретаря и трех членов редакционной комиссии. Сколько существует возможностей выбора этих пяти человек?

2) Сколькими способами можно расставить 8 томов энциклопедии на книжной полке так, чтобы первый и второй тома:

а) стояли рядом; б) не стояли рядом?

3) На окружности расположено 20 точек. Сколько существует вписанных треугольников с вершинами в этих точках?

4) Сколько существует номерных знаков для автомобилей, состоящих из двух букв с последующими четырьмя цифрами, если буквы могут повторяться, а цифры — нет?

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

6) В алфавите племени Бум-Бум шесть букв. Словом является любая последовательность из шести букв, в которой есть хотя бы две одинаковые буквы. Сколько слов в языке племени Бум-Бум?

7) В стране 20 городов, каждые два из которых соединены авиалинией. Сколько авиалиний в этой стране?

8) На глобусе проведены 17 параллелей и 24 меридиана. На сколько частей разделена поверхность глобуса? Меридиан — это дуга, соединяющая Северный полюс с Южным. Параллель — это окружность, параллельная экватору (экватор тоже является параллелью).

Указание. Решите задачу для двух меридианов (0^o и 180^o) и одной параллели (экватора).

9) У людоеда в подвале томятся 25 пленников.

а) Сколькими способами он может выбрать трех из них себе на завтрак, обед и ужин? б) Сколько есть способов выбрать 3-х, чтобы отпустить на свободу?

 

 

Рис. 1. Алгоритм определения вида комбинации

Задание 1.

0) Из города А в город В ведут пять дорог, а из города В в город С – три дороги. Сколько путей, проходящих через В, ведут из А в С?

1) Из двух спортивных обществ, насчитывающих по 100 фехто­вальщиков каждое, надо выделить по одному фехтовальщику для участия в состязании. Сколькими способами может быть сделан этот выбор?

2) Имеется пять видов конвертов без марок и четыре вида ма­рок одного достоинства. Сколькими способами можно выбрать кон­верт с маркой для посылки письма?

3) Сколькими способами можно выбрать гласную и согласную буквы из слова «камзол»?

4) Сколькими способами можно выбрать гласную и согласную буквы из слова «здание»?

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

6) На вершину горы ведут пять дорог. Сколькими способами •турист может подняться на гору и спуститься с нее? То же самое при условии, что спуск и подъем происходят по разным путям.

7) На ферме есть 20 овец и 24 свиньи. Сколькими способами можно выбрать одну овцу и одну свинью? Если такой выбор уже сделан, сколькими способами можно сделать его еще раз?

8) Сколькими способами можно указать на шахматной доске два квадрата – белый и черный? А если нет ограничений на цвет выбранных квадратов?

9) Из 12 слов мужского рода, 9 женского и 10 среднего надо выбрать по одному слову каждого рода. Сколькими способами мо­жет быть сделан этот выбор?

Задание 2.

0) В местком избрано 9 человек. Из них надо выбрать предсе­дателя, заместителя председателя, секретаря и культорга. Сколь­кими способами это можно сделать?

1) Из состава конференции, на которой присутствует 52 чело­века, надо избрать делегацию, состоящую из 5 человек. Сколькими способами это можно сделать?

2) Автомобильные номера состоят из одной, двух или трех букв и четырех цифр. Найти число таких номеров, если используют­ся 32 буквы русского алфавита.

3) Сколько различных перестановок можно получить, переставляя бук­вы в слове «математика»? В слове «парабола»?

4) В почтовом отделении продаются открытки 10 сортов. Сколь­кими способами можно купить в нем 12 открыток? Сколькими спо­собами можно купить 8 открыток?

5) Из группы, состоящей из 7 мужчин и 4 женщин, надо вы­брать 6 человек так, чтобы среди них' было не менее 2 женщин. Сколькими способами это можно сделать?

6) Четверо студентов сдают экзамен. Сколькими способами мо­гут быть поставлены им отметки, если известно, что никто из них не получил неудовлетворительной отметки?

7) Из колоды, содержащей 52 карты, вынули 10 карт. Во скольких случаях среди этих карт окажется хотя бы один туз?

8) Из колоды, содержащей 52 карты, вынули 10 карт. Во скольких случаях среди этих карт окажется ровно один туз?

9) Из колоды, содержащей 52 карты, вынули 10 карт. Во скольких случаях среди этих карт окажется ровно два туза?

Задание 3. Записать все размещения из элементов множества А по два элемента с повторениями: 0) А = {2,7,9, 11}; 1) A = {x,y,z,t}; 2) A = {a,b,c,d}; 3) A = {X,Y,Z,T}; 4) А = {+,-,×,/}; 5) А = {!,#,%,+}; 6) А = {α,β,λ,δ} 7) А = {←,↑,→,↓}; 8) А = {В, П, М, Р}; 9) A = {Q,W,E,R}.	Задание 4. Записать все размещения из элементов множества А по три элемента без повторений:   0) А = {2,7,9, 11}; 1) A = {x,y,z,t}; 2) A = {a,b,c,d}; 3) A = {X,Y,Z,T}; 4) А = {+,-,×,/}; 5) А = {!,#,%,+}; 6) А = {α,β,λ,δ} 7) А = {←,↑,→,↓}; 8) А = {В, П, М, Р}; 9) A = {Q,W,E,R}.
Задание 5. Записать все сочетания из элементов множества А по два элемента без повторений: 0) А = {2,7,9, 11}; 1) A = {x,y,z,t}; 2) A = {a,b,c,d}; 3) A = {X,Y,Z,T}; 4) А = {+,-,×,/}; 5) А = {!,#,%,+}; 6) А = {α,β,λ,δ} 7) А = {←,↑,→,↓}; 8) А = {В, П, М, Р}; 9) A = {Q,W,E,R}.	Задание 6. Записать все сочетания из элементов множества А по три элемента с повторениями:   0) А = {2,7,9, 11}; 1) A = {x,y,z,t}; 2) A = {a,b,c,d}; 3) A = {X,Y,Z,T}; 4) А = {+,-,×,/}; 5) А = {!,#,%,+}; 6) А = {α,β,λ,δ} 7) А = {←,↑,→,↓}; 8) А = {В, П, М, Р}; 9) A = {Q,W,E,R}.
Задание 7. Записать все перестановки без повторений из элементов множества А:   0) А = {2,7,9, 11}; 1) A = {x,y,z,t}; 2) A = {a,b,c,d}; 3) A = {X,Y,Z,T}; 4) А = {+,-,×,/}; 5) А = {!,#,%,+}; 6) А = {α,β,λ,δ} 7) А = {←,↑,→,↓}; 8) А = {В, П, М, Р}; 9) A = {Q,W,E,R}.	Задание 8.Записать все: - размещения из элементов множества А по три элемента с повторениями; - размещения из элементов множества А по четыре элемента без повторений; - сочетания из элементов множества А по четыре элемента без повторений; - сочетания из элементов множества А по три элемента с повторениями; - перестановки из элементов множества А без повторений; 0) А = {1,3,5,7,8}; 1) А= {2,a,1,d,8}; 2) A = x,y,z,t,1; 3) A = a,b,z,t,2}; 4) A= {a,b,d,1,2}; 5) A = {a, b, c, d,х}; 6) A= {a,b,d,e,f}; 7 ) A = {x, y, a, b,6}; 8) A ={х,с,3,8,0}; 9) A = {с, b, 3, d, 4}.
Задание 9. Сколько трехзначных чисел, меньших заданного числа А, можно образовать, используя цифры 2,3,4,5,6,8,9 без повторений, если: 0) А=450; 1) А=350; 2) А=250; 3) А=420; 4) А=410; 5) А=380; 6) А=370; 7) А=430; 8) А=390; 9) А=460.	Задание 10. Сколькими способами N пар, пришедших в кино, могут занять места, если все пять пар сидят подряд и: 0) N=4; 1) N=5; 2) N=7; 3) N=6; 4 ) N=8; 5) N=9; 6) N=3; 7) N=10; 8) N=12; 9) N=11.
Задание 11. В соревнованиях участвуют N спортсменов. Сколько существует вариантов распределения трех призовых мест, если: 0) N=8; 1) N=7; 2) N=6; 3) N=9; 4 ) N=10; 5) N=5; 6) N=11; 7) N=12; 8) N=15; 9) N=14.	Задание 12. Сколько существует N-битовых строк, содержащих А нулей и К единиц, если: 0) N=8; А=3, К=5; 1) N=8; А=2,К=6; 2) N=8; А=4, К=4; 3) N=9; А=2,К=7; 4) N=9; А=3, К=6; 5) N=9; А=4, К=5; 6) N=10; А=3, К=7; 7) N=10; А=4, К=6; 8) N=10; А=2, К=8; 9) N=10; А=5, К=5.
Задание 13. В совете директоров компании, состоящего из n человек, при выборе президента за выдвинутую кандидатуру проголосовали k человек, против —j, воздержались — s. Сколькими способами может быть проведено такое голосование? 0) n=21, k=15, i=4, s=2; 1) n=23, k=17, i=3, s=3; 2) n=26, k=19, i=3, s=4; 3) n=27, k=16, i=7, s=4; 4) n=29, k=21, i=5, s=3; 5) n=28, k=14, i=10, s=4; 6) n=27, k=18, i=3, s=6; 7) n=26, k=20, i=2, s=4; 8) n=25, k=23, i=1, s=1; 9) n=24, k=16, i=5, s=3.	Задание 14. Сколькими способами из группы в n человек можно сформировать k групп по i человек, s групп по l человек и m групп из j человек, если: 0) n=15, k=3, i=2, s=2, l=2, m=2, j=1; 1) n=16, k=2, i=3, s=1, l=2, m=1, j=2; 2) n=18, k=3, i=1, s=2, l=3, m=2, j=1; 3) n=17, k=4, i=2, s=2, l=1, m=1, j=1; 4) n=19, k=3, i=3, s=1, l=2, m=3, j=2; 5) n=28, k=1, i=5, s=3, l=4, m=2, j=3; 6) n=27, k=2, i=3, s=1, l=2, m=2, j=3; 7) n=26, k=2, i=2, s=3, l=3, m=3, j=2; 8) n=25, k=3, i=2, s=3, l=2, m=2, j=2; 9) n=24, k=2, i=5, s=2, l=1, m=2, j=2.

 

Глава 3. Графы

Операции над графами

Пусть даны два графа G₁(V₁, E₁) и G₂(V₂, E₂).

Объединением графов G₁(V₁, E₁) и G₂(V₂, E₂) при условии, что V₁ìüV₂ = Æ; E₁ìüE ₂ = Æ, называется граф G₁(V₁, E₁) îþ G₂(V₂, E₂), множеством вершин которого является множество V₁îþ V_2, а множеством его ребер является множество E₁îþE _2.

Пересечением графов G₁(V₁, E₁) и G₂(V₂, E2) называется граф G₁ (V₁, E₁) ìü G₂ (V₂, E₂), множеством вершин которого является множество V₁ìü V_2, а множеством его ребер - множество E₁ìüE _2.

Суммой по модулю два графов G₁(V₁, E₁) и G₂(V₂, E₂) при условии, что V₁ìüV₂ = Æ; E₁ìüE ₂ = Æ, называется граф G₁(V₁, E₁) Å G₂(V₂,E₂), множеством вершин которого является множество V₁îþ V_2, а множеством его ребер - множество E₁ Å E _2.. Этот граф состоит только из ребер, присутствующих либо в первом, либо во втором графе, но не в обоих одновременно.

Дополнением графа G₁ (V₁, E₁) называется граф множеством вершин которого является множество V₁, а множеством его ребер является множество = {eÎ V₁ x V₁: eÏE₁}

Примеры выполнения заданий

Пусть заданы два графа G₁(V₁, E₁) и G₂(V₂, E₂). Изобразите геометрически объединение, пересечение и сумму по модулю два.

a b c e d Решение:	a b c f g
G1(V1, E1)îþG2(V2, E2) f g	G1 (V1, E1)ìüG2(V2, E2)
G1(V1, E1) Å G2(V2,E2) f g

Задания для самостоятельного выполнения

3.2.1. Пусть заданы два графа G₁(V₁, E₁) и G₂(V₂, E₂). Изобразите геометрически объединение, пересечение и сумму по модулю два.

0) d	f
1)
2) d	g f
a 3) d f c e	d g
4)	f
g f g f g d e k 5) a d b c e d
6)
7) d
8)
9)	f g c a

Представление графов в ПЭВМ

Неориентированные графы

Неориентированный граф G (V, E) – непустое конечное множество узлов (вершин) V и набор неупорядоченных пар вершин (ребер) E.

Способы задания графа:

1) аналитический (в виде алгебраической системы);

2) геометрический (в виде произвольного рисунка);

3) матричный (в виде матриц смежности и инцидентности).

Пусть v ₁, v ₂,... v_n - вершины графа G (V, E), а e ₁, e ₂,... e_m - его ребра.

Матрицей смежности графа G называется матрица A(G)= || a_ij ||, i =1,..., n;
j = 1,..., n, у которой элемент a_ij равен числу ребер, соединяющих вершины v_i и v_j (соответственно, идущих из вершины v_i в вершину v_j).

Свойства матрицы смежности:

1) симметричная относительно главной диагонали,

2) значениями являются натуральные числа и ноль,

3) количество петель записывается на главной диагонали,

4) сумма значений по строке или в столбце равна валентности вершины.

Матрицей инцидентности для неориентированного графа с n вершинами и m ребрами называется матрица В(G) = [b_ij], i=1, 2,..., n, j = 1,2,..., m, строки которой соответствуют вершинам, а столбцы - ребрам. Элемент b_ij=1, если вершина v_i инцидентна ребру e_j и b_ij=0, если вершина v_i не инцидентна ребру e_j.

Свойства матрицы инцидентности:

1) несимметричная,

2) значениями являются ноль и единица,

3) сумма значений по строке или в столбце равна 2, если нет петель.