Задание 7. Преобразование выражений.

Доказательство:

Данное тождество означает, что каждый элемент множества АÇ( ÈВ) принадлежит и множеству АÇВ, и обратно.

    Пусть х Î АÇ( ÈВ) Þ (по определению Ç) х ÎА и х Î ( ÈВ) Þ 

(хÎА и хÎ ) или (хÎА и хÎВ). Так как х не может одновременно принадлежать множествам А и , то получаем: хÎА и хÎВ Þ хÎАÇВ

    Обратно: пусть хÎАÇВ Þ хÎА и хÎВ. Из того, что хÎВ следует, что х может принадлежать объединению В с любым множеством, тогда пусть хÎ( ÈВ) и, в итоге, хÎАÇ( ÈВ).

2 задание. Заданное бинарное отношение R доопределите минимальным образом до отношения эквивалентности R`и выпишите классы эквивалентности.

Вариант 1: R={(7,9),(8,8),(4,5),(6,3),(1,1),(9,10),(2,7),(1,6)};

Вариант 2: R={(3,1),(2,4),(5,8),(6,2),(10,7),(9,1),(8,11)};

Вариант 3: R={(7,3),(4,2),(8,9),(9,4),(1,5),(6,11),(10,7),(9,9)};

Вариант 4: R={(1,1),(8,8),(7,9),(4,5),(6,3),(10,9),(7,2),(1,6)};

Вариант 5: R={(1,3),(2,2),(2,7),(1,5),(5,5),(10,7),(4,6),(8,8),(9,2)};

Вариант 6: R={(2,2),(1,5),(1,3),(7,2),(6,4),(10,7),(5,5),(7,7),(9,2)};

Вариант 7: R={(4,1),(3,2),(1,5),(6,8),(9,10),(7,7),(10,6)}.

Пояснения. Отношение R есть отношение эквивалентности, если оно рефлексивно (" аÎА (а,а)ÎR), симметрично ( если (а,b)ÎR, то (b,а)ÎR) и транзитивно (если (а,b) и (b,с) ÎR, то (а,с)ÎR).

Задание. Теория графов.

Вариант 1. Занумеровать узлы и дуги и задать орграф матрицами смежности и инцидентности.

Вариант 2.Занумеровать узлы и дуги и задать орграф матрицами Кирхгофа и инцидентности.

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

Вариант 4. Занумеровать узлы и дуги и задать орграф матрицами Кирхгофа и инцидентности.

Вариант 5. Задать граф матрицей смежности и массивом смежности?

Вариант 6. Задать граф матрицами Кирхгофа и инцидентности, занумеровав вершины и ребра.

Вариант 7. Задать граф матрицами смежности и инцидентности, занумеровав узлы и дуги.

Задание. Алгоритмы.

Вариант 1. В каком порядке алгоритм поиска в ширину посетит вершины графа, заданного списками смежности, начиная из 2–ой вершины?

52

613

274

3

16

25

3

Вариант 2. В каком порядке алгоритм поиска в ширину посетит вершины графа, заданного списками смежности, начиная из 3–ей вершины?

52

613

274

3

16

25

3

Вариант 3. В каком порядке алгоритм поиска в глубину посетит вершины графа, заданного списками смежности, начиная из 3–ей вершины?

52

613

274

3

16

25

3

Вариант 4.В каком порядке алгоритм поиска в глубину посетит вершины графа, заданного списками смежности, начиная из 1–ой вершины?

52

613

247

3

16

25

3

Вариант 5. В каком порядке алгоритм поиска в глубину посетит вершины графа, заданного списками смежности, начиная из 4–ой вершины?

52

613

274

3

16

25

3

Вариант 6. В каком порядке алгоритм поиска в ширину посетит вершины графа, заданного списками смежности, начиная из 4–ой вершины?

52

613

472

3

16

25

3

Вариант 7.В каком порядке алгоритм поиска в ширину посетит вершины графа, заданного списками смежности, начиная из первой вершины?

25

613

274

3

16

25

3

Задание. Алгоритмы.

Вариант 1. Областное управление планирует строительство дорог, которые должны соединить пять населенных пунктов либо друг с другом, либо через другие города. В таблице приведены затраты на строительство дорог. Ноль означает, что дорога есть. (Воспользоваться алгоритмом построения минимального остова)

Вариант 2. Областное управление планирует строительство дорог, которые должны соединить пять населенных пунктов либо друг с другом, либо через другие города. В таблице приведены затраты на строительство дорог. Ноль означает, что дорога есть. (Воспользоваться алгоритмом построения минимального остова)

Вариант 3. В графе найти длину кратчайшего пути из х₄ в х₁ при помощи алгоритма Дейкстры.

Вариант 4. В графе найти длину кратчайшего пути из х₄ в х₂ при помощи алгоритма Дейкстры.

Вариант 5. Используя алгоритм Дейкстры, найти расстояния от вершины v₀ до остальных вершин сети:

Вариант 6. Используя алгоритм Дейкстры, найти расстояния от вершины v₀ до остальных вершин сети:

Вариант 7. Найдите минимальный остов во взвешенном графе:

Задание 6. Булевы функции.Заданные булевы функции представить в виде таблицы и разложить в СДНФ, СКНФ, полином Жегалкина, проверить является ли функция самодвойственной, монотонной, линейной.

Вариант 1. (a®b) + (b®ac) Ú (a®c)

Вариант 2. ((a®`b) ®c) Úa`dc) +( `a +b);

Вариант 3. ((d®b) ®c) Ú`adc) + (`a +b);

Вариант 4. ((d®b) +(`b®c)) + d;

Вариант 5. ((а + b) + (bÚd)) ®bd.

Вариант 6. ;

Вариант 7. .

Задание 7. Преобразование выражений.

Максимально упростите выражение, используя тождества.

Вариант 1. ;

Вариант 2. ;

Вариант 3. ;

Вариант 4. ;

Вариант 5. ;

Вариант 6. ;

Вариант 7. .

Мы поможем в написании ваших работ!