Дискретная математика. Кулаков Ю.В - 21 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

c
11
c
1
c
11
c
1 1
d
1
d
11 1
d
1 1
d
1 1
12 Определить число n классов эквивалентности и класс эквивалентности K(a) элемента a в задан-
ном в множестве M = {a, b, c, d} бинарном отношении эквивалентности T:
а) Т = {(a, a), (b, b), (c, c), (c, d), (d, c), (d, d)};
б) Т = {(a, a), (a, b), (a, c), (b, b), (b, a), (b, c), (c, c), (c, a), (c, b), (d, d)};
в) Т = {(a, a), (a, d), (b, b), (b, c), (c, b), (c, c), (d, a), (d, d)};
г) Т = {(a, a), (b, b), (c, c), (d, d)};
д) Т = {(a, a), (b, b), (b, c), (c, b), (c, c), (d, d)};
е) Т = {(a, a), (a, b), (a, c), (a, d), (b, a), (b, b), (b, c), (b, d), (c, a), (c, b),
(c, c), (c, d), (d, a), (d, b), (d, c), (d, d)};
ж) Т = {(a, a), (a, c), (a, d), (b, b), (c, a), (c, c), (c, d), (d, a), (d, c), (d, d)};
з) Т = {(a, a), (a, c), (b, b), (c, a), (c, c), (d, d)}.
13 Установить, является ли симметричным заданное 3-арное отношение T в множестве M = {1, 2, 3,
4}:
а) Т = {(1, 2, 3), (3, 2, 1), (2, 3, 4), (4, 3, 2)};
б) Т = {(1, 2, 3), (1, 3, 2), (2, 3, 1), (2, 1, 3), (3, 1, 2)};
в) Т = {(2, 3, 4), (2, 4, 3), (3, 2, 4), (3, 4, 2), (4, 2, 3), (4, 3, 2)};
г) Т = {(1, 3, 4), (1, 4, 3), (3, 1, 4), (3, 4, 1), (4, 1, 3), (4, 3, 1), (1, 2, 4),
(1, 4, 2), (2, 1, 4), (2, 4, 1)};
д) Т = {(1, 2, 3), (3, 2, 1), (2, 1, 3), (3, 1, 2), (1, 4, 2), (2, 4, 1)};
е) Т = {(3, 4, 1), (4, 1, 3), (1, 3, 4), (3, 1, 4), (4, 3, 1), (1, 4, 3)};
ж) Т = {(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1), (2, 3, 4),
(2, 4, 3), (3, 2, 4), (3, 4, 2), (4, 2, 3), (4, 3, 2)};
з) Т = {(1, 2, 3), (3, 2, 1)}.
14 Представить с помощью модельного графа, гиперграфа и двудольного графа симметричное 3-
арное отношение в множестве M = {a, b, c, d, e}, заданное матрицей инцидентности:
ab c d e abcde
0 1 0 1 1
10011;
а)
Q
= 1 0 1 1 0 ;
б)
Q
=
01101
1 1 1 0 0
a b c d e
abcde
0 1 1 1 0
00111.
в)
Q
= 1 0 1 0 1 ;
г)
Q
=
11100
0 1 1 0 1
4 БУЛЕВЫ ФУНКЦИИ. СПОСОБЫ ЗАДАНИЯ.
МИНИМИЗАЦИЯ В КЛАССЕ ДНФ
Функция f (x
1
, x
2
, ..., x
n
), принимающая одно из двух значений: 0 или 1 от n переменных, каждая из
которых принимает одно из двух значений:
0 или 1, называется булевой функцией от n переменных.
Булеву функцию можно задать различными способами: табличным, дизъюнкцией конституент, ги-
перкубом и перечислением десятичных эквивалентов.
При табличном задании булевой функции от n переменных строят прямоугольную таблицу. Столб-
цам этой таблицы сопоставляют переменные функции и саму функцию, а в строках записывают всевоз-
можные комбинации значений переменных (всего 2
n
комбинаций) и соответствующие им значения
функции. Например, с помощью табл. 2 задана булева функция от трех переменных.
Таблица 2
x
1
x
2
x
3
f (x
1
, x
2
,
x
3
)
x
1
x
2
x
3
f (x
1
, x
2
,
x
3
)
0 0 0 0 1 0 0 0

Страницы