Nazarova_Met-ka_po_DM_2006

59

19.x y ↓ (y ≡ z | y) xz → y

20.z ≡ x | y x → xz ↓ y

21.z y | x ↓ y z → x ≡ y

22.z x ≡ yz → y | z ↓ xz

23.(x → y)→(y z)| x | y (z y)

24.xz → z y ↓ z x

25.x y ↓ z | x ≡ x ↓ zx → z

26.(x ≡ z) (y xz)→ xy

27.(x ↓ y) (y ↓ x) (z ↓ y)

28.(yz x)| (y z)↓ (yz x)

29.(xy z) (x | y) y

30.(y ≡ z)| (x y z) (y → z)x y

6.Минимизировать функцию трех переменных F(x,y,z) c использованием куба.Функция F(x,y,z) задана выше.

7.Сгенерировать по указанному ниже алгоритму функции Q(x1, x2, x3, x4), R(x1, x2, x3, x4, x5) и S(x1, x2, x3, x4, x5).

8.Минимизировать функцию четырех переменных Q(x1,x2,x3,x4) c

использованием куба, карт Карно и метода Квайна – Мак-Класки.

9.Минимизировать функцию пяти переменных R(x1,x2,x3,x4,x5) c использованием карт Карно и метода Квайна – Мак-Класки.

10.Минимизировать не полностью определеннные функции W(x1,x2,x3,x4,x5) пяти переменных и P(x1,x2,x3,x4 ,x5) пяти переменных c использованием карт Карно.

6.3 Алгоритм генерации варианта

Записать строку S =<ФИО>.Удалить в строке S повторяющиеся буквы. Пронумеровать все буквы получившейся строки таким образом, что n(Si) − номер буквы в русском алфавите.

Для генерации функции Q(x1,x2,x3,x4) оставить первые 7 неповторяющихся чисел, полученных после преобразования n(Si) = n(Si) mod 16. Полученные значения определяют единичные наборы функции Q(x1,x2,x3,x4).

Для генерации функции R(x1,x2,x3,x4,x5) оставить первые 11 неповторяющихся чисел, полученных после преобразования n(Si) = n(Si) mod 32. Полученные значения определяют единичные наборы функции R(x1,x2,x3,x4,x5).

60

Для генерации функции W(x1,x2,x3,x4,x5) оставить первые 11 неповторяющихся чисел, полученных после преобразования n(Si) = n(Si) mod 32.

Для генерации функции Р(x1,x2,x3,x4,x5) оставить первые 11 неповторяющихся чисел, полученных после преобразования n(Si) = n(Si) mod 16. Первые 5 из этих 11 значений определяют единичные наборы функции Р(x1,x2,x3,x4,x5), а значения с 6 по 11 − задают наборы функции, на которых она неопределена.

61

7 ПРИМЕРЫ РЕШЕНИЯ ТИПОВЫХ ЗДАНИЙ.

7.1Контрольная работа №1.

Задание 1. Способы задания множеств. Операции над множествами.

ФИО студента: Широкова Екатерина Алексеевна.

Исходные данные:

A= {е, к, а, т, р, и, н}

B= {а, л, е, к, с, в, н}

C= {ш, и, р, к, о, в, а}

V = {а, б, в, г, д, е, ë, ж, з, и, й, к, л, м, н, о, п, р, с, т, у, ф, х, ц, ч, ш, щ, ь, ы, ъ,

э, ю, я}

−А∩В = {а, е, к, н}

−А∩С = {к, а, р, и,}

−В∩С = {а, в, к}

−А∩В∩С = {а, к}

−А В = {е, к, а, т, р, и, н, л, с, в}

−А С = {е, к, а, т, р, и, н, ш, о, в}

−В С = {е, к, а, р, и, н, л, с, в, ш, о}

−А В С = {е, к, а, р, и, н, л, с, в, ш, о, т}

−А \ В ={и, р, т }

−В \ А ={с, л, в,}

−А \ С = {т, е, н}

−В \ С = {е, л, н, с}

−С \ А ={в, о, ш}

−С \ В ={и, о, р, ш}

−A = {б, в, г, д, ë, ж, з, й, л, м, о, п, с, у, ф, х, ц, ч, ш, щ, ь, ы, ъ, э, ю, я}

−В = {б, г, д, ë, ж, з, и, й, м, о, п, р, т, у, ф, х, ц, ч, ш, щ, ь, ы, ъ, э, ю, я}

−С = {б, г, д, е, ë, ж, з, й, л, м, н, п, с, т, у, ф, х, ц, ч, щ, ь, ы, ъ, э, ю, я}

−А ∩ А =

−В В = V

−А С = {а, е, к, и, н, р, т, б, г, д, ж, з, л, м, п, с, у, ф, х, ц,ч, ш, щ, ь, ы, ъ, э,

ю, я}

−А ∆ В = {в, и, л, р, с, т}

−А ∆ С = {в, е, н, о, ш, т}

−В ∆ С = {е, и, л, н, о, р, с, ш}

−С ∆ А = А ∆ С

− (А ∩ С) В = {а, к, б, г, д, ж, з, и, м, о, п, р, т, у, ф, х, ц, ч, ш, щ, ь, ы, ъ, э, ю,

я}

62

−А (В ∩ С) = {в, а, е, к, и, н, р, т}

−(А В) ∩ (А С) = {в, а, е, к, и, н, р, т} = А (В ∩ С)

−(А – С) (В – С) = {е, л, т, с, н}

Задание 2. Диаграммы Эйлера-Венна.

Задание 3. Основные соотношения алгебры множеств.

а. A ∩ B = А В

A ∩ B = {б, в, г, д, ж, з, и, л, м, о, п, р, с, т, у…я}

А В = {б, в, г, д, ж, з, и, л, м, о, п, р, с, т, у…я} b. A B = А ∩В

A B = {б, г, д, ж, з, м, о, п, у…я}

А ∩В = {б, г, д, ж, з, м, о, п, у…я}

c.А – (В С) =(А – В)∩ (А – С)

А– (В С) = {т}

(А – В)∩ (А – С) = {т}

d.А – (В∩С) = (А – В) (А – С)

А– (В∩С) = {е, и, н, р, т}

(А – В) (А – С) = {и, р, т, е, н, }

Задание 4. Доказать тождества, используя отношения принадлежности. Продемонстрировать тождества на диаграммах Эйлера-Венна.

1.A = A

x A x A x A

x A x A x A

63

3.A ∩(B∆C )= (A ∩ B)∆(A ∩C )

A ∩[(B −C ) (C − B)]= [(A ∩ B)−(A ∩C )] [(A ∩C )−(A ∩ B)]

Задание 5. Прямое произведение множеств.

Исходные данные: N1 = {2,0,5,9} N2 = {2,0}

a. N1× N2 = {(0,0), (0,2), (2,0), (2,2), (5,0), (5,2), (9,0), (9,2)}

64

b.N2× N1 = {(0,0), (0,2), (0,5), (0,9), (2,0), (2,2), (2,5), (2,9)}

1.G =(N1× N2)∩(N2× N1) = {(0,0), (0,2), (2,0), (2,2)}

2.F = (N1∩ N2)× (N2∩ N1).

N1∩ N2 = N2∩ N1 = N2 = {2,0} F = {(0,0), (0,2), (2,0), (2,2)} G = F

3.A = (N1× N2) (N2× N1) ={(0,0), (0,2), (2,0), (2,2), (5,0), (5,2), (9,0), (9,2), (0,5), (0,9), (2,5), (2,9)}

4.B = (N1 N2)× (N2 N1).

N1 N2 = N2 N1 = N1 = {2, 0, 5, 9}

5.B = {(0,0), (0,2), (2,0), (2,2), (5,0), (5,2), (9,0), (9,2), (0,5), (0,9), (2,5), (2,9),

(5,5), (5,9), (9,5), (9,9)} A ≠B; A B

ρ1 =

ρ1′ = {(n, m) | n – нечетно, m – четно} ρ1′ = {(5,0), (5,2), (9,0), (9,2)}

ρ2 = {(n, m) | n – четно, m – четно} ρ2 = {(0,0), (0,2), (2,0), (2,2)}

ρ3 = {(n, m) | m>=n }

ρ3 = {(0,0), (2,0), (2,2), (5,0), (5,2), (9,0), (9,2)}

65

ρ1 – нерефлексивно, антирефлексивно, симметрично, антисимметрично, транзитивно.

ρ2 – нерефлексивно, не антирефлексивно, симметрично, не антисимметрично, транзитивно.

ρ3 – нерефлексивно, не антирефлексивно, несимметрично, антисимметрично, нетранзитивно.

Задание 7.

66

ρ9, ρ14, ρ15 – отношения частичного порядка. ρ9, ρ2 – отношения эквивалентности:

Задание 8.

Исходные данные:

А = {1, 2, 3, 4, 5, 6,}

ρ= {(m, n) | (m – n) – делится нацело на 3}

γ= {(m, n) | m <= n}

Dρ = Dγ = Z – “0” (отрицательные и положительные без 0)

A2 = {(1,1), (1,2), (1,3), (1,4), (1,5), (1,6), (2,1), (2,2), (2,3), (2,4), (2,5), (2,6), (3,1), (3,2), (3,3), (3,4), (3,5), (3,6), (4,1), (4,2), (4,3), (4,4), (4,5), (4,6), (5,1), (5,2), (5,3) (5,4), (5,5), (5,6), (6,1), (6,2), (6,3), (6,4), (6,5), (6,6)}

ρ = {(1,4), (2,5), (3,6), (4,1), (5,2), (6,3)} γ = {(1,1), (1,2), (1,3), (1,4), (1,5), (1,6), (2,2), (2,3), (2,4), (2,5), (2,6), (3,3), (3,4),

(3,5), (3,6), (4,4), (4,5), (4,6), (5,5), (5,6), (6,6)}

ρ-1 = {(m, n) | (m – n) – не делится нацело на 3}

ρ-1 = {(1,1), (1,2), (1,3), (1,5), (1,6), (2,1), (2,2), (2,3), (2,4), (2,6), (3,1), (3,2), (3,3), (3,4), (3,5), (4,2), (4,3), (4,4), (4,5), (4,6), (5,1), (5,3) (5,4), (5,5), (5,6), (6,1), (6,2), (6,4), (6,5), (6,6)}

ρ γ ={(1,4), (1,5), (1,6), (2,5), (2,6), (3,6), (4,1), (4,2), (4,3), (4,4), (4,5), (4,6), (5,2), (5,3) (5,4), (5,5), (5,6), (6,3), (6,4), (6,5), (6,6)}

ρ-1 γ = {(1,1), (1,2), (1,3), (1,4), (1,5), (1,6), (2,1), (2,2), (2,3), (2,4), (2,5), (2,6), (3,1), (3,2), (3,3), (3,4), (3,5), (3,6), (4,2), (4,3), (4,4), (4,5), (4,6), (5,1), (5,2), (5,3) (5,4), (5,5), (5,6), (6,1), (6,2), (6,3), (6,4), (6,5), (6,6)}

ρ−1 γ = {(4,1)}

67

68

7.2 Контрольная работа №2.

Задание 10.Функции Алгебры логики.

f (x, y,z)=z x ≡y z →y|z ↓x z

Фиктивных аргументов нет.

Задание 11.

Представить фал аналитически в ДСНФ и КСНФ.