Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364141
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62791)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21320)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21692)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8693)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3462)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20644)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

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

Название: Задачи и упражнения по математической логике и теории множеств. Часть математическая логика
Раздел: Остальные рефераты
Тип: учебное пособие Добавлен 04:09:28 07 сентября 2011 Похожие работы
Просмотров: 95 Комментариев: 0 Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать

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

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

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

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

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

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

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

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

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

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

1980

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

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.

Оценить/Добавить комментарий
Имя
Оценка

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

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

Да, в любом случае.
Да, но только в случае крайней необходимости.
Возможно, в зависимости от цены.
Нет, напишу его сам.
Нет, забью.



Результаты(222409)
Комментарии (3004)
Copyright © 2005-2019 BestReferat.ru bestreferat@gmail.com реклама на сайте

Рейтинг@Mail.ru