Решить 11 задач

Задача 1
Определить, являются ли формулы f и g
эквивалентными.
f(x,y,z)=((z?>y)?(z&x))?((y ? z)?(y ? x))
v v
g(x,y,z)=((y ? x)V(x?>z))?((z?x)~(z&y))
v
Примечание :
& - конъюнкция
V - дизъюнкция
~ - эквивалентность
?> - импликация
+ - сложение по модулю 2
? - штрих Шеффера
? - стрелка Пирса
v
Задача 2
Для булевой функции, заданной вектором значений (11110110),
определить :
1) существенные и фиктивные переменные;
2) совершенную дизъюнктивную нормальную форму;
3) совершенную конъюнктивную нормальную форму;
4) полином Жегалкина двумя способами;
5) принадлежность классам T0,T1, S, M, L
Задача 3
По заданной матрице смежности построить неориентированный граф,
составить таблицу степеней вершин, матрицу инцидентности, таблицу
расстояний и условных радиусов, найти радиус и центр графа.
? 0 1 1 1 0 0 0 0 0 ?
? 1 0 0 0 0 1 0 0 0 ?
? 1 0 0 1 0 0 1 0 0 ?
? 1 0 1 0 0 0 1 0 1 ?
A(G) = ? 0 0 0 0 0 0 0 0 1 ?
? 0 1 0 0 0 0 0 1 0 ?
? 0 0 1 1 0 0 0 0 0 ?
? 0 0 0 0 0 1 0 0 0 ?
? 0 0 0 1 1 0 0 0 0 ?
Задача 4
Выяснить, применима ли машина Тьюринга T к слову P.
Если применима, то выписать результат T(P) применения
машины Тьюринга T к слову P.
?
?q1 1 q3 1 E
?q2 1 q3 1 L
T: < q2 0 q1 0 R
?q3 1 q2 0 R
?q3 0 q2 1 L
?
P=11101001
Предполагается, что начальный момент Машина Тьюринга
обозревает самую левую единицу слова.
Задача 5
Найти число способов расстановки 36 томов на
книжной полке, при котором первые 30 томов стоят
рядом в порядке возрастания номеров
Задача 6
В военном подразделении служат 10 офицеров и 11 рядовых
оперативная группа состоит из командира, заместителя и 8 рядовых,
причём командир и заместитель назначаются случайным образом
из числа офицеров. Найти число возможных различных
оперативных групп.
Задача 7
Найти множество всех подмножеств множества {3,7,6}
Задача 8
Найти декартово произведение множеств A={1,6}, B={1,2,4}
Задача 9
В вузе 45 отличников, 70 хорошистов и 186 троечников.
Делегация на студенческую конференцию включает 8 отличников,
6 хорошистов и 3 троечников. Найти число возможных делегаций
Задача 10
Даны числовые множества
A={18,33,32,29}, B={32,34,33,29}, C={32,35,37,38},
Найти множество A&(B\C).
Задача 11
На множестве M={1,4,7,8} задано отношение
R = {(1,1),(4,4),(7,7),(8,8),(1,4),(1,7),(1,8),(4,7),(4,8),(7,8)}
Выяснить, является ли это отношение отношением
эквивалентности, отношением частичного порядка, отношением
строгого порядка или отношением линейного порядка.