ЗАДАНИЯ контрольно-курсовой работы

Задание 1.

1. составить таблицу истинности;

2. доказать истинность заключения методом дедукции и нарисовать граф дедуктивного вывода;

3. доказать истинность заключения по принципу резолюции и нарисовать граф вывода пустой резольвенты.

Вариант	Доказать истинность заключения
1.	(BA); (B(AC))  (B(BC))
2	(AB); (CB)  (AC)(AC)
3.	(AB)  ( BA)(АС)
4.	(AB)  ((BC)(AC))
5	(AB); (CD)  (ACBD)
6	(AB); ( AB)  B (AC)
7.	(BA); (B(AC))  (BC)
8.	(AB)  (CA)( CB)
9	(AB); (A(BC))  (AC)
10.	(ABAB)  (AC)(BC)
11.	(A(BC));(AB);A  C
12.	(ABC)  (A(BC))
13.	(B(AC)); (BA)  (B(BC))
14	(ABCD); (A A)  C
15.	(A(BC)); ( DA);B  (DC)
16.	(AB); (AC); (BD)  CD
17.	(AB); (CB); (D(AC)); D  B
18.	(AB); (BC); (CD)  (AD)
19	(B(AC)); (BA)  (B(BC))
20	(A(CB)); ( DA); C; D  DB
21	(AB)  (CA)(CB)
22.	A; (AB)  (CABC)
23	(AB);  (BC)   A
24	(A(BC)); ( DA);B  (DC)
25	(AC); (AB);A  (AC)(BC)
26	(A(BC)); (AB)  (AC)
27	( AB); (C B)  A C
28	C; (AB)  ((CA)(CB))
29	(A(BC))  ((AB) C)
30	(AB)  ACBC
31.	(A(BC)); ( DA);B  (DC)
32.	(AB); (BC); (CD)  (AD)
33.	(B (AC)); (BA)  (BC)
34.	(AB)  (AC)BC)
35.	(B(AC)); (BA)  (B(BC))
36.	(A(BC); (AB)  (A(AC))
37.	(B(AC)); (BA)  (B(BC)
38.	(AC); (BA)  ( CB)
39.	(AB); (CB); (D(AC)); D  B
40.	(AB) ( A CBC)
41.	(B(AC)); (BA)  (B(BC))
42.	(ABC)  (A(BC))
43	(A(BC)); ( DA);B  (DC)
44.	(A(BC));(AB);A  C
45.	(A(BC)); (AB)  (AC)
46.	(A(BC))  (B(AC))
47.	(AB); (BC); (CD)  (AD)
48.	(AB)  (AC)(BC)
49.	(AB); B   A CBC
50.	(AB)  (AC)(BC)

Задание 2. Задан алгоритм функционирования некоторого комбинационного цифрового устройства в виде связи между входны­ми и выходными сигналами. Эта связь представлена таблицей истинности (задан последний столбец таблицы истинности, первые три столбца значений переменных имеют стандартный вид

X	y	z
1	1	1
1	1	0
1	0	1
1	0	0
0	1	1
0	1	0
0	0	1
0	0	0

Спроектируйте схему этого цифрового устройства, отличающуюся минимумом. минимальным числом логических элементов.

№ варианта	F(X,Y,Z)
1	1	1	1	0	0	0	0	0
2	0	1	1	1	0	0	0	0
3	0	0	1	1	1	0	0	0
4	0	0	0	1	1	1	0	0
5	0	0	0	0	1	1	1	0
6	0	0	0	0	0	1	1	1
7	1	0	0	0	0	0	1	1
8	1	1	0	0	0	0	0	1
9	0	1	1	0	1	0	0	0
10	0	0	1	1	0	1	0	0
11	0	0	0	1	1	0	1	0
12	0	0	0	0	1	1	0	1
13	1	0	0	0	0	1	1	0
14	0	1	0	0	0	0	1	1
15	1	0	1	0	0	0	0	1
16	0	0	0	1	1	1	1	1
17	1	0	0	0	1	1	1	1
18	1	1	0	0	0	1	1	1
19	1	1	1	0	0	0	1	1
20	1	1	1	1	0	0	0	1
21	1	1	1	1	1	0	0	0
22	0	1	1	1	1	1	0	0
23	0	0	1	1	1	1	1	0
24	0	0	1	0	1	1	1	1
25	1	0	0	1	0	1	1	1
26	1	1	0	0	1	0	1	1
27	1	1	1	0	0	1	0	1
28	1	1	1	1	0	0	1	0
29	0	1	1	1	1	0	0	1
30	1	0	1	1	1	1	0	0

Задание 3. Найти предваренную и клаузальную нормальные формы формул.

Вариант	Формула
1	x(A(x) B(y))y(B(y) A(x))
2	x( A(x)x( C(x)))x((C(x)A(x))
3	x(A(x)x(B(x)))y( A(x) C(y)C(y)B(x))
4	x(A(x)x(B(y)))x( A(x) B(y))
5	x(A(x)B(y))y(A(x)(B(y)C(z))z(A(x)C(z))
6	x(A(x)y(B(y)C(z)))z(A(x)B(y)C(z))
7	x(A(x)B(z))y(C(y)A(x))z(C(y)B(z))
8	x(A(x)B(y))y((C(y)A(x))(C(y)y(B(y)))
9	x(A(x)B(y))y(A(x)(B(y)C(z)))(A(x)z(C(z)))
10	x(A(x)B(y)A(x)y(B(y)C(z)))(A(x)z(C(z)))
11	x(A(x)z(B(y)C(z)))y(B(y)(A(x)C(z)))
12	(x(A(x))x(B(x)))z((B(x)C(z))(A(x)C(z)))
13	(x( A(x))x( B(x)))( B(x)A(x))
14	(x(A(x)))(x(B(x)))y(C(y)A(x)C(y)B(x))
15	ч( Ф(ч)н(И(н)))( И(н)Ф(ч))
16	(x(B(x))x(A(x)))y((A(x)C(y))( C(y)B(x)))
17	x( A(x)y(B(y)))(B(y)A(x))
18	x( A(x)y( B(y)))(B(y)A(x))
19	x(A(x)B(x))y(B(x)C(y)z(C(y)D(z)))
20	(x(A(x)B(x))z(C(z)A(x)))y(C(z)B(y))
21	(x(B(x)y(A(y)))(y(B(y)(A(x)C(z))))z(C(z))
22	x(B(x))y(A(y)B(x))
23	x(A(x)B(x))(y(C(y)A(x))z(C(z)B(x)))
24	x(B(x)A(y))(B(x)y(A(y)C(z)))z(C(z)))
25	x(A(x)B(z))y(C(y)A(x)z(C(y)B(z)))
26	(x(B(x))x(A(x)))(A(y)yC(y))( A(x)C(y))
27	(x(A(x))x(B(x)))y((A(x)C(y))(B(x)C(y)))
28	x(A(x)y(B(y)))( A(x)y(B(y)))B(y)
29	x(A(x)y(B(y)))( A(x)B(x))B(x)
30	x( A(x))(A(x)y(B(y)))
31	(x(B(x))x(A(x)))( B(x)A(x))A(x)
32	(x(B(x))x(C(x)))(A(y)B(x)A(y)C(x))
33	ч(Ф(ч)И(н))ня((С(я)Ф(ч))(С(я)И(н)))
34	(x(A(x))x(C(x)))y(C(x)B(y))(A(x)B(y))
35	x(A(x))y(B(y))y(C(y)xD(x))(A(x)C(y)) D(y))
36	x(A(x))( A(x)y(B(y)))
37	x(B(x))y(A(y)B(x))
38	x(B(x)y(A(y)))y(B(y)(A(x)C(z)))z(B(z) C(z))
39	x(B(x)A(y))(B(x)y(A(y)C(z)))z(B(x)C(z))
40	x(A(x)B(x))y((C(y)A(x))(C(y)B(x)))
41	(x( A(x)y( C(y)))(C(x)A(x))
42	x(A(x) B(y))y(B(y) A(x))
43	x(A(x)B(z))y((C(y)A(x))z(C(y)B(z)))
44	x(A(x)B(y))z(C(z)A(x))y(C(z)B(y))
45	ч(Ф(ч)И(ч))н(И(ч)С(н))я(С(н)В(я)))
46 46	x( A(x)y( B(y)))(B(x)A(x))
47	x( A(x)x(B(x)))(B(x)A(x))
48	(x(B(x)y(A(y))))y(A(x)C(y)) C(y)B(x)
49	(x( A(x)y(B(y))))( B(x)A(x))
50	x(A(x)B(y))y(A(x)(B(y)C(z)))z(A(x)C(z))

Задание 4. Определить временную и емкостную сложность следующего алгоритма при равномерном и логарифмическом весовых критериях:

1. Алгоритм метода поиска перебором в квадратной матрице.

2. Алгоритм метода бинарного поиска в квадратной матрице.

3. Алгоритм метода сортировки вставками для одномерного массива.

4. Алгоритм метода сортировки Хоара для одномерного массива.

5. Алгоритм метода сортировки слиянием для одномерного массива.

6. Алгоритм метода сортировки расческой для одномерного массива.

7. Алгоритм метода сортировки Шелла для одномерного массива.

8. Алгоритм построения таблицы истинности логической функции трёх переменных (на примере конкретной функции).

9. Алгоритм построения таблицы значений функции (на примере конкретной функции).

10. Алгоритм поиска минимального элемента в матрице.

11. Алгоритм вычисления суммы элементов главной диагонали матрицы.

12. Алгоритм суммирования элементов квадратной матрицы, расположенных в нечётных строках.

13. Алгоритм умножения двух матриц.

14. Алгоритм вычисления суммы элементов матрицы, выделенных на рисунке символом х (m = n):

15. Алгоритм вычисления суммы элементов матрицы, выделенных на рисунке символом х (m = n):

16. Алгоритм поворота квадратной матрицы против часовой стрелки на 90 градусов.

17. Алгоритм нахождения одного из седловых элементов квадратной матрицы (наибольший в строке и наименьший в столбце).

18. Алгоритм проверки, является ли матрица магическим квадратом (суммы элементов всех строк и столбцов одинаковы).

19. Алгоритм нахождения суммы последних элементов каждой строки и каждого столбца квадратной матрицы.

20. Алгоритм перестановки левой и правой половин квадратной матрицы (размер n матрицы является четным числом).

Задание 5. Составить программу машины Тьюринга в заданном алфавите и показать ее работоспособность на примере

1 A={a,b,c}. Приписать слева к слову P символ b (P → bP).

2 A={a,b,c}. Приписать справа к слову P символы bc (P → Pbc).

3 A={a,b,c}. Заменить на a каждый второй символ в слове P.

4 A={a,b,c}. Оставить в слове P только первый символ (пустое слово не

менять).

5 A={a,b,c}. Оставить в слове P только последний символ (пустое слово не

менять).

6 A={a,b,c}. Определить, является ли P словом ab. Ответ (выходное слово):

слово ab, если является, или пустое слово иначе.

7 A={a,b,c}. Определить, входит ли в слово P символ a. Ответ: слово из

одного символа a (да, входит) или пустое слово (нет).

8 A={a,b,c}. Если в слово P не входит символ a, то заменить в P все символы

b на с, иначе в качестве ответа выдать слово из одного символа a.

9 A={a,b,0,1}. Определить, является ли слово P идентификатором (непустым

словом, начинающимся с буквы). Ответ: слово a (да) или пустое слово (нет).

10 A={a,b,0,1}. Определить, является ли слово P записью числа в двоичной

системе счисления (непустым словом, состоящем только из цифр 0 и 1). Ответ:

слово 1 (да) или слово 0.

11 A={0,1}. Считая непустое слово P записью двоичного числа, удалить из

него незначащие нули, если такие есть.

12 A={0,1}. Для непустого слова P определить, является ли оно записью