Дискретная математика - методичка

Добавил:

Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Национальный Технический Университет Харьковский Политехнический Институт

Предмет:

Дискретная математика

Файл:

) x3 ( x1 x2

Записати логічну функцію f(x1, x2, x3)= x2

.pdf

Скачиваний:

104

Добавлен:

02.02.2015

Размер:

718.13 Кб

Скачать

☆

<<< < Предыдущая 1 2 3 45 / 55

11.21.

еі	e1	e2	е3	е4	e5	e6	e7	e8	e9	e10	e11	e12	e13	e14	e15	e16	e17	e18	e19	e20
mi	3	4	2	1	1	2	3	3	4	1	1	1	3	2	2	2	1	3	2	3

11.22.

еі	e1	e2	е3	е4	e5	e6	e7	e8	e9	e10	e11	e12	e13	e14	e15	e16	e17	e18	e19	e20
mi	3	4	5	1	4	5	3	2	4	5	3	3	2	1	2	3	4	1	2	2

11.23.

еі	e1	e2	е3	е4	e5	e6	e7	e8	e9	e10	e11	e12	e13	e14	e15	e16	e17	e18	e19	e20
mi	1	3	4	2	1	1	3	4	2	1	3	3	4	4	3	2	1	1	2	4

11.24.

еі	e1	e2	е3	е4	e5	e6	e7	e8	e9	e10	e11	e12	e13	e14	e15	e16	e17	e18	e19	e20
mi	4	1	2	4	3	1	2	4	3	3	2	1	3	4	2	1	2	4	3	1

11.25.

еі	e1	e2	е3	е4	e5	e6	e7	e8	e9	e10	e11	e12	e13	e14	e15	e16	e17	e18	e19	e20
mi	3	2	4	1	3	4	2	1	2	4	1	3	4	2	1	2	3	3	2	4

11.26.

еі	e1	e2	е3	е4	e5	e6	e7	e8	e9	e10	e11	e12	e13	e14	e15	e16	e17	e18	e19	e20
mi	2	2	3	4	3	2	1	1	2	1	3	1	4	1	3	1	2	2	4	2

11.27.

еі	e1	e2	е3	е4	e5	e6	e7	e8	e9	e10	e11	e12	e13	e14	e15	e16	e17	e18	e19	e20
mi	3	3	2	1	3	2	1	2	2	3	2	1	1	3	4	1	2	3	5	3

11.28.

еі	e1	e2	е3	е4	e5	e6	e7	e8	e9	e10	e11	e12	e13	e14	e15	e16	e17	e18	e19	e20
mi	1	2	3	4	4	3	2	1	1	2	3	4	4	3	2	1	1	2	5	3

11.29.

еі	e1	e2	е3	е4	e5	e6	e7	e8	e9	e10	e11	e12	e13	e14	e15	e16	e17	e18	e19	e20
mi	1	3	1	4	2	3	2	4	1	3	3	4	4	2	1	1	2	1	2	4

11.30.

еі	e1	e2	е3	е4	e5	e6	e7	e8	e9	e10	e11	e12	e13	e14	e15	e16	e17	e18	e19	e20
mi	3	2	1	2	2	4	3	2	1	2	4	3	3	3	3	4	5	3	3	2

Розв’язання задач варіанта 0

Задача 1. Видаливши з множини А елементи {1, 2}, В – {9, 10},

С – {11, 13} і D {14, 16}, записати множини, одержані після виконання вказаних операцій A Ç D, A \ ( B Ç C ), B È D.

Вважаємо, що:

U = A È B È C È D

A = { 1, 2, 3, 4, 5, 6, 7, 8 }

B = { 4, 5, 6, 7, 8, 9, 10, 11, 12, 13} C = { 11, 12, 13, 14, 15, 16 }

D = { 1, 2, 3, 4, 14, 15, 16 }

Розв’язання. Видаляємо вказані елементи з даних множин. A = {3, 4, 5, 6, 7, 8},

B = {4, 5, 6, 7, 8, 11, 12, 13}, C = {12, 14, 15, 16},

D = {1, 2, 3, 4, 15}.

Виконуємо вказані в завданні операції.

1). A Ç D – це операція перерізу. Перерізом множин А та D називають множину А∩ D , яка складається з усіх елементів, що належать А та D одночасно.

А∩ D = {3, 4}.

2). Спочатку виконуємо операцію в дужках. ( B Ç D) = {4}.

A \ ( B Ç D ) – це різниця множин. Різницею множин А і ( B Ç D ) називається множина А\( B Ç D ), що складається з усіх елементів А, які не належать ( B Ç D ).

A \ ( B Ç D ) = {3, 5, 6, 7, 8}.

3). B È D – це операція об’єднання. Об'єднанням множин В та D називається множина B È D , яка складається з усіх елементів, що належать хоча б одній з цих множин, тому

B È D ={1, 2, 3, 4, 5, 6, 7, 8, 11, 12, 13, 15}.

Задача 2. Спростити вираз.

A I (B U A) I ( A U B) U B

Розв’язання. Послідовно будемо «опускати» операції доповнення, використовуючи закони де Моргана й спрощувати за рахунок інших властивостей і законів (поглинання, ідемпотентності ):

A I (B U A) I ( A U B) U B = A I (B U A) I ( A I B) U B = A I (B U A) I ( A U B) U

UB = A I ( A U B) U B = A I ( A I B) U B = A I ( A I B) U B = ( A I A I B) U B = = Æ U В = В

Задача 3. Виконати операції над трьома множинами та закреслити результат на діаграмі Ейлера-Венна.

а) A UВ∩С	б) (АÅВ)U C
А В І	В	А І
	В
С		С

Розв’язання.

а). Знайдемо спочатку A :

Далі знайдемо В∩С:

Остаточно:

б). Знайдемо АÅВ:

C :

Остаточно:

Задача 4. Довести тотожність: А∩[В\(A\ B )]=Æ.

Розв’язання. Почнемо спрощення лівої частини рівності з виразу в квадратних дужках, причому для цього застосуємо рівність A\В=А∩B , а також інші властивості операцій.

В\(А\ B )=В\(А∩B )=В\(А∩В)=В∩(A Ç B)=В∩( A B )=(В∩ A )U(В∩B )=

= (В∩ A )UÆ=В∩ A

А∩[B\(A\ B )]=A∩(B∩ A )=(A∩ A )∩B=Æ ∩B=Æ

Отже Æ= Æ. Тотожність доведено.

Задача 5. У групі 35 студентів. З них 20 чоловік рудих, а 11 – встигаючих. Крім того відомо, що не рудих відстаючих – 10 чоловік. Знайти число рудих встигаючих і число рудих невстигаючих студентів.

Розв’язання. Нехай Е – множина студентів, A E - множина рудих студентів, B E - множина встигаючих. Тоді з умови одержимо, що

= 35,

= 20,

= 11,

= 10

, і потрібно знайти

A I B

A I

З формули включень і виключень треба, що:

A U B

−

A I B

−

A U B

(1)

Отже, нам необхідно знайти A U B . Для цього розглянемо співвідношення: A I B = A U B A I B = A U B = 10 , а використовуючи той факт, що

E = ( A U B) U ( A U B) й ( A U B) I ( A U B) = Æ, можемо записати:

E = A U B + A U B - ( A U B) I ( A U B) = A U B + A U B | A U B = = E - A U B = A U B = 35 -10 = 25

Тепер з рівняння (1) одержимо: A I B = 20 + 11 − 25 = 6 .

Помітимо тепер той факт, що: ( A I B) U ( A I B) = A U (B I B) = A U = A ,

тоді:

( A I B) U ( A I

)

A I B

A I

−

( A I B) I ( A I

)

(2)

A I B + A I B − A I B I B I A = A A I B + A I B = A

Тут ми скористалися розподільним законом, законом ідемпотентності й тим, що X I X = й = 0 . Тоді з (2) витікає цілком природній результат:

A I B = A − A I B = 20 − 6 = 14 .

У такий спосіб число рудих устигаючих студентів дорівнює 6, а рудих невстигаючих – 14.

Задача 6. Дано дві множини: М={а ,б, в, г} та N = {1,3,π ,15}. Записа-

ти M×N, N×M, M×M, N×N.

Розв’язання. В відповідності з означенням прямого (декартового) добутку маємо:

M×N={(a,1),(a,3),(a,π),(a, 15 ),(б,1),(б,3),(б,π),(б, 15 ),(в,1),(в,3),(в,π), (в, 15 ), (г,1),(г,3),(г,π),(г, 15 )}.

N×M={(1,а),(1,б),(1,в),(1,г),(3,а),(3,б),(3,в),(3,г)(π,а),(π,б),(π,в),(π,г), ( 15 ,a),( 15 ,б)( 15 ,в)( 15 ,г)}.

M×M={(a,а),(a,б),(a,в),(a,г),(б,а),(б,б),(б,в),(б,г), (в,а),(в,б),(в,в),(в,г),(г,а), (г,б),(г,в),(г,г)}.

N×N={(1,1),(1,3),(1,π),(1, 15 ),(3,1),(3,3),(3,π),(3, 15 )(π,1),(π,3),(π,π), (π, 15 ),( 15 ,1),( 15 ,3)( 15 ,π)( 15 , 15 )}.

Задача 7. На множині А={2,5,7,8} задано відношення R1 – " бути порівняними по модулю 2" та R2 – " бути більше". Записати R1 та R2 перерахуванням пар, графами. Визначити: які мають властивості R1 та R2 і до яких видів

відносяться. Виконати операції R1 Å R2,					R1 \ R2, R1 ○ R2 та подати у вигляді
графів та перерахуванні пар.
Розв’язання. R1 ={(2,8),(2,2),(8,2),(8,8),(5,7),(7,5),(5,5),(7,7)}
	1	0	0	1
	0	1	1	0
R1 =	0	1	1	0
	0	1	1	0
1		0	0	1

R1 2

Довідка.		Числа а і b порівняні по модулю m>0, якщо різниця а-b ді-
литься на m без залишку.
Властивості: рефлексивність, симетричність, транзитивність (тобто ек-
вівалентність)
	R2 = {(5,2),(7,2),(8,2),(7,5),(8,5),(8,7)}
	0	0	0	0	2

	1	0	0	0
R2 =	1	1	0	0	8	5

1		1	1	0

Властивості: антирефлексивність, антисиметричність, транзитивність. Вид – суворий порядок.

R1 Å R2 = (R1 U R2) \ (R1 ∩ R2 ) = {(2,8),(2,2),(8,8),(5,7),(5,5),(7,7),(5,2), (7,2),(8,5),(8,7)}

	2
8	5
	5
	7

R1 \ R2 = {(2,8),(2,2),(8,8),(5,7),(5,5),(7,7)}

. 5

8 .7

R1 ○ R2 = {(2,2),(2,5),(2,7),(8,2),(8,7),(8,5),(5,2),(5,5),(7,2),(7,5)}

8	5
	5
	7

в диз'юнктивній нормальній формі. Підставляючи набори логічних змінних знайти значення логічної функції. Знайти Д.Д.Н.Ф.

Розв’язання.

x2 ( x1						) x3																									= x2 x1 x2									x3
												(x x												)																		(x x								)	x	=
																																						х
			х																		x							x										х										x
					3						1					2				3						1												3			1				2				3	1
x2 x1 x2								x3																	x1=x2 x1 x2														x3				(			x3) x1=
																			x																						х
																																					х
																																												х
							х							x									x																					х
					3						1					2				3															3						1				2
= x2 x1 x2											x3																					x3 x1 = (x2 x1 x1 ) x2
= x2 x1 x2									х		x3							х				х						х				x3 x1 = (x2 x1 x1 ) x2															х
					3											1				2						1																			3
( x3				x3)													= x1 x2															x3							– це є Д.Н.Ф.
( x3		х		x3)						х					х		= x1 x2												х			x3		х		х			– це є Д.Н.Ф.
1											1					2										3							1		2
						Знайдемо значення логічної функції:

	x1					x2							x3						x2	х										х			х		f(x1, x2, x3)
																				3							1						2

	0				0						0									0													1					1

	0				0						1									0													1					1

	0				1						0									1													0					1

	1				0						0									0													0					1

	0				1						1									0													0					1

	1				0						1									0													0					1

	1				1						0									1													0					1

	1				1						1									0													0					1

Знайдемо Д.Д.Н.Ф. "розщепленням":

x1 x2

= x1

( x2

) x2

(x1

) x3

(x1

)

( x3

)= x1 x2 x1

x1 x2

x3 x1 x3

						x3						=x1				) x1				)
	х		х		х		х		х		х		x2 (x3		х		х (x3		х
1		1		2		1		2		3				3			2	3

x1 x2

x3 x1 ( x2

) x3

( x2

)

= x1 x2 x3 x1 x2

x1 Ù

2 Ù x3

х2

х3

х1

х2

х3

x1 x2

x1 x2 x3

x1 Ù

2 Ù x3

x2 x3

х1

х3

х1

=║ оскільки

х х = х║ =

= x1 x2

x3 x1

x2 x3

Оскільки присутні в доданках всі можливі набори змінних x1 , x2 , x3, то функція приймає на них значення 1.

Задача 9. а ). В якої кількості випадків, граючи в "Спортлото" (угадування 5 номерів з 36) будуть правильно вгадані, не менш 3 номерів?

Розв’язання.

3 з 5 "правильних" номерів можна вибрати за формулою для числа спо-

лучень з 5 по 3, тобто C 3 . Два залишившихся вибираємо з 31 номера за фор-

мулою C

2 . Далі за правилом добутку знаходимо кількість варіантів де пра-

вильно вгадано 3 номери з 5, а 2 не вгадано, тобто

C 3

×C 2

31!

5 × 4

31× 30

= 4650 .

3!×2! 2!×29!

Аналогічно знаходимо кількість варіантів, коли вгадано 4 номера:

C 4

×C 1

31!

= 5 × 31 = 15 .

4!×1! 1!×30!

Кількість варіантів правильно вгадано 5 номерів дорівнює

C 5

×C 0

31!

= 1.

5!×0! 0!×31!

Кількість варіантів правильного вибору не менш 3 номерів знаходимо за правилом суми, тобто 4650+155+1=4806.

Відповідь: 4806.

б). Задана множина Х={0,1,2,3,4,5,6,7,8,9,10}. Властивість α1(х): "х –

парне", α2(х): "х >6", α3(х): "2< х <8". Знайти кількість елементів N0 з X , яким не притаманні ані властивості α1, ані α2, ані α3.

Розв’язання. Використаємо формулу (2) розділу Ш.

N=11

N(α1)=6 (кількість парних чисел з Х) N(α2)=4 (кількість чисел більш ніж 6 з Х)

N(α3)=5 (кількість чисел х Х, які задовольняють умові 2< х <8) N(α1,α2)=2 (кількість парних чисел більш ніж з Х)

N(α1,α3)=2 (кількість парних чисел з Х, які належать (2;8)) N(α2,α3)=1 (кількість парних чисел більш ніж 6 з інтервалу (2;8), які

належать Х)

N(α1,α2,α3)=0 (кількість чисел, які задовольняють всім трьом властивостям).

Остаточно.

N0=N-(N(α1)+N(α2)+N(α3)) + (N(α1,α2)+N(α2,α3)+N(α1,α2,α3))= 11-15+5-0=1.

Це є число х = 1. Відповідь. 1 число.

Задача 10. Які з наведених графів ізоморфні?

а)		б)
а)		б)

в)		г)
в)		г)

Розв’язання. Ізоморфні графи мають однакову кількість вершин. Тому треба порівнювати графи а) та б), а також в) та г). Але граф а) має дві висячі вершини, а граф б) – одну. Тому вони не можуть бути ізоморфними.

Розглянемо графи в) і г). Число вершин і число ребер у них однакові. Обидва графи мають по дві компоненти зв'язності і по дві висячі вершини. Позначимо вершини графів і знайдемо відповідні вершини, враховуючи степені вершин.

в)			г)
v1		v2	v1		v4


v4		v3	v2		v3


	v5			v6
	v6		v7	v7

Матриці суміжності обох графів мають вигляд:

010

A( G ) = 2

000

Відповідь:

1	0	2	0	0	0
0	1	1	0	0	0
1	0	1	0	0	0
1	1	0	0	0	0
0	0	0	0	1	1
0	0	0	0	1	1
0	0	0	1	0	0
0	0	0	1	0	0

в) і г) є ізоморфні.

Задача 11. Побудувати мінімальне остове дерево для зваженого графа G(V,E) за алгоритмом Краскала.

Розв’язання.

	v2		3		v5		2	v9
			3				2
3		1	2	4		2	2	4
3		1	2			2	2
v1	2	v3		v6	1		v8	v11
v1		v3		v6			v8	v11
2		4	2		3	4	2	3
2
				1			3
				1			3
	v4				v7			v10

1.Обираємо найкоротше ребро, наприклад (v2,v3) з довжиною 1 і позначаємо іншим кольором або двома рисками.

2.Обираємо найкоротше ребро з залишившихся, наприклад (v4,v7) .

3.За таким же принципом обираємо дуги (v6,v8), (v1,v2), (v1,v4),(v4,v6),

(v5,v9), (v8,v9), (v8,v10), (v10,v11). При цьому треба уважно дивитись, щоб не утворювалося циклів.

Сумарна довжина ребер дорівнює 18.

<<< < Предыдущая 1 2 3 45 / 55

	v2		3		v5		2	v9
			3				2
3		1	2	4		2	2	4
3		1	2			2	2
v1	2	v3		v6	1		v8	v11
v1		v3		v6			v8	v11
2		4	2		3	4	2	3
2
				1			3
				1			3
	v4				v7			v10

	v2		3		v5		2	v9
			3				2
3		1	2	4		2	2	4
3		1	2			2	2
v1	2	v3		v6	1		v8	v11
v1		v3		v6			v8	v11
2		4	2		3	4	2	3
2
				1			3
				1			3
	v4				v7			v10

	v2		3		v5		2	v9
			3				2
3		1	2	4		2	2	4
3		1	2			2	2
v1	2	v3		v6	1		v8	v11
v1		v3		v6			v8	v11
2		4	2		3	4	2	3
2
				1			3
				1			3
	v4				v7			v10