Task_ 10 (1)
.pdfВариант 10
1.На множестве целых чисел {35 40 37 38 15 18 28 11} задано отношение R следующим образом: xRy тогда и только тогда, когда в наборе имеется элемент, больший x, но меньший y. Для
заданного отношения:
(a)проверьте, является ли отношение рефлексивным, антирефлексивным, симметричным, асиммет• ричным, антисимметричным, транзитивным;
(b)постройте граф отношения;
(c)определите, являются ли отношение отношением эквивалентности, частичного порядка, линейно• го порядка; для отношения частичного порядка примените алгоритм топологической сортировки
иполучите отношение линейного порядка;
2.Для графа отношения
|
|
|
HIJKONMLm |
|
|
a |
|
|
|
|
HIJKONMLl |
|
|
|
|
|||||
|
|
|
|
|
b |
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
++ |
|
|
|
|
|
|
|
|
|
|
|
A |
m |
|
|
|
|
|
|
|
B |
|
|
|
l |
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
g |
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
d |
|
|
|
|
|
e |
|
|
|
|
|
f |
||||
|
|
c |
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
•• |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
HIJKONML |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
♦♦HIJKONML |
|
C |
t |
t |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
** |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
D |
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
77 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
♦ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
♦ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
♦♦♦♦♦ |
||||
|
|
|
|
|
|
|
|
|
|
|
|
♦n♦♦♦♦ |
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
♦ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
♦♦♦ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
♦♦♦ |
|
p |
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
♦ |
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
HIJKONML |
♦♦♦ |
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
♦ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
E |
pp |
|
|
|
|
|
|
|
|
постройте его транзитивное замыкание алгоритмом Уоршалла.
3. Для булевой функции
f(x, y, z) = ((x y) (xz)) ((yz) y)
(a)постройте СДНФ этой функции;
(b)постройте многочлен Жегалкина исходной функции;
(c)постройте СКНФ двойственной функции;
(d)проверьте f на принадлежность основным классам замкнутости T0, T1, L, M, S;
4.Машина Тьюринга имеет алфавит из трех символов {1, 2, α0} (символ α0 означает отсутствие символа на ленте), два состояния {q0, q1}, из которых q1 - начальное состояние, q0 - конечное. Символ R означает сдвиг читающей головки вправо по ленте, L - влево, E - головка остается на месте. В
начальный момент головка указывает на крайний левый символ записи. Команды машины задаются набором:
q11 → q12R; q12 → q11L; q1α0 → q02E
Какой результат даст машина на наборе 22122 ?
5.Постройте конечный автомат, распознающий язык L = {caa, bcb, b, aa}.
6.Опишите язык, который определяет грамматика S → 1|1S0.
7.Алгебраическое выражение, заданное в инфиксной записи, переведите в постфиксную форму
(a c + d)/e − a/d.