VoprosyMatemat_logike2013
.doc
ФЕДЕРАЛЬНОЕ АГЕНТСТВО МОРСКОГО И РЕЧНОГО ТРАНСПОРТА
Федеральное бюджетное образовательное учреждение высшего профессионального образования «Санкт-Петербургский государственный университет водных коммуникаций»
Кафедра Комплексного обеспечения информационной безопасности
Дисциплина "Математическая логика и теория алгоритмов" ( ИЗ - I )
Специальность "090900.62 - Информационная безопасность" профиль "Безопасность автоматизированных систем"
Список вопросов
-
Свойства операций над множествами.
-
Отношения: инъекция, сюръекция, биекция, их свойства.
-
Отношение эквивалентности. Классы эквивалентности, их свойства.
-
Отношения частичного и линейного порядка. Теорема об изоморфизме частично упорядоч. множеств.
-
Равносильность формул. Основные свойства.
-
Основные тавтологии.
-
Правильные рассуждения. Основные схемы.
-
Двойственные формулы. Лемма. Теорема – принцип двойственности.
-
Теорема о представлении булевой функции формулой логики высказываний.
-
Полные системы связок.
-
Дизъюнктивная нормальная форма. Совершенная ДНФ. Теорема о представлении в ДНФ.
-
Теоремы о приведении к СДНФ и об единственности СДНФ.
-
Конъюнктивная нормальная форма. Совершенная КНФ. Теорема о представлении в КНФ.
-
Теорема о представимости булевых функций многочленами Жегалкина.
-
Приложение логики высказываний: к синтезу логических схем вычисл. устройств, и др.
-
Простейшие свойства выводимых формул в аксиоматических теориях (1- 8).
-
Вывод в теории Черча: .
-
Вывод в теории Черча: если , то .
-
Вывод в теории Черча: .
-
Вывод в теории Черча: .
-
Вывод в теории Черча: и .
-
Теорема о дедукции.
-
Правило силлогизма.
-
Вывод формулы: .
-
Правило перевертывания.
-
Производное правило вывода: .
-
Производное правило вывода: .
-
Производное правило вывода: .
-
Производное правило вывода: и .
-
Производное правило вывода: если , то
-
Производное правило вывода: если , то .
-
Лемма к теореме о полноте (в широком смысле).
-
Теорема о корректности АТЧ.
-
Теорема о полноте (в широком смысле).
-
Теорема о непротиворечивости.
-
Теорема о абсолютной непротиворечивости. Теорема об альтернативности АТ.
-
Частично–рекурсивные и примитивно–рекурсивные функции: ; .
-
Машина Тьюринга для простейших функций.
-
Машина Тьюринга для копирования слов.
-
Машина Тьюринга для удвоения чисел.
-
Машина Тьюринга для сложения двух чисел.