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

Методы доказательства клаузы: с помощью резолюций и таблиц истинности. Определение ложности и истинности клаузы. Особенности составления легенды по клаузе. Составление клаузы по легенде. Определение истинности логического выражения путем конкретизации.

Рубрика Математика
Вид контрольная работа
Язык русский
Дата добавления 14.06.2009
Размер файла 29,9 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

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

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

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

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

Контрольная работа
по дисциплине «Математическая логия и теория алгоритмов»
Студент
гр. ВМз-01-08, факультет УиИТ
____________________ М.О.Белозерова
«__»___________2009
Преподаватель
___________________ С.А. Рудаков
к.п.н. «__»___________2009
Челябинск
2009
1. Задание по логике высказываний

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

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

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

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

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

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

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 В(х)

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


Подобные документы

  • История возникновения булевой алгебры, разработка системы исчисления высказываний. Методы установления истинности или ложности сложных логических высказываний с помощью алгебраических методов. Дизъюнкция, конъюнкция и отрицание, таблицы истинности.

    презентация [1,9 M], добавлен 22.02.2014

  • Построение таблицы истинности. Доказательство истинности заключения путём построения дерева доказательства или методом резолюции. Выполнение различных бинарных операций. Построение графа вывода пустой резольвенты. Основные правила исчисления предикатов.

    курсовая работа [50,7 K], добавлен 28.05.2015

  • Степень истинности или ложности высказывания. Операции над нечеткими высказываниями. Отрицание, конъюнкция, дизъюнкция, импликация и эквивалентность высказываний. Типы лингвистических высказываний. Множество нечетких продукций и входных переменных.

    лекция [23,6 K], добавлен 15.10.2013

  • Порядок доказательства истинности заключения методом резолюции (с построением графа вывода пустой резольвенты) и методом дедуктивного вывода (с построением графа дедуктивного вывода). Выполнение бинарных операций и составление результирующих таблиц.

    курсовая работа [185,3 K], добавлен 24.05.2015

  • Составление таблицы истинности. Получение уравнений функций алгебры логики для заданных выходов. Реализация схемы логического автомата на электромагнитных реле РП-23, на диодной матрице. Реализация структурной схемы логического автомата, на микросхемах.

    курсовая работа [862,4 K], добавлен 12.12.2012

  • Изучение истинности суждений. Определение отношений понятий с использованием иллюстрации кругов Л. Эйлера. Виды, структура сложных суждений. Противоположные и противоречащие модальности. Структурная схема силлогизмов. Определение правил доказательства.

    контрольная работа [34,4 K], добавлен 02.01.2011

  • Основные формы мышления: понятия, суждения, умозаключения. Сочинение Джорджа Буля, в котором подробно исследовалась логическая алгебра. Значение истинности (т.е. истинность или ложность) высказывания. Логические операции инверсии (отрицания) и конъюнкции.

    презентация [399,6 K], добавлен 14.12.2016

  • Доказательство тождества с помощью диаграмм Эйлера-Венна. Определение вида логической формулы с помощью таблицы истинности. Рисунок графа G (V, E) с множеством вершин V. Поиск матриц смежности и инцидентности. Определение множества вершин и ребер графа.

    контрольная работа [463,0 K], добавлен 17.05.2015

  • Изучение понятия о логической величине. Отличия общих, частных, единичных высказываний. Таблица истинности. Принципы использования простых и составных логических выражений. Вложенное ветвление. Определение наибольшего среди трех чисел неполного ветвления.

    презентация [97,3 K], добавлен 09.10.2013

  • Понятие алгебры логики, ее сущность и особенности, основные понятия и определения, предмет и методика изучения. Законы алгебры логики и следствия из них, методы построения формул по заданной таблице истинности. Формы представления булевых функций.

    учебное пособие [702,6 K], добавлен 29.04.2009

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.