Контрольная работа по дисциплине "Дискретная математика"

 

Задание № 1 . Множества, отношения, логика

 

I. МНОЖЕСТВА И ОПЕРАЦИИ НАД НИМИ.

1.1. Для  заданных множеств А, В и С найти:

АᴗВ, АᴗС, ВᴗС, АᴗВᴗС, АᴖВ, АᴖС, ВᴖС, АᴖВᴖС, А \ В, В \ А, А \ С,С \ А,

B \ C, C \ B, (А \ В) \ С, А \ (В \ С), А B, А С, B C, A B C. Изобразить на плоскости А В, А С, В С. Найти ,,, считая универсальным множеством множество ℝ – всех вещественных чисел (всю числовую ось).

А = (-10; 4) – интервал на числовой оси

В = [0;10] – отрезок на числовой оси

С = (2; 7] – полуинтервал на числовой оси

Решение:

АᴗВ = (-10;10].

АᴗС = (-11;7]

ВᴗС = [0;10]

АᴗВᴗС =(-10;10].

Аᴖ В = [0;4)

АᴖС = (2;4)

ВᴖС = (2; 7]

АᴖВᴖС = (2;4)

А \ В = (-10;0)

В \ А = [4;10]

А \ С = (-10;2]

С \ А = [4;7]

B \ C = {[0;2],(7;10]}

C \ B =

(A ǀ B) ǀ C =(-10;0)

A ǀ(B ǀ C) =(-10;0)

А B=(AǀB) ᴗ(BǀA)={(-10;0), [4;10]}

А С={(-10;2], [4;7]}

B C={[0;2],(7;10]}

A B C={(-10;0), (2;4),(7;10]}

={(-∞;-10],[4, ∞)},

={(-∞;2],(7; ∞)}

А В

 

 

 

 

 

А С

 

 

 

В С

 

 

 

 

 

 

1.2. Докажите  тождество, используя диаграммы  Эйлера – Венна.

(А B)\C=A\(BᴗC))ᴗ(B\(AᴗC))

Решение:

Изобразим диаграмму для левой части:

(А B)\C

 

Рассмотрим  правую часть A\(BᴗC))ᴗ(B\(AᴗC)).

Поэтапно

A\(BᴗC))

(B\(AᴗC)).

И в итоге  получаем A\(BᴗC))ᴗ(B\(AᴗC)).

Сравнивая диаграммы левой и правой части, можно сделать вывод, что выражение  выполняется. Левая часть является подмножеством правой части.

 

 

II. ОТНОШЕНИЯ. ФУНКЦИИ. ОТНОШЕНИЯ ЭКВИВАЛЕНТНОСТИ И УПОРЯДОЧЕННОСТ И.

2.1. Даны множества А ={[а, b, c }и В={1,2,3,4} и два бинарных отношения: Р₁ А В и Р₂ В²

Р1 = {(а,1); (a,2); (a,3); (a,4); (b, 3); (с, 2)}

Р2 = {(1,1); (1, 4); (2, 2); (2, 3); (3, 3);(3,2);(4;1); (4, 4)} .

Изобразите Р₁, Р₂ графически. Найдите Р₁^-1,Р₂^-1, (Р₂ ° Р₁), (Р₂ ° Р₁)^-1 ,

(Р₁^-1 °Р 2 ^-1).

Определите, является ли отношение Р2 рефлексивным, транзитивным, симметричным, антисимметричным.

Решение:

Рассмотрим графическое представление бинарных отношений:

Р₁

 

 

 

Р₂

 

По определению обратное отношение P^-1 = {(x, y) : ( y, x)Î P}. Таким образом, Р1^-1={(1,a); (2,a);(3,a); (4,a); (3,b); (2,c)} и P2^-1={(1,1); (4,1); (2,2);

(3,2); (3,3); (2,3);(1,4);(4,4)}.

По определению композиции бинарных отношений

 P₂ °P ₁={( x,z ): xA, z B и yB (x, y P₁ и (y,z) P₂}

Таким образом, P₂ °P ₁ ={ (a,1);(a,4); (a,2);(a,3);(b,3); (b,2); (c,3); (c,2)}.

Тогда P₂ °P ₁^-1={(1,a); (4,a); (2,a);(3,a);(3,b); (2,b); (3,c); (2,c)}.

P₂ ^-1°P ₁^-1={(1,a); (4,a); (2,a);(3,a);(3,b); (2,b); (3,c); (2,c)}.

Последние два множества совпадают, что и должно быть по свойствам

композиции.

Отношение Р2 рефлексивно, т. к. в соответствии с определением рефлексивности xB(x,x)P₂ . У нас выполняется, т.к. (1,1);(2,2);(3,3);(4,4) P₂.

a) Отношение Р2 является транзитивным, поскольку по определению транзитивности требуется, чтобы для любых пар (x, y) и (y, z), таких что (x, y) P₂ и ( y, z)P₂ следовало бы, чтобы пара (x, yP₂ .

Например, пары (1,4) и (4,1) P₂, и пара (1,1) принадл.Р2.

b) Отношение Р2 является симметричным, т. к. по определению

симметричности для любой пары (x, y) Р2 должно быть и (y, x) Р2 .

Например, пара (1,4) Р2 и пара (4,1) P₂.

c) Отношение Р2 неантисимметрично, поскольку для любой пары (x, y) Р2 такой, что (y, x) Р2 необязательно следует, что x=y.

Например, (1,4)P₂ и (4,1)P₂. Но 4≠1.

III. ФУНКЦИИ И ФОРМУЛЫ АЛГЕБР Ы ЛОГИК И. ЭКВИВАЛЕНТНОСТ Ь

ФОРМУЛ.

3.1. Составьте  полную и сокращенную таблицы  истинности формул.

(x˅)→(y⊕); x↓(≡(z↓))

Решение.

Для построения полной таблицы истинности первой

формулы выделим подформулы:

f1=

f2= x˅f1

f3=

f4=y⊕f3

f5=f2→f4

Таким образом, таблица будет содержать 4 строки и 7 столбцов.

Значения  формулы совпадают со значениями последнего столбца таблицы.

x	y	F1	F2	F3	F4	F5
0	0	1	1	1	1	1
0	1	0	0	1	0	1
1	0	1	1	0	0	0
1	1	0	1	0	1	1

 

Сокращенная таблица истинности строится непосредственно под формулой. Столбец  результата выделяем. Стрелками показываем столбцы,

участвующие в операции. Номером  – столбец, полученный в результате операции.

(x˅)→(y⊕);

x	˅		→	y	⊕
0	1	1	1	0	1	1
0	0	0	1	1	0	1
1	1	1	0	0	0	0
1	1	0	1	1	1	0

 

 

Рассмотрим  вторую формулу.  x↓(≡(z↓))

Выделим подформулы второй заданной формулы:

Построим  полную таблицу истинности.

x↓(≡(z↓))

F1=

F2=

F3=

F4=z↓f3

F5=(f1≡f4)

F6=x↓f5

 

 

 

x	y	z	F1	F2	F3	F4	F5	F6
0	0	0	1	0	1	0	0	1
0	0	1	1	0	1	0	0	1
0	1	0	0	0	1	0	1	0
0	1	1	0	0	1	0	1	0
1	0	0	1	0	1	0	0	0
1	0	1	1	0	1	0	0	0
1	1	0	0	1	0	1	0	0
1	1	1	0	1	0	0	1	0

 

Сокращенная таблица истинности для второй формулы

x                    ↓          (≡         (z           ↓                 

0	1	1	0	0	0	1	0	0	0
0	1	1	0	1	0	1	0	0	0
0	0	0	1	0	0	1	0	0	1
0	0	0	1	1	0	1	0	0	1
1	0	1	0	0	0	1	1	0	0
1	0	1	0	1	0	1	1	0	0
1	0	0	0	0	1	0	1	1	1
1	0	0	1	1	0	0	1	1	1

 

 

4.1. Игральный  кубик имеет шесть граней, на  каждой из которых нанесены  очки в количестве от 1 до 6. Какова вероятность того, что после двух бросаний количество очков в сумме составит 4.

Решение.

Как известно, вероятность равна P=m*n,

где n - общее число испытаний, m - число благоприятствующих испытаний, т.е. испытаний при которых в сумме выпало число 4. Подсчитаем общее число испытаний n=6∗6=36 - количество возможных комбинаций чисел при двух бросках кубика. Подсчитаем число испытаний при которых в сумме выпало 4очка. Это комбинации (2;2), (3;1), (1;3).

т.е. получили 3 испытания, при которых в сумме выпало 4очка. Найдем вероятность

P=mn=3/36≈0,083.

Ответ: вероятность того что в  сумме выпадет 2 или 12 очков после 2-х бросков кубика равна P≈0,083.

5.1. Первое предприятие выпускает 25% всей продукции данного вида;

второе – 35 % и третье – 40%. При этом доля изделий, обладающих не-

стандартными характеристиками, составляет на первом предприятии 6%, а на втором и третьем, соответственно, 12% и 21%. Какова вероятность приобрести стандартное изделие? На каком предприятии оно вероятнее всего было выпущено?

Решение

1. Доля стандартных изделий на 1 предприятии=1-0,06=0,94.
2. Доля стандартных изделий на 2 предприятии=1-0,12=0,88.
3. Доля стандартных изделий на 3 предприятии=1-0,21=0,79.

Вероятность приобрести стандартное  изделие находим по формуле полной вероятности.

Р=0,25*0,94+0,35*0,88+0,4*0,79=0,859.

Вероятность того, что изделие выпущено на первом предприятии

Р1=0,25*0,94/0,859=0,274.

Вероятность того, что изделие выпущено на втором предприятии

Р2=0,35*0,88/0,859=0,359.

Вероятность того, что изделие выпущено на третьем предприятии

Р3=0,4*0,79/0,859=0,368.

Ответ. вероятность приобрести стандартное  изделие 0,859, на третьем предприятии оно вероятнее всего было выпущено.

 

 

 

 

 

Задание № 3 . Графы

VI. ОРИЕНТ ИРОВАННЫЕ Г РАФЫ

6.1. Найдите вершины и ориентированные  ребра графа. Для каждой вершины

определите степень входа и  выхода. Имеются ли здесь источники  и стоки?

 

a,b,c,d– вершины, {(a,b);(a,d);(b,b);(b,d);(b,c); (d,c);(d,b)}- ребра

1. степень входа 0, степень выхода 2.
2. степень выхода 3, степень входа 3
3. степень входа 2, степень выхода 0-сток
4. степень входа 2, степень выхода 2.

6.2. Составить матрицу смежности  графа.

	a	b	c	d	e
a	0	0	1	0	1
b	0	1	0	1	0
c	1	0	1	0	1
d	0	1	0	1	0
e	1	0	1	0	0