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

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

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

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

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

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

По дисциплине “Математическая логия и теория алгоритмов”

Студент

Гр. ВМз-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.0P1, P4
3.01, 2

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

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

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

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

P1 P2 P3

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

№ п/пВыводыПочему
1.АР1, Р2
2.0P3, 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 – DP4,P5
2.A v – CP2,P7
3.B v CP6,P8
4.-A v – DP12,1
5.-C v – AP9,P11
6.-C2,5
7.B3,6
8.-A v – DP10,4
9.-A v – DP14,8
10.0P1,P3
11.0P13,7
12.09,10
13.011,12

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

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

P1 P2 C1 C2

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

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

P1 P2 C1

Теперь составим таблицу истинности (табл. 1.1) , в которой под Р понимается обобщенная причина, т. е. конъюнкция всех Р.

NАBCP1P2PC1
00000100
10011110
20101110
30111000
41000101
51011111
61101111
71111111

Клауза считается ложной, т. к. единицы следствия (С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АBCDP1P2Р3Р4Р5P6P7P8P9PC1C2C3C4C5
00000111111101000000
10001111101111000001
20010111111011000000
30011111101111000001
40100111111101001010
50101101111111001111
60110110111111001110
70111100111111001111
81000011111111010100
91001011110111010101
101010111111010010100
111011111110110010101
121100111011111011110
131101111011111011111
141110111111111111110
151111111111111111111

Клауза считается истинной, т. к единицы следствия (С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).

1

NАBCDEFGP1P2Р3Р4PC1
00000000111110
10000001111111
20000010111111
30000011111111
40000100111110
50000101111110
60000110111111
70000111111111
80001000110100
90001001110101
100001010110101
110001011110101
120001100110100
130001101110101
140001110111111
150001111111111
160010000111110
170010001111111
180010010111110
190010011111111
200010100111110
210010101111110
220010110111110
230010111111110
240011000110100
250011001110101
260011010110100
270011011110101
280011100110100
290011101110100
300011110111110
310011111111110
320100001111111
330100010111001
340100011111110
350100100111000
360100101111110
370100110111001
380100111111111
390101000110000
400101001110111
410101010110001
420101011110111
430101100110000
440101101110110
450101110111001
460101111111111
470110000111000
48010001111111
490110010111000
500110011111111
510110100111000
520110101111110
530110110111000
540110111111110
550111000110000
560111001110111
570111010110000
580111011110111
590111100110000
600111101110110
610111110111000
620111111111110
631000000001100
641000001001101
651000010001101
661000011001101
671000100001100
681000101001100
691000110001101
701000111001101
711001000010100
721001001010101
731001010010101
741001011010101
751001100010100
761001101010100
771001110011101
781001111011101
791010000011100
801010001011101
811010010011100
821010011011101
831010100011100
841010101011100
851010110011100
861010111011100
871011000010100
881011001010101
891011010010100
901011011010101
911011100010100
921011101010100
931011110010100
941011111010100
951100000101000
961100001101101
971100010 101001
981100011101101
991100100101000
1001100101101100
1011100110101001
1021100111101101
1031101000110000
1041101001110101
1051101010110001
1061101011110101
1071101100110000
1081101101110100
1091101110111001
1101101111111111
1111110000110000
1121110001110101
1131110010110000
1141110011110101
1151110100110000
1161110101110100
1171110110110000
1181110111110100
1191111000111000
1201111001111111
1211111010111000
1221111011111111
1231111100111000
1241111101111110
1251111110111000
1261111111111110

Из таблицы видно, что четыре единицы обобщенной посылки (Р) не покрываются единицами ложного следствия (-Е); единицы же истинного следствия (Е -> (В &; D )) целиком накрывают единицы обобщенной посылки.

4. Задание по логике предикатов

Установить истинность логического выражения своего варианта путем конкретизации.

Х Y (А(x) -> В(у)) = Х A(x) -> X В(х)

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


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