Форма №20а экзаменационный билет № 3

МИНОБРНАУКИ РОССИИ

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

"Московский государственный технический университет радиотехники, электроники и автоматики"

МГТУ МИРЭА

Кафедра: ОНД

УТВЕРЖДАЮ

Зав. кафедрой

Дисциплина: «Математическая логика и теория алгоритмов»

Форма обучения: очно-заочная

Дата:

1. Алгебраический подход. Основные тождества.

2. Представить в ССФ предикат .

3. Используя метод резолюций для предикатных выражений для заданного множества гипотез и утверждения , доказать справедливость выражения .

, ,

.

4. Найти функцию , полученную из функций и по схеме примитивной рекурсии.

5. Написать формулу числовой функции , вычислимой машиной Тьюринга с множеством внутренних состояний , где 0 – заключительное, а 1 – начальное состояния, если машина задана своей программой.

МИНОБРНАУКИ РОССИИ

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

"Московский государственный технический университет радиотехники, электроники и автоматики"

МГТУ МИРЭА

Кафедра: ОНД

УТВЕРЖДАЮ

Зав. кафедрой

Дисциплина: «Математическая логика и теория алгоритмов»

Форма обучения: очно-заочная

Дата:

1. Дизъюнкты и нормальные формы. Алгоритм нормализации.

2. Представить в ССФ предикат .

3. Используя метод резолюций для предикатных выражений для заданного множества гипотез и утверждения , доказать справедливость выражения .

, .

4. Найти функцию , полученную из функций и по схеме примитивной рекурсии.

5. Написать формулу числовой функции , вычислимой машиной Тьюринга с множеством внутренних состояний , где 0 – заключительное, а 1 – начальное состояния, если машина задана своей программой.