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

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

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


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


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


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


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

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


Студент


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


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

Сохранить в соц. сетях:
Обсуждение:
comments powered by Disqus

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

Слов:4007
Символов:54641
Размер:106.72 Кб.