Языки и исчисления

Упражнение 1:

Номер 1

Если в бескванторной формуле заменить атомы на пропозициональные, то получим формулу:

Ответ:

(1) атомарную

(2) прототип

(3) тавтологию

Номер 2

Бескванторная формула выводима, если ее прототип является:

Ответ:

(1) атомом

(2) тавтологией

(3) истиной

Номер 3

Если прототип формулы - тавтология, то бескванторная формула:

Ответ:

(1) выводима

(2) атом

(3) истина

Упражнение 2:

Номер 1

Значения разных атомарных формул выбирать независимо:

Ответ:

(1) можно

(2) нельзя

(3) можно лишь для тавтологий

Номер 2

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

Ответ:

(1) дополнения

(2) замыкания

(3) отрицания

Номер 3

Формулы класса :

Ответ:

(1) по существу ничем не отличаются от бескванторных

(2) ничем, по существу не схожи с бескванторными

(3) совпадают с термами

Упражнение 3:

Номер 1

Формула  (А - бескванторная ) общезначима, если общезначима дизъюнкция подстановок:

Ответ:

(1)

(2)

(3)

Номер 2

Если существуют подстановки  для которых общезначима дизъюнкция, то формула (А - бескванторна):

Ответ:

(1) общезначима

(2) тавтология

(3) аксиома

Номер 3

Формула , c,d - const:

Ответ:

(1) общезначима

(2) тавтология

(3) ложна

Упражнение 4:

Номер 1

Теорема Эрбрана:

Ответ:

(1) если выводима math

- формула, то существует конечное число подстановок с выводимой дизъюнкцией

(2) если выводима math

- формула, то существует конечное число подстановок с выводимой дизъюнкцией

(3) если выводима math

- формула, то выводима и math

- формула

Номер 2

Утверждение  нельзя записать в виде:

Ответ:

(1)

(2)

(3)

Номер 3

Утверждение  выполнимо только тогда, когда выполнимо:

Ответ:

(1)

(2)

(3)

Упражнение 5:

Номер 1

Для замкнутой А можно указать  этой же сигнатуры с добавленными  функциональными символами, которая:

Ответ:

(1) лишь выполнима всегда с А

(2) лишь невыполнима всегда с А

(3) выполнима или невыполнима с А

Номер 2

Замкнутая формула невыполнима, если:

Ответ:

(1) ее отрицание общезначимо

(2) ее дополнение общезначимо

(3) она тавтология

Номер 3

Если отрицание замкнутой формулы общезначимо, то она:

Ответ:

(1) тавтология

(2) выполнима

(3) невыполнима

Упражнение 6:

Номер 1

Теорема о полноте позволяет заменить в формулировке:

Ответ:

(1) общезначимость на выводимость

(2) выводимость на общезначимость

(3) замкнутость на полноту

Номер 2

"Сколемовская нормальная форма" позволяет получать формулы класса:

Ответ:

(1)

(2)

(3)

Номер 3

Из выводимости формулы, выводимость ее "Сколемовской нормальной формы":

Ответ:

(1) следует

(2) не следует

(3) нельзя определить

Упражнение 7:

Номер 1

Из выводимости "Сколемовской нормальной формы", выводимость формулы:

Ответ:

(1) не следует

(2) следует

(3) нельзя определить

Номер 2

Вопрос о выводимости формулы исчисления предикатов сводится к выводимости:

Ответ:

(1)

- формулы

(2)

- формулы

(3) тавтологии

Номер 3

Вопрос о выводимости произвольных формул языка первого порядка:

Ответ:

(1) неразрешим

(2) разрешим

(3) неопределен

Упражнение 8:

Номер 1

Алгоритм, который по произвольной замкнутой формуле определяет ее выводимость:

Ответ:

(1) не существует

(2) существует практически

(3) существует теоретически

Номер 2

Алгоритм вывода формул :

Ответ:

(1) не существует

(2) существует практически

(3) существует теоретически

Номер 3

Алгоритм вывода формул :

Ответ:

(1) не существует

(2) существует практически

(3) существует теоретически

Языки и исчисления - тест 11