Книжная полка Сохранить
Размер шрифта:
А
А
А
|  Шрифт:
Arial
Times
|  Интервал:
Стандартный
Средний
Большой
|  Цвет сайта:
Ц
Ц
Ц
Ц
Ц

Математическая логика и теория алгоритмов. Часть I. Математическая логика

Покупка
Новинка
Артикул: 891196.01.99
Доступ онлайн
139 ₽
В корзину
В учебно-методическом пособии изложены основные сведения по математической логике. Учебно-методическое пособие содержит расширенный материал лекций (часть 1 - математическая логика) по дисциплине «Математическая логика и теория алгоритмов», предусмотренных учебным планом и рабочей программой дисциплины. Учебно-методическое пособие предназначено для студентов всех форм обучения направления 09.03.01 «Информатика и вычислительная техника» направленности (профиля) «Автоматизированные системы обработки информации и управления».
40
Математическая логика и теория алгоритмов. Часть I. Математическая логика : учебное пособие / сост. Н. Ю. Шабанова, О. А. Ефремова. - Москва : Директ-Медиа, 2025. - 89 с. - ISBN 978-5-4499-5080-2. - Текст : электронный. - URL: https://znanium.ru/catalog/product/2275865 (дата обращения: 18.11.2026). – Режим доступа: по подписке.
Фрагмент текстового слоя документа размещен для индексирующих роботов
Математическая логика 
и теория алгоритмов 
Часть I 
Математическая логика
Учебно-методическое пособие 
Москва 
2025 


УДК 510.6(075) 
ББК 22.12я73 
М34 
Составители: 
Шабанова Н. Ю., Ефремова О. А. 
Рецензенты: 
Гринюк А. В., канд. техн. наук, 
кафедра информатики и информационной безопасности 
АНО «Международная полицейская академия»; 
Михед А. Д., канд. техн. наук, доц. каф. информационной 
безопасности и вычислительной техники ТулГУ 
Математическая логика и теория алгоритмов. В 2 ч. 
М34  Ч. 1 : математическая логика : учебно-методическое 
пособие / сост. Н. Ю. Шабанова, О. А. Ефремова. — 
Москва : Директ-Медиа, 2025. — 88 с. 
ISBN 978-5-4499-5080-2 (ч. 1) 
ISBN 978-5-4499-5082-6 
В учебно-методическом пособии изложены основные 
сведения по математической логике. Учебно-методическое 
пособие содержит расширенный материал лекций (часть 1 — 
математическая логика) по дисциплине «Математическая 
логика и теория алгоритмов», предусмотренных учебным 
планом и рабочей программой дисциплины. 
Учебно-методическое пособие предназначено для студентов всех форм обучения направления 09.03.01 «Информатика 
и 
вычислительная 
техника» 
направленности 
(профиля) 
«Автоматизированные системы обработки информации и 
управления».  
УДК 510.6(075) 
ББК 22.12я73 
ISBN 978-5-4499-5080-2 (ч. 1)
ISBN 978-5-4499-5082-6 
© Шабанова Н. Ю., составление, 2025
© Ефремова О. А., составление, 2025 
© Издательство «Директ-Медиа», оформление, 2025 


Оглавление 
Введение ......................................................................................... 5 
История возникновения логики как науки .................................. 7 
1. Исчисление высказываний ..................................................... 10 
1.1. Введение в исчисление высказываний  
и основные понятия ................................................................. 10 
1.2. Пропозициональные связки............................................. 12 
1.3. Понятие клаузы ................................................................ 16 
1.4. Тавтологии, противоречия, парадоксы ........................... 18 
Контрольные вопросы и упражнения .................................... 20 
1.5. Сопоставление логики Буля и логики 
высказываний........................................................................... 21 
1.6. Методы доказательства справедливости 
логических клауз ..................................................................... 22 
1.6.1. Аксиоматический метод ........................................... 22 
1.6.2. Общезначимые формулы логики 
высказываний ...................................................................... 25 
1.6.3. Конструктивный метод ............................................. 27 
1.6.4. Метод резолюций ...................................................... 27 
1.6.5. Метод Вонга ............................................................... 32 
1.6.6. Метод натурального исчисления ............................. 34 
1.6.7. Формальные теории — основные 
определения ......................................................................... 36 
1.6.8. Классическое определение исчисления 
высказывания ....................................................................... 37 
Контрольные вопросы и упражнения ................................ 39 
2. Исчисление предикатов .......................................................... 40 
2.1. Общие положения исчисления предикатов ................... 40 
2.2. Схема решения логических задач с помощью 
логики предикатов ................................................................... 42 
2.3. Логические операции над предикатами ......................... 44 
2.4. Кванторные операции ...................................................... 46 
2.5. Понятие формулы исчисления предикатов .................... 50 
2.6. Значение формулы логики предикатов .......................... 51 
2.7. Равносильные формулы логики предикатов .................. 52 
2.8. Общезначимость и выполнимость формул .................... 55 
Контрольные вопросы и упражнения .................................... 56 


2.9. Применение языка логики предикатов 
для записи математических предложений ............................ 56 
2.10. Использование формул логики предикатов 
в теории математических доказательств ............................... 58 
2.11. Содержательные примеры предикатов ........................ 63 
2.12. Аксиомы исчисления предикатов ................................. 64 
2.13. Правило вывода .............................................................. 64 
2.14. Общезначимые формулы исчисления 
предикатов ............................................................................... 69 
2.15. Полнота чистого исчисления предикатов .................... 69 
2.16. Формальная арифметика ................................................ 70 
2.17. Теорема Геделя о неполноте ......................................... 71 
2.18. Модели с предикатами ................................................... 71 
Контрольные вопросы и упражнения .................................... 76 
3. Получение дизъюнктов ........................................................... 78 
4. Примеры неклассических логик ............................................ 79 
Заключение................................................................................... 82 
Список литературы ...................................................................... 83 
Для заметок .................................................................................. 84 


Введение 
Дисциплина «Математическая логика и теория алгоритмов» закладывает прочный фундамент для изучения практически 
всех специализированных курсов, преподаваемых в технических 
вузах и университетах для направлений подготовки, связанных с 
изучением компьютеров, информационных технологий и коммуникационных сетей.  
Непосредственная цель дисциплины «Математическая 
логика и теория алгоритмов» — дать основы теории математического обеспечения для современных компьютерных и информационных технологий. 
Логика необходима в любой формальной дисциплине и 
состоит из правил получения обоснования вывода (заключения). 
Логику можно выделить из контекста тех дисциплин, в которых она используется, и изучать как отдельный раздел науки. 
Приложения изучаемых методов в информатике, например, 
логические методы доказательств используются при проверке 
корректности алгоритмов. 
Логика лежит в основе неоспоримых рассуждений и доказательств. В том виде, в котором будем рассматривать математическую логику, она имеет два аспекта.  
С одной стороны, — это логика — аналитическая теория 
искусства рассуждения, целью которой является систематизация 
и кодификация принципов правильного рассуждения. Она возникла из изучения использования языка в споре для убеждения 
слушателя и основывается на выделении и исследовании тех 
сторон языка, которые существенны для этих целей. Она формальна в том смысле, что не делает ссылок на значение. Посредством этого она достигает многосторонности: она может быть 
использована для суждения о корректности цепи рассуждений 
(в частности, «математического доказательства») исключительно 
на основании формы (а не содержания), последовательности 
утверждений, образующих эту цепь. Существует много символических логик. В рамках дисциплины рассматривается лишь 
логика, охватывающая большинство выводов того рода, какие 
встречаются в математике. В пределах самой логики — это 
«классическая» символическая логика. 
Другой аспект символической логики переплетается с 
проблемами, связанными с основаниями математики. Вкратце, 


он состоит в формулировании математической теории как логической системы, расширенной дополнительными аксиомами. Идея 
рассмотрения математической теории как «прикладной» системы 
логики принадлежит немецкому математику Г. Фреге (1848–
1925 гг.), который разработал систему логики для применения в 
своем труде об основаниях арифметики. Уайтхед и Рассел в 
Principia mathematica (1910–1913 гг.) продолжили работу Фреге 
и показали, что математика может быть «сведена к логике».  
Так, немецкий математик Г. Фреге (1846–1926 гг.) и итальянский математик Д. Пеано (1858–1932 гг.) применили математическую логику для обоснования арифметики и теории 
множеств. 
В рамках данного раздела дисциплины предполагается 
изучить: 
1. Логику высказываний: принцип дедукции, метод резолюций, аксиоматические системы. 
2. Логику предикатов. 
 
 


История возникновения логики 
как науки 
Для получения информации о каком-либо предмете используют два пути: 
1. Изучение того, что уже сделано, то есть обращение к 
справочникам и энциклопедиям. 
2. Самостоятельный поиск решения, наблюдения, эксперименты и как результат — умозаключение, то есть новое знание, полученное на основе известного. 
Именно вторым путем получена вся собранная до нас 
информация. Второй путь познания является логической категорией. Именно этим путем шли древние философы 2300 лет 
назад, пытаясь понять законы мышления.  
Логика — древняя наука (от греческого слова «логос» — 
мысль). Древние философы стремились понять, по каким законам мыслит человек, какими путями можно прийти к истине в 
рассуждении о событиях и явлениях окружающего мира. Задачей логики является изучение правильных способов рассуждения, которые приводят к верным результатам в тех случаях, 
когда верны исходные посылки. Предметом логики является 
изучение законов человеческого мышления.  
По дошедшим рукописям Аристотеля считают основателем 
логики, как науки. В логике Аристотеля сформулированы логические категории «понятие», «суждение», «умозаключение», 
законы логики, метод дедукции, понятие гипотезы. Логика 
Аристотеля — это классическая формальная логика, которая 
просуществовала без серьезных изменений более двадцати 
столетий и в своем развитии привела к математической логике. 
Словесная форма рассуждений стала тормозить развитие 
логики. В логике появились математические методы исследования. Логика обретает символьный язык, конкретность законов и 
выходит за рамки гуманитарных наук. Но формальная логика не 
утратила своего значения со временем и используется в гуманитарных науках: криминалистика, юриспруденция, философия, 
психология. 
Математика является наукой, в которой все утверждения 
доказываются с помощью умозаключений, т. е. путем использования законов человеческого мышления. Математика является 
основным потребителем логики. Развитие математики выявило 


недостаточность Аристотелевой логики и поставило задачу о ее 
дальнейшем построении на математической основе. Появление 
математической логики связано с именем математика Г. Лейбница (1646–1716 гг.). Он считал, что основные понятия логики 
должны быть обозначены символами, которые соединяются по 
определенным правилам, и это позволяет всякие рассуждения 
заменить вычислением.  
Общим между формальной и математической логикой являются законы и категории логики. В формальной логике они 
имеют абстрактную форму, а в математической они более конкретны, обладают строгой определенностью и реализуются на 
практике конкретными техническими средствами.  
Первая реализация идеи Лейбница принадлежит английскому математику Дж. Булю (1815–1864 гг.). Буль создал алгебру, 
в которой буквами обозначены высказывания, и это привело к 
алгебре высказываний. Сочинение Дж. Буля, в котором подробно 
исследовалась эта алгебра, было опубликовано в 1854 г., т. е. 
150 лет назад. Оно называлось «Исследование законов мысли» 
(Investigation of the Laws of Thought). Отсюда ясно, что Дж. Буль 
рассматривал свою алгебру как инструмент изучения законов 
человеческого мышления, т. е. законов логики. 
Основное назначение математической логики определилось в конце XIX в., когда стала ясна необходимость обоснования понятий и идей самой математики. Главная роль 
математической логики состоит в изучении основания математики, принципов построения математических теорий. 
Математическая логика — это наука о средствах и методах математических доказательств.  
Родоначальником науки о логике является греческий философ Аристотель (384–322 г. до н. э.). Он, используя законы 
человеческого мышления, формализовал известные до него 
правила рассуждений. Лишь в конце XVII в. немецкий математик Г.  Лейбниц предложил математизировать формальные 
рассуждения Аристотеля, вводя символьное обозначение для 
основных понятий и используя особые правила, близкие к вычислениям. Лейбниц утверждал, что «мы употребляем знаки не 
только для того, чтобы передать наши мысли другим лицам, но 
и для того, чтобы облегчить сам процесс нашего мышления». 
Применение математики в логике определило новую 
науку — математическую логику. Математическое описание 


рассуждений позволило получить точные утверждения и эффективные процедуры в решении конкретных задач логики. Рассуждения в математической логике изучаются с точки зрения формы 
описания процесса, явления или события и формального преобразования этого описания. Такой процесс называют выводом заключения. Иногда математическое описание рассуждений называют 
логико-математическим моделированием.  
Основными объектами при изучении математической логики являются формальный язык логики и правила вывода. Формальный язык необходим для символьного описания процессов, 
явлений или событий и логических связей между ними. Правила 
вывода необходимы для формирования процедуры рассуждения. 
Для обеспечения вывода вводится система аксиом, формализующая весь механизм вывода заключения.  
Математическое описание логики следует воспринимать, 
как некую формальную систему, оперирующую с символами 
по определенным правилам, облегчающим интерпретацию в 
реальном мире.  
Выделяют несколько типов математических моделей 
формальной логики. Среди них можно выделить Логику высказываний, Логику предикатов, Логику нечетких множеств и 
отношений, Реляционную логику и др. 
Логика высказываний (prepositional calculus) есть модель 
формальной системы, предметом которой являются высказывания или повествовательные предложения, взятые целиком без 
учета их внутренней структуры.  
Логика предикатов (predicate calculus) есть модель формальной системы, предметом которой являются повествовательные 
предложения с учетом их внутренних состава и структуры. 
Логика нечетких множеств и отношений (fuzzy calculus) 
есть модель формальной системы, предметом которой являются 
повествовательные предложения с учетом их внутренних состава 
и структуры и при нечетком (размытом) задании характерных 
признаков отдельных элементов или отношений между ними. 
Логика реляционная (relation calculus) есть модель формальной системы, предметом которой являются отношения в 
виде множества однородных повествовательных предложений, 
существенно расширяющие логику предикатов. 


Доступ онлайн
139 ₽
В корзину