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