КАЗАНСКИЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ им. А. Н. Туполева

Ш. И. ГАЛИЕВ

МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ

УЧЕБНОЕ ПОСОБИЕ

Казань 2002

Галиев Ш. И. Математическая логика и теория алгоритмов. – Казань: Издательство КГТУ им. А. Н. Туполева. 2002. - 270 с.

ISBN 5-93629-031-X

Пособие содержит следующие разделы. Логику высказываний и предикатов с приложениями, в том числе метод резолюций и элементы его реализации в языке ПРОЛОГ. Классические исчисления (высказываний и предикатов) и элементы неклассических логик: трёхзначные и многозначные логики, модальную, временную и нечеткую логики. Теорию алгоритмов: нормальные алгоритмы, машины Тьюринга, рекурсивные функции и их взаимосвязи. Понятие о сложности вычислений, различные (по сложности) классы задач и примеры таких задач.

Все главы снабжены контрольными вопросами и упражнениями, приведены варианты типовых заданий и тесты для самоконтроля усвоения материала.

Пособие предназначено студентам технических вузов по специальности 2201 направления «Информатика и вычислительная техника» и может быть использовано для специальности 2202 и других специальностей данного направления.

ВВЕДЕНИЕ

Логика обычно понимается как наука о способах доказательств и опровержений. Математическая логика – это логика, развиваемая с помощью математических методов.

Изучая методы доказательств и опровержений, логика интересуется в первую очередь формой получения истинных выводов, а не содержанием посылок и заключений в том или ином рассуждении. Рассмотрим, например, следующие два вывода:

1. Все люди смертны. Сократ – человек. Следовательно, Сократ – смертен.

2. Все котята любят играть. Мура – котенок. Следовательно, Мура любит играть.

Оба эти вывода имеют одну и ту же форму: Все А сутьВ ;С естьА ; следовательно,С естьВ . Эти выводы верны в силу своей формы, независимо от содержания, независимо от того истинны или ложны взятые по себе посылки и заключения. Систематическая формализация и каталогизация правильных способов рассуждений – одна из основных задач логики. Если при этом применяется математический аппарат и исследования посвящены в первую очередь изучению математических рассуждений, то эта логика является математической логикой (формальной логикой). Данное определение не является строгим (точным) определением. Чтобы понять предмет и метод математической логики лучше всего приняться за ее изучение.

Математическая логика начала формироваться давно. Зарождение ее идей и методов происходило в Древней Греции, Древней Индии и Древнем Китае примерно с VI в. до н. э. Уже в этот период ученые пытались расположить цепь математических доказательств в такую цепочку, чтобы переход от одного звена к другому не оставлял сомнений и завоевал всеобщее признание. Уже в самых ранних дошедших до нас рукописях «канон» математического стиля изложения прочно установлен. Впоследствии он получает окончательное завершение у великих классиков: Аристотеля, Евклида, Архимеда. Понятие доказательства у этих авторов уже ничем не отличается от нашего.

Логика как самостоятельная наука берет свое начало в исследованиях Аристотеля (384 – 322 г. до н. э.). Великий философ древности Аристотель осуществляет энциклопедическую систематизацию античных знаний во всех областях существовавшей тогда науки. Логические исследования Аристотеля изложены, в основном, в двух его трудах «Первая аналитика» и «Вторая аналитика», объединенных под общим названием «Органон» (Орудие познания).

Следует особо отметить большое значение для становления и развития математической логики одного из самых блестящих достижений в истории человечества, а именно, превращение геометрии в точную дедуктивную систему в работе Евклида (330 – 275 г. до н. э.) «Начала». Именно этот дедуктивный подход с ясным осознанием целей и методов был положен в основу развития философской и математической мысли последующих столетий.

Также большое значение для становления и развития логики сыграли достижения в алгебре (алгебра Буля) и в других математических дисциплинах, в том числе и вновь в геометрии (создание неевклидовой геометрии - геометрии Лобачевского – Гаусса – Бойяи). Краткий обзор становления математической логики можно найти в .

В формировании и становлении математической логики участвовали многие и многие ученые, как древних времен, так средневековья и последующих времен.

Принципиальное и прикладное значение математической логики

Принципиальное значение математической логики – обоснование математики (анализ основ математики).

Прикладное значение математической логики в настоящее время очень велико. Математическая логика применяется для следующих целей:

анализа и синтеза (построения) цифровых вычислительных машин и других дискретных автоматов, в том числе и интеллектуальных систем;

анализа и синтеза формальных и машинных языков, для анализа естественного языка;

анализа и формализации интуитивного понятия вычислимости;

выяснения существования механических процедур для решения задач определённого типа;

анализа проблем сложности вычислений.

Также математическая логика оказалась тесно связанной и с рядом вопросов лингвистики, экономики, психологии и философии.

В данном пособии излагаются основные понятия математической логики и теории алгоритмов. Материал, изложенный в пособии,

соответствует государственному образовательному стандарту для направления «Информатика и вычислительная техника» и может быть использован для студентов обучающихся по разным специальностям этого направления.

При написании пособия использовались литература , и, конечно, использованы и другие источники. В перечень литературы включены книги, которые желательно просмотреть любознательному и требовательному студенту.

В пособии в каждой главе приведены вопросы для самопроверки теоретического материала и упражнения, предназначенные для выработки навыков решения задач и углубления знаний по излагаемой теме. Кроме того, в пособии приведены варианты типовых заданий и тесты для самоконтроля усвоения материала.

С. Н. ПОЗДНЯКОВ С. В. РЫБИН

Учебное пособие

Министерство образования и науки РФ

Санкт-Петербургский государственный электротехнический университет „ЛЭТИ“

С. Н. ПОЗДНЯКОВ С. В. РЫБИН

МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ

Санкт-Петербург Издательство СПбГЭТУ „ЛЭТИ“

УДК 510.6 ББК В12 П47

Поздняков С. Н., Рыбин С. В. Математическая логика и теория алго ритмов: Учеб. пособие. СПб.: Изд-во СПбГЭТУ „ЛЭТИ“, 2004. 64 с.

Рассматриваются основные идеи, понятия и методы математической логики, интерес к которым вырос благодаря новым приложениям, появив шимся за последнее время в связи с развитием информационных техноло гий.

Может использоваться как для студентов дневной формы обучения, так и для вечерних и заочных факультетов технических вузов.

Рецензенты: кафедра математического анализа СПбГУ; доц. М. В. Дмитриева (СПбГУ).

Утверждено редакционно-издательским советом университета

в качестве учебного пособия

Математическая логика, как и теория алгоритмов, появились задолго до возникновения компьютеров. Их возникновение было связано с внут ренними проблемами математики, с изучением границ применимости ее теорий и методов.

В настоящее время обе эти (взаимосвязанные между собой) теории получили прикладное развитие в так называемой компьютерной матема тике (computer science). Вот несколько направлений их использования в прикладных областях:

– экспертные системы используют формально-логические выводы для имитации деятельности экспертов в различных областях;

– при проектировании микросхем используется теория булевых функций;

– тестирование программ основано на логическом анализе их структуры;

– доказательство корректности программ базируется на теории логическо го вывода;

– алгоритмические языки связывают два важных понятия логики: поня тие языка и понятие алгоритма;

– автоматизация доказательства теорем основана на методе резолюций, изучаемом в курсе логики.

В данном учебном пособии изложены основные идеи, понятия и мето ды математической логики, лежащие в основе как перечисленных, так и других ее применений.

1. Бинарные отношения и графы

1.1. Введение. Постановка задачи

Бинарные отношения уже встречались в школьном курсе математи ки. Примерами таких отношений являются отношения неравенства, равен ства, подобия, параллельности, делимости и пр. Бинарное отношение каж дым двум объектам сопоставляет логическое значение “да”, если объекты находятся в этом отношении, и “нет” в ином случае. Другими словами, множество пар объектов разбивается на два подмножества, пары первого подмножества находятся в данном отношении, а второго – не находятся. Это свойство можно положить в основу определения бинарного отношения.

Определение 1.1. Пусть задано множествоM . Рассмотрим декар тово произведение этого множества на себяM × M . ПодмножествоR множестваM ×M называется бинарным отношениемR на множествеM . Если пара(x; y) принадлежит множествуR , говорят, что элементx находится в отношенииR с элементомy , и записываютxRy .

Пример 1.1. Введем отношение сравнимостиR :x сравнимо сy по модулюm тогда и только тогда, когдаx иy имеют одинаковые остатки от деления наm . То естьx ≡ y (mod m) .

Рассмотрим введенное отношение R для случаяm = 3 на множе ствеM = {1; 2; 3; 4; 5; 6} , тогда

Отношение R определяется множеством таких пар:

Пример 1.2. Рассмотрим в качествеM = R – множество веще

ственных чисел, или, иными словами, множество точек вещественной прямой. Тогда M × M = R 2 – множество точек координатной плос кости. Отношение неравенства< определяется множеством парR = = {(x; y)|x < y} .

Упражнение 1.1.

1. На множестве вещественных чисел задано отношение: xRy то

гда и только тогда, когда одно из чисел вдвое больше другого. Изобразить на плоскости множество точек, определяющее это отношение.

2. На множестве M = {1; 2; 3; 4; 5; 6} задано отношение делимости:xRy тогда и только тогда, когдаx делится наy . Сколько пар содержит

это отношение? Перечислите эти пары.

3. Введем на множестве M = {1; 2; 3; 4; 5; 6} отношение взаимной простоты, т. е.xRy тогда и только тогда, когдаx иy взаимно просты:D(x; y) = 1 . Сколько пар содержит это отношение? Перечислите эти

1.2. Свойства бинарных отношений

Определение 1.2. Бинарное отношениеR на множествеM называ

ется рефлексивным, если каждый элемент этого множества находится в отношении с самим собой: xRx x M .

Пример 1.3.

1. Отношение сравнимости рефлексивно (при любом натуральном m и на любом множестве целых чисел).

2. Отношение строгого неравенства на множестве вещественных чисел не рефлексивно.

3. Отношение делимости рефлексивно (на любом множестве целых чисел, не содержащем нуля).

Определение 1.3. Бинарное отношениеR на множествеM назы

вается антирефлексивным, если ни один элемент этого множества не находится в отношении с самим собой: x M неверно, чтоxRx .

Пример 1.4.

1. Отношение строгого неравенства на множестве вещественных чисел антирефлексивно.

2. Отношение взаимной простоты антирефлексивно на любом мно жестве целых чисел, не содержащем 1 и−1 , рефлексивно на множествах{1}, {−1} ,{−1; 1} и не является ни рефлексивным, ни антирефлексивным

в ином случае.

Определение 1.4. Бинарное отношениеR на множествеM назы вается симметричным, если вместе с каждой парой(x; y) в отношение входит и симметричная пара(y; x) :x, y M xRy yRx .

Пример 1.5.

1. Отношение сравнимости симметрично при любом натуральном

2. Отношение строгого неравенства на множестве вещественных чисел не симметрично.

3. Отношение делимости симметрично только на множестве по парно взаимно простых целых чисел, не содержащем единицу. Например, на множестве простых чисел.

4. Отношение взаимной простоты симметрично на любом множе стве целых чисел.

Определение 1.5. Бинарное отношениеR на множествеM называ

ется асимметричным, если ни одна пара не входит в отношение вместе с симметричной ей: x, y M , еслиxRy , то неверно, чтоyRx .

Пример 1.6.

1. Отношение строгого неравенства на множестве вещественных чисел асимметрично.

2. Отношение делимости не является асимметричным ни на каком множестве целых чисел, не содержащем нуля.

Определение 1.6. Бинарное отношениеR на множествеM называ

ется антисимметричным, если никакая пара, состоящая из разных эле ментов, не входит в отношение вместе с симметричной ей: x, y M , еслиxRy иyRx тоx = y .

Пример 1.7.

1. Отношение нестрогого неравенства на множестве веществен ных чисел антисимметрично.

2. Отношение делимости является антисимметричным на любом множестве целых чисел, не содержащем нуля.

Упражнение 1.2.

1. Верно ли, что асимметричное отношение всегда антирефлексив но? Докажите.

2. Верно ли, что симметричное отношение всегда рефлексивно? До кажите.

3. Верно ли, что асимметричное отношение всегда антисиммет рично? Докажите.

4. Верно ли, что отношение асимметрично тогда и только тогда, когда оно антирефлексивно и антисимметрично? Докажите.

Определение 1.7. Бинарное отношениеR на вается транзитивным, если вместе с парами(x; y) входит и пара(x, z) , т. е.x, y, x M , еслиxRy и

множестве M назы и(y; z) в отношениеyRz , тоxRz .

Замечание 1.1. Свойство транзитивности хорошо иллюстрирует ся отношением достижимости: если пунктy достижим из пунктаx , а из пунктz – из пунктаy , то пунктz достижим из пунктаx .

Пример 1.8.

1. Отношение сравнимости транзитивно при любом натуральном m и на любом множестве целых чисел.

2. Отношение строгого (нестрогого) неравенства транзитивно на любом подмножестве вещественных чисел.

3. Отношение делимости транзитивно на множестве целых чисел, не содержащем нуля.

4. Отношение взаимной простоты не является транзитивным на любом множестве целых чисел. Например, 2 взаимно просто с3 ,3 вза имно просто с4 , но2 и4 не взаимно просты.

Упражнение 1.3. Верно ли, что транзитивное и симметричное

отношение всегда рефлексивно? Докажите.

1.3. Способы задания отношений

Кроме явного перечисления пар, определяющих бинарное отношение, возможны следующие способы задания отношений.

Задание процедурой проверки.

Пример 1.9.

1. Oтношение взаимной простоты проверяется процедурой нахождения наибольшего общего делителя: если D(x; y) = 1 , то(x; y) входит в

отношение взаимной простоты.

2. Oтношение делимости проверяется процедурой деления с остат ком: если x ≡ 0 (mod y) , то(x; y) входит в отношение делимости.

3. Той же процедурой проверяется отношение равенства остатков при делении на m : если(x−y)≡0 (mod m) , то(x; y) входит в отношение.

Для отношений на конечных множествах (которые являются основны ми для дискретной математики) используются также следующие способы задания и описания отношений.

Задание матрицей смежностей. Определим матрицу A размера

|M | × |M |, где |M | – количество элементов множества M . Пронумеруем элементы множества M . Тогда aij = 1, если элемент с номерoм i находится в отношении с элементом с номером j (iRj) и aij = 0 иначе.

Пример 1.10. Матрица смежностей для отношения делимости на множествеM = {1; 2; 3; 4; 5; 6} выглядит так:

Задание графом. Элементы множества изображаются точками плоскости и образуют множество вершин графа. Отношениe изображаются дугами (ребрами) графа: если (x; y) входит в отношение, то из вершины x проводится ориентированная дуга в y.

Пример 1.11. Граф для отношения сравнимости по модулю три на

Задание списком смежностей. Для каждого элемента множества перечисляются элементы, находящиеся с ним в данном отношении.

Пример 1.12. Список смежностей для отношения взаимной про стоты на множествеM = {1; 2; 3; 4; 5; 6} выглядит так:

Дадим интерпретацию свойств бинарных отношений на описывающих их графах и матрицах.

Теорема 1.1. Справедливы следующие утверждения.

1. Диагональ матрицы смежностей рефлексивного отношения со стоит из единиц.

2. У симметричного отношения матрица смежностей симметрич

3. Граф рефлексивного отношения имеет петли в каждой вершине.

4. Граф симметричного отношения вместе с дугой, соединяющей x

с y , содержит дугу, соединяющуюy сx .

5. Граф транзитивного отношения обладает следующим свойством: если из вершины x , двигаясь вдоль дуг, можно попасть в вершинуy , то в графе должна быть дуга, непосредственно соединяющаяx сy .

Замечание 1.2. Для симметричных

петли обычно не изображаются, а пары ориентированных дуг, соединяющих дан ные вершины, заменяются одной – неори ентированной – дугой.

Например, граф из примера 1.11 бу дет выглядеть так, как показано на рис. 1.2.

и рефлексивных отношений

Упражнение 1.4.

1. Опишите свойства матрицы смежностей: a)антирефлексивного отношения; б) асимметричного отношения; в) антисимметричного от ношения; г) транзитивного отношения.

2. Oпишите свойства графа: а) антирефлексивного отношения; б) асимметричного отношения; в) антисимметричного отношения.

1.4. Отношение эквивалентности

Определение 1.8. Бинарное отношение, обладающее свойствами ре

флексивности, симметричности и транзитивности, называется отно шением эквивалентности.

Пример 1.13. Отношение сравнимости (по любому модулю) явля

ется отношением эквивалентности.

Сопоставим каждому элементу множества M все элементы, находя щиеся с ним в данном отношении эквивалентности: Mx = {y M | xRy}. Справедлива следующая теорема.

Теорема 1.2. МножестваM x иM y либо не пересекаются, либо сов

Доказательство. Все элементы одного класса эквивалентны между собой, т. е. если x, y Mz , то xRy. Действительно, пусть x, y Mz , следо вательно xRz и yRz. По симметричности отношения R имеем zRy. Тогда, в силу транзитивности, из xRz и zRy получаем xRy.

Федеральное агентство по образованию

ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)

Кафедра автоматизации обработки информации

Утверждаю:

Зав. каф. АОИ

профессор

Ю.П. Ехлаков

«__» _____________2007 г.

Методические указания

к выполнению практических работ по дисциплине

«Математическая логика и теория алгоритмов»

для студентов специальности 230102 –

«Автоматизированные системы обработки информации и управления»

Разработчики:

ст. преподаватель каф. АОИ

Т.О. Перемитина

Томск – 2007

Практическое занятие № 1 «Формулы алгебры высказываний» 3

Практическое занятие № 2 «Равносильные преобразования формул алгебры высказываний» 10

Практическое занятие № 3 «Нормальные формы формул» 12

Практическое занятие № 4 «Логические рассуждения» 14

Практическое занятие № 5 «Формулы логики предикатов» 18

Практическое занятие № 6 «Булевы функции» 23

Практическое занятие № 7 «Частично рекурсивные функции» 28

Практическое занятие № 8 «Машины Тьюринга» 34

Практическое занятие № 1 «Формулы алгебры высказываний»

Учение о высказываниях – алгебра высказываний, или алгебра логики, – является простейшей логической теорией. Атомарным понятием алгебры высказываний является высказывание – повествовательное предложение, в отношении которого имеет смысл утверждение об его истинности или ложности.

Пример истинного высказывания: "Земля вращается вокруг Солнца". Пример ложного высказывания: "3 > 5". Не всякое предложение является высказыванием, к высказываниям не относятся вопросительные и восклицательные предложения. Не является высказыванием предложение: «Каша – вкусное блюдо», так как не может быть единого мнения о том, истинно оно или ложно. Предложение «Есть жизнь на Марсе» следует считать высказыванием, так как объективно оно либо истинно, либо ложно, хотя никто пока не знает, какое именно.

Поскольку предметом изучения логики являются только значения истинности высказываний, для них вводят буквенные обозначения A, B, … или X,Y...

Считается, что каждое высказывание либо истинно, либо ложно. Для краткости, будем вместо значения истинно писать 1, а вместо значения ложно – 0. Например, X= "Земля вращается вокруг Солнца" иY= "3 > 5", причемX=1 иY= 0. Высказывание не может быть одновременно истинным и ложным.

Высказывания могут быть простыми и составными. Высказывания "Земля вращается вокруг Солнца" и "3 > 5" являются простыми. Составные высказывания образуются из простых с помощью связок естественного (русского) языка НЕ, И, ИЛИ, ЕСЛИ-ТО, ТОГДА-И-ТОЛЬКО-ТОГДА. При использовании буквенных обозначений для высказываний эти связки заменяются специальными математическими символами, которые можно рассматривать как символы логических операций.

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

Отрицанием (инверсией) высказыванияX называется высказывание, истинное тогда и только тогда, когдаX ложно (обозначаетсяили, читается “неX ” или “неверно, чтоX ”).

Конъюнкцией
двух высказываний называется высказывание, истинное тогда и только тогда, когда истинны оба высказыванияX иY . Эта логическая операция соответствует соединению высказываний союзом ”и”.

Дизъюнкцией
двух высказыванийX иY называется высказывание ложное в том и только в том случае, когда оба высказыванияX иY ложны. В разговорной речи этой логической операции соответствует союз “или” (не исключающее “или”).

Импликацией двух высказыванийX и Y называется высказывание, ложное тогда и только тогда, когдаX истинно, аY – ложно (обозначается
; читается “X влечетY ”, “еслиX , тоY ”). Операнды этой операции имеют специальные названия:X – посылка,Y – заключение.

Эквиваленцией двух высказыванийX иY называется высказывание, истинное тогда и только тогда, когда истинностные значенияX иY одинаковы (обозначение:
).

Таблица 1. Логические операции

Операнды логических операций могут принимать только два значения: 1 или 0. Поэтому каждую логическую операцию , &,,,легко задать с помощью таблицы, указав значение результата операции в зависимости от значений операндов. Такая таблица называется таблицей истинности (табл. 2).

Таблица 2. Таблица истинности логических операций

С помощью логических операций, определенных выше, можно из простых высказываний строить формулы логики высказываний , представляющие различные составные высказывания. Логическое значение составного высказывания зависит от структуры высказывания, выраженной формулой, и логических значений образующих его элементарных высказываний.

Для систематического изучения формул, выражающих высказывания, вводят переменные высказывания P, P 1 , P 2 , ..., P N , принимающие значения из множества {0, 1}.

Формула логики высказываний F (P 1 , P 2 ,..., P N ) называется тавтологией или тождественно истинной , если ее значение для любых значений P 1 , P 2 ,..., P N есть 1 (истина). Формулы, принимающие значение “истина” хотя бы при одном наборе списка переменных, называются выполнимыми . Формулы, принимающие значение “ложь” при любых значениях переменных, называются противоречиями (тождественно ложными, невыполнимыми).

Книги. Скачать книги DJVU, PDF бесплатно. Бесплатная электронная библиотека
А.К. Гуц, Математическая логика и теория алгоритмов

Вы можете (программа отметит желтым цветом)
Вы можете посмотреть список книг по высшей математике с сортировкой по алфавиту.
Вы можете посмотреть список книг по высшей физике с сортировкой по алфавиту.

• Бесплатно скачать книгу , объем 556 Кб, формат.djvu (совр. уч. пособие)

Уважаемые дамы и господа!! Для того, чтобы без "глюков" скачать файлы электронных публикаций, нажмите на подчеркнутую ссылку с файлом ПРАВОЙ кнопкой мыши , выберите команду "Save target as ..." ("Сохранить объект как..." ) и сохраните файл электронной публикации на локальный компьютер. Электронные публикации обычно представлены в форматах Adobe PDF и DJVU.

I. Логика
1. Классическая логика
1.1. Логика высказываний
1.1.1. Высказывания
1.1.2. Основные законы логики
1.1.3. Логический парадокс Рассела
1.1.4. Алгебра (логика) высказываний
1.1.5. Релейно-контактные схемы
1.1.6. Равносильные формулы
1.1.7. Алгебра Буля
1.1.8. Истинные и общезначимые формулы
1.1.9. Проблема разрешимости
1.1.10. Логическое следствие
1.1.11. Силлогизмы
1.2. Логика предикатов
1.2.1. Предикаты и формулы
1.2.2. Интерпретации
1.2.3. Истинность и выполнимость формул. Модели, общезначимость, логическое следствие
1.2.4. Готлоб Фреге
1.2.5. Сколемовские функции
и сколемизация формул
1.3. Метод резолюций
1.3.1. Метод резолюций в логике высказываний
1.3.2. Метод резолюций в логике предикатов

2. Формальные теории (исчисления)
2.1. Определение формальной теории, или исчисления
2.1.1. Доказательство. Непротиворечивость теории. Полнота теории
2.2. Исчисление высказываний
2.2.1. Язык и правила вывода исчисления высказываний
2.2.2. Пример доказательства теоремы
2.2.3. Полнота и непротиворечивость исчисления высказываний
2.3. Исчисление предикатов
2.3.1. Язык и правила вывода исчисления предикатов
2.3.2. Полнота и непротиворечивость исчисления предикатов
2.4. Формальная арифметика
2.4.1. Эгалитарные теории
2.4.2. Язык и правила вывода формальной арифметики
2.4.3. Непротиворечивость формальной арифметики. Теорема Генцена
2.4.4. Теорема Геделя о неполноте
2.4.5. Курт Гёдель
2.5. Автоматический вывод теорем
2.5.1. С.Ю. Маслов
2.6. Логическое программирование
2.6.1. Логическая программа
2.6.2. Языки логического программирования

3. Неклассические логики
3.1. Интуиционистская логика
3.2. Нечеткая логика
3.2.1. Нечеткие подмножества
3.2.2. Операции над нечеткими подмножествами
3.2.3. Свойства множества нечетких подмножеств
3.2.4. Нечеткая логика высказываний
3.2.5. Нечеткие релейно-контактные схемы
3.3. Модальные логики
3.3.1. Типы модальности
3.3.2. Исчисления 1 и Т (Фейса-фон Вригта)
3.3.3. Исчисления S4, S5 и исчисление Врауэра
3.3.4. Означивание формул
3.3.5. Семантика Крипке
3.3.6. Другие интерпретации модальных знаков
3.4. Георг фон Вригт
3.5. Временные логики
3.5.1. Временная логика Прайора
3.5.2. Временная логика Леммона
3.5.3. Временная логика фон Вригта
3.5.4. Приложение временных логик к программированию
3.5.5. Временная логика Пнуели
3.6. Алгоритмические логики
3.6.1. Принципы построения алгоритмической логики
3.6.2. Чарльз Хоар
3.6.3. Алгоритмическая логика Хоара

II. Алгоритмы
4. Алгоритмы
4.1. Понятие алгоритма и вычислимой функции
4.2. Рекурсивные функции
4.2.1. Примитивно рекурсивные функции
4.2.2. Частично рекурсивные функции
4.2.3. Тезис Чёрча
4.3. Машина Тьюринга-Поста
4.3.1. Вычисления функций на машине Тьюринга-Поста
4.3.2. Примеры вычислений
4.3.3. Тезис Тьюринга
4.3.4. Универсальная машина Тьюринга-Поста
4.4. Алан Тьюринг
4.5. Эмиль Пост
4.6. Эффективные алгоритмы
4.7. Алгоритмически неразрешимые проблемы

5. Сложность алгоритмов
5.1. Понятие о сложности алгоритмов
5.2. Классы задач Р и NP
5.2.1. Класс задач Р
5.2.2. Класс задач NP
5.2.3. Недетерминированная машина Тьюринга
5.3. О понятии сложности
5.3.1. Три типа сложности
5.3.2. Четыре категории чисел по Колмогорову
5.3.3. Тезис Колмогорова
5.4. А.Н. Колмогоров

6. Алгоритмы реальности
6.1. Генератор виртуальной реальности
6.2. Принцип Тьюринга
6.3. Логически возможные среды Кантгоуту

Краткая аннотация книги

Учебное пособие посвящено изложению основ математической логики и теории алгоритмов. Основу пособия составляют конспекты лекций, которые читались студентам второго курса отделения компьютерных наук Омского государственного университета в 2002 году. Для студентов, обучающихся по специальности "Компьютерная безопасность" и по специальности "Вычислительные машины, комплексы, системы и сети".

Чем занимается наука логика. Это теория, которая учит, как нужно правильно рассуждать, правильно делать умозаключения и выводы, получая в результате верные (правильные) высказывания. Поэтому логика как наука должна содержать список правил получения правильных высказываний. Такой набор правил, умозаключений называется списком силлогизмов. Высказывание - это утверждение об изучаемых объектах, имеющее однозначное и точно определенное значение. В русском языке высказывание представляет собой повествовательное предложение, о котором молено сказать, что оно сообщает нам нечто верное либо нечто совершенно неверное. Следовательно, высказывание может быть либо истинным, либо ложным.

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

,
С 2017 года возобновляем мобильную версию веб-сайта для мобильных телефонов (сокращенный текстовый дизайн, технология WAP) - верхняя кнопка в левом верхнем углу веб-страницы. Если у Вас нет доступа в Интернет через персональный компьютер или интернет-терминал, Вы можете воспользоваться Вашим мобильным телефоном для посещения нашего веб-сайта (сокращенный дизайн) и при необходимости сохранить данные с веб-сайта в память Вашего мобильного телефона. Сохраняйте книги и статьи на Ваш мобильный телефон (мобильный интернет) и скачивайте их с Вашего телефона на компьютер. Удобное скачивание книг через мобильный телефон (в память телефона) и на Ваш компьютер через мобильный интерфейс. Быстрый Интернет без излишних тэгов, бесплатно (по цене услуг Интернет) и без паролей. Материал приведен для ознакомления. Прямые ссылки на файлы книг и статей на веб-сайте и их продажи третьими лицами запрещены.

Примечание. Удобная текстовая ссылка для форумов, блогов, цитирования материалов веб-сайта, код html можно скопировать и просто вставить в Ваши веб-страницы при цитировании материалов нашего веб-сайта. Материал приведен для ознакомления. Сохраняйте также книги на Ваш мобильный телефон через сеть Интернет (есть мобильная версия сайта - ссылка вверху слева страницы) и скачивайте их с Вашего телефона на компьютер. Прямые ссылки на файлы книг запрещены.

11.1. Понятие об алгоритме и теории алгоритмов

Интуитивно под алгоритмом понимается процесс последовательного решения задачи, протекающей в дискретном времени так, что в каждый следующий момент времени система объектов алгоритма получается по определённому закону из системы объектов, имевшихся в предыдущий момент времени . Интуитивно потому, что, строго говоря, понятие алгоритма сродни понятию множества, которое неопределимо.

В соответствии с ГОСТ 19781-74 «Машины вычислительные. Программное обеспечение. Термины и определения» алгоритм – это точное предписание, определяющее вычислительный процесс, ведущий от варьируемых начальных данных к искомому результату. При этом предполагается наличие исполнителя алгоритма – такого объекта, который «умеет» выполнять эти действия.

Слово «алгоритм» происходит, как предполагают, от имени среднеазиатского (узбекского) математика XIII века Аль Хорезми (Абу Абдалла Мухаммед ибн Муса ал Хорезми ал Меджуси) – «Algorithmi» в латинской транскрипции, впервые сформулировавшего правила (процедуру) выполнения четырех арифметических действий в десятичной системе счисления.

Пока вычисления были несложными, особой необходимости в алгоритмах не было. Когда появилась потребность в многократных пошаговых процедурах, тогда и появилась теория алгоритмов. Но при еще большем усложнении задач, оказалось, что часть из них невозможно решать алгоритмическим путем. Таковы, например, многие задачи, решаемые «бортовым компьютером» человека – головным мозгом. Решение таких задач основывается на иных принципах – эти принципы использует новая наука – нейроматематика и соответствующие технические средства – нейрокомпьютеры. В этом случае применяются процессы обучения, проб и ошибок – то есть то, чем мы сейчас и занимаемся.

Качество алгоритма определяется его свойствами (характеристиками). К основным свойствам алгоритма относятся :

1. Массовость . Предполагается, что алгоритм может быть пригоден для решения всех задач данного типа. Например, алгоритм для решения системы линейных алгебраических уравнений должен быть применим к системе, состоящей из произвольного числа уравнений.

2. Результативность . Это свойство означает, что алгоритм должен приводить к получению результата за конечное число шагов.

3. Определенность . Предписания, входящие в алгоритм, должны быть точными и понятными. Эта характеристика обеспечивает однозначность результата вычислительного процесса при заданных исходных данных.

4. Дискретность . Это свойство означает, что описываемый алгоритмом процесс и сам алгоритм могут быть разбиты на отдельные элементарные этапы, возможность выполнения которых на ЭВМ у пользователя не вызывает сомнений.

Сегодня на дворе «цифровое тысячелетие» и может создастся впечатление, что алгоритмам подвластны любые задачи. Оказывается, многие задачи не могут быть решены алгоритмически. Это так называемые алгоритмически неразрешимые задачи.

Для доказательства алгоритмической разрешимости или неразрешимости задач необходимы математически строгие и точные средства. В середине 30-х годов прошлого века были предприняты попытки формализовать понятие алгоритма и были предложены различные модели алгоритмов : рекурсивные функции; «машины» – Тьюринга, Поста; нормальные алгорифмы Маркова.

Впоследствии было установлено, что эти и другие модели эквивалентны в том смысле, что классы решаемых ими задач совпадают . Этот факт носит название тезиса Черча. Сейчас это общепризнанно. Формальное определение понятия алгоритма создало предпосылки для разработки теории алгоритма ещё до разработки первых ЭВМ. Прогресс вычислительной техники стимулировал дальнейшее развитие теории алгоритмов. Помимо установления алгоритмической разрешимости задач, теория алгоритмов занимается еще и оценкой сложности алгоритмов в смысле числа шагов (временная сложность) и требуемой памяти (пространственная сложность), а также занимается разработкой эффективных в этом смысле алгоритмов.

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

Поэтому еще одна задача теории алгоритмов – решение вопроса исключения перебора вариантов в комбинаторных алгоритмах. Оценка сложности алгоритмов и создания так называемых эффективных алгоритмов – одна из важнейших задач современной теории алгоритмов.