Логика высказываний

Муниципальное образовательное учреждение высшего профессионального образования

Южно-Уральский профессиональный институт

Факультет управления и информационных технологий

Кафедра информатики и вычислительной техники

Контрольная работа

по дисциплине «Математическая логия и теория алгоритмов»

Студент

гр. ВМз-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.	0	Р2, Р3
2.	0	P1, P4
3.	0	1, 2

Докажем с помощью метода резолюций истинность следующей клаузы:

Bv С, (А -> В) -> (С -> А) => А

Доказательство ее справедливости следует начать с приведения ее в нормальную конъюнктивную форму.

В v С, A v -B v -C, -A => 0

P1 P2 P3

Справа от каждого нового дизъюнкта будем писать номера используемых дизъюнктов, получим:

№ п/п	Выводы	Почему
1.	А	Р1, Р2
2.	0	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.	0	P1,P3
11.	0	P13,7
12.	0	9,10
13.	0	11,12

Докажем с помощью таблиц истинности следующую клаузу:

А, В v С => А, В vС

P1 P2 C1 C2

Докажем с помощью таблиц истинности следующую клаузу:

Bv С, (А -> В) -> (С -> А) => А

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 - > (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
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:

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
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 В(х)

Доказательство: