Шифр 87: 8 задач. Пусть имеется множество A={1,2,3,4}, на этом множестве определены отношения RНA2 и PНA2.

  • ID: 18111 
  • 10 страниц

Фрагмент работы:

Шифр 87: 8 задач. Пусть имеется множество A={1,2,3,4}, на этом мно…

5+

32+

48+

78+

93+

103+

122+

145+

Задание 5.

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

5

Решение:

Задание 32.

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

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

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

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

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

Решение:

а) Рефлексивность отношения P означает, что для каждого x из A выполняется P(x,x). Проверим это. Рассмотрим x+x2=x(x+1). Очевидно, что при x=1 пара (1,1) не принадлежит множеству P, т.к. 2 не делится на 3. Значит, отношение P не является рефлексивным.

отношение P◦R = { (x,y) | существует z P(x,z) и R(z,y)}={(2,2),(2,3),(2,4)}.

Задание 48.

48 1111223456780

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

Разобьём все варианты на пять групп:

1-я группа без повторений цифр.

n1=8*8*7*6. Считаем, что для первой цифры восемь вариантов (все, без нуля). Вторая цифра – 8 вариантов (с нулем). Третья цифра – 7 вариантов, потом – 6. Итого n1= 2688.

Задание 78.

Найти количество положительных трехзначных чисел:

а) не делящихся ни на одно из чисел a,b,c;

б) делящихся ровно на одно число из чисел a,b,c.

78 9 10 12

Решение:

а) Рассмотрим все трёхзначные числа, которые делятся либо на 9, либо на 10, либо на 12.

Пусть N9, N10, N12, N90, N108, N120, N1080, это количество всех трёхзначных чисел, делящихся на индексы.

Задание 93.

Найти последовательность {an}, удовлетворяющую рекуррентному соотношению и начальными условиями a1=e, a2=f. Коэффициенты b, c, d, e, f выбираются из таблицы.

93 2 7 6 0 15

Решение:

Задание 103.

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

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

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

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

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

103 0,1,2,3,4,6,9,11,12,13

Решение:

Задание 122.

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

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

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

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

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

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

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

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

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

б) (4, 4, 2, 6, 4, 4, 2, 4) – степенная последовательность графа.

в) матрица смежности:

г) Перенумеруем рёбра в порядке их задания:

д) 1 компонента связности, т.к. каждая вершина достижима из каждой.

е) В данном орграфе нет простых циклов.

ж) Остов графа: (1,6), (2,3), (2,4), (4,5), (4,6), (4,7), (6,8). Вес=20.

Задание 145.

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

Задача 145

0 1

1 6,1 8,1

2 1,1 5,0

3 7,0 1,1

4 2,0 6,1

5 6,0 1,1

6 8,0 7,1

7 8,0 4,1

8 1,1 3,0

9 2,0 7,1