Реферат: Логика высказываний

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

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

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

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

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

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

Студент

гр. ВМз-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 В(х)

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