Г. И. Анкудинов - Математическая логика и теория алгоритмов
Название: | Математическая логика и теория алгоритмов | |
Автор: | Г. И. Анкудинов | |
Жанр: | Учебники и самоучители по компьютеру | |
Изадано в серии: | неизвестно | |
Издательство: | неизвестно | |
Год издания: | - | |
ISBN: | неизвестно | |
Отзывы: | Комментировать | |
Рейтинг: | ||
Поделись книгой с друзьями! Помощь сайту: донат на оплату сервера |
Краткое содержание книги "Математическая логика и теория алгоритмов"
Читаем онлайн "Математическая логика и теория алгоритмов". Главная страница.
- 1
- 2
- 3
- . . .
- последняя (10) »
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
Государственное образовательное учреждение
высшего профессионального образования
СЕВЕРО-ЗАПАДНЫЙ ГОСУДАРСТВЕННЫЙ ЗАОЧНЫЙ
ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
Г.И.Анкудинов
И.Г.Анкудинов
О.А.Петухов
МАТЕМАТИЧЕСКАЯ
ЛОГИКА И ТЕОРИЯ
АЛГОРИТМОВ
Утверждено редакционно-издательским советом университета
в качестве учебного пособия
ИЗДАНИЕ ВТОРОЕ
Санкт-Петербург
2003
85
УДК 512
Анкудинов
Г.И.,
Анкудинов
И.Г.,
Петухов
О.А.
Математическая логика и теория алгоритмов: Учеб. пособие.–
2-е изд. − СПб.: СЗТУ, 2003, 104 c.
Учебное пособие соответствует государственному образовательному
стандарту дисциплины “Математическая логика и теория алгоритмов”
направления подготовки дипломированных специалистов 654600 –
“Информатика и вычислительная техника” (Специальность 220100 –
“Вычислительные машины, комплексы, системы и сети”) и направления
подготовки бакалавров 552800 – “Информатика и вычислительная техника”.
В пособии излагаются разделы математической логики и теории
алгоритмов, необходимые для освоения общепрофессиональных и
специальных дисциплин специальности 220100. Достаточно подробно
изложены основы логики высказываний и логики предикатов, включая
приложение логики предикатов к доказательству правильности алгоритмов.
Пособие содержит вводный материал по логическому программированию и
клаузальной логике, а также основные понятия нечеткой и модальной логики.
Приведены основы теории алгоритмов и алгоритмической разрешимости,
доказательство эквивалентности моделей алгоритмов Тьюринга и рекурсивных
схем Клини. Пособие содержит также введение в теорию эффективной
вычислимости, переборных NP-полных и NP-трудных задач.
Во втором издании исправлены опечатки и неточности.
Рецензенты:
кафедра процессов управления и информационных систем СевероЗападного
государственного
заочного
технического
университета
(зав.кафедрой О.И.Золотов, канд.техн.наук, доц., А.Б.Шадрин, д-р техн.наук,
проф.);
В.В.Лохмотко, д-р техн.наук, проф., М.О.Колбанев, канд.техн.наук, доц.
(кафедра
информационных
управляющих
систем
Государственного
университета телекоммуникаций им. проф. М.А.Бонч-Бруевича).
© Северо-Западный государственный заочный технический университет, 2003
© Анкудинов Г.И., Анкудинов И.Г., Петухов О.А., 2003
86
Глава 1
ЛОГИКА ВЫСКАЗЫВАНИЙ
В основе стандартной (классической) логики лежит логика
высказываний (пропозициональная логика) и логика предикатов.
Высказывание это повествовательное предложение, в отношении
которого имеет смысл утверждение об его истинности или
ложности. Пример истинного высказывания: "Земля вращается
вокруг Солнца". Предикат это повествовательное предложение,
содержащее предметные (индивидные переменные), замена которых
на константные значения превращает рассматриваемое предложение
в высказывание – истинное или ложное.
1.1. Логические операции над высказываниями
Высказывание – это повествовательное предложение,
утверждающее что-то о чем-либо, причем высказывание может быть
истинным либо ложным. Высказывания могут быть простыми и
составными. Составные высказывания образуются из простых с
помощью связок НЕ, И, ИЛИ, ЕСЛИ-ТО, ТОГДА-И-ТОЛЬКОТОГДА.
В алгебре высказываний все высказывания рассматриваются с
точки зрения их логического значения или истинности. Считается,
что каждое высказывание либо истинно (И), либо ложно (Л).
Высказывание не может быть одновременно истинным и ложным.
Будем обозначать высказывания простыми латинскими буквами
A,B,C,.... Составные высказывания образуются из простых с
помощью логических операций над высказываниями. Перечислим
основные логические операции:
• отрицание,
• конъюнкция,
• дизъюнкция,
• импликация,
• эквивалентность.
87
Отрицание высказывания A образуется с помощью операции
отрицания и в данном тексте будет обозначаться ⎯A или ⎤A (читается:
"неверно, что A" или, короче "не A"). Логическую
Таблица 1.1
функцию,
соответствующую
зависимости
логического значения ⎯A от логического
A
⎯A
значения высказывания A, можно представить с
И
Л
помощью таблицы истинности (табл.1.1): если A
Л
И
истинно, то ⎯A ложно и наоборот.
Конъюнкцией двух высказываний A, B называется --">
Государственное образовательное учреждение
высшего профессионального образования
СЕВЕРО-ЗАПАДНЫЙ ГОСУДАРСТВЕННЫЙ ЗАОЧНЫЙ
ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
Г.И.Анкудинов
И.Г.Анкудинов
О.А.Петухов
МАТЕМАТИЧЕСКАЯ
ЛОГИКА И ТЕОРИЯ
АЛГОРИТМОВ
Утверждено редакционно-издательским советом университета
в качестве учебного пособия
ИЗДАНИЕ ВТОРОЕ
Санкт-Петербург
2003
85
УДК 512
Анкудинов
Г.И.,
Анкудинов
И.Г.,
Петухов
О.А.
Математическая логика и теория алгоритмов: Учеб. пособие.–
2-е изд. − СПб.: СЗТУ, 2003, 104 c.
Учебное пособие соответствует государственному образовательному
стандарту дисциплины “Математическая логика и теория алгоритмов”
направления подготовки дипломированных специалистов 654600 –
“Информатика и вычислительная техника” (Специальность 220100 –
“Вычислительные машины, комплексы, системы и сети”) и направления
подготовки бакалавров 552800 – “Информатика и вычислительная техника”.
В пособии излагаются разделы математической логики и теории
алгоритмов, необходимые для освоения общепрофессиональных и
специальных дисциплин специальности 220100. Достаточно подробно
изложены основы логики высказываний и логики предикатов, включая
приложение логики предикатов к доказательству правильности алгоритмов.
Пособие содержит вводный материал по логическому программированию и
клаузальной логике, а также основные понятия нечеткой и модальной логики.
Приведены основы теории алгоритмов и алгоритмической разрешимости,
доказательство эквивалентности моделей алгоритмов Тьюринга и рекурсивных
схем Клини. Пособие содержит также введение в теорию эффективной
вычислимости, переборных NP-полных и NP-трудных задач.
Во втором издании исправлены опечатки и неточности.
Рецензенты:
кафедра процессов управления и информационных систем СевероЗападного
государственного
заочного
технического
университета
(зав.кафедрой О.И.Золотов, канд.техн.наук, доц., А.Б.Шадрин, д-р техн.наук,
проф.);
В.В.Лохмотко, д-р техн.наук, проф., М.О.Колбанев, канд.техн.наук, доц.
(кафедра
информационных
управляющих
систем
Государственного
университета телекоммуникаций им. проф. М.А.Бонч-Бруевича).
© Северо-Западный государственный заочный технический университет, 2003
© Анкудинов Г.И., Анкудинов И.Г., Петухов О.А., 2003
86
Глава 1
ЛОГИКА ВЫСКАЗЫВАНИЙ
В основе стандартной (классической) логики лежит логика
высказываний (пропозициональная логика) и логика предикатов.
Высказывание это повествовательное предложение, в отношении
которого имеет смысл утверждение об его истинности или
ложности. Пример истинного высказывания: "Земля вращается
вокруг Солнца". Предикат это повествовательное предложение,
содержащее предметные (индивидные переменные), замена которых
на константные значения превращает рассматриваемое предложение
в высказывание – истинное или ложное.
1.1. Логические операции над высказываниями
Высказывание – это повествовательное предложение,
утверждающее что-то о чем-либо, причем высказывание может быть
истинным либо ложным. Высказывания могут быть простыми и
составными. Составные высказывания образуются из простых с
помощью связок НЕ, И, ИЛИ, ЕСЛИ-ТО, ТОГДА-И-ТОЛЬКОТОГДА.
В алгебре высказываний все высказывания рассматриваются с
точки зрения их логического значения или истинности. Считается,
что каждое высказывание либо истинно (И), либо ложно (Л).
Высказывание не может быть одновременно истинным и ложным.
Будем обозначать высказывания простыми латинскими буквами
A,B,C,.... Составные высказывания образуются из простых с
помощью логических операций над высказываниями. Перечислим
основные логические операции:
• отрицание,
• конъюнкция,
• дизъюнкция,
• импликация,
• эквивалентность.
87
Отрицание высказывания A образуется с помощью операции
отрицания и в данном тексте будет обозначаться ⎯A или ⎤A (читается:
"неверно, что A" или, короче "не A"). Логическую
Таблица 1.1
функцию,
соответствующую
зависимости
логического значения ⎯A от логического
A
⎯A
значения высказывания A, можно представить с
И
Л
помощью таблицы истинности (табл.1.1): если A
Л
И
истинно, то ⎯A ложно и наоборот.
Конъюнкцией двух высказываний A, B называется --">
- 1
- 2
- 3
- . . .
- последняя (10) »