Читать онлайн «Математическая логика. Курс лекций и практических занятий»

С. Д. Шапарев МАТЕМАТИЧЕСКАЯ ЛОГИКА КУРС ЛЕКЦИЙ И ПРАКТИЧЕСКИХ ЗАНЯТИЙ Алгебра и исчисление высказываний Логика и исчисление предикатив Рекурсивнь е функции и машины Тьюринга 400 задач в решениями и ответами А УЧЕБНОЕ ПОСОБИЕ <*&" С. Д. Шапорев МАТЕМАТИЧЕСКАЯ ЛОГИКА КУРС ЛЕКЦИЙ И ПРАКТИЧЕСКИХ ЗАНЯТИЙ УДК 681. 3. 06+519. 6(075. 8) ББК 32. 973я73 Ш24 Шапорев С. Д. Ш24 Математическая логика. Курс лекций и практических занятий. — СПб. : БХВ-Петербург, 2005. - 416 с: ил. ISBN 5-94157-702-8 В учебном пособии представлены разделы, традиционно изучаемые в курсе математической логики: алгебра логики и исчисление высказываний, логика и исчисление предикатов, рассмотрены вопросы содержательного и формального определения логики высказываний и логики предикатов. Дается введение в теорию алгоритмов и вычислимых функций. Содержание разделов книги взаимно связано друг с другом и снабжено большим количеством примеров и решенных задач, помогающих усвоить и закрепить излагаемый материал. Для студентов, аспирантов и преподавателей технических вузов УДК 681. 3. 06+519. 6(075. 8) ББК 32. 973я73 Рецензенты: Попов М. С. — доктор технических наук, профессор, заведующий кафедрой высшей математики Балтийского государственного технического университета "Военмех" (БГТУ) Дегтярев В. Г. — доктор технических наук, профессор, заведующий кафедрой высшей математики Петербургского государственного университета путей сообщения (ПГУПС) Группа подготовки издания: Главный редактор Екатерина Кондукова Зам. гл. редактора Людмила Еремеевская Зав. редакцией Григорий Добин Редактор Наталья Довгулевич Компьютерная верстка Натальи Караваевой Корректор Виктория Пиотровская Дизайн обложки Игоря Цырульникова Зав. производством Николай Тверских Лицензия ИД № 02429 от 24. 07. 00. Подписано в печать 27. 09. 05. Формат 70х10071в. Печать офсетная. Усл. печ. я. 33,54, Тираж 3000 экз. Заказ № 4306 "БХВ-Петербург", 194354, Санкт-Петербург, ул. Есенина, 5Б. Санитарно-эпидемиологическое заключение на продукцию No 77. 99. 02. 953. Д. 006421. 11. 04 от 11Л1. 2004 г. выдано Федеральной службой по надзору в сфере защиты прав потребителей и благополучия человека. Отпечатано с готовых диапозитивов в ГУП "Типография "Наука" 199034, Санкт-Петербург, 9 линия, 12 ISBN 5-94157-702-8 с Шапорев С. Д. , 2005 С Оформление, издательство "БХВ-ПетепбУПГ". 2005 Оглавление ЧАСТЬ I. МАТЕМАТИЧЕСКАЯ ЛОГИКА 1 Глава 1. Алгебра логики (алгебра высказываний) 3 1. 1. Введение 3 1. 2. Операции над высказываниями 5 1. 3. Формулы алгебры логики 9 1. 4. Равносильные группы формул и равносильные преобразования 11 1. 5. Практическое занятие № 1. Алгебра высказываний 16 1. 6. Алгебра Буля 20 1. 7. Функции алгебры логики 23 1. 8. Разложение булевых функций по переменным 25 1. 9. Дизъюнктивная и конъюнктивная нормальные формы 28 1. 10. Закон двойственности 32 1. 11. Практическое занятие № 2. Функции алгебры логики. Закон двойственности 34 1. 12. Минимизация булевых функций в классе ДНФ 37 Карты Карно 37 1. 13. Проблема разрешимости 42 1. 14. Полиномы Жегалкина 45 115.