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

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

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

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

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

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

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

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

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

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

1980

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

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

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

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

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

Отрицание

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

0

1

0

0

0

0

1

1

1

0

0

1

1

0

1

0

1

0

1

0

0

0

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

0

0

0

0

0

1

0

0

1

1

1

1

0

1

0

1

0

0

0

1

1

0

1

0

1

0

0

1

0

1

1

0

1

0

1

1

1

1

0

0

0

0

1

1

1

0

0

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.