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

1. х = А Ç`В \<sup></sup> Д È (`С Ç`А) , А = {x / 0 < x £ 5},

В = {x / x ³ 5}, С = {x / х < 2}, Д = {x / -3 < x < 3}

2 Доказать следующее тождество

A∪B=(A \^ B)∪(A∩B)

3 Методом математической индукции доказать

ÇA_k x ÇB_t = Ç (A_kxB_t);

k∈K t∈T (k,t) ∈KxT

4 На множестве A={18,5,19,3,17,8} задано бинарное однородное отношение R с помощью характеристического свойства «разница между компонентами больше 1 ». Представить данное отношение R перечислением, матрицей, графом.

5. Решить задачу и проиллюстрировать решение с помощью

диаграмм Венна.

Из Х выпускников вузов города владеют основами программирования на Делфи А1, на Паскале А2, на Си А3, на Делфи и Паскале А4, на Паскале и Си А5, на Делфи и Си А6, на Делфи, Си, Паскале А7.

Определить: 1) число выпускников владеющих только одним языком.

2) число выпускников не владеющих ни одним языком.

А1=62, А2=53, А3=50, А4=25, А5=20, А6=20, А7=10

Х= 110

Математическая логика

Задание 1.

Ниже приведены логические выражения. Максимально упростите выражение, воспользовавшись равносильностью алгебры высказываний. Затем с помощью таблиц истинности сравните ваше упрощенное выражение с исходным.

(BD)((C¬D)  (AC)  (¬D¬C)  (A¬C))  (¬BD)

Задание 2.

В таблице 1 заданы номера наборов аргументов, на которых логическая функция принимает значение, равное единице. Необходимо записать эту функцию в CДНФ и провести ее минимизацию методом карт.

Номера наборов аргументов
1	4	6	9	12	13	14	-

Задание 3.

Комплекс задач АСУ разработали 5 программистов T, S , K , R , D. В процессе опытной эксплуатации выяснилось, что один из блоков работает неверно. На вопрос, кто какой блок разрабатывал, были даны ответы:

1)T-2,K-3; 2)R-4,K-1; 3) T-2,R-4; 4) D-1, S-2; 5) S-3, D-5

Выяснилось, что в каждом ответе одна часть верна, другая неверна. Выяснить, кто какой блок делал?

Задание 4.

Пусть Q(x, у) - предикат порядка Рас­смотреть различные варианты квантификации его перемен­ных. Определить истинность получаемых выражений для разных случаев интерпретации области определения М пре­диката,

Теория графов

1. Для графа, приведенного на рис. 2 найти матрицу смежности А,

2. Для графа, приведенного на рис. 2 найти матрицу инциденций В.

3. Для графа, приведенного на рис. 1 найти сильные ком­поненты, начертить конденсацию и построить все его базы и антибазы.

4. Перечислить все максимальные независимые множества графа G, показанного на рис. 3 и найти число независимости [G].

5. Найти клики графа с рис. 3.

6. Произвести операции над графами с рисунка 5 и рисунка 6. Для операций отождествления и стягивания использовать граф с рисунка 6.

7. Решить задачу о наименьшем покрытии с использованием упрощений по заданному графу с рис.1 как задачу о маршрутах самолетов х₁, …., х_n – аэропорты, присвоив каждому маршруту стоимость маршрута.

8. Найти минимальное доминирующее множество по графу с рис. 2 как ЗНП

9. Раскрасить граф с рис. 4 (через r-подграфы) 1 способом

10. Раскрасить граф c рис. 6 как ЗНП-2-м способом