Вопросы к экзамену по математической логике и теории алгоритмов



Скачать 15.92 Kb.
НазваниеВопросы к экзамену по математической логике и теории алгоритмов
Дата08.06.2013
Размер15.92 Kb.
ТипВопросы к экзамену
источник

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


I Алгебра логики.

  1. Понятие высказывания. Логические операции над высказываниями.

  2. Формула алгебры логики. Равносильные формулы алгебры логики. Равносильные преобразования формул.

  3. Алгебра Буля.

  4. Функции алгебры логики. Представление произвольной функции алгебры логики в виде формулы алгебры логики. Закон двойственности.

  5. Дизъюнктивная нормальная форма и совершенная дизъюнктивная нормальная форма (ДНФ и СДНФ).

  6. Конъюнктивная нормальная форма и совершенная конъюнктивная нормальная форма (КНФ и СКНФ).

  7. Проблема разрешимости. Критерий тождественности истинности и ложности .

  8. Приложения алгебры логики.


II Исчисление высказываний.

  1. Понятие формулы исчисления высказываний.

  2. Определение доказуемой формулы.

  3. Производные правила вывода.

  4. Понятие выводимости формул из совокупности формул.

  5. Понятие вывода. Правила выводимости.

  6. Доказательство некоторых законов логики.

  7. Связь между алгеброй высказываний и исчислением высказываний.

  8. Проблемы аксиоматического исчисления высказываний.


III Логика предикатов.

  1. Понятие предикаты. Логические операции над предикатами.

  2. Кванторные операции.

  3. Понятие формулы логики предикатов. Значение формулы логики предикатов.

  4. Равносильные формулы логики предикатов.

  5. Предваренная нормальная форма.

  6. Общезначимость и выполнимость формул.

  7. Пример формулы, выполнимой в бесконечной области и невыполнимой ни в какой конечной области.

  8. Алгоритм распознавания общезначимости формул в частных случаях.

  9. Применение языка логики предикатов для записи математических предложений, определений, построения отрицания предложений. Прямая, обратная и противоположная теоремы. Доказательство методом от противного.

  10. Замечание об аксиоматическом исчислении предикатов.


IV Алгоритмы.

  1. Понятие алгоритма и его характерные черты.

  2. Разрешимые и перечислимые множества.

  3. Машина Тьюринга.

Добавить документ в свой блог или на сайт


Похожие:



Если Вам понравился наш сайт, Вы можеть разместить кнопку на своём сайте или блоге:
refdt.ru


©refdt.ru 2000-2013
условием копирования является указание активной ссылки
обратиться к администрации
refdt.ru