О.В. Собенина
Математическая логика и теория алгоритмов
Учебное пособие
Воронеж 2011
ФГБОУВПО «Воронежский государственный технический университет»
О.В. Собенина
МАТЕМАТИЧЕСКАЯ ЛОГИКА
И ТЕОРИЯ АЛГОРИТМОВ
Утверждено Редакционно-издательским советом университета
в качестве учебного пособия
Воронеж 2011
УДК 519.1
Собенина О.В. Математическая логика и теория алгоритмов: учеб. пособие / О.В.Собенина. Воронеж: ФГБОУВПО «Воронежский государственный технический университет», 2011. 148 с.
В учебном пособии излагаются основы современной математической логики и теории алгоритмов: логика и исчисление высказываний, логика и исчисление предикатов, теория алгоритмов и неклассические логики. Каждый раздел иллюстрирован примерами, содержит задачи и упражнения для развития навыков решения основных типов задач.
Издание соответствует требованиям Федерального государственного образовательного стандарта высшего профессионального образования по направлению 230100.62 «Информатика и вычислительная техника» профиля «Системы автоматизированного проектирования в машиностроении», дисциплине «Математическая логика и теория алгоритмов».
Предназначено для студентов всех форм обучения.
Учебное пособие подготовлено в электронном виде в текстовом редакторе Word и содержится в файле «logik.doc».
Табл. 7. Ил. 9. Библиогр.: 9 назв.
-
Рецензенты:
кафедра вычислительной математики и прикладных информационных технологий Воронежского государственного университета, (зав. кафедрой д-р техн. наук, проф. Т.М. Леденева);
канд. физ.-мат. наук, доц. В.Н. Дурова
Собенина О.В., 2011
Оформление. ФГБОУ ВПО
«Воронежский государственный
технический университет», 2011
ВВЕДЕНИЕ
Родоначальником науки о логике является греческий философ Аристотель (384-322 г. до н. э.). Он, используя законы человеческого мышления, формализовал известные до него правила рассуждений. Лишь в конце XVII века немецкий математик Г. Лейбниц предложил математизировать формальные рассуждения Аристотеля, вводя символьное обозначение для основных понятий и используя особые правила, близкие к вычислениям. Лейбниц утверждал, что «мы употребляем знаки не только для того, чтобы передать наши мысли другим лицам, но и для того, чтобы облегчить сам процесс нашего мышления».
Применение математики в логике определило новую науку – математическую логику. Математическое описание рассуждений позволило получить точные утверждения и эффективные процедуры в решении конкретных задач логики. Рассуждения в математической логике изучаются с точки зрения формы описания процесса, явления или события и формального преобразования этого описания. Такой процесс называют выводом заключения. Иногда математическое описание рассуждений называют логико-математическим моделированием.
Основными объектами при изучении математической логики являются формальный язык логики и правила вывода. Формальный язык необходим для символьного описания процессов, явлений или событий и логических связей между ними. Правила вывода необходимы для формирования процедуры рассуждения. Для обеспечения вывода вводится система аксиом, формализующая весь механизм вывода заключения.
Математическое описание логики следует воспринимать, как некую формальную систему, оперирующую с символами по определенным правилам, облегчающим интерпретацию в реальном мире.
Выделяют несколько типов математических моделей формальной логики. Среди них можно выделить логику высказываний, логику предикатов, логику нечетких множеств и другие.
Логика высказываний (prepositional calculus) есть модель формальной системы, предметом которой являются высказывания или повествовательные предложения, взятые целиком без учета их внутренней структуры.
Логика предикатов (predicate calculus) есть модель формальной системы, предметом которой являются повествовательные предложения с учетом их внутренних состава и структуры.
Логика нечетких множеств и отношений (fuzzi calculus) есть модель формальной системы, предметом которой являются повествовательные предложения с учетом их внутренних состава и структуры и при нечетком (размытом) задании характерных признаков отдельных элементов или отношений между ними.
Математическая логика рассматривает формальный способ рассуждения, встречающийся не только в математике, но и в повседневной жизни.
Теория алгоритмов – раздел математики, изучающий общие свойства алгоритмов. Содержательные явления, приведшие к образованию понятия алгоритма, прослеживаются в математике в течение всего времени ее существования. Однако само это понятие сформировалось лишь в двадцатом веке в связи с вопросами о границах вычислимости.
Бурное развитие математической логики и теории алгоритмов во многом обусловлено прогрессом компьютерной техники, необходимостью создания средств обработки и передачи информации, а также представление моделей на компьютерах.