20. Найти ядро графа с помощью алгоритмов Магу (рис. 4.12).

1.Найдем множества внутренней устойчивости:

	1	2	3	4	5
1			1
2				1
3					1
4	1
5		1

(1v3)(1v4)(2v4)(2v5)(3v5)

Перейдем к ДНФ

123v125v145v234v345

Для каждой конъюнкции выписываем недостающие вершины, образующие множества внутренней устойчивости.

{4,5},{3,4},{2,3},{1,5},{1,2}

2.Найдем множества внешней устойчивости:

	1	2	3	4	5
1	1		1
2		1		1
3			1		1
4	1			1
5		1			1

(1v3)(2v4)(3v5)(1v4)(2v5)

Перейдем к ДНФ

123v125v145v234v345

{1,2,3}{1,2,5},{1,4,5},{2,3,4},{3,4,5}

Совпадающих множеств нет.

21. Привести граф к яруcно-параллельной форме (рис. 4.13).

	1	2	3	4	5	6
1
2
3		1
4	1		1		1
5
6	1		1	1	1

6

4

1 5 5

2

28. Используя метод Магу, определить максимально внутренне устойчивые, а также минимально внешне устойчивые множества вершин орграфов и найти их ядра.

v1 v2

v3 v4

1.Найдем множества внутренней устойчивости:

	1	2	3	4
1		1	1
2
3		1		1
4			1

(1v2)(1v3)(2v3)(3v4)

Перейдем к ДНФ

13v23v124

Для каждой конъюнкции выписываем недостающие вершины, образующие множества внутренней устойчивости.

{2,4},{1,4},{3}

2.Найдем множества внешней устойчивости:

	1	2	3	4
1	1	1	1
2		1
3		1	1	1
4			1	1

(1v2v3)(2)(2v3v4)(3v4)

Перейдем к ДНФ

23v24

{2,3},{2,4}

{2,4} ядро графа

3. Резолюции

1. Необходимо ответить, являются ли следующие конструкции термами

max (x,y,z), (x,y), (xy), .

Все конструкции – термы, т.к. являются функциями

2. Необходимо ответить, являются ли следующие конструкции формулами

 P(x); х P(x)

Все конструкции являются формулами, т.к P(x)это атом.

3. Являются ли выполнимыми следующие формулы? P(a) P(a);

Формула является выполнимой т.к. результат 1.

31. Получить множество дизъюнктов.

1. x, y, z (P(x)&Q(x, y)R(z))

Приведем к конъюктивной нормальной форме

x, y, z ((P(x) R(z))&(Q(x, y)R(z)))

Кванторов существования нет, а кванторы общности можно отбросить

(P(x) R(z)),(Q(x, y)R(z))

2. x, y, z (P(x)Q(x, y)R(z)M(y))

Избавимся от импликации:

x, y, z ((P(x)Q(x, y))R(z)M(y))

Приведем к конъюктивной нормальной форме

x, y, z ((P(x)&Q(x, y))R(z)M(y))

Т.к. есть квантор существования, и левее нет кванторов общности, то заменяем х_i на константу k.

(P(k)&Q(k, y))R(z)M(y)

4. Машины Тьюринга

3. Построить машину Т, сдвигающую головку вправо на следующий массив единиц, который будет обнаружен на ленте: 1q₁^x1^y  1^x1^y-1q₀1 (машина находит следующий справа массив единиц и останавливается, воспринимая самую правую заполненную ячейку).

	q1	q2
1	Q21П	Q21П
	Q1П	Q0Л

8. По заданной машине Т и начальной конфигурации М₁ найти заключительную конфигурацию .

8.1. T:

	q1	q2
0	q01C	q10П
1	q20П	q21Л

а) M₁ = 1²q₁1³01;

Ответ: М₂=11000000q₀1

9. Построить в алфавите {0,1} машину Т, переводящую конфигурацию M₀ в конфигурацию М₁.

3) М₀ = 1ⁿq₁0, М₁ = q₀1²ⁿ, (n1);

	q1	q2	q3	q4	q5	q6	q7
1	-	Q21Л	Q40П	Q41П	Q51П	-	Q71Л
0	q20Л	Q30П	Q00С	Q50П	Q61П	Q71Л	Q1,0С

5. Рекурсивные функции

1. Применить операцию примитивной рекурсии к функциям g(x1) и h(x1, x2, x3)

3) g(x1)= 1 и h(x1, x2, x3) = x3(1+sgx1+2-2x3);

3. Доказать примитивную рекурсивность следующих функций

3) (усеченная разность)

6. Применить операцию минимизации к функции f по переменной xi. Результирующую функцию представить в аналитической форме.

3) f(x₁, x₂) =I₁²(x₁, x₂), i=2;