ЗАДАНИЯ контрольно-курсовой работы
.docЗадание 1.
1. составить таблицу истинности;
2. доказать истинность заключения методом дедукции и нарисовать граф дедуктивного вывода;
3. доказать истинность заключения по принципу резолюции и нарисовать граф вывода пустой резольвенты.
Вариант |
Доказать истинность заключения |
1. |
(BA); (B(AC)) (B(BC)) |
2 |
(AB); (CB) (AC)(AC) |
3. |
(AB) ( BA)(АС) |
4. |
(AB) ((BC)(AC)) |
5 |
(AB); (CD) (ACBD) |
6 |
(AB); ( AB) B (AC) |
7. |
(BA); (B(AC)) (BC) |
8. |
(AB) (CA)( CB) |
9 |
(AB); (A(BC)) (AC) |
10. |
(ABAB) (AC)(BC) |
11. |
(A(BC));(AB);A C |
12. |
(ABC) (A(BC)) |
13. |
(B(AC)); (BA) (B(BC)) |
14 |
(ABCD); (A A) C |
15. |
(A(BC)); ( DA);B (DC) |
16. |
(AB); (AC); (BD) CD |
17. |
(AB); (CB); (D(AC)); D B |
18. |
(AB); (BC); (CD) (AD) |
19 |
(B(AC)); (BA) (B(BC)) |
20 |
(A(CB)); ( DA); C; D DB |
21 |
(AB) (CA)(CB) |
22. |
A; (AB) (CABC) |
23 |
(AB); (BC) A |
24 |
(A(BC)); ( DA);B (DC) |
25 |
(AC); (AB);A (AC)(BC) |
26 |
(A(BC)); (AB) (AC) |
27 |
( AB); (C B) A C |
28 |
C; (AB) ((CA)(CB)) |
29 |
(A(BC)) ((AB) C) |
30 |
(AB) ACBC |
31. |
(A(BC)); ( DA);B (DC) |
32. |
(AB); (BC); (CD) (AD) |
33. |
(B (AC)); (BA) (BC) |
34. |
(AB) (AC)BC) |
35. |
(B(AC)); (BA) (B(BC)) |
36. |
(A(BC); (AB) (A(AC)) |
37. |
(B(AC)); (BA) (B(BC) |
38. |
(AC); (BA) ( CB) |
39. |
(AB); (CB); (D(AC)); D B |
40. |
(AB) ( A CBC) |
41. |
(B(AC)); (BA) (B(BC)) |
42. |
(ABC) (A(BC)) |
43 |
(A(BC)); ( DA);B (DC) |
44. |
(A(BC));(AB);A C |
45. |
(A(BC)); (AB) (AC) |
46. |
(A(BC)) (B(AC)) |
47. |
(AB); (BC); (CD) (AD) |
48. |
(AB) (AC)(BC) |
49. |
(AB); B A CBC |
50. |
(AB) (AC)(BC) |
Задание 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. Определить временную и емкостную сложность следующего алгоритма при равномерном и логарифмическом весовых критериях:
-
Алгоритм метода поиска перебором в квадратной матрице.
-
Алгоритм метода бинарного поиска в квадратной матрице.
-
Алгоритм метода сортировки вставками для одномерного массива.
-
Алгоритм метода сортировки Хоара для одномерного массива.
-
Алгоритм метода сортировки слиянием для одномерного массива.
-
Алгоритм метода сортировки расческой для одномерного массива.
-
Алгоритм метода сортировки Шелла для одномерного массива.
-
Алгоритм построения таблицы истинности логической функции трёх переменных (на примере конкретной функции).
-
Алгоритм построения таблицы значений функции (на примере конкретной функции).
-
Алгоритм поиска минимального элемента в матрице.
-
Алгоритм вычисления суммы элементов главной диагонали матрицы.
-
Алгоритм суммирования элементов квадратной матрицы, расположенных в нечётных строках.
-
Алгоритм умножения двух матриц.
-
Алгоритм вычисления суммы элементов матрицы, выделенных на рисунке символом х (m = n):
-
Алгоритм вычисления суммы элементов матрицы, выделенных на рисунке символом х (m = n):
-
Алгоритм поворота квадратной матрицы против часовой стрелки на 90 градусов.
-
Алгоритм нахождения одного из седловых элементов квадратной матрицы (наибольший в строке и наименьший в столбце).
-
Алгоритм проверки, является ли матрица магическим квадратом (суммы элементов всех строк и столбцов одинаковы).
-
Алгоритм нахождения суммы последних элементов каждой строки и каждого столбца квадратной матрицы.
-
Алгоритм перестановки левой и правой половин квадратной матрицы (размер 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 определить, является ли оно записью