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

СОДЕРЖАНИЕ: Муниципальное образовательное учреждение высшего профессионального образования Южно-Уральский профессиональный институт Факультет управления и информационных технологий

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

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

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

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

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

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

Студент

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

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

Скачать архив с текстом документа