Выдержка из текста работы
Для универсального множества U={-5,-4,-3,-2,-1,1,2,3,4,5}, множества A={-2,1,3,4}, заданного списком, и для , являющегося множеством корней уравнения x^4-11x^2-18x-8=0.
1. Найти множества: A?B, B?A, A\B, B\A, A?B, B ?, C=(A?B)?A.
2. Выяснить, какая из пяти возможностей выполнена для множества A и C: A?C, или C?A, или A=C, или A?C=?, или A B.
3. Найти P(B) и |P(B)|.
Решение:
Сначала найдем множество B корней данного уравнения. Подбором устанавливаем, что корнем исходного многочлена x^4-11x^2-18x-8 является -1; поделив этот многочлен на x+1, получим многочлен x^3-x^2-10x-8.
Также подбором устанавливаем, что -2 является корнем многочлена x^3-x^2-10x-8 и делим этот многочлен на x+2. Получим многочлен x^2-3x-4. Его корни совпадают и равны 4.
Итак, множество B найдено, B={-2,-1,4}. Теперь решаем пункты 1 – 3 данного задания.
A?B={-2,-1,1,3,4},
A?B={-2,4},
A\B={1,3},
B\A={-1},
A?B={1,3}?{-1}={-1,1,3},
B ?={-5,-4,-3,1,2,3,5},
C=(A?B)?A={-1,1,3}?{-2,1,3,4}={-1}?{-2,4}={-2,-1,4}.
2. Так как -2?A и -2?C, 4?C и 4?A, -1?A?C, значит, A B.
3. P(B)={?,{-2},{-1},{4},{-2,-1},{-1,4},{-2,4},{-2,-1,4}}.
Как видим, P(B)содержит 8 элементов, т.е. |P(B)|=8.
Задание 2.
Построить таблицу данной булевой функцииf(x,y,z)=x?(y>z) ?+y.
Решение:
x y z y>z (y>z) ? x?(y>z) ? x?(y>z) ?+y
0 0 0 1 0 0 0
0 0 1 1 0 0 0
0 1 0 0 1 1 0
0 1 1 1 0 0 1
1 0 0 1 0 1 1
1 0 1 1 0 1 1
1 1 0 0 1 1 0
1 1 1 1 0 1 0
Исходная формула задаёт булеву функцию f(x,y,z), имеющую вектор значений (0 0 0 1 1 1 0 0).
Задание 3.
1. Построить машину Тьюринга, применимую ко всем словам x_1 x_2…x_n в алфавите {a,b} и переводящую их в слово ?=x_1 x_2…x_n, если в данном слове количество букв a нечетно, bb, если четно.
2. Проверить работу машины Тьюринга над некоторыми словами.
Решение:
1. Опишем работу алгоритма, решающего эту задачу.
Будем обозначать состояния машины Тьюринга числами 0,1,2… причём 1 – начальное, а 0 – заключительное состояния.
Рассмотрим четыре варианта возможных событий (ab,ba,aa,bb).
aa: Движемся вправо, сохраняя символы (a,1)>aП2; (a,2)>aП3; третий элемент добавляем (a,3)>aП4; все остальные элементы удаляем (a,4)>?H0; (a,4)>?П4; ?(a,4)>?П4?^*.
ab: Движемся вправо (a,1)>aП2; меняем символы (b,2)>aЛ; (a,5)>bП6; затем (a,6)>aП3; (b,6)>aП3; удаляем все остальные символы.
ba: (b,1)>bП7; (b,7)>aП8; (a,8)>bП4; удаляем элементы.
bb: (b,1)>bП7; (b,7)>aП8; (a,8)>bП4; удаляем оставшиеся символы.
Запишем программу найденной машины Тьюринга в виде таблицы:
A S 1 2 3 4 5 6 7 8
— — — ?H0 — — — —
aП2 aП3 aП4 ?П4 bП6 aП3 aЛ5 bП4
bП7 bЛ5 bП4 ?П4 aП8 aП3 aП8 bП4
Проверим работу построенной машины Тьюринга над словом abba:
abba, abba, aaba, aaba, baba, baba, aaba, aaba, aaba, aaba, aab?,
1 2 2 5 5 6 6 3 3 4 0
Итак, слово abba после выполнения программы слово будет aab?.
Задание 4.
Построить 3 – местные предикаты на множестве N?R?R такие, что выполнено условие P(x,1,z)?0,P(x,y,z)?Q(1,y,z) – выполним.
Решение:
Построить трехместные предикаты и на множестве такие, что – выполним, и .
Пусть P(x,y,z): (2x+y+z кратно 4);
Q(x,y,z): (x+y+z+5 – нечетное число).
Тогда P(x,1,z)=T(x,z): (2x+1+z кратно 4).
T(1,1)= (2+1+1 кратно 4)=0; T(2,2)= (4+1+1 кратно 4)=1.
Значит, T(x,z)=P(x,1,z) – выполнимый предикат.
Обозначим S(x,y,z)=P(x,y,z)?Q(1,y,z).
Покажем, что S(x,y,z)?0.
Предикат S(x,y,z) может принять значение 1 лишь на таком наборе (a,b,c), при котором P(a,b,c)=1и Q(1,b,c)=0, т.е. 2a+b+c кратно 4 и 1+b+c+5 – нечетное число.
Запишем эти высказывания в равносильной форме:
{-(2a+b+c =4m@1+b+c+5=2n-1)+, где m,n?Z.
Но тогда, складывая уравнения этой системы, получим:
2a+2b+2c+6 =4m+2n-1, или 4m+2n-2a-2b-2c=, откуда 2(2m+n-a-b-c)=.В левой части этого равенства стоит чётное число, а в правой – нечётное. Значит, ни при каких значениях переменных x, y, z предикат S(x,y,z) не может принимать значения 1, следовательно,
S(x,y,z)=P(x,y,z)?Q(1,y,z)
Задание 5.
Сколько различных слов можно получить перестановкой букв слова пастух, так чтобы между двумя гласными расположены 2 согласные?
Решение:
Количество способов расстановки 2-х гласных: P(3)=3!=6
Количество способов расстановки 4-х согласных: P(4)=4!=24
Количество слов которые можно получить, так чтобы между двумя гласными расположены 2-е согласные: 24*6=144
Ответ: 144 слова.
Задание 6. По данной кодовой комбинации xxxyxxyx построить дешифратор с входным алфавитом и записать его:
1) диаграммой состояний;
2) таблицей состояний.
Решение.
Составим диаграмму состояний дешифратора, содержащего 8 внутренних состояний (по количеству символов кодовой комбинации).
Пусть начальное состояние – . определим , для остальных случаев значение функции выходов равно 0.
Функцию переходов зададим следующим образом:
, .
В дальнейшем, если ( ) – начало кодовой комбинации, то , в остальных случаях , где – наименьший номер, такой что слово является начальным отрезком кодовой комбинации.
Найдя, действуя аналогично, значения функции переходов на остальных наборах переменных, получим диаграмму состояний (рис. 1).
Теперь запишем таблицу состояний дешифратора:
q_2,0 q_3,0 q_4,0 q_1,0 q_6,0 q_7,0 q_7,0 q_2,1
q_1,0 q_2,0 q_2,0 q_5,0 q_2,0 q_5,0 q_8,0 q_5,0
