Читать онлайн «Математическая логика и теория алгоритмов: Учебное пособие»

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ Государственное образовательное учреждение высшего профессионального образования «ОРЕНБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ» Кафедра информатики В. А. СТЕНЮШКИНА МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ Рекомендовано Ученым советом Государственного образовательного учрежде- ния высшего профессионального образования «Оренбургский государственный университет»в качестве учебного пособия для студентов экономических и есте- ственнонаучных специальностей Оренбург 2004  ББК 22. 12я7 С 79 УДК [510. 5+510. 6](075. 8) Рецензент кандидат технических наук, доцент Ю. Н. Пивоваров Стенюшкина В. А. C 79 Математическая логика и теория алгоритмов: Учебное пособие. - Оренбург: ГОУ ОГУ, 2004. – 106 с. ISBN Пособие предназначено студентам экономических и естественнонауч- ных специальностей для выработки конструктивных знаний в области фо- рмальной логики и алгоритмизации ББК 22. 12я7 ISBN © Стенюшкина В. А. , 2004 © ГОУ ОГУ, 2004  ЧАСТЬ 1 МАТЕМАТИЧЕСКАЯ ЛОГИКА Введение Математическая логика – естественнонаучная дисциплина, изучающая математические доказательства и вопросы оснований математики. Логика как искусство рассуждений зародилась в глубокой древности. Начало формальной логики как науки о структуре суждений и умозаключений связано с именем Аристотеля (IV в. до н. э. ). Дедуктивные умозаключения, в которых из двух суждений следует новое суждение – силлогизмы – были про- ведены Аристотелем на категорических суждениях – суждениях типа: А – общеутвердительное суждение «Всякое S суть Р»; Е – общеотрицательное суждение «Никакое S не суть Р»; I – частноутвердительное суждение «Некоторые S суть Р»; О – частноотрицательное суждение «Некоторые S не суть Р». Пример «первой фигуры» силлогизма: «Все люди смертны. Кай – чело- век. Следовательно, Кай смертен. » Первый этап развития формальной логики – традиционная логика – дли- лся два тысячелетия. Второй этап – современная логика - длится поныне. Дру- гие имена этого этапа – символическая логика или математическая логика. Ос- новы современной формальной логики заложили (середина XIX – начало XXв. в. ) Дж. Буль, О. Морган, Г. Фреге, Дж. Пеано. Традиционная логика опиралась на естественный язык, который из-за многозначности и аморфности требований к построению выражений и прида- ния им смысла приводит к парадоксам. В средние века был распространен па- радокс: “Сказанное Платоном – ложно, - говорит Сократ. – Сказанное Сократом – истинно, - говорит Платон”. Современная логика использует формальные те- ории (ФТ), или исчисления.