Супрун В.П. Основы математической логики

URSS. 2017. 200 с. ISBN 978-5-9710-4113-9.

Серия: Книга для школьников... И НЕ ТОЛЬКО!

Белая офсетная бумага

Твердый переплет

Аннотация

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

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

В пособии рассматриваются основные... (Подробнее)

Содержание

От автора		6
Предисловие		8
Глава 1.История возникновения математической логики		10
	1.1.Общие сведения	10
	1.2.Некоторые вопросы оснований математики	12
	1.3.Пример математической теории	13
	1.4.Проблемы Давида Гильберта	15
	1.5.Применение математической логики	16
Глава 2.Алгебра высказываний		18
	2.1.Высказывания	18
	2.2.Логические операции	20
	2.3.Формулы алгебры высказываний	24
	2.4.Функции алгебры высказываний	30
	2.5.Основные равносильности	31
	2.6.Задачи для самостоятельной работы	36
	2.7.Приведенные формулы	37
	2.8.Минимизация функций алгебры высказываний	38
	2.9.Минимизация функций в классе ДНФ	39
	2.10.Релейно-контактные схемы	42
	2.11.Контактные схемы	49
	2.12.Проблема минимизации контактных схем	51
	2.13.Функция Шеннона для контактных схем	52
	2.14.Достаточное условие минимальности	54
	2.15.Задачи для самостоятельной работы	55
	2.16.Схемы из функциональных элементов	59
	2.17.Функция Шеннона для схем из функциональных элементов	63
	2.18.Задачи для самостоятельной работы	64
Глава 3.Исчисление высказываний		69
	3.1.Описание исчисления высказываний	70
	3.2.Аксиомы исчисления высказываний	72
	3.3.Правила вывода	72
	3.4.Производные правила вывода	75
	3.5.Некоторые правила исчисления высказываний	76
	3.6.Выводимость из гипотез	78
	3.7.Теорема дедукции	82
	3.8.Примеры вывода секвенций	85
	3.9.Некоторые правила исчисления высказываний (продолжение)	87
	3.10.Монотонность в исчислении высказываний	99
	3.11.Эквивалентные формулы	104
	3.12.Примеры вывода секвенций (продолжение)	108
	3.13.Приведенные формулы	122
	3.14.Непротиворечивость исчисления высказываний	124
	3.15.Полнота исчисления высказываний	127
	3.16.Независимость аксиом	133
	3.17.Задачи для самостоятельной работы	137
Глава 4.Логика предикатов		139
	4.1.Предикаты	139
	4.2.Одноместные предикаты	142
	4.3.Кванторы	143
	4.4.Формулы логики предикатов	145
	4.5.Равносильные формулы	146
	4.6.Приведенные формулы	148
	4.7.Нормальные формулы	149
	4.8.Проблема разрешения	150
Глава 5.Исчисление предикатов		154
	5.1.Символы	154
	5.2.Формулы	155
	5.3.Правила вывода	156
	5.4.Правила связывания квантором	159
	5.5.Непротиворечивость и полнота	161
	5.6.Некоторые теоремы исчисления предикатов	164
	5.7.Приведенные формулы	171
	5.8.Закон двойственности	172
	5.9.Некоторые теоремы исчисления предикатов (продолжение)	174
	5.10.Задачи для самостоятельной работы	180
Глава 6.Машины Тьюринга		182
	6.1.Историческая справка	182
	6.2.Определение машины Тьюринга	184
	6.3.Анализ машин Тьюринга	186
	6.4.Синтез машин Тьюринга	187
Заключение		195
Рекомендуемая литература		197

Об авторе

Супрун Валерий Павлович

Кандидат технических наук, доцент механико-математического факультета Белорусского государственного университета. Область научных интересов — дискретная математика и вычислительная техника. Автор около 350 изобретений в области автоматики и вычислительной техники. Награжден золотой медалью и дипломом Всемирной организации интеллектуальной собственности (ВОИС) как "Лучший изобретатель Беларуси 2006 года". Заслуженный работник Белорусского государственного университета.

Автор 80 научных статей по дискретной математике, а также учебных пособий "Математика для старшеклассников: Задачи повышенной сложности" (М.: URSS), "Математика для старшеклассников: Нестандартные методы решения задач" (М.: URSS), "Математика для старшеклассников: Методы решения и доказательства неравенств" (М.: URSS), "Математика для старшеклассников: Дополнительные разделы школьной программы" (М.: URSS), "Математика для старшеклассников: Нестандартные методы решения уравнений повышенной сложности" (М.: URSS), "Основы теории булевых функций" (М.: URSS), "Основы математической логики" (М.: URSS). Многие книги автора были переведены и выходили в URSS также на испанском языке.