Алебра логики.Теория множеств. Графы. 16 задач

1 Алгебра логики
Задание 1
Упростите логическое выражение:
Задание 2
Составьте таблицу истинности логического выражения:
Задание 3
Нарисуйте логическую схему для следующего логического выражения:
Задание 4
По заданной таблице истинности записать логическую функцию
1) 
а b F(a,b)
0 0 1
0 1 0
1 0 0
1 1 1


2 Теория множеств

Важно: объекты, из которых состоит множество, называют элементами множества или точками множества. Каждый элемент множества уникален, и в множестве не может быть двух идентичных элементов. Иначе говоря, добавление к множеству элементов, идентичных уже принадлежащим множеству, не меняет его:
{6, 11} = {11, 6} = {11, 11, 6, 11, 6}.

Задание 1
Даны множества А, B, C.
2,4,5,8 3,4,7,8 1,2,4,7
Найти

Для полученных множеств вычислить их мощность. Для множества найти булеан и вычислить его мощность.


Задание 2
Множества A,B,C находятся в общем положении. Проиллюстрируйте диаграммами Венна

Задание 3
Общее положение множеств A,B,C изображено на диаграмме Венна:

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

1)


Задание 4
Выполнить аналитические преобразования, применяя законы алгебры множеств:

1) 
Задание 5
Задание полностью для всех. Указать в каких отношениях находятся множества:

a) {0,1} и {2,3}
b) {0,1}и {0,1,2,3}
c) {0,1,1}и {1,0}
d) {-1,0,1} и N
e) {0,1,2,3} и {0,1,{2,3}}
f) Z и R
g) C и R
h) Z\{n|n=k∈N} и N

Задание 6
Задание полностью для всех. Представьте вашу фамилию или имя в виде множества символов. Для этого множества представьте два семейства, одно из которых является покрытием, второе – разбиением.
Мощность покрытия – 6, мощность разбиения не менее 3.

Задание 7
Записать эквивалентное выражение для выражения:

1)  , используя только операции , ̄
2)  , используя только операцию \


3 Теория графов
Задание 1
Выделить компоненты сильной связности в орграфе:


Задание 2
Выделить компоненты сильной связности в орграфе, заданной матрицей смежности:
 1 2 3 4 5 6 7 8 9
1 0 1 0 1 0 0 0 0 0
2 0 0 0 0 1 0 0 0 0
3 0 0 0 0 0 1 0 0 0
4 0 0 0 0 0 0 0 0 0
5 0 0 1 1 0 0 0 0 0
6 0 1 0 0 0 0 0 0 0
7 0 0 0 0 0 0 0 1 0
8 1 0 0 0 0 0 0 0 1
9 0 0 0 1 0 1 0 0 0


Задание 3. Выделить остов минимального веса в графе, заданном матрицей расстояний

7)

Задание 4
Дан список дуг с указанием их длин. Составьте по нему рисунок ориентированного графа. В полученном графе алгоритмом Форда-Беллмана найти кратчайшие маршруты от вершины 1.

1.  (0;1) – 3, (0;2) – 2, (2;1) – 1,
(2;5) – 3, (1;5) – 4, (5;4) – 8,
(5;3) – 5, (3;4) – 3, (4;6) – 2,
(3;6) – 4.

Задание 5.
Для орграфа дана матрица весов. В позиции ( i, j ) записана длина дуги из вершины i в вершину j (ноль означает, что пути из i в j не существует). Если согласно матрице путь i j существует, то путь j i не существует. Задание: найти кратчайшие маршруты от вершины 1 используя алгоритм Дейкстры.
6.