Дискретная математика

Задача 1

Доказать равенство, используя свойства операций над множествами:

 (A\B)U(A^C)=A\(B\C)

Задача 2

Пусть имеется множество A={1,2,3,4}, на этом множестве определены отношения R0A2 и P0A2.

а) Определить, является ли отношение P рефлексивным.

б) Построить графические представления отношений R, P, P0R.

в) Найти области определения и множества значений для отношений R, P, P0R.

R={(x,y)| x2 >= 12y }, P={(x,y)| x+y2 делится на 3}

Задача 3

Сколько четырехзначных чисел можно образовать из цифр указанного числа?

1112345678900

Задачи 4

Управление имеет 151 предприятий, из них 80 предприятий выпускают продукцию А, 90 – продукцию B, 70 – продукцию С. Продукцию А и В выпускают 40 предприятий, В и С – 50 предприятий, А и С – 20 предприятий. Все виды продукции выпускают 3 предприятия. Сколько предприятий

а) выпускают ровно один вид продукции А, В или С?

б) не выпускают ни одного из указанных видов продукции?

Задача 5

Найти последовательность {an}, удовлетворяющую рекуррентному соотношению   и начальным условиям a1=1, a2=3.

Задача 6

В таблице заданы номера наборов аргументов, на которых логическая функция принимает значение, равное единице. Найти

1. СКНФ, СДНФ;

2. минимальную ДНФ:

а) методом Квайна;

б) с помощью карт Карно.

1,2,4,5,7,9,10,12,13,15

Задача 7

Граф G задан списком ребер (каждый элемент списка – это тройка чисел: номера двух смежных вершин и вес ребра, их соединяющего). Требуется

а) Нарисовать граф G.

б) Найти степенную последовательность графа G.

в) Найти матрицу смежности графа G.

г) Обозначить ребра и найти матрицу инцидентности графа.

д) Определить количество компонент связности графа.

е) Найти четыре простых цикла.

ж) Найти минимальный остов графа и его вес.

(1,4,3), (1,5,6), (2,6,8), (2,7,9), (2,8,2), (3,7,5), (3,8,4),

(4,6,1), (4,8,3), (5,6,7), (5,7,9), (5,8,4)

Задача 8

Найти минимальный автомат, эквивалентный данному.