Логика высказываний (работа 1)

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

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

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

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

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

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

Студент

гр. ВМз-01-08, факультет УиИТ

____________________ М.О.Белозерова

«__»___________2009

Преподаватель

___________________ С.А. Рудаков

к.п.н. «__»___________2009

Челябинск

2009

1. Задание по логике высказываний

Ниже приведены по три клаузы в одном варианте. Каждую клаузу необходимо доказать следующими методами: резолюций и с помощью таблиц истинности.

      А, В v С => А & В; С

      B v С, (А -> В) -> (С -> А) => А

      А -> (В v С), В -> (D -> А), С -> (В -> А), А -> (В -> С), D - > (A v В),

D -> (А -> В), С -> (В v D), A v С v D, С -> (А -> В) => А & В & С; А & В & D

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

      А, В v С => А & В; С

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

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

P1 P2 P3 P4

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

№ п/п

Выводы

Почему

0

Р2, Р3

0

P1, P4

0

1, 2

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

B v С, (А -> В) -> (С -> А) => А

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

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

P1 P2 P3

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

№ п/п

Выводы

Почему

1.

А

Р1, Р2

2.

0

P3, 1

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

c. А -> (В v С), В -> (D -> А), С -> (В -> А), А -> (В -> С), D - > (A v В),

D -> (А -> В), С -> (В v D), A v С v D, С -> (А -> В) => А & В & С;

А & В & D

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

А v В v С, -В v -D v А, -С v –В v А, -А v -В v С, -D v A v В, P1 P2 P3 P4 P5 D v -А v В,

- С v В v D, A v С v D,

-С 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

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

B v С, (А -> В) -> (С -> А) => А

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 - > (A v В),

P1 P2 P3 P4 P5

D -> (А -> В), С -> (В v D), A v С v D, С -> (А -> В) => А & В & С; А & В & 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: B v С, (А -> В) -> (С -> А) => А

Студент Иванов находился на уроке или в коридоре. На уроке была контрольная работа, Иванов получил четвертку, то он был на уроке, он был в коридоре, не смотря на то, что он получил четверку. Это говорит о том, что у студента Иванова есть, стремление хорошо учится.

3. Составление клаузы по легенде

Ниже приведена легенда. Запишите с использованием 4—6 различных букв клаузу, отвечающую тексту или контексту вашей легенды, для чего сформулируйте необходимые посылки и два следствия: одно истинное, другое ложное. С помощью таблицы истинности найдите МНФ, минимальное и все трансверсальные покрытия.

Увеличение денег в обращении влечет за собой инфляцию. Но рост денежной массы происходит по двум причинам: из-за денежной эмиссии или снижения товарооборота. Снижение товарооборота приводит к безработице и спаду производства. Из-за инфляции падает курс денежной единицы. Рекомендации экономиста Иванова: увеличить денежную эмиссию и поднять производство, тогда избежим безработицы и курс денежной единицы останется неизменным.

Можно составить следующую клаузу:

A → B, A → (C v D), D → (E&F), B → G => (C & -F) → (-E & G)

Введем обозначения:

A – Увеличение денег (денежная масса, курс денежной единицы);

B – Инфляция;

C – Денежная эмиссия;

D – Снижение товарооборота;

E – Безработица;

F – Спад производства;

G – курс денежной единицы.

Увеличение денег в обращении влечет за собой инфляцию (A → B). Но рост денежной массы происходит по двум причинам: из-за денежной эмиссии или снижения товарооборота (A → (C v D)). Снижение товарооборота приводит к безработице и спаду производства (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 В(х)

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