Учебное пособие: Задачи и упражнения по математической логике и теории множеств. Часть математическая логика

МИНИСТЕРСТВО ОБЩЕГО И ПРОФЕССИОНАЛЬНОГО

ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

РОСТОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Я.М.ЕРУСАЛИМСКИЙ, М.Р.УХОВСКИЙ, А.В.КОЗАК

ЗАДАЧИ И УПРАЖНЕНИЯ ПО МАТЕМАТИЧЕСКОЙ ЛОГИКЕ

И ТЕОРИИ МНОЖЕСТВ. ЧАСТЬ 1. МАТЕМАТИЧЕСКАЯ ЛОГИКА.

МЕТОДИЧЕСКИЕ УКАЗАНИЯ ДЛЯ СТУДЕНТОВ 1-ГО КУРСА

МЕХАНИКО-МАТЕМАТИЧЕСКОГО ФАКУЛЬТЕТА ПО КУРСАМ

“МАТЕМАТИЧЕСКАЯ ЛОГИКА”, ”МАТЕМАТИЧЕСКАЯ ЛОГИКА, И ДИСКРЕТНАЯ МАТЕМАТИКА.”

РОСТОВ-НА-ДОНУ

1980

Печатается по решению учебно-методической комиссии механико-математического факультета РГУ от 11 января 1980 г.

I. АЛГЕБРА ВЫСКАЗЫВАНИЙ.

§ 1. ЛОГИЧЕСКИЕ ОПЕРАЦИИ. ТАБЛИЦЫ ИСТИННОСТИ.

Цель этого параграфа — познакомиться с определениями основных логических операций: отрицанием ( , ), дизъюнкцией ( , ), конъюнкцией ( , ), импликацией ( , ), эквиваленцией ( , « , ), их свойствами, построением таблиц истинности формул алгебры высказываний, а также равносильными преобразованиями формул.

Под высказыванием мы понимаем связное (осмысленное) повествовательное предложение, о котором можно сказать истинно оно или ложно. Если A — символ высказывания, то через будем обозначать его значение истинности. 1 (И) – истина, 0 (Л) – ложь. В высказываниях нас будет интересовать только значение истинности, поэтому логические операции можно определить с помощью таблиц истинности.

Отрицание

Бинарные операции

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

Составить таблицу истинности для следующих формул:

1) 2)

3) 4)

5) 6)

7) 8)

9) 10) (x~y)~z

11)

12)

13)

14)

15)

16)

Пусть xi (i=1,2,3…) – символы булевских переменных (т.е. принимающих два значения: 0,1 ). Построить таблицы истинности.

17) ( x1 =x2 ) Ú (x2 =x3 ) 18) (x1 >x2 ) ® (x2 =x3 )

19) (x1 ¹ x2 ) Ù (x2 ¹ x3 ) 20) ((x1 >x2 ) Ù (x2 =x3 )) ® (x2 =x3 )

Применяя таблицы истинности, доказать тождественную истинность формул:

21) x ~ x 22) x Ú

23) 24)

25) x ® (y ® x) 26) ® (x ® y)

27) ((x ® y) Ù x) ® y 28) ((x ® y) Ù ) ®

29) ((x Ú y) Ù ) ® y 30) ((x Ú Ú y) Ù x) ®y

31) (x ® y) ~ (y ®x ) 32) ((x ® y) Ù (y ® z)) ® (x ® z)

33) (x ® (y ® z)) ® ((x Ù y) ® z) 34) ((x ® z) Ù (y ® z)) ® ((x Ú y) ® z)

35) (x ® (y ® z)) ® ((x ® y) ® (x ® z))

Применяя таблицы истинности, доказать равносильность формул:

36) x Ú y º y Ú x 37) x Ù y º y Ù x

38) x Ú (y Ú z) º (x Ú y) Ú z 39) x Ù (y Ù z) º (x Ù y) Ù z

40) x Ù (y Ú z) º (x Ù y) Ú (x Ú z) 41) x Ú (y Ù z) º (x Ú y) Ù (x Ú z)

Законы де Моргана.

Законы идемпотентности .

46) x Ú 0 º x 47) x Ù 1 º x

48) 49) x ~ y º y ~ x

50) x ~ (y ~ z) º (x ~ y) ~ z 51) x ® y º Ú y

52) x ~ y º (x ® y) Ù (y ® x)

При записи формул принимают следующие соглашения об упрощении записи формул:

1). Операции располагаются по старшинству (от «сильных» к «слабым» ) а ù Ù Ú

2). Знак конъюнкции опускается.

Учитывая соглашения о порядке выполнения операций, опустить «лишние» скобки и знак «Ù » в формулах:

53) x Ù (y Ù (x Ú ))

54) (x Ù y) Ú ((y Ù z) Ú (( Ù y) Ú (x Ù )))

55) ((x Ú y) Ú z) ® ((x Ù ) Ú z)

56) ((x Ú y) Ù (x Ú (y Ù z))) ® (( Ù ` y ) ®

57) ((x Ú y) Ú (x Ú ((y Ù (x Ú z)) Ù (y ® z))) ~ z)

58) ((x Ú y) ® (x Ù y)) Ú (( Ù y) Ù ( x Ú ))

59) ((x Ú y) Ù z) ® (((x Ù y) Ú z) ~ ( Ú ))

60) (x Ù (y Ú z)) Ù ((x ® (y ® z)) ~ (x Ù y))

Восстановить скобки и знак «Ù » в формулах:

61) x Ú y ® z 62) x Ú y ® x y

63) 64) x Ú y(x y Ú z)

65) x y Ú x ® Ú y z 66) (x ® x Ú y z) ~ (x Ú y ® z)

67) (x Ú y) ® (x y ~ Ú ) 68) x Ú y ® x Ú y (x ® z) Ú x (y ~ z)

69) x y z ® (x ~ y z) Ú x Ú y (x ® (y ~ z)) 70) x y ~ x(y ® z)(x ~ y) Ú x z Ú y z

§ 2. РАВНОСИЛЬНЫЕ ПРЕОБРАЗОВАНИЯ ФОРМУЛ. НОРМАЛЬНЫЕ ФОРМУЛЫ. ДВОЙСТВЕННОСТЬ В АЛГЕБРЕ ВЫСКАЗЫВАНИЙ.

Две формулы F и G называются равносильными ( F º G) , если .

При равносильных преобразованиях формул используются основные равносильности булевой алгебры высказываний (см. [1] стр.42).

Применяя равносильные преобразования доказать следующие соотношения:

71) 72)

73) 74) x ® y º ®

75) x y Ú x º x 76) x Ú x y º x

77) x(x Ú y) º x 78) x Ú y º x Ú y

79) Ú x y º Ú y 80) (x ® y) ® y º x Ú y

81) (x Ú y)(x Ú ) º x 82) Ú º y ®

83) x ~ y º ~ 84) x y Ú y Ú º x ® y

85) x ® (y ® z) º (x Ú z)(y Ú z) 86) x ® (y ® z) º y ® (x ® z)

87) Ú x y Ú x z Ú y Ú z º x ® y z

Применяя равносильные преобразования доказать тождественную истинность формул:

88) x ® x Ú y 89) x y ® x

90) ® (x ® y) 91) (x ® y) ® ( Ú y)

92) ( ® y) ® ( ® x) 93) ( ® ) ® (y ® x)

94) (x ® y) Ú (y ® x) 95) (x ® y) Ú (x ® )

96) x ® (y ® x y) 97) (x ® y) x ® y

98) (x ® y) ® 99) (x Ú y) ® y

100) (x ÚÚ y)x ® ; « ÚÚ » — альтернативная дизъюнкция.

101) ( x ® y)(y ® z) ® (x ® z) 102) (x ® (y ® z)) ® (x y ® z)

103) (x ® z)(y ® z) ® (x Ú y ® z) 104) (x ® z) ® ((y ® z) ® (x Ú y ® z))

Применяя равносильные преобразования, «упростить»:

105) 106)

107) 108) (x Ú y)(x ~ y)

109) (x ® y)(y ® z) ® (z ® x) 110) x z Ú x Ú y z Ú y z

111) 112) x y (x ~ y)

113) (x ® ) (x ~ y) 114)

Следующие формулы преобразовать так, чтобы они содержали только «Ù » и «ù »

115) x Ú y 116) x ® y

117) x ~ y 118) x Ú y Ú z

119) x ® (y ® z) 120) x Ú (x ~ y)

121) Ú ( ® ) 122) x ÚÚ y

123) x ® ( ® x) 124) x Ú y ® ( ® y)

Следующие формулы преобразовать так, чтобы они содержали только «Ú » и «ù »:

125) x y 126) x y z

127) x ~ y 128) x ÚÚ y

129) x (x ~ y) 130) x ~ y ~ z

131) (x ~ y) (y ~ z) 132) x y ~ x z

Следующие формулы преобразовать так, чтобы знак отрицания был отнесен только к переменным высказываниям:

133) 134)

135) 136)

137) 138)

Преобразовать формулы так, чтобы они содержали только операции «Ú », «Ù » и «ù » :

139) x ~ y 140) (x ® y) ~ (y ® z)

141) (x ~ y) ® (y ® z) 142) (x ~ y) ® (y ~ z)

143) (x ~ y)(y ~ z) ® (x ~ z) 144) ((x ~ y) Ú (y ~ z)) ® (x ~y~ z)

145) x ~ y ~ z ~ v 146) (x ® y) ~ (z ® (x~ ))

Найти двойственные формулы:

147) x( Ú z) 148) x y Ú x z

149) 150) (x y Ú y z Ú z v)

151) 152)

153) ((x Ú y) Ú x y) Ú ( Ú x)

154) x y( Ú x y z Ú )(x Ú y Ú z)

Применить закон двойственности к следующим равносильностям:

155) x x º x 156) x Ú 0 º x

157) x y º y x 158) x Ú (y Ú z) º (x Ú y) Ú z

159) º Ú 160) x (x Ú y) º x

161) x Ú y º x Ú y 162) x Ú x y Ú y z Ú z º x Ú z

Привести к дизъюнктивной нормальной форме (ДНФ ):

163) 164)

165) 166)

167) 168)

169) 170)

171) 172)

Привести к конъюнктивной нормальной форме (КНФ ):

173) 174)

175) 176)

177) 178)

179) 180)

181) 182) .

Приведением к нормальной форме выяснить, какие из формул являются тождественно истинными, тождественно ложными, выполнимы:

183) 184)

185) 186)

187) 188)

189)

190)

191)

Для каждой из следующих формул найти дизъюнктивное и конъюктивное разложение:

192) 193)

194) 195)

196) 197)

198) 199)

200)

Привести к совершенной ДНФ (СДНФ) следующие формулы:

201) 202)

203) 204)

205) 206)

207) 208)

Привести к совершенной КНФ (СКНФ) следующие формулы:

209) 210)

211) 212)

213) 214)

215) 216)

217) 218)

Приведением к совершенным нормальным формам доказать не равносильность

следующих формул:

219) и

220) и

221 ) и

222) и

223) и

224) и

225) и

226) и

227) и

228) и

Следующие формулы разложить по переменным x, y, z :

229) 230) 231) x

232) 233)

Выяснить, является ли первая формула логическим следствием остальных:

234) y;

235) x;

236) ;

237)

238) y;

239) ;

240) ;

241)

242)

243) ;

244) ;

245) z;

246)

247)

248)

249)

250)

Найти все (с точностью до равносильности) логические следствия из посылок:

251) 252)

253) 254)

255) 256)

257) 258)

259) 260)

Найти все (с точностью до равносильности) посылки, логическим следствием

которых являются формулы:

261) 262) 263)

264) 265) 266) xyz

267) 268) 269)

270)

Докажите правильность умозаключений:

271) 272)

273) 274)

275) 276)

277) 278)

279) 280)

281) 282)

Выяснить, правильны ли следующие умозаключения:

283) 284)

285) 286)

287) 288)

289) 290)

291) 292)

§3.АНАЛИЗ И СИНТЕЗ РЕЛЕЙНО-КОНТАКТНЫХ СХЕМ.

Составить схемы, реализующие следующие функции:

293) 294) 295)

296) 297)

298)

X

Y

Z

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

299) Имеется одна лампа в лестничном пролёте двухэтажного дома. Построить схему так, чтобы на каждом этаже своим выключателем можно было гасить и зажигать лампу независимо от положения другого выключателя.

300) По установленному сигналу каждый игрок замыкает или размыкает выключатель, находящийся под своим управлением. Если оба делают одно и тоже, то выигрывает А, в противном случае — В. Построить схему так, чтобы в случае выигрыша А зажигалась лампочка.

301) Комитет из 5 человек принимает решения большинством голосов, председатель пользуется правом ”вето”. Построить схему, чтобы голосование происходило нажатием кнопок и в случае принятия решения загоралась лампочка.

302) Построить схему, управляющую спуском лифта со второго этажа на первый. Условия, определяющие работу лифта, следующие:

дверь лифта на первом этаже закрыта,

дверь лифта на втором этаже закрыта,

пассажир находится в кабине лифта,

кнопка вызова на первом этаже нажата,

кнопка спуска на первый этаж в кабине нажата.

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




II .ПРЕДИКАТЫ И КВАНТОРЫ.

§1. П РИМЕРЫ ПРЕДИКАТОВ. ОБЛАСТЬ ИСТИННОСТИ ПРЕДИКАТА. КВАНТОРЫ. СВОБОДНЫЕ И СВЯЗАННЫЕ ПЕРЕМЕННЫЕ.

310) Какие из следующих предложений являютсе предикатами?

1) х делится на 3.

2) х делится на 5.

3)

4)

5)

6)

7)

8)

9) Для всякого найдётся такой, что .

10)

311) Какие из предикатов п.310 тождественно истинны, тождественно ложны, выполнимы?

312) Выделить свободные переменные следующих предикатов:

1)

2)

3)

4)

5)

313) Из предикатов примера 310 образовать с помощью кванторов высказывания, найти их значения истинности.

§ 2. ОСНОВНЫЕ РАВНОСИЛЬНОСТИ, СОДЕРЖАЩИЕ КВАНТОРЫ. ПРИМЕНЕНИЕ АЛГЕБРЫ ПРЕДИКАТОВ К АНАЛИЗУ МАТЕМАТИЧЕСКИХ УТВЕРЖДЕНИЙ.

314) Доказать следующие равносильности:

1)

2)

3)

4)

5)

6)

7)

8)

9)

315) Ввести необходимые предикаты и с помощью кванторов записать следующие определения, с помощью законов де Моргана получить их отрицания:

1) Определение предела часовой последовательности.

2) Определение фундаментальной по Коши последовательности.

3) Определение предела функции в точке.

4) Определение непрерывности функции в точке.

5) Определение непрерывной на интервале функции.

6) Определение равномерно непрерывной на интервале функции.

Почему из равномерной непрерывности на ( a, b) следует непрерывность функции (a, b )?

316) Доказать, что существуют предикаты Ф и Р такие, что:

1)

2)

3)

317) Какие из следующих формул тождественно истины?

1)

2)

3)

4)

5)

РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА

1. Новиков П.С. Элементы математической логики. Наука. М., 1973.

2. Гиндикин С.Г. Алгебра логики в задачах. Наука. М., 1972.

3. Гохман А.В., Спивак М.А., Житомирский Г.И. и др. Сборник задач по математической

логике и алгебре множеств. Изд. Саратовского университета. 1965.

4. Гаврилов В.П., Сапоженко А.А. Сборник задач по дискретной математике. Наука.М., 1977.

5. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике теории

алгоритмов. Наука. М., 1975.

еще рефераты
Еще работы по остальным рефератам