Главная / Алгоритмы и дискретные структуры / Языки и исчисления

Языки и исчисления - ответы на тесты Интуит

Правильные ответы выделены зелёным цветом.
Все ответы: В курсе рассказывается об основных понятиях математической логики (логика высказываний, языки первого порядка, выразимость, исчисление высказываний, разрешимые теории, теорема о полноте, начала теории моделей).

Если A и B - пропозициональные формулы, то такой же формулой будет:

(1) ¬A

(2) A¬B

(3) A¬∨¬B

Теория Г в сигнатуре S - это произвольное:

(1) множество замкнутых формул в S

(2) замыкание S

(3) множество Г

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

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

(2) прототип

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

Для сигнатуры аксиомой равенства будет:

(1)

(2)

(3)

Множество истинных бескванторных формул сигнатуры с равенством и константами для всех элементов интерпретации - это:

(1) диаграмма

(2) область определения

(3) интерпретация

Если S не пусто, math

, то для того, чтобы F был фильтром нужно:

(1)

(2)

(3)

Схема "И - НЕ" имеет:

(1) 2 входа и 2 выхода

(2) 1 вход и 2 выхода

(3) 2 входа и 1 выход

Аксиомой исчисления высказываний является:

(1)

(2)

(3)

Вариант исчисления высказываний - исчисление:

(1) множеств

(2) секвенций

(3) продукций

Если М - непустое множество, то множество всех <m1, m2,…, mk> - это:

(1) M_k

(2) M^k

(3) М(k)

Арифметические формулы определяются сигнатурой S, носителем N вида:

(1) S=‹+,x,=›, N=‹1,2,3,…›

(2) S=‹+,-x›, N=‹1,2,3,…›

(3) S=‹+,-,=›, N=‹1,2,3,…›

элиминация кванторов:

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

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

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

В игре Эренфойхта игроков:

(1) 4

(2) 3

(3) 2

Исчисление предикатов построено над:

(1) высказываниями

(2) формулами первого порядка

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

Формулы A и B эквивалентны тогда и только тогда, когда тавтологией является формула:

(1) (A→B)∧(B→A)

(2) (A→B)∨(B→A)

(3) (A→B)∧(¬A→¬B)

Теория Г может быть:

(1) обычной

(2) прямой

(3) противоречивой

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

(1) можно

(2) нельзя

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

Теория сигнатуры с равенством имеет нормальную модель тогда и только тогда, когда:

(1) она непротиворечива при добавлении аксиом равенства

(2) она противоречива при добавлении аксиом равенства

(3) все равенства нормальные.

Нормальная интерпретация А сигнатуры S с равенством может быть расширена до нормальной модели теории Т, если:

(1) все П₁-формулы S, выводимые из Т, истинны в А

(2) хоть одна П₁-формула S, выводимая из Т, истинна в А

(3) все П₁-формулы S, выводимые из Т, ложны в А

Если S не пусто, math

, то для того, чтобы F был фильтром нужно:

(1)

(2)

(3)

Сложность булевой функции относительно базисных функций - это:

(1) максимальный размер схемы из B-элементов

(2) минимальный размер схемы из B-элементов

(3) мощность множества B

Аксиомой исчисления высказываний является:

(1)

(2)

(3)

Если А и В - некоторые конечные множества формул, то секвенция обозначается:

(1)

(2)

(3)

Унарным предикатом на множестве М будет:

(1) М → ‹И, Л›

(2) М² → ‹И, Л›

(3) М³ → ‹И, Л›

Предикат определяемый формулой math

(1) арифметический

(2) не арифметический

(3) арифметический или нет, в зависимости от значений x,y

Если удалить символ < из сигнатуры math

, класс выразимых предикатов:

(1) изменяется

(2) не изменяется

(3) станет пустым

В игре Эренфойхта игроки:

(1) ходят по очереди

(2) ходят независимо

(3) делают по k ходов каждый сразу

Общезначима формула:

(1)

(2)

(3)

Тавтологией является формула (A,B - формулы):

(1) ¬(A∨B)↔(A∧¬B)

(2) ¬(A∨B)↔(A∧B)

(3) ¬(A∨B)↔(¬A∧¬B)

Непротиворечиво:

(1) подмножество непротиворечивого множества

(2) дополнения противоречивого множества

(3) универсальное множество

Формула

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

(1)

(2)

(3)

Если теория имеет сколь угодно большое конечные нормальные модели, то она:

(1) имеет бесконечную нормальную модель

(2) не имеет бесконечную нормальную модель

(3) универсальна

Кольцо может быть в поле, если:

(1) нет делителей (никаких)

(2) нет делителей нуля

(3) есть простые делители

Фильтр на S со свойством math

или

называется:

(1) ультрафильтром

(2) мегафильтром

(3) главнейшим

Если A и B - полные наборы булевых функций, то для любой функции:

(1)

(2)

(3)

Выводом является:

(1)

(2)

(3)

Верно правило для некоторых конечных множеств формул А, В, С, Д:

(1)

(2)

(3)

Количество различных 0-местных предикатов равно:

(1) 0

(2) 1

(3) 2

Предикат определяемый формулой math

(1) арифметический

(2) не арифметический

(3) арифметический или нет, в зависимости от значений x,y

Для всякой формулы F сигнатуры math

существует бескванторная формула, задающая F на R - это:

(1) теорема Тарского - Зайденберга

(2) теорема Гегеля

(3) аксиома исчисления предикатов

В игре Эренфойхта, если есть предикат сигнатуры, различающий помеченные элементы интерпретации, то:

(1) выигрывает Новатор

(2) выигрывает Консерватор

(3) будет ничья

Общезначима формула:

(1)

(2)

(3)

Верно утверждение для любой булевой функции math

от

аргументов:

(1)

- записывается в виде пропозициональной формулы

(2)

- тавтология, или math

- неопределенна

(3)

и все получаемые из нее формулы - тавтологии

Множество Г с моделью называется:

(1) совместным

(2) совершенным

(3) моделируемым

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

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

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

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

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

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

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

- формула

Формула А семантически следует из теории T,если она:

(1) истинна в любой модели T

(2) ложна в некоторой модели T

(3) имеет смысл (семантику)

Если T₁, T₂ - теории сигнатуры с равенством, то:

(1) объединение T₂ со всеми math

- теоремами T₁ совместно

(2) объединение T₂ со всеми math

- теоремами T₁ не совместно

(3) дополнение T₂ до T₁ совместно

Всякий фильтр F на S расширить до ультрафильтра math

(1) можно

(2) нельзя

(3) можно или нет, в зависимости от S

Количество всех math

-местных булевых функций равно:

(1)

(2)

(3)

, где

Любая тавтология в исчислении высказываний есть:

(1) аксиома

(2) теорема

(3) истина или ложь

Секвенция, в обеих частях которой встречаются только переменные, причем хоть одна из них встречается в обеих частях - это:

(1) аксиома

(2) доказательство

(3) вывод

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

(1) сигнатурой

(2) носителем

(3) термом

Предикат "двоичное слово x состоит только из нулей":

(1) арифметический

(2) не арифметический

(3) арифметический или нет, в зависимости от числа нулей

Для семейства многочленов P_n(x), взятие старшего коэффициента:

(1) понижает степень на единицу

(2) повышает степень на единицу

(3) понижает степень до нуля

Для упорядоченных множеств сигнатуры math

и носителей Z и Q:

(1) выигрывает Новатор

(2) выигрывает Консерватор

(3) будет ничья

Формулы А и В эквивалентны, если формула:

(1)

- общезначима

(2)

- общезначима

(3)

- общезначима

Верна теорема для любой булевой функции math

(1)

- представима дизъюнктивно нормальной формой

(2)

- не представима дизъюнктивно нормальной формой

(3)

- представима только дизъюнктивной нормальной формой

Если в Г все формулы истинны в интерпретации М, то для некоторой замкнутой формулы А:

(1)

(2)

(3)

Для замкнутой А можно указать math

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

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

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

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

Непротиворечивая теория с равенством в не более счетной сигнатуре, не имеющая конечных моделей и категоричная в счетной мощности:

(1) полна

(2) неполна

(3) замкнута

Чтобы задать подструктуру нормальной интерпретации В, нужно взять подмножество носителя В:

(1) замкнутое относительно сигнатурных операций

(2) не замкнутое относительно сигнатурных операций

(3) разрешимое

Аксиомы равенства в фильтрованном произведении нормальных интерпретаций:

(1) истинны

(2) ложны

(3) нормальны

Если B - полный базис, то существует math

(1)

(2)

(3)

Для любых формул исчисления высказывания А В, С выводима формула:

(1)

(2)

(3)

Секвенция выводима тогда и только тогда, когда она:

(1) имеет контрпример

(2) не имеет контрпримера

(3) является контрпримером

Формулу можно построить с использованием правила:

(1) атомарная - формула

(2) сигнатура - формула

(3) символ валентности - формула

Предикат "двоичное слово x - начало двоичного слова y":

(1) арифметический

(2) не арифметический

(3) арифметический или нет, в зависимости от значений x,y

Для некоторой сигнатуры S две ее интерпретации называются элементарно эквивалентными, если:

(1) в них истины одни и те же замкнутые формулы S

(2) в них ложны одни и те же замкнутые формулы S

(3) совпадают все формулы S

Число ходов Новатора соответствует:

(1) кванторной глубине различающей интерпретации формулы

(2) числу переменных формулы

(3) количеству элементов носителя его итерации

Формула, истинная в некоторой интерпретации на некоторой оценке называется:

(1) выполнимой

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

(3) силлогизмом

Функция

эквивалентна:

(1)

(2)

(3)

Множество всех истинных в N формул сигнатуры math

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

(1) полно

(2) не полно

(3) пусто

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

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

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

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

В теорию плотных линейных упорядоченных множеств без первого и последнего элемента входит аксиома:

(1) сохранения

(2) неравенства

(3) равенства

Если теория П₁ аксиоматизируема, то подструктура ее нормальной модели является:

(1) ее моделью

(2) ее сигнатурой

(3) полной

Всякое конечное гипердействительное число бесконечно близко к:

(1) некоторому стандартному числу

(2) бесконечно

(3) нулю

Для умножения двух math

-разрядных двоичных чисел существует схема:

(1) размера math

и глубины

(2) размера math

и глубины

(3) размера math

и глубины

Если А, В, С - формулы, то:

(1)

(2)

(3)

В выводе секвенции принципиально новое, не содержащегося в секвенции всегда:

(1) есть

(2) нет

(3) возможно, если оно вывод

Формулу можно построить с использованием правила:

(1) если А, В - формулы, то math

- формула

(2) если А, В - формулы, то math

- формула

(3) если А, В - формулы, то math

- формула

Предикат "x - простое число номер n":

(1) арифметический

(2) не арифметический

(3) арифметический или нет, в зависимости от значений x,n

Тождественное отображение:

(1) не будет изоморфизмом

(2) будет изоморфизмом

(3) будет морфизмом

Глубина формулы math

равна:

(1) максимуму глубин A и B

(2) минимуму глубин A и B

(3) произведению глубин A и B

Любое вхождение переменной в терм:

(1) свободно

(2) атомарно

(3) терм

В списке выражений: 2-2=0, 2+3=6, 3+12, 2+2>2+2, 2-0=3-0, 56=50+6 приведено всего истинных и ложных высказываний соответственно:

(1) 2,3

(2) 3,2

(3) 3,3

Любая непротиворечивая теория:

(1) совместна

(2) несовместна

(3) замкнута

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

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

(2) следует

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

В теорию плотных линейных упорядоченных множеств без первого и последнего элемента входит аксиома:

(1)

(2)

(3)

Теория

аксиоматизируема, если она:

(1) устойчива относительно перехода к подструктурам

(2) позволяет переходить к подструктурам

(3) если она полна

Нестандартные гипернатуральные числа:

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

(2) существуют

(3) не имеют смысла

Для вычисления функции голосования существует схема:

(1) размера math

и глубины

(2) размера math

и глубины

(3) размера math

O и глубины math

Теоремой исчисления высказываний является:

(1)

(2)

(3)

Верна формула:

(1)

(2)

(3)

Чтобы задать интерпретацию сигнатуры S, необходимо:

(1) указать ее носитель

(2) определить ее мощность

(3) перечислить ее элементы

Предикат "x>y", x,y - целое:

(1) арифметический

(2) не арифметический

(3) арифметический или нет, в зависимости от значений x,y

Естественные интерпретации сигнатуры math

на носителе R:

(1) элементарно эквивалентны

(2) элементарно не эквивалентны

(3) естественно

Глубина формулы math

(1) на единицу больше глубины A

(2) на единицу меньше глубины A

(3) равна глубине A

Если х - свободное вхождение в формулу А или В, то оно:

(1) может быть или нет свободным вхождением в math

(2) свободное вхождение в math

всегда

(3) формула в math

или в

Если

- формула, Г - непротиворечива, то:

(1) А - истинна

(2) А - ложна

(3)

- истинна

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

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

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

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

Множество теорем теории равенств:

(1) не является разрешимым

(2) является разрешимым

(3) универсально

Если любая подструктура любой нормальной модели является ее моделью, то теория:

(1)

аксиоматизируема

(2) П₁ не аксиоматизируема

(3) противоречива

Если все элемнеты гипердействительного аналога множества math

конечны, то:

(1) X - неограничено

(2) X - пусто

(3) X - ограничено

Отношение x mod y=0 (x, y - натуральные) является:

(1) симметричным, рефлексивным, транзитивным

(2) несимметричным, рефлексивным, нетранзитивным

(3) симметричным, рефлексивным, нетранзитивным

Для произвольных формул А, В:

(1)

(2)

(3)

Верна формула:

(1)

(2)

(3)

Параметром формулы A может быть:

(1) все его индивидуальные переменные A

(2) все символы A

(3) всевозможные комбинации символов A

Предикат, выразимый в данной интерпретации:

(1) устойчив относительно ее автоморфизмов

(2) совпадает с любым ее автоморфизмом

(3) истинен для любых автоморфизмов

Любые два алгебраически замкнутых поля характеристики О:

(1) элементарно эквивалентны

(2) не эквивалентны

(3) пусты

Любые два плотно упорядоченных множества без первого и последнего элемента:

(1) эквиваленты

(2) элементарно эквивалентны

(3) не эквивалентны

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

(1) является общезначимой

(2) не является общезначимой

(3) является правилом вывода

Если A и B - пропозициональные формулы, то такой же формулой будет:

(1) A∧B

(2) AB∨¬B

(3) ¬A∧¬B¬∨A

Теория Г противоречива, если в ней выводится:

(1) А и

(2) А или math

(3)

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

(1) атомом

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

(3) истиной

Для сигнатуры аксиомой равенства будет:

(1)

(2)

(3)

Истинность бескванторных формул из D(A) от присутствия дополнительных элементов:

(1) зависит

(2) не зависит

(3) изменяет А

Если S не пусто, math

, то для того, чтобы F был фильтром нужно:

(1)

(2)

(3)

Схема "ИЛИ - НЕ" имеет:

(1) 2 входа и 2 выхода

(2) 1 вход и 2 выхода

(3) 2 входа и 1 выход

Аксиомой исчисления высказываний является:

(1)

(2)

(3)

Исчисление секвенций - исчисление типа:

(1) генценцовского

(2) гельдеровского

(3) гильбертовского

k-местной функцией на М является:

(1) f: M^k→M

(2) f: X→M, X - подмножество M^k

(3) f: M→M^k

Арифметическое множество - это множество:

(1) арифметических знаков

(2) арифметических формул

(3) натуральных чисел и арифметических знаков

Выразимые в арифметике Пресбургера предикаты - это бескванторные формулы из:

(1) констант, сложения, равенства, отношение порядка и сравнения

(2) переменных, сложения, сравнения, эквивалентности

(3) констант, переменных, отношений

Игроки игры Эренфойхта называются:

(1) Нападающий и Отступающий

(2) Новатор и Консерватор

(3) Выигрывающий и Проигрывающий

Формула, истинная в любой интерпретации сигнатуры называется:

(1) общей

(2) глобальной

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

Тавтологией является формула (A,B - формулы):

(1) (A∧B)→(B∧A)

(2) (A∨B)→(A∧B)

(3) (A∧B)→(A∨B)

Теория Г противоречива, если в ней выводима

(1)

- любая формула

(2)

(3)

Общезначимость формулы math

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

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

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

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

Если всякое конечное подмножество теории в сигнатуре с равенством имеет нормальную модель, то теория:

(1) не имеет нормальную модель

(2) имеет нормальную модель

(3) противоречива.

Если все П₁-формулы сигнатуры S с равенством, выводимые из теории Т, истинны в А, то:

(1) нормальная интерпретация А расширяема до нормальной теории Т

(2) А не расширяема до Т

(3) А и Т совпадают

Если S не пусто, math

, то для того, чтобы F был фильтром нужно:

(1)

(2)

(3)

Полным набором B булевых функций называется набор, для которого:

(1) схемы B-элементов всегда максимальны

(2) некоторая булева функция задаваемая задаваема схемой из B-элементов

(3) любая булева функция задаваемая задаваема схемой из B-элементов

Аксиомой исчисления высказываний является:

(1)

(2)

(3)

Контрпример к секвенции math

- это набор значений переменных, для которых все формулы:

(1) из В - истинны, а из А - ложны

(2) из А - истинны, из В - истинны

(3) из А - истинны, а из В - ложны

Бинарным предикатом на множестве М будет:

(1) М → ‹И, Л›

(2) М² → ‹И, Л›

(3) М³ → ‹И, Л›

Предикат определяемый формулой x=const:

(1) арифметический

(2) не арифметический

(3) арифметический или нет, в зависимости от const

Бескванторная формула сигнатуры math

(1) приводима к д.н.ф.

(2) не приводима к д.н.ф.

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

В игре Эренфойхта:

(1) Новатор и Консерватор выбирают числа из интерпретации

(2) Консерватор выбирает элемент интерпретации и помечает его числом

(3) Новатор выбирает элемент интерпретации и помечает его числом

Общезначима формула:

(1)

(2)

(3)

Тавтологией является формула (A,B - формулы):

(1) (A∨(A∧B))↔B

(2) (A∨(A∧B))↔A

(3) (A∨(A∧B))↔A∧B

Если бесконечное множество противоречиво, то некоторое его конечное подмножество будет:

(1) пустым

(2) непротиворечивым

(3) противоречивым

Если существуют подстановки math

для которых общезначима дизъюнкция, то формула math

(А - бескванторна):

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

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

(3) аксиома

Однородное линейное упорядоченное множество такой же мощности для всякой бесконечной мощности:

(1) не найдется

(2) найдется

(3) пусто

Если T₁, T₂ - теории сигнатуры с равенством, то:

(1) существует нормальная модель T₁ и ее расширение - нормальная модель T₂

(2) не существует нормальная модель T₁ и ее расширение - нормальная модель T₂

(3)

Любой главный фильтр является:

(1) мегафильтром

(2) ультрафильтром

(3) универсальным

Сложность любой булевой math

-местной функций при наибольшем размере math

их схем:

(1) не превосходит math

при

и больших

(2) не превосходит math

при

и больших

(3) равна

при

и больших

Выводом является:

(1)

(2)

(3)

Верно правило для некоторых конечных множеств формул А, В, С, Д:

(1)

(2)

(3)

Количество различных 1-местных предикатов:

(1) равно 1

(2) равно 2

(3) равно 3

Предикат

(1) арифметический

(2) не арифметический

(3) арифметический или нет, в зависимости от значений x,y

Число возможных диаграмм семейства многочленов:

(1) бесконечно

(2) конечно

(3) равно нулю

У Консерватора есть способ выиграть если интерпретации:

(1) совпадают

(2) изоморфны

(3) полиморфны

Не общезначима формула:

(1)

(2)

(3)

Верно утверждение для произвольных литералов, конъюнктов и дизъюнктов:

(1) дизъюнктивная нормальная форма - дизъюнкция литералов

(2) дизъюнктивная нормальная форма - дизъюнкция конъюнктов

(3) дизъюнктивная нормальная форма - конъюнкция дизъюнктов

Любое совместное множество замкнутых формул:

(1) противоречиво

(2) непротиворечиво

(3) замкнуто

Утверждение math

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

(1)

(2)

(3)

Семантическое следование равносильно:

(1) эквивалентности

(2) выводимости

(3) совместности

- теорема

А теории T₁ и отрицающая ее П₁-теорема math

А теории T₂:

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

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

(3) совпадают

Свойство ультрафильтра отражает:

(1) по любому вопросу можно принять решение

(2) не по любому вопросу можно принять решение

(3) решение принимается голосованием

Количество всех различных math

-местных схем размера math

оценивается:

(1)

(2)

(3)

Для любой формулы А, формула А → А есть:

(1) аксиома

(2) теорема

(3) истина или ложь

Правило вывода в исчислении секвенций - это правило, объявляющее:

(1) истинной нижнюю секвенцию при истинных верхних

(2) выводимой верхнюю секвенцию, если выводимы нижние

(3) выводимой нижнюю секвенцию, если выводимы верхние

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

(1) термом

(2) термином

(3) терминалом

Предикат "двоичные слова x и y имеют одинаковую длину":

(1) арифметический

(2) не арифметический

(3) арифметический или нет, в зависимости от значений длины

Для семейства многочленов P_n(x), дифференцирование по X:

(1) понижает степень на единицу

(2) повышает степень на единицу

(3) не изменяет степень

Для упорядоченных множеств сигнатуры math

и носителей Z и R:

(1) выигрывает Новатор

(2) выигрывает Консерватор

(3) будет ничья

Формулы А и В эквивалентны, если они обе:

(1) истины на одной и той же интерпретации

(2) ложны на одной и той же интерпретации

(3) совпадают или неопределенны

Верна теорема для любой булевой функции math

(1)

- представима конъюнктивно нормальной формой

(2)

- не представима конъюнктивно нормальной формой

(3)

- представима только конъюнктивной нормальной формой

Если А - замкнутая формула сигнатуры непротиворечивого множества Г и выводима А, то:

(1) Г будет полным в этой сигнатуре

(2) Г будет неполным в этой сигнатуре

(3) Г будет пополняемым в этой сигнатуре

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

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

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

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

Непротиворечивая теория с равенством в не более счетной сигнатуре, не имеющая конечных моделей и категоричная в несчетной мощности:

(1) полна

(2) пуста

(3) плотна

Теория П₁ аксиоматизируема, если она:

(1) устойчива относительно перехода к подструктурам

(2) позволяет переходить к подструктурам

(3) если она полна

Голосование можно проводить для:

(1) атомарных вопросов

(2) любых формул

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

Для сложения двух math

-разрядных двоичных чисел:

(1) не существует схемы размера math

(2) существует схема размера math

(3) существует схема размера math

Если Г - множество формул, то:

(1)

(2)

(3)

Формула, представляющая секвенцию math

(1)

(2)

(3)

Формулу можно построить с использованием правила:

(1) если А - формула, то math

- формула

(2) если

- формула, то А и В - формулы

(3) если

- формула, то А и В - формулы

Предикат "двоичное слово x - конец двоичного слова y":

(1) арифметический

(2) не арифметический

(3) арифметический или нет, в зависимости от значений x,y

Верно утверждение:

(1) изоморфные интерпретации - элементарно эквивалентны

(2) изоморфные интерпретации - не эквивалентны

(3) изоморфные интерпретации - элементарны

Глубина атомарных формул равна:

(1) 0

(2) 1

(3) 2

Двойственна к выполнимости:

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

(2) значимость

(3) обратимость

Функция

эквивалентна:

(1)

(2)

(3)

Из множества всех истинных в N формул сигнатуры math

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

(1)

(2)

(3)

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

(1)

(2)

(3)

В теорию плотных линейных упорядоченных множеств без первого и последнего элемента входит аксиома:

(1)

(2)

(3)

Если любая подструктура любой нормальной модели является ее моделью, то теория:

(1) П₁ аксиоматизируема

(2) П₁ не аксиоматизируема

(3) противоречива

Среди гипердействительных чисел есть:

(1) ненулевые бесконечно малые

(2) нулевые бесконечно большие

(3) все остальные

Для умножения двух math

-разрядных двоичных чисел существует схема:

(1) размера math

и глубины

(2) размера math

и глубины

(3) размера math

и глубины

Если А, В, С - формулы, то:

(1)

(2)

(3)

Интуиционистское исчисление высказываний получается:

(1) исключением аксиомы "исключенного третьего"

(2) включением аксиомы "исключенного третьего"

(3) исключением аксиомы МР

Формулу можно построить с использованием правила:

(1) если А, В - формулы, то math

- формула

(2) если А, В - формулы, то math

- формула

(3) если А, В - формулы, то math

- формула

Предикат "x=2_n", n - натуральное:

(1) арифметический

(2) не арифметический

(3) арифметический или нет, в зависимости от значений n

Отображение, обратное изоморфизму будет:

(1) изоморфизмом

(2) морфизмом

(3) тождественным

Глубина формулы math

равна:

(1) глубине A

(2) глубин A со знаком минус

(3) глубин A минус единица

Любое вхождение переменной в атомарную формулу:

(1) атомарно

(2) терм

(3) свободно

Для любого непротиворечивого множества замкнутых формул полное непротиворечивое множество замкнутых формул той же сигнатуры:

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

(2) существует

(3) пусто

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

(1)

- формулы

(2)

- формулы

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

В теорию плотных линейных упорядоченных множеств без первого и последнего элемента входит аксиома:

(1)

(2)

(3)

Если теория устойчива относительно перехода к подструктурам, то она:

(1)

аксиоматизируема

(2) не аксиоматизируема

(3) не моделируема

Все нестандартные гипернатуральные числа:

(1) бесконечно малы

(2) бесконечно велики

(3) совпадают

Для вычисления функции голосования существует схема:

(1) размера math

и глубины

(2) размера

O\left( {{\raise0.5ex\hbox{$\scriptstyle n$}
\kern-0.1em/\kern-0.15em
\lower0.25ex\hbox{$\scriptstyle 2$}}} \right)

и глубины

O\left( {{\raise0.5ex\hbox{$\scriptstyle n$}
\kern-0.1em/\kern-0.15em
\lower0.25ex\hbox{$\scriptstyle 2$}}} \right)

(3) размера math

и глубины

Теоремой исчисления высказываний является:

(1)

(2)

(3)

Верна формула:

(1)

(2)

(3)

Чтобы задать интерпретацию сигнатуры S, необходимо:

(1) для каждого предикатного символа S указать предикат

(2) для каждого символа указать ее носитель

(3) перечислить все формулы

Биекция

- автоморфизм интерпретации, если все функции и предикаты интерпретации:

(1) автономны

(2) совпадают

(3) устойчивы

Если всякий многочлен P_n(x),n>0 имеет в поле X хотя бы один корень, то:

(1) X - алгебраически замкнуто

(2) X - разрешимо

(3) X - плотно

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

(1) только истинны

(2) только ложны

(3) истинны и ложны

Если х - свободное вхождение в формулу А или В, то оно:

(1) может быть или нет свободным вхождением в math

(2) свободное вхождение в math

всегда

(3) формула в math

или в

Если

- формула, Г - непротиворечива, то:

(1) А - ложна

(2)

- ложна

(3)

- истинна

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

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

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

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

Сигнатура теории полугрупп состоит из:

(1)

(2)

(3)

Любая теория, имеющая П₂-аксиоматизацию:

(1) устойчива относительно объединения

(2) не устойчива относительно объединения

(3) не полна

Число а - предел ‹a_i›, i=0,1,…, если есть бесконечно далекий a_k:

(1) бесконечно далекий от а

(2) бесконечно близкий к а

(3) совпадающий с а

Отношение x>y (x, y - натуральные) является:

(1) симметричным, рефлексивным, транзитивным

(2) несимметричным, нерефлексивным, транзитивным

(3) симметричным, рефлексивным, нетранзитивным

Для произвольных формул А, В:

(1)

(2)

(3)

Без аксиомы "исключенного третьего" выводима:

(1)

(2)

(3)

Параметром формулы A может быть:

(1) параметры формулы math

(2) параметры формулы math

(3) все части A

Класс выразимых предикатов:

(1) бескванторные формулы

(2) кванторные формулы

(3) устойчивые формулы

Любые два алгебраически замкнутых поля конечной характеристики n:

(1) элементарно эквивалентны

(2) не эквивалентны

(3) пусты

Для счетной (конечной) сигнатуры и бесконечной ее интерпретации M:

(1) существует счетное подмножество M - подструктура M

(2) не существует счетное подмножество M - подструктура M

(3) существует несчетное подмножество M - подструктура M

Все теоремы теории Г:

(1) истинны в любой ее модели М

(2) ложны в некоторой ее модели М

(3) истинны только в одной модели М

Если A и B - пропозициональные формулы, то такой же формулой будет:

(1) A∨B

(2) A∨B¬A

(3) A→B¬A

Теория Г может быть:

(1) неопределенной

(2) непротиворечивой

(3) противоположной

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

(1) выводима

(2) атом

(3) истина

Для сигнатуры аксиомой равенства будет:

(1)

(2)

(3)

Любую модель теории D(A) можно считать расширением интерпретации А, если:

(1) отождествить a из А со значением константы из math

(2) расширить А до В

(3) интерпретировать В как и А

Если S не пусто, math

, то для того, чтобы F был фильтром нужно:

(1)

(2)

(3)

Схема "ИСКЛЮЧАЮЩЕЕ - ИЛИ" имеет:

(1) 2 входа и 2 выхода

(2) 1 вход и 2 выхода

(3) 2 входа и 1 выход

Аксиомой исчисления высказываний является:

(1)

(2)

(3)

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

(1) теста правильности А

(2) задачи такого же или общего вида

(3) доказательства формулы А

Количество синонимов в списке ‹"арность", "местность", "валентность", "эквивалентность"› равна:

(1) 2

(2) 3

(3) 4

Множество натуральных чисел, не являющееся арифметическим:

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

(2) существует

(3) совпадает с N

В теории действительных чисел со сложением и умножением, элиминация кванторов:

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

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

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

Игра Эренфойхта определяется:

(1) парой интерпретаций

(2) парой стратегий

(3) Новатором

Если в тавтологию вместо пропозициональных переменных подставить формулы сигнатуры, получим:

(1) общезначимую формулу

(2) подстановку

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

Тавтологией является формула (A,B - формулы):

(1) ¬(A∧B)↔(A∨B)

(2) ¬(A∧B)↔(¬A∨¬B)

(3) ¬(A∧B)↔(A∧B)

Если в теории Г выводима формула math

(А - любая формула), то она:

(1) замкнута

(2) противоречива

(3) непротиворечива

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

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

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

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

Если А - бесконечная нормальная интерпретация сигнатуры с равенством,то нормальная интерпретация В А большой мощности , является элементарным расширением А:

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

(2) существует

(3) пусто

Всякая коммутативная полугруппа с сокращением:

(1) может быть вложена в коммутативную группу

(2) не может быть вложена в коммутативную группу

(3) пуста

Если S не пусто, math

, то для того, чтобы F был фильтром нужно:

(1)

(2)

(3)

Размером схемы называется число:

(1) входов

(2) проводников

(3) циклов

Аксиомой исчисления высказываний является:

(1)

(2)

(3)

Контрпример к секвенции math

будет контрпримером к формуле ( math

- конъюнкция, math

- дизъюнкция формул из А)

(1)

(2)

(3)

Тернарным (тренарным) предикатом на множестве М будет:

(1) М → ‹И, Л›

(2) М² → ‹И, Л›

(3) М³ → ‹И, Л›

Предикат определяемый формулой math

(1) арифметический

(2) не арифметический

(3) арифметический или нет, в зависимости от значений x,y

Бескванторная формула сигнатуры math

(1) приводима к системам вида P=0, P>0

(2) не приводима к системам вида P=0

(3) не приводима к системам вида P>0

В игре Эренфойхта:

(1) Консерватор помечает элемент другой интерпретации после хода Новатора

(2) Новатор помечает элемент другой интерпретации после хода Консерватора

(3) Новатор и Консерватор одновременно ходят

Общезначима формула:

(1)

(2)

(3)

Тавтологией является формула (A, B - формулы):

(1) (A∧(A∨B))↔B

(2) (A∧(A∨B))↔A

(3) (A∧(A∨B))↔A∨B

Интерпретация М теории Г, в которой все формулы из Г истинны в М - это:

(1) модель

(2) морфизм

(3) модуль

Формула

, c,d - const:

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

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

(3) ложна

Если А - бесконечная нормальная интерпретация сигнатуры S с равенством math

, то нормальное элементарное расширение мощности m:

(1) пусто

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

(3) существует

Если T₁, T₂ - теории сигнатуры с равенством, то:

(1) пресечение T₁ со всеми П₁-теоремами T₂ совместно

(2) объединение T₁ со всеми П₁-теоремами T₂ совместно

(3) дополнение T₁ до T₂ совместно

Ультрафильтр - это фильтр:

(1) не имеющий собственных расширений

(2) имеющий собственных расширений

(3) включающий все другие фильтры

Сложность большинства булевой math

-местной функций при наибольшем размере math

их схем:

(1) не меньше math

при

и больших

(2) не меньше math

при

и больших

(3) равна

при

и больших

Выводом является:

(1)

(2)

(3)

Верно правило для некоторых конечных множеств формул А, В, С, Д:

(1)

(2)

(3)

Количество 2-местных предикатов:

(1) равно 2

(2) равно 4

(3) больше 4

Предикат z=НОД(x,y), math

(1) арифметический

(2) не арифметический

(3) арифметический или нет, в зависимости от значений x,y

Для семейства многочленов P_n(x), отбрасывание старшего члена:

(1) понижает степень на единицу

(2) повышает степень на единицу

(3) сводит P_n(x) к P_n(x)

Для упорядоченных множеств сигнатуры math

и носителей N и Z:

(1) выигрывает Новатор

(2) выигрывает Консерватор

(3) будет ничья

Не общезначима формула:

(1)

(2)

(3)

Верно утверждение для произвольных литералов, конъюнктов и дизъюнктов:

(1) конъюнктивная нормальная форма - конъюнкция литералов

(2) конъюнктивная нормальная форма - конъюнкция дизъюнктов

(3) конъюнктивная нормальная форма - дизъюнкция конъюнктов

Если в Г все формулы истинны в интерпретации М, то для некоторой замкнутой формулы А:

(1)

(2)

(3)

Утверждение math

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

(1)

(2)

(3)

В противоречивой теории:

(1) выводима любая формула

(2) не выводима любая формула

(3) не выводима хотя бы одна формула

Теория Т - П₁ аксиоматизируема, если существуют П₁-формулы,из которых:

(1) выводятся все теоремы Т и другие

(2) не выводятся все теоремы Т

(3) выводятся все теоремы Т и только они

Если ультрафильтр неглавный, то:

(1) все игроки имеют выигрышные стратегии

(2) ни один игрок не имеет выигрышной стратегии

(3) игра сводится к ничье

При некотором math

сложность большинства булевых math

-местных функций:

(1) не больше math

(2) не меньше math

(3) не меньше

C{\raise0.7ex\hbox{${2^n }$} \!\mathord{\left/
 {\vphantom {{2^n } n}}\right.\kern-\nulldelimiterspace}
\!\lower0.7ex\hbox{$n$}}

Если Г - множество формул, то тогда:

(1)

(2)

(3)

Процесс вывода можно представить:

(1) деревом

(2) орграфом

(3) неорграфом

Если А - предикатный символ валентности k, t1, t2, …, tk - термы, то выражение А(t1, t2, …, tk) - это:

(1) терминальная функция

(2) характеристическая функция

(3) атомарная функция

Предикат "z=x+y", где "+" - конкатенация двоичных слов:

(1) арифметический

(2) не арифметический

(3) арифметический или нет, в зависимости от значений x,y

Для сигнатуры math

и носителя С (комплексные числа) всякая формула:

(1) эквивалентна бескванторной

(2) совпадает с кванторной

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

Для упорядоченных множеств сигнатуры math

и носителей R и Q:

(1) выигрывает Новатор

(2) выигрывает Консерватор

(3) будет ничья

Формулы А и В эквивалентны, если формула:

(1)

- общезначима

(2)

- общезначима

(3)

- общезначима

Верна теорема для любой булевой функции math

(1)

- однозначно представима полиномом Жегалкина

(2)

- представима полиномом Жегалкина неоднозначно

(3)

- не представима полиномом Жегалкина

Если А - замкнутая формула сигнатуры непротиворечивого множества Г и выводима math

, то:

(1) Г будет полным в этой сигнатуре

(2) Г будет неполным в этой сигнатуре

(3) Г будет пополняемым в этой сигнатуре

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

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

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

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

Конечно аксиоматизируемая полная теория в конечной сигнатуре:

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

(2) разрешима

(3) пуста

Если теория устойчива относительно перехода к подструктурам, то она:

(1) П₁ аксиоматизируема

(2) не аксиоматизируема

(3) не моделируема

Ультрапроизведение семейства моделей некоторой теории моделью той же теории:

(1) не является

(2) не может быть

(3) является

Для сложения двух math

-разрядных двоичных чисел:

(1) не существует схемы размера math

и глубины

(2) существует схема размера math

и глубины

(3) существует схема размера math

и глубины

Если Г - множество формул, то:

(1)

(2)

(3)

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

(1) выводима

(2) не выводима

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

Формулу можно построить с использованием правила:

(1) если А, В - формулы, то math

- формула

(2) если

- формулы, то math

- формула

(3) если А, В - формулы, то math

- формула

Предикат "двоичное слово x входит в двоичного слова y":

(1) арифметический

(2) не арифметический

(3) арифметический или нет, в зависимости от значений x,y

Две интерпретации - изоморфны, если между ними существует:

(1) морфизм

(2) изоморфизм

(3) изометризм

Глубина формулы math

равна:

(1) минимуму глубин A и B

(2) максимуму глубин A и B

(3) сумме глубин A и B

Вхождение индивидной переменной, не из области действия одноименного квантора называется:

(1) пустым

(2) неопределенным

(3) свободным

Функция

эквивалентна:

(1)

(2)

(3)

Из множества всех истинных в N формул сигнатуры math

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

(1)

(2)

(3)

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

(1) следует

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

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

В теорию плотных линейных упорядоченных множеств без первого и последнего элемента входит аксиома:

(1)

(2)

(3)

Теория Т - math

аксиоматизируема, если существуют math

-формулы, из которых:

(1) выводятся все теоремы Т и другие

(2) не выводятся все теоремы Т

(3) выводятся все теоремы Т и только они

Среди гипердействительных чисел есть:

(1) бесконечно большие числа

(2) бесконечно малые числа

(3) все остальные

Вычитание двух math

-разрядных двоичных чисел по модулю math

выполнима схема:

(1) размера math

и глубины

(2) размера math

и глубины

(3) размера math

и глубины

Если А, В, С - формулы, то:

(1)

(2)

(3)

Интуиционистская логика возникла как попытка формализовать:

(1) методы рассуждений

(2) математическую индукцию

(3) интуитивные рассуждения

Если А - формула, а x - ее индивидная переменная, то:

(1)

- формула

(2)

- формула

(3)

- формула

Предикат "x=4_n", n - натуральное:

(1) арифметический

(2) не арифметический

(3) арифметический или нет, в зависимости от значений n

Композиция двух изоморфизмов:

(1) не будет изоморфизмом

(2) будет изоморфизмом

(3) будет тождественным

Глубина формулы math

(1) на единицу меньше глубины A

(2) на единицу больше глубины A

(3) равна глубине A

Если х - свободное вхождение в формулу А, то оно всегда:

(1) свободное вхождение в math

(2) терм в math

(3) формула в math

Отметьте высказывание, которое является выражением:

(1) "климат теплый"

(2) "климат местами теплый, местами - холодный"

(3) "1+2=4"

Замкнутым термам соответствуют:

(1) элементы носителя

(2) правила вывода

(3) замкнутые формулы

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

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

(2) разрешим

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

В теорию плотных линейных упорядоченных множеств без первого и последнего элемента входит аксиома:

(1)

(2)

(3)

Если теория math

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

(1) ее моделью

(2) ее сигнатурой

(3) полной

Множество

ограничено, если все элементы его гипердействительного аналога:

(1) конечны

(2) бесконечны

(3) нуль

Если

- минимальная глубина схемы, вычисляющая функцию math

, то:

(1)

(2)

(3)

Теоремой исчисления высказываний является:

(1)

(2)

(3)

Верна формула:

(1)

(2)

(3)

Чтобы задать интерпретацию сигнатуры S, необходимо:

(1) для каждого функционального символа S указать функцию

(2) для каждого символа указать ее сигнатуру

(3) указать валентность всех функции

n - местный предикат P - устойчив относительно автоморфизма math

, если:

(1)

(2)

(3)

Минимальное число слагаемых в сумме вида 1+1+…+1, при котором она обращается в нуль - это:

(1) характеристическое поле

(2) характеристика поля

(3) характеристическое число

Итерации A и B элементарно эквивалентны тогда и только тогда, когда в соответствующей игре Эренфойхта:

(1) будет ничья

(2) выигрывает Консерватор

(3) выигрывает Новатор

Если х - свободное вхождение в формулу А или В, то оно:

(1) может быть или нет свободным вхождением в math

(2) свободное вхождение в math

всегда

(3) формула, если формула math

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

(1) имеет модель

(2) не может иметь модель

(3) имеет нечетное число моделей

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

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

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

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

Арифметика Пеано - это арифметика:

(1) формальная

(2) из чисел 1,2,…,9

(3) неформальная

Любая теория, устойчивая относительно объединения:

(1) имеет П₂ аксиоматизацию

(2) не имеет П₂ аксиоматизацию

(3) не полна

Если существует бесконечно далекий a_k из ряда ‹a_i›, I=0,1,… который бесконечно близок к а, то:

(1) а - предел ‹a_i›

(2) а - большая величина

(3) а - малая величина

Отношение x + 5=y (x, y - натуральные) является:

(1) симметричным, рефлексивным, транзитивным

(2) несимметричным, нерефлексивным, нетранзитивным

(3) симметричным, рефлексивным, нетранзитивным

Для произвольных формул А, В:

(1)

(2)

(3)

Без аксиомы "исключенного третьего" выводима:

(1)

(2)

(3)

Параметром формулы A может быть:

(1)

(2)

(3) параметры math

- формула

Всякая формула в math

, где +1 - функция прибавления 1:

(1) эквивалентна некоторой бескванторной формуле

(2) эквивалентна некоторой кванторной формуле

(3) не эквивалентна никакой бескванторной формуле

Если группа - интерпретация сигнатуры math

, то подструктуры - это:

(1) поля

(2) группы

(3) подгруппы

Для счетного (конечного) подмножество интерпретации M:

(1) не существует сигнатуры

(2) не существует конечной или счетной подструктуры M

(3) существует конечное (счетное) подструктура M

Если выводима формула А(с/х), где А - формула, х - переменная, с - константа не входящая в А, то тогда:

(1) не выводима А

(2) выводима и А

(3) выводима math