Логика высказываний
Муниципальное образовательное учреждение высшего профессионального образования
Южно-Уральский профессиональный институт
Факультет управления и информационных технологий
Кафедра информатики и вычислительной техники
Контрольная работа
по дисциплине «Математическая логия и теория алгоритмов»
Студент
гр. ВМз-01-08, факультет УиИТ
____________________ М.О.Белозерова
«__»___________2009
Преподаватель
___________________ С.А. Рудаков
к.п.н. «__»___________2009
Челябинск
2009
1. Задание по логике высказываний
Ниже приведены по три клаузы в одном варианте. Каждую клаузу необходимо доказать следующими методами: резолюций и с помощью таблиц истинности.
А, В v С => А & В; С
B v С, (А -> В) -> (С -> А) => А
А -> (В v С), В -> (D -> А), С -> (В -> А), А -> (В -> С), D - > (A v В),
D -> (А -> В), С -> (В v D), A v С v D, С -> (А -> В) => А & В & С; А & В & D
Докажем с помощью метода резолюций истинность следующей клаузы:
А, В v С => А & В; С
Доказательство ее справедливости следует начать с приведения ее в нормальную конъюнктивную форму.
A, В v C, -B v -C, -A => 0
P1 P2 P3 P4
Справа от каждого нового дизъюнкта будем писать номера используемых дизъюнктов, получим:
№ п/п
Выводы
Почему
0
Р2, Р3
0
P1, P4
0
1, 2
Докажем с помощью метода резолюций истинность следующей клаузы:
B v С, (А -> В) -> (С -> А) => А
Доказательство ее справедливости следует начать с приведения ее в нормальную конъюнктивную форму.
В v С, A v -B v -C, -A => 0
P1 P2 P3
Справа от каждого нового дизъюнкта будем писать номера используемых дизъюнктов, получим:
-
№ п/п
Выводы
Почему
1.
А
Р1, Р2
2.
0
P3, 1
Докажем с помощью метода резолюций истинность следующей клаузы:
c. А -> (В v С), В -> (D -> А), С -> (В -> А), А -> (В -> С), D - > (A v В),
D -> (А -> В), С -> (В v D), A v С v D, С -> (А -> В) => А & В & С;
А & В & D
Доказательство ее справедливости следует начать с приведения ее в нормальную конъюнктивную форму.
А v В v С, -В v -D v А, -С v –В v А, -А v -В v С, -D v A v В, P1 P2 P3 P4 P5 D v -А v В,
- С v В v D, A v С v D,
-С v -А v В, -А, -В, -С v -А, -В, -D =>0 P6 P7 P8 P9 P10 P11 P12 P13 P14
Справа от каждого нового дизъюнкта будем писать номера используемых дизъюнктов, получим:
-
№ п/п
Выводы
Почему
1.
C v -D
P4,P5
2.
A v -C
P2,P7
3.
B v C
P6,P8
4.
-A v -D
P12,1
5.
-C v -A
P9,P11
6.
-C
2,5
7.
B
3,6
8.
-A v -D
P10,4
9.
-A v -D
P14,8
10.
0
P1,P3
11.
0
P13,7
12.
0
9,10
13.
0
11,12
Докажем с помощью таблиц истинности следующую клаузу:
А, В v С => А, В v С
P1 P2 C1 C2
Докажем с помощью таблиц истинности следующую клаузу:
B v С, (А -> В) -> (С -> А) => А
P1 P2 C1
Теперь составим таблицу истинности (табл. 1.1) , в которой под Р понимается обобщенная причина, т.е. конъюнкция всех Р.
-
n
А
B
C
P1
P2
P
C1
0
0
0
0
0
1
0
0
1
0
0
1
1
1
1
0
2
0
1
0
1
1
1
0
3
0
1
1
1
0
0
0
4
1
0
0
0
1
0
1
5
1
0
1
1
1
1
1
6
1
1
0
1
1
1
1
7
1
1
1
1
1
1
1
Клауза считается ложной, т.к. единицы следствия (С1) не накрывают все единицы обобщенной причины (Р), т.е. единицы обобщенной причины не образуют подмножество единиц следствия.
Докажем с помощью таблиц истинности следующую клаузу:
А -> (В v С), В -> (D -> А), С -> (В -> А), А -> (В -> С), D - > (A v В),
P1 P2 P3 P4 P5
D -> (А -> В), С -> (В v D), A v С v D, С -> (А -> В) => А & В & С; А & В & D
Р6 Р7 Р8 Р9 С1 C2 C3 C4 C5
Теперь составим таблицу истинности (табл. 1.3) , в которой под Р понимается обобщенная причина, т.е. конъюнкция всех Р.
n
А
B
C
D
P1
P2
Р3
Р4
Р5
P6
P7
P8
P9
P
C1
C2
C3
C4
C5
0
0
0
0
0
1
1
1
1
1
1
1
0
1
0
0
0
0
0
0
1
0
0
0
1
1
1
1
1
0
1
1
1
1
0
0
0
0
0
1
2
0
0
1
0
1
1
1
1
1
1
0
1
1
0
0
0
0
0
0
3
0
0
1
1
1
1
1
1
0
1
1
1
1
0
0
0
0
0
1
4
0
1
0
0
1
1
1
1
1
1
1
0
1
0
0
1
0
1
0
5
0
1
0
1
1
0
1
1
1
1
1
1
1
0
0
1
1
1
1
6
0
1
1
0
1
1
0
1
1
1
1
1
1
0
0
1
1
1
0
7
0
1
1
1
1
0
0
1
1
1
1
1
1
0
0
1
1
1
1
8
1
0
0
0
0
1
1
1
1
1
1
1
1
0
1
0
1
0
0
9
1
0
0
1
0
1
1
1
1
0
1
1
1
0
1
0
1
0
1
10
1
0
1
0
1
1
1
1
1
1
0
1
0
0
1
0
1
0
0
11
1
0
1
1
1
1
1
1
1
0
1
1
0
0
1
0
1
0
1
12
1
1
0
0
1
1
1
0
1
1
1
1
1
0
1
1
1
1
0
13
1
1
0
1
1
1
1
0
1
1
1
1
1
0
1
1
1
1
1
14
1
1
1
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
15
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
Клауза считается истинной, т.к единицы следствия (С1) накрывают все единицы обобщенной причины (Р), т.е. единицы обобщенной причины образуют подмножество единиц следствия.
2. Составление легенды по клаузе
Клауза 1: А, В v С => А & В; С
Машина едет по Копейскому шоссе. На дороге опасно, так как она покрыта льдом или мокрая. Итак, машина едет по шоссе или по ледяной дороге или по мокрой.
Клауза 2: B v С, (А -> В) -> (С -> А) => А
Студент Иванов находился на уроке или в коридоре. На уроке была контрольная работа, Иванов получил четвертку, то он был на уроке, он был в коридоре, не смотря на то, что он получил четверку. Это говорит о том, что у студента Иванова есть, стремление хорошо учится.
3. Составление клаузы по легенде
Ниже приведена легенда. Запишите с использованием 4—6 различных букв клаузу, отвечающую тексту или контексту вашей легенды, для чего сформулируйте необходимые посылки и два следствия: одно истинное, другое ложное. С помощью таблицы истинности найдите МНФ, минимальное и все трансверсальные покрытия.
Увеличение денег в обращении влечет за собой инфляцию. Но рост денежной массы происходит по двум причинам: из-за денежной эмиссии или снижения товарооборота. Снижение товарооборота приводит к безработице и спаду производства. Из-за инфляции падает курс денежной единицы. Рекомендации экономиста Иванова: увеличить денежную эмиссию и поднять производство, тогда избежим безработицы и курс денежной единицы останется неизменным.
Можно составить следующую клаузу:
A → B, A → (C v D), D → (E&F), B → G => (C & -F) → (-E & G)
Введем обозначения:
A – Увеличение денег (денежная масса, курс денежной единицы);
B – Инфляция;
C – Денежная эмиссия;
D – Снижение товарооборота;
E – Безработица;
F – Спад производства;
G – курс денежной единицы.
Увеличение денег в обращении влечет за собой инфляцию (A → B). Но рост денежной массы происходит по двум причинам: из-за денежной эмиссии или снижения товарооборота (A → (C v D)). Снижение товарооборота приводит к безработице и спаду производства (D → (E&-F)).
Из-за инфляции падает курс денежной единицы (B → G). Рекомендации экономиста Иванова: увеличить денежную эмиссию и поднять производство(C & F), тогда избежим безработицы и курс денежной единицы останется неизменным (-E & G).
n
А
B
C
D
E
F
G
P1
P2
Р3
Р4
P
C1
0
0
0
0
0
0
0
0
1
1
1
1
1
0
1
0
0
0
0
0
0
1
1
1
1
1
1
1
2
0
0
0
0
0
1
0
1
1
1
1
1
1
3
0
0
0
0
0
1
1
1
1
1
1
1
1
4
0
0
0
0
1
0
0
1
1
1
1
1
0
5
0
0
0
0
1
0
1
1
1
1
1
1
0
6
0
0
0
0
1
1
0
1
1
1
1
1
1
7
0
0
0
0
1
1
1
1
1
1
1
1
1
8
0
0
0
1
0
0
0
1
1
0
1
0
0
9
0
0
0
1
0
0
1
1
1
0
1
0
1
10
0
0
0
1
0
1
0
1
1
0
1
0
1
11
0
0
0
1
0
1
1
1
1
0
1
0
1
12
0
0
0
1
1
0
0
1
1
0
1
0
0
13
0
0
0
1
1
0
1
1
1
0
1
0
1
14
0
0
0
1
1
1
0
1
1
1
1
1
1
15
0
0
0
1
1
1
1
1
1
1
1
1
1
16
0
0
1
0
0
0
0
1
1
1
1
1
0
17
0
0
1
0
0
0
1
1
1
1
1
1
1
18
0
0
1
0
0
1
0
1
1
1
1
1
0
19
0
0
1
0
0
1
1
1
1
1
1
1
1
20
0
0
1
0
1
0
0
1
1
1
1
1
0
21
0
0
1
0
1
0
1
1
1
1
1
1
0
22
0
0
1
0
1
1
0
1
1
1
1
1
0
23
0
0
1
0
1
1
1
1
1
1
1
1
0
24
0
0
1
1
0
0
0
1
1
0
1
0
0
25
0
0
1
1
0
0
1
1
1
0
1
0
1
26
0
0
1
1
0
1
0
1
1
0
1
0
0
27
0
0
1
1
0
1
1
1
1
0
1
0
1
28
0
0
1
1
1
0
0
1
1
0
1
0
0
29
0
0
1
1
1
0
1
1
1
0
1
0
0
30
0
0
1
1
1
1
0
1
1
1
1
1
0
31
0
0
1
1
1
1
1
1
1
1
1
1
0
32
0
1
0
0
0
0
1
1
1
1
1
1
1
33
0
1
0
0
0
1
0
1
1
1
0
0
1
34
0
1
0
0
0
1
1
1
1
1
1
1
0
35
0
1
0
0
1
0
0
1
1
1
0
0
0
36
0
1
0
0
1
0
1
1
1
1
1
1
0
37
0
1
0
0
1
1
0
1
1
1
0
0
1
38
0
1
0
0
1
1
1
1
1
1
1
1
1
39
0
1
0
1
0
0
0
1
1
0
0
0
0
40
0
1
0
1
0
0
1
1
1
0
1
1
1
41
0
1
0
1
0
1
0
1
1
0
0
0
1
42
0
1
0
1
0
1
1
1
1
0
1
1
1
43
0
1
0
1
1
0
0
1
1
0
0
0
0
44
0
1
0
1
1
0
1
1
1
0
1
1
0
45
0
1
0
1
1
1
0
1
1
1
0
0
1
46
0
1
0
1
1
1
1
1
1
1
1
1
1
47
0
1
1
0
0
0
0
1
1
1
0
0
0
48
0
1
1
0
0
0
1
1
1
1
1
1
1
49
0
1
1
0
0
1
0
1
1
1
0
0
0
50
0
1
1
0
0
1
1
1
1
1
1
1
1
51
0
1
1
0
1
0
0
1
1
1
0
0
0
52
0
1
1
0
1
0
1
1
1
1
1
1
0
53
0
1
1
0
1
1
0
1
1
1
0
0
0
54
0
1
1
0
1
1
1
1
1
1
1
1
0
55
0
1
1
1
0
0
0
1
1
0
0
0
0
56
0
1
1
1
0
0
1
1
1
0
1
1
1
57
0
1
1
1
0
1
0
1
1
0
0
0
0
58
0
1
1
1
0
1
1
1
1
0
1
1
1
59
0
1
1
1
1
0
0
1
1
0
0
0
0
60
0
1
1
1
1
0
1
1
1
0
1
1
0
61
0
1
1
1
1
1
0
1
1
1
0
0
0
62
0
1
1
1
1
1
1
1
1
1
1
1
0
63
1
0
0
0
0
0
0
0
0
1
1
0
0
64
1
0
0
0
0
0
1
0
0
1
1
0
1
65
1
0
0
0
0
1
0
0
0
1
1
0
1
66
1
0
0
0
0
1
1
0
0
1
1
0
1
67
1
0
0
0
1
0
0
0
0
1
1
0
0
68
1
0
0
0
1
0
1
0
0
1
1
0
0
69
1
0
0
0
1
1
0
0
0
1
1
0
1
70
1
0
0
0
1
1
1
0
0
1
1
0
1
71
1
0
0
1
0
0
0
0
1
0
1
0
0
72
1
0
0
1
0
0
1
0
1
0
1
0
1
73
1
0
0
1
0
1
0
0
1
0
1
0
1
74
1
0
0
1
0
1
1
0
1
0
1
0
1
75
1
0
0
1
1
0
0
0
1
0
1
0
0
76
1
0
0
1
1
0
1
0
1
0
1
0
0
77
1
0
0
1
1
1
0
0
1
1
1
0
1
78
1
0
0
1
1
1
1
0
1
1
1
0
1
79
1
0
1
0
0
0
0
0
1
1
1
0
0
80
1
0
1
0
0
0
1
0
1
1
1
0
1
81
1
0
1
0
0
1
0
0
1
1
1
0
0
82
1
0
1
0
0
1
1
0
1
1
1
0
1
83
1
0
1
0
1
0
0
0
1
1
1
0
0
84
1
0
1
0
1
0
1
0
1
1
1
0
0
85
1
0
1
0
1
1
0
0
1
1
1
0
0
86
1
0
1
0
1
1
1
0
1
1
1
0
0
87
1
0
1
1
0
0
0
0
1
0
1
0
0
88
1
0
1
1
0
0
1
0
1
0
1
0
1
89
1
0
1
1
0
1
0
0
1
0
1
0
0
90
1
0
1
1
0
1
1
0
1
0
1
0
1
91
1
0
1
1
1
0
0
0
1
0
1
0
0
92
1
0
1
1
1
0
1
0
1
0
1
0
0
93
1
0
1
1
1
1
0
0
1
0
1
0
0
94
1
0
1
1
1
1
1
0
1
0
1
0
0
95
1
1
0
0
0
0
0
1
0
1
0
0
0
96
1
1
0
0
0
0
1
1
0
1
1
0
1
97
1
1
0
0
0
1
0
1
0
1
0
0
1
98
1
1
0
0
0
1
1
1
0
1
1
0
1
99
1
1
0
0
1
0
0
1
0
1
0
0
0
100
1
1
0
0
1
0
1
1
0
1
1
0
0
101
1
1
0
0
1
1
0
1
0
1
0
0
1
102
1
1
0
0
1
1
1
1
0
1
1
0
1
103
1
1
0
1
0
0
0
1
1
0
0
0
0
104
1
1
0
1
0
0
1
1
1
0
1
0
1
105
1
1
0
1
0
1
0
1
1
0
0
0
1
106
1
1
0
1
0
1
1
1
1
0
1
0
1
107
1
1
0
1
1
0
0
1
1
0
0
0
0
108
1
1
0
1
1
0
1
1
1
0
1
0
0
109
1
1
0
1
1
1
0
1
1
1
0
0
1
110
1
1
0
1
1
1
1
1
1
1
1
1
1
111
1
1
1
0
0
0
0
1
1
0
0
0
0
112
1
1
1
0
0
0
1
1
1
0
1
0
1
113
1
1
1
0
0
1
0
1
1
0
0
0
0
114
1
1
1
0
0
1
1
1
1
0
1
0
1
115
1
1
1
0
1
0
0
1
1
0
0
0
0
116
1
1
1
0
1
0
1
1
1
0
1
0
0
117
1
1
1
0
1
1
0
1
1
0
0
0
0
118
1
1
1
0
1
1
1
1
1
0
1
0
0
119
1
1
1
1
0
0
0
1
1
1
0
0
0
120
1
1
1
1
0
0
1
1
1
1
1
1
1
121
1
1
1
1
0
1
0
1
1
1
0
0
0
122
1
1
1
1
0
1
1
1
1
1
1
1
1
123
1
1
1
1
1
0
0
1
1
1
0
0
0
124
1
1
1
1
1
0
1
1
1
1
1
1
0
125
1
1
1
1
1
1
0
1
1
1
0
0
0
126
1
1
1
1
1
1
1
1
1
1
1
1
0
Из таблицы видно, что четыре единицы обобщенной посылки (Р) не покрываются единицами ложного следствия (-Е); единицы же истинного следствия (Е -> (В & D)) целиком накрывают единицы обобщенной посылки.
4. Задание по логике предикатов
Установить истинность логического выражения своего варианта путем конкретизации.
х y (А(x) -> В(у)) = 
х A(x) -> x В(х)
Доказательство:
Нравится материал? Поддержи автора!
Ещё документы из категории математика:
Чтобы скачать документ, порекомендуйте, пожалуйста, его своим друзьям в любой соц. сети.
После чего кнопка «СКАЧАТЬ» станет доступной!
Кнопочки находятся чуть ниже. Спасибо!
Кнопки:
Скачать документ