Практика по дискретной математике: логика и графы

Задача 1.
Даны числовые множества
A = {12, 14, 33, 39},
B = {33, 14, 39, 40},
C = {33, 41, 43, 44}.

Найти множества:

1. D=A∩(B∖C)D = A cap (B setminus C)D=A∩(B∖C);
2. E=B∪(A△C)E = B cup (A triangle C)E=B∪(A△C).

Задача 2.
Найти декартовы произведения A×BA times BA×B и B×AB times AB×A для данных множеств:
A = {3, 1},
B = {8, 1, 7}.

Задача 3.
Для заданных формул fff и ggg построить таблицы истинности и определить, являются ли эти формулы эквивалентными.

Формулы:
f(x,y,z)=((x∧y)∨(x↓y))↑((z↑y)↓(y↔x))f(x,y,z) = ((x land y) lor (x ↓ y)) ↑ ((z ↑ y) ↓ (y ↔ x))f(x,y,z)=((x∧y)∨(x↓y))↑((z↑y)↓(y↔x))
g(x,y,z)=((z∣x)∣(z∣y))→((x∨z)↓(z↓y))g(x,y,z) = ((z | x) | (z | y)) → ((x lor z) ↓ (z ↓ y))g(x,y,z)=((z∣x)∣(z∣y))→((x∨z)↓(z↓y))

Задача 4.
Для булевой функции f(x,y,z)f(x,y,z)f(x,y,z), заданной двоичным вектором значений, определить:

1. существенные и фиктивные переменные;
2. совершенную дизъюнктивную нормальную форму (СДНФ);
3. совершенную конъюнктивную нормальную форму (СКНФ);
4. полином Жегалкина двумя способами.

Дано: f(x,y,z)=(01011000)f(x,y,z) = (01011000)f(x,y,z)=(01011000).

Задача 5.
Для булевой функции, заданной двоичным вектором значений
f(x1,x2,x3,x4)=(1011 1111 1110 0010)f(x_1,x_2,x_3,x_4) = (1011,1111,1110,0010)f(x1​,x2​,x3​,x4​)=(1011111111100010),
с помощью карты Карно найти:

1. минимальную дизъюнктивную нормальную форму (МДНФ);
2. минимальную конъюнктивную нормальную форму (МКНФ).

Задача 6.
Найти число способов такой расстановки 20 томов на книжной полке, при которой первые 15 томов стоят рядом в порядке возрастания номеров.

Задача 7.
В военном подразделении служат 9 офицеров и 16 рядовых.
Оперативная группа состоит из командира, заместителя и 10 рядовых, причем командир и его заместитель назначаются случайным образом из числа офицеров.

Найти число возможных оперативных групп.

Задача 8.
По заданной матрице смежности A(G)A(G)A(G) построить неориентированный граф GGG.
Составить:

• таблицу степеней вершин,
• матрицу инцидентности,
• таблицу расстояний и условных радиусов.

Найти радиус и центр графа.