Математическая логика и теория алгоритмов
ВедениеИНФОРМАЦИОННО-ЛОГИЧЕСКИЕ СТРУКТУРЫ 1. ЭЛЕМЕНТАРНОЕ ВВЕДЕНИЕ В ТЕОРИЮ МНОЖЕСТВТеоретико-множественная символика и терминологияОперации над множествами и их основные свойстваДекартово произведение множеств и отношения на множествахЭлементы теории отображенийОтношение эквивалентности и разбиение множества на классыОтношения порядкаБазовые алгебраические системыВопросы и упражнения для самопроверкиАЛГЕБРА ВЫСКАЗЫВАНИЙ И ЛОГИКА ПРЕДИКАТОВАлгебраические операции над высказываниями и их свойстваФормулы и функции алгебры логики. Закон двойственностиСовершенные дизъюнктивные и конъюнктивные нормальные формы булевых функцийПолнота и замкнутость системы булевых функций. Представление о классах ПостаЛогика предикатовВопросы и упражнения для самопроверкиИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙАлфавит, формулы и подформулы исчисления высказыванийАксиомы исчисления высказыванийОсновные правила выводаОпределение доказуемой (выводимой) формулыПроизводные правила вывода. Теорема дедукцииСвязь алгебры высказываний с исчислением высказыванийВопросы и упражнения для самопроверкиИСЧИСЛЕНИЕ ПРЕДИКАТОВОпределение формулы исчисления предикатовАксиомы исчисления предикатов и основные правила выводаОбщезначимость и выполнимость формул исчисления предикатовПредваренная, скулемовская и клаузальная формы представления формул исчисления предикатовВопросы и упражнения для самопроверкиОСНОВНЫЕ ПОНЯТИЯ АКСИОМАТИЧЕСКИХ ТЕОРИЙ ПЕРВОГО ПОРЯДКАФормальные аксиоматические теорииЛогические и специальные аксиомыПравила вывода и понятие доказательства в теории первого порядкаПонятия интерпретации и модели теории. Изоморфизм интерпретацийПримеры аксиоматических теорий первого порядка со специальными аксиомамиВопросы и упражнения для самопроверкиПРОБЛЕМЫ АКСИОМАТИЧЕСКОГО ПОСТРОЕНИЯ ТЕОРИИ ПЕРВОГО ПОРЯДКАПроблема непротиворечивостиПроблема независимости системы аксиомФормализуемость и разрешимость теорииКатегоричность теорииПроблема полноты теорииЛИТЕРАТУРА К ГЛАВЕ IП. НЕТРАДИЦИОННЫЕ ЛОГИКИ 1. ОСНОВНЫЕ НАПРАВЛЕНИЯ ИССЛЕДОВАНИЙ В ОБЛАСТИ ИСКУССТВЕННОГО ИНТЕЛЛЕКТАЕстественный и искусственный интеллектНекоторые философские аспекты проблем искусственного интеллектаПримеры систем искусственного интеллектаВопросы и упражнения для самопроверкиОСНОВНЫЕ ПРИНЦИПЫ ПОСТРОЕНИЯ СИСТЕМ АВТОМАТИЗАЦИИ ДОКАЗАТЕЛЬСТВПостановка задачи автоматического доказательства теоремУнификацияМетод резолюцийАлгоритм поиска опровержения методом резолюцийДоказательство истинности логических клауз методом резолюцийВопросы и упражнения для самопроверкиОСНОВНЫЕ ПРИНЦИПЫ ЛОГИЧЕСКОГО ПРОГРАММИРОВАНИЯИспользование формализмов логики для алгоритмических вычислений. Факты, правила, запросыОбщие правила выполнения запросов логическими программамиМетодика составления логических программВопросы и упражнения для самопроверкиСИСТЕМЫ ИСКУССТВЕННОГО ИНТЕЛЛЕКТА, ОСНОВАНННЫЕ НА ЗНАНИЯХПредставление и использование нечетких знанийНечеткая, вероятностная и монотонная логикиНечеткие множества и нечеткие выводыМногозначная логикаМодальные логикиПродукционные системыО механизмах вывода в экспертных системахВопросы и упражнения для самопроверкиЛИТЕРАТУРА К ГЛАВЕ ПШ. ТЕОРИЯ АЛГОРИТМОВ 1. УТОЧНЕНИЕ ПОНЯТИЯ АЛГОРИТМА НА ОСНОВЕ ЧАСТИЧНО РЕКУРСИВНЫХ ФУНКЦИЙИнтуитивное понятие алгоритма. Общие свойства алгоритмовЭффективно вычислимые и примитивно рекурсивные функцииОператор минимизации и частично рекурсивные функции. Тезис ЧерчаВопросы и упражнения для самопроверкиУТОЧНЕНИЕ ПОНЯТИЯ АЛГОРИТМА НА ОСНОВЕ МАШИН ТЬЮРИНГА.Модель одноленточной машины ТьюрингаКомпозиция, итерация и разветвление машин ТьюрингаМетодологическое значение моделей машин ТьюрингаВопросы и упражнения для самопроверкиНОРМАЛЬНЫЕ АЛГОРИТМЫ МАРКОВАОсновные понятияКомпозиция, итерация и разветвление нормальных алгоритмов. Эквивалентность тезиса Черча и принципа нормализации МарковаВопросы и упражнения для самопроверкиАНАЛИЗ СЛОЖНОСТИ АЛГОРИТМОВПодходы к оценке сложности алгоритмов. АсимптотикаМеры и оценки сложностиАнализ сложности генерирования перестановокКласс задач, детерминировано решаемых с полиномиальной СложностьюNP-полные и NP-трудные задачиПонятие алгоритмически неразрешимых проблемПримеры алгоритмически неразрешимых проблемВопросы и упражнения для самопроверкиЛИТЕРАТУРА К ГЛАВЕ IIIЗАКЛЮЧЕНИЕ
