Добавлен пользователем tanga, дата добавления неизвестна
Описание отредактировано
Автор неизвестен. Конспект лекций по курсу "Матем. логика и теория алгоритмов". 2008 год. - 80 стр. Исчисления высказываний. Определение формального исчисления. Исчисление высказываний генценовского типа. Эквивалентность формул. Нормальные формы. Семантика исчисления секвенций. Исчисление высказываний гильбертовского типа. Алгоритмы проверки общезначимости и противоречивости в ИВ. Логика и исчисления предикатов. Алгебр. системы. Формулы сигнатуры. Истинность формулы на алгебр. системе. Секвенциальное исчисление предикатов. Эквивалентность формул в. Нормальные формы. Теорема о существовании модели. Исчисление предикатов гильбертовского типа. Скулемизация алгебраических систем. Метод резолюций в исчислении предикатов. Некоторые проблемы аксиоматического исчисления предикатов. Элементы теории алгоритмов. Машины Тьюринга. Функции, вычислимые на машинах Тьюринга. Рекурсивные функции и отношения. Неразрешимость исчисления предикатов. Теорема Геделя о неполноте. Разрешимые и неразрешимые теории.
Чтобы скачать этот файл зарегистрируйтесь и/или войдите на сайт используя форму сверху.
Пер. с нем. / Под ред. Б. Ф. Мельникова. - 3-е изд. - СПб.: БХВ-Петербург, 2010. - 336с (Учебная литература для вузов)
Изложены основные понятия теоретической информатики: алфавиты, слова, языки, алгоритмические проблемы, конечные автоматы, машины Тьюринга. Рассматриваются теория вычислимости, теория сложности, алгоритмизация труднорешаемых задач, рандомизация, теория связи и...