Материалы для самостоятельной работы по дисциплине «Математическая логика и теория алгоритмов» (по материалам проф. ) (стр. 1 )

МАТЕРИАЛЫ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ

ПО ДИСЦИПЛИНЕ

«МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ»

(по материалам проф. )

Оглавление

Задание 1. Логика высказываний        3

Задание 2. Логика предикатов        5

Задание 3. Реляционная логика        6

Задание 4. Нечеткая логика        9

Задание 5. Теория алгоритмов        11

Задание 1. Логика высказываний

Согласно варианту (см. табл. 1):

составить таблицу истинности, столбцы которой включают: пропозициональные переменные, посылки по отдельности, заключение, конъюнкцию всех посылок, импликацию заключения из этой конъюнкции, выделить штриховкой строки, в которых истинны все посылки и заключение, указать необходимые значения пропозициональных переменных для истинных значений всех посылок и заключения; доказать истинность заключения:

а) методом дедукции и нарисовать граф дедуктивного вывода,

b) методом резолюции и нарисовать граф вывода пустой резольвенты.

                                                               Таблица 1

Вариант	Формула
1	(A→B), (C→D), (B→¬D), (A&¬D) |- (¬C&B)
2	(B→(A→C)), (B→A), ¬C&¬D |- ¬(B∨D)
3	(B→A), (B→(¬A∨C)), (¬С∨¬D) |- (¬B∨¬D)
4	(A→B), (C→B), (B→D), ¬D |- (¬A&¬C)
5	(A→B), (A→(B→C)), (B→C), ¬C|- (¬A&¬B)
6	(A→B), (C→D), (B→¬D), C |- (¬A&D)
7	(A↔B),  (B→(A→C)),¬C|- (¬A&¬B)
8	(A→B), (D→C), ¬B, ¬C |- ¬(A∨D)
9	(A→B), (C→¬B), (C&¬D) |- ¬ (A∨D)
10	(A→B), (¬B∨C), (A→C), (A∨B∨D),  ¬B|- (C∨D)
11	(A→B), (D→C), ¬(B∨C) |- (¬A&¬D)
12	(A→B), (C→¬B), (D→C), D |- ¬A
13	(A→B), (B&D →C), (A&D) |- C
14	(A→B), (C→B), (¬B∨D), ¬(D∨C) |- (¬A&¬C)
15	(A→B), (A→(B→C)), (A&D) |- C
16	(A→B), (C→B), (D→(A∨C)), D |- B
17	(A→B), (C→D), (B→¬D), (C&¬D) |- (¬A&¬D)
18	(A→B), (A→(B→C)), ¬(C∨D) |- (¬A&¬D)
19	(A→B), (B→C), (C→D), A&B |- B&D
20	(A→(B→C)), (A→B), ¬(C∨D) |- (¬A&¬D)
21	(A→(B→C)), (¬D∨A), B |- (¬D∨C)
22	(A→(B→C)), (¬D∨A), B, D |- C
23	(A→(B→C)), (A→B), A&D |- C&D
24	(A→(B→C)), (¬ D∨A), B  |- (¬D∨C)
25	(A→(B→C)), (¬D∨A), B |- (D→C)
26	(A→(B→C)), ((A→C)→D), ¬D |- ¬B
27	(A→B), (B→C), (C→D), (A∨C) |- (C∨D)
28	(B→A), (B→(A→C)), B&D |- C
29	(B→A), (B→(A→C)), ¬(C∨D) |- ¬(B∨D)
30	(B→A), (B→(¬A∨C)), (B&D) |- C&D
31	(B→A), (A→C), (D→C), (B∨D) |- (C∨D)
32	(B→(A→C)), (B→A), (C→D), ¬D |- ¬B
33	(A→(B→C)), (¬ D∨A), B |- (D∨C)
34	(B→ (A→C)), (B→A), ¬C∨¬D  |- ¬(B&D)
35	(¬A∨B), (C∨¬B), (¬С&¬D) |- ¬(A∨D)
36	(¬A∨¬B), (C→A), (B∨¬D) |- (¬C∨¬D)
37	(¬A∨B), (C∨¬B), (A∨D), ¬D |- C
38	(¬A∨¬B), (C→A), B&D |-¬C→D
39	(A∨B), (A→C), (B→D),¬C |- D
40	(¬A∨B), (C→¬B), ¬(C→B) |- (¬A&¬B)
41	(A→B), (C→D), (B→¬D), (A&¬D) |- (¬C&B)
42	(A→B), (C→B), (B→D), ¬D |- (¬A&¬C)
43	(A→B), (D→C), ¬B, ¬C |- ¬(A∨D)
44	(A→B), (C→¬B), (D→C), D |- ¬A
45	(A→B), (C→B), (D→(A∨C)), D |- B
46	(A→(B→C)), (A→B), ¬(C∨D) |- (¬A&¬D)
47	(A→(B→C)), (¬ D∨A), B  |- (¬D∨C)
48	(B→A), (B→(A→C)), B&D |- C
49	(B→(A→C)), (B→A), (C→D), ¬D |- ¬B
50	(¬A∨¬B), (C→A), (B∨¬D) |- (¬C∨¬D)

Задание 2. Логика предикатов

Согласно варианту (см. табл. 2):

преобразовать формулу к виду ПНФ, затем - ССФ, сформировать множество дизъюнктов К, выполнить унификацию дизъюнктов множества  К.

                                                                       Таблица 2

Вариант	Формула
1	∀x(A(x)→B(y))&∀y(A(x)→(B(y)→C(z)))→∃z(C(z))
2	∀x(B(x)→∃z(A(z)))&∃y(A(z)→C(y))→(¬C(y)&B(x))
3	∀x(A(x)→∃y(B(y)))→∃y(¬A(x)∨¬C(z)∨B(y))
4	∀x(A(x)→∃z(C(z)))&∀y(C(z)→B(y))→(A(x)→B(y))
5	∀x(A(x)→∃y(B(y)→C(z)))→∀z(A(x)&B(y)→C(z))
6	∀x(A(x)→B(z))&∀y(C(y)→A(x))→∃z(C(y)→B(z))
7	∀x((A(x)→B(y))→∀y(C(y)∨A(x)))→(C(y)∨∃y(B(y)))
8	∀x(A(x)→B(y))&∀y(A(x)→(B(y)→C(z)))→(A(x)®∃z(C(z)))
9	∀x(A(x)→B(y))&(A(x)→∀y(B(y)→C(z)))→∃z(C(z))
10	∀x(A(x)→∃z(B(y)→C(z)))→∀y(B(y)→(A(x)→C(z)))
11	(∀x(A(x))→∃z(B(z)))→∀z((B(x)→C(z))→C(z))
12	(∃x(¬A(x))→∀z(¬B(z)))→(¬B(x)∨A(x))
13	(∀x(A(x))→∀y(B(y)))→∃y(C(y)&A(x)→C(y)&B(x))
14	∀x(¬A(x)→∃y(B(y)))→(¬B(y)→A(x))
15	∀x(¬A(x)→∃y(¬B(y)))→(B(y)→A(x))
16	∀x(A(x)→B(x))&∃y(B(x)→C(y))→∃z(C(y)→D(z))
17	∀x(A(x)→B(x))&∀z(C(z)→A(x))→∃y(C(z)→B(y))
18	∀x(B(x)→∀y(A(y)))&∀y(B(y)→(A(x)→C(z)))®∃z(C(z))
19	(∀x(A(x)→B(y)))&(A(x)→∀y(B(y)→C(z)))→∃z(C(z))
20	∀x(A(x)→B(x))→(∀y(C(y)→A(x))→∃z(C(z)→B(x)))
21	∀x(B(x)→A(y))&(B(x)→∀y(A(y)→C(z)))→∃z(C(z))
22	(∃x(A(x)→B(z))→∃y(C(y)∨A(x)))→∀z(C(y)∨B(z))
23	(∀x(B(x))→∃y(A(y)))&(A(y)→∃y(C(y)))→(¬A(x)∨C(y))
24	((∀x(A(x))→∃x(B(x)))→∃y(A(x)∨C(y)))→(B(x)∨C(y))
25	∃x(A(x)→∀y(B(y)))&(¬A(x)→∀y(B(y)))→B(y)
26	∀x(A(x)→∃y(B(y)))&(¬A(x)→B(x))→B(x)
27	(∃x(B(x))→∀y(A(y)))&(¬B(x)→A(y))→A(z)
28	(∀x(B(x))→∃z(C(z)))→(A(y)&B(x)→A(y)&C(z))
29	∃x(A(x)→B(y))→∀y∀z((C(z)→A(x))→(C(z)→B(y)))
30	(∀x(A(x))→∃z(C(z)))&∀y(C(z)→B(y))→(A(x)→B(y))
31	(∀x(A(x))→∃y(B(y)))&∀y(C(y)→∃x(D(x)))→(A(x)&C(y))
32	∀x(A(x)→B(y))&(A(x)→∀y(B(y)→C(z)))→∃z(C(z))
33	(∃x(A(x)→B(z))→∃y(C(y)∨A(x)))→∀z(C(y)∨B(z))
34	∀x(A(x)→B(y))&∀z(C(z)→A(x))→∃y(C(z)→B(y))
35	(∀x(A(x)→∃z(B(z)))→∃y(A(x)∨C(y)))→(B(z)∨C(y))
36	∀x(B(x)→∀y(A(y)))&∀y(B(x)→(A(y)→C(z)))
37	∀x(A(x)→B(x))→∀y((C(y)→A(x))→(C(y)→B(x)))
38	(∀x(A(x))→∃z(C(z)))&∀y(C(z)→B(y))→(A(x)→B(y))
39	∀x(A(x)→∃y(B(y)))&(¬A(x)→B(x))→B(x)
40	(∀x(B(x))→∃y(A(y)))&(A(y)→∃y(C(y)))→(¬A(x)∨C(y))
41	∀x(B(x)→A(y))&(B(x)→∀y(A(y)→C(z)))→∃z(C(z))
42	∀x(B(x)→∀y(A(y)))&∀y(B(y)→(A(x)→C(z)))®∃z(C(z))
43	∀x(A(x)→B(x))&∃y(B(x)→C(y))→∃z(C(y)→D(z))
44	∀x(¬A(x)→∃y(B(y)))→(¬B(y)→A(x))
45	(∃x(¬A(x))→∀z(¬B(z)))→(¬B(x)∨A(x))
46	∀x(A(x)→∃z(B(y)→C(z)))→∀y(B(y)→(A(x)→C(z)))
47	∀x(A(x)→B(y))&∀y(A(x)→(B(y)→C(z)))→(A(x)®∃z(C(z)))
48	∀x(A(x)→B(z))&∀y(C(y)→A(x))→∃z(C(y)→B(z))
49	∀x(A(x)→∃y(B(y)))→∃y(¬A(x)∨¬C(z)∨B(y))
50	∀x(A(x)→B(y))&∀y(A(x)→(B(y)→C(z)))→∃z(C(z))

Задание 3. Реляционная логика

Согласно варианту (см. табл. 4):