Контрольная «Вариант 153-502 Задача 1 Определить, являются ли формулы f и g»,
Дискретная математика в Красноярске

Вариант 153-502 Задача 1 Определить, являются ли формулы f и g эквивалентными. f(x,y,z)=((y+x) ? (x~z))+((z&x)V(z+y)) v g(x,y,z)=((y&x)&(z&x))V((z~y) ? (z+x)) v Примечание : & - конъюнкция V - дизъюнкция ~ - эквивалентность ?> - импликация + - сложение по модулю 2 ? - штрих Шеффера ? - стрелка Пирса v Задача 2 Для булевой функции, заданной вектором значений (01101111), определить : 1) существенные и фиктивные переменные; 2) совершенную дизъюнктивную нормальную форму; 3) совершенную конъюнктивную нормальную форму; 4) полином Жегалкина двумя способами; 5) принадлежность классам T0,T1, S, M, L Задача 3 По заданной матрице смежности построить неориентированный граф, составить таблицу степеней вершин, матрицу инцидентности, таблицу расстояний и условных радиусов, найти радиус и центр графа. ? 0 1 0 0 0 1 0 0 1 ? ? 1 0 1 0 0 1 0 0 1 ? ? 0 1 0 0 1 0 1 0 0 ? ? 0 0 0 0 0 1 0 0 1 ? A(G) = ? 0 0 1 0 0 1 1 0 0 ? ? 1 1 0 1 1 0 1 0 0 ? ? 0 0 1 0 1 1 0 1 0 ? ? 0 0 0 0 0 0 1 0 0 ? ? 1 1 0 1 0 0 0 0 0 ? Задача 4 Выяснить, применима ли машина Тьюринга T к слову P. Если применима, то выписать результат T(P) применения машины Тьюринга T к слову P. ? ?q1 1 q1 1 R ?q1 0 q2 1 L T: < q2 1 q3 1 L ?q2 0 q2 1 E ?q3 0 q3 1 E ? P=11110011 Предполагается, что начальный момент Машина Тьюринга обозревает самую левую единицу слова. Задача 5 Найти число способов расстановки 12 томов на книжной полке, при котором первые 9 томов стоят рядом в порядке возрастания номеров