Главная / Языки и исчисления

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

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

Список вопросов:

# Если A и B - пропозициональные формулы, то такой же формулой будет:
# Если A и B - пропозициональные формулы, то такой же формулой будет:
# Если A и B - пропозициональные формулы, то такой же формулой будет:
# Формулы A и B эквивалентны тогда и только тогда, когда тавтологией является формула:
# Тавтологией является формула (A,B - формулы):
# Тавтологией является формула (A,B - формулы):
# Тавтологией является формула (A,B - формулы):
# Тавтологией является формула (A,B - формулы):
# Тавтологией является формула (A, B - формулы):
# Верно утверждение для любой булевой функции от аргументов:
# Верно утверждение для произвольных литералов, конъюнктов и дизъюнктов:
# Верно утверждение для произвольных литералов, конъюнктов и дизъюнктов:
# Верна теорема для любой булевой функции :
# Верна теорема для любой булевой функции :
# Верна теорема для любой булевой функции :
# Функция эквивалентна:
# Функция эквивалентна:
# Функция эквивалентна:
# В списке выражений: 2-2=0, 2+3=6, 3+12, 2+2>2+2, 2-0=3-0, 56=50+6 приведено всего истинных и ложных высказываний соответственно:
# Отметьте высказывание, которое является выражением:
# Теория Г в сигнатуре S - это произвольное:
# Теория Г противоречива, если в ней выводится:
# Теория Г может быть:
# Теория Г может быть:
# Теория Г противоречива, если в ней выводима
# Если в теории Г выводима формула (А - любая формула), то она:
# Непротиворечиво:
# Если бесконечное множество противоречиво, то некоторое его конечное подмножество будет:
# Интерпретация М теории Г, в которой все формулы из Г истинны в М - это:
# Множество Г с моделью называется:
# Любое совместное множество замкнутых формул:
# Если в Г все формулы истинны в интерпретации М, то для некоторой замкнутой формулы А:
# Если в Г все формулы истинны в интерпретации М, то для некоторой замкнутой формулы А:
# Если А - замкнутая формула сигнатуры непротиворечивого множества Г и выводима А, то:
# Если А - замкнутая формула сигнатуры непротиворечивого множества Г и выводима , то:
# Множество всех истинных в N формул сигнатуры не выводится формула:
# Из множества всех истинных в N формул сигнатуры не выводится формула:
# Из множества всех истинных в N формул сигнатуры не выводится формула:
# Любая непротиворечивая теория:
# Для любого непротиворечивого множества замкнутых формул полное непротиворечивое множество замкнутых формул той же сигнатуры:
# Замкнутым термам соответствуют:
# Если - формула, Г - непротиворечива, то:
# Если - формула, Г - непротиворечива, то:
# Всякое непротиворечивое множество замкнутых формул:
# Если в бескванторной формуле заменить атомы на пропозициональные, то получим формулу:
# Бескванторная формула выводима, если ее прототип является:
# Если прототип формулы - тавтология, то бескванторная формула:
# Значения разных атомарных формул выбирать независимо:
# Общезначимость формулы свободными переменными равносильна общезначимости ее:
# Формулы класса :
# Формула (А - бескванторная ) общезначима, если общезначима дизъюнкция подстановок:
# Если существуют подстановки для которых общезначима дизъюнкция, то формула (А - бескванторна):
# Формула , c,d - const:
# Теорема Эрбрана:
# Утверждение нельзя записать в виде:
# Утверждение выполнимо только тогда, когда выполнимо:
# Для замкнутой А можно указать этой же сигнатуры с добавленными функциональными символами, которая:
# Замкнутая формула невыполнима, если:
# Если отрицание замкнутой формулы общезначимо, то она:
# Теорема о полноте позволяет заменить в формулировке:
# "Сколемовская нормальная форма" позволяет получать формулы класса:
# Из выводимости формулы, выводимость ее "Сколемовской нормальной формы":
# Из выводимости "Сколемовской нормальной формы", выводимость формулы:
# Вопрос о выводимости формулы исчисления предикатов сводится к выводимости:
# Вопрос о выводимости произвольных формул языка первого порядка:
# Алгоритм, который по произвольной замкнутой формуле определяет ее выводимость:
# Алгоритм вывода формул :
# Алгоритм вывода формул :
# Для сигнатуры аксиомой равенства будет:
# Для сигнатуры аксиомой равенства будет:
# Для сигнатуры аксиомой равенства будет:
# Теория сигнатуры с равенством имеет нормальную модель тогда и только тогда, когда:
# Если всякое конечное подмножество теории в сигнатуре с равенством имеет нормальную модель, то теория:
# Если А - бесконечная нормальная интерпретация сигнатуры с равенством,то нормальная интерпретация В А большой мощности , является элементарным расширением А:
# Если теория имеет сколь угодно большое конечные нормальные модели, то она:
# Однородное линейное упорядоченное множество такой же мощности для всякой бесконечной мощности:
# Если А - бесконечная нормальная интерпретация сигнатуры S с равенством ,, то нормальное элементарное расширение мощности m:
# Формула А семантически следует из теории T,если она:
# Семантическое следование равносильно:
# В противоречивой теории:
# Непротиворечивая теория с равенством в не более счетной сигнатуре, не имеющая конечных моделей и категоричная в счетной мощности:
# Непротиворечивая теория с равенством в не более счетной сигнатуре, не имеющая конечных моделей и категоричная в несчетной мощности:
# Конечно аксиоматизируемая полная теория в конечной сигнатуре:
# В теорию плотных линейных упорядоченных множеств без первого и последнего элемента входит аксиома:
# В теорию плотных линейных упорядоченных множеств без первого и последнего элемента входит аксиома:
# В теорию плотных линейных упорядоченных множеств без первого и последнего элемента входит аксиома:
# В теорию плотных линейных упорядоченных множеств без первого и последнего элемента входит аксиома:
# В теорию плотных линейных упорядоченных множеств без первого и последнего элемента входит аксиома:
# В теорию плотных линейных упорядоченных множеств без первого и последнего элемента входит аксиома:
# Множество теорем теории равенств:
# Сигнатура теории полугрупп состоит из:
# Арифметика Пеано - это арифметика:
# Множество истинных бескванторных формул сигнатуры с равенством и константами для всех элементов интерпретации - это:
# Истинность бескванторных формул из D(A) от присутствия дополнительных элементов:
# Любую модель теории D(A) можно считать расширением интерпретации А, если:
# Нормальная интерпретация А сигнатуры S с равенством может быть расширена до нормальной модели теории Т, если:
# Если все П1-формулы сигнатуры S с равенством, выводимые из теории Т, истинны в А, то:
# Всякая коммутативная полугруппа с сокращением:
# Кольцо может быть в поле, если:
# Если T1, T2 - теории сигнатуры с равенством, то:
# Если T1, T2 - теории сигнатуры с равенством, то:
# Если T1, T2 - теории сигнатуры с равенством, то:
# - теорема А теории T1 и отрицающая ее П1-теорема А теории T2:
# Теория Т - П1 аксиоматизируема, если существуют П1-формулы,из которых:
# Чтобы задать подструктуру нормальной интерпретации В, нужно взять подмножество носителя В:
# Теория П1 аксиоматизируема, если она:
# Если теория устойчива относительно перехода к подструктурам, то она:
# Если теория П1 аксиоматизируема, то подструктура ее нормальной модели является:
# Если любая подструктура любой нормальной модели является ее моделью, то теория:
# Теория Т - аксиоматизируема, если существуют -формулы, из которых:
# Теория аксиоматизируема, если она:
# Если теория устойчива относительно перехода к подструктурам, то она:
# Если теория аксиоматизируема, то подструктура ее нормальной модели является:
# Если любая подструктура любой нормальной модели является ее моделью, то теория:
# Любая теория, имеющая П2-аксиоматизацию:
# Любая теория, устойчивая относительно объединения:
# Если S не пусто, , то для того, чтобы F был фильтром нужно:
# Если S не пусто, , то для того, чтобы F был фильтром нужно:
# Если S не пусто, , то для того, чтобы F был фильтром нужно:
# Если S не пусто, , то для того, чтобы F был фильтром нужно:
# Если S не пусто, , то для того, чтобы F был фильтром нужно:
# Если S не пусто, , то для того, чтобы F был фильтром нужно:
# Фильтр на S со свойством или называется:
# Любой главный фильтр является:
# Ультрафильтр - это фильтр:
# Всякий фильтр F на S расширить до ультрафильтра :
# Свойство ультрафильтра отражает:
# Если ультрафильтр неглавный, то:
# Аксиомы равенства в фильтрованном произведении нормальных интерпретаций:
# Голосование можно проводить для:
# Ультрапроизведение семейства моделей некоторой теории моделью той же теории:
# Всякое конечное гипердействительное число бесконечно близко к:
# Среди гипердействительных чисел есть:
# Среди гипердействительных чисел есть:
# Нестандартные гипернатуральные числа:
# Все нестандартные гипернатуральные числа:
# Множество ограничено, если все элементы его гипердействительного аналога:
# Если все элемнеты гипердействительного аналога множества конечны, то:
# Число а - предел ‹ai›, i=0,1,…, если есть бесконечно далекий ak:
# Если существует бесконечно далекий ak из ряда ‹ai›, I=0,1,… который бесконечно близок к а, то:
# Схема "И - НЕ" имеет:
# Схема "ИЛИ - НЕ" имеет:
# Схема "ИСКЛЮЧАЮЩЕЕ - ИЛИ" имеет:
# Сложность булевой функции относительно базисных функций - это:
# Полным набором B булевых функций называется набор, для которого:
# Размером схемы называется число:
# Если A и B - полные наборы булевых функций, то для любой функции:
# Сложность любой булевой -местной функций при наибольшем размере их схем:
# Сложность большинства булевой -местной функций при наибольшем размере их схем:
# Количество всех -местных булевых функций равно:
# Количество всех различных -местных схем размера оценивается:
# При некотором сложность большинства булевых -местных функций:
# Если B - полный базис, то существует :
# Для сложения двух -разрядных двоичных чисел:
# Для сложения двух -разрядных двоичных чисел:
# Для умножения двух -разрядных двоичных чисел существует схема:
# Для умножения двух -разрядных двоичных чисел существует схема:
# Вычитание двух -разрядных двоичных чисел по модулю выполнима схема:
# Для вычисления функции голосования существует схема:
# Для вычисления функции голосования существует схема:
# Если - минимальная глубина схемы, вычисляющая функцию , то:
# Отношение x mod y=0 (x, y - натуральные) является:
# Отношение x>y (x, y - натуральные) является:
# Отношение x + 5=y (x, y - натуральные) является:
# Аксиомой исчисления высказываний является:
# Аксиомой исчисления высказываний является:
# Аксиомой исчисления высказываний является:
# Аксиомой исчисления высказываний является:
# Аксиомой исчисления высказываний является:
# Аксиомой исчисления высказываний является:
# Выводом является:
# Выводом является:
# Выводом является:
# Любая тавтология в исчислении высказываний есть:
# Для любой формулы А, формула А → А есть:
# Если Г - множество формул, то тогда:
# Для любых формул исчисления высказывания А В, С выводима формула:
# Если Г - множество формул, то:
# Если Г - множество формул, то:
# Если А, В, С - формулы, то:
# Если А, В, С - формулы, то:
# Если А, В, С - формулы, то:
# Теоремой исчисления высказываний является:
# Теоремой исчисления высказываний является:
# Теоремой исчисления высказываний является:
# Для произвольных формул А, В:
# Для произвольных формул А, В:
# Для произвольных формул А, В:
# Вариант исчисления высказываний - исчисление:
# Исчисление секвенций - исчисление типа:
# Поиск контрпримера для формулы А сводится к поиску:
# Если А и В - некоторые конечные множества формул, то секвенция обозначается:
# Контрпример к секвенции - это набор значений переменных, для которых все формулы:
# Контрпример к секвенции будет контрпримером к формуле ( - конъюнкция, - дизъюнкция формул из А)
# Верно правило для некоторых конечных множеств формул А, В, С, Д:
# Верно правило для некоторых конечных множеств формул А, В, С, Д:
# Верно правило для некоторых конечных множеств формул А, В, С, Д:
# Секвенция, в обеих частях которой встречаются только переменные, причем хоть одна из них встречается в обеих частях - это:
# Правило вывода в исчислении секвенций - это правило, объявляющее:
# Процесс вывода можно представить:
# Секвенция выводима тогда и только тогда, когда она:
# Формула, представляющая секвенцию :
# Если секвенция выводима в исчислении секвенций, то представляющая ее формула в исчислении высказываний:
# В выводе секвенции принципиально новое, не содержащегося в секвенции всегда:
# Интуиционистское исчисление высказываний получается:
# Интуиционистская логика возникла как попытка формализовать:
# Верна формула:
# Верна формула:
# Верна формула:
# Верна формула:
# Без аксиомы "исключенного третьего" выводима:
# Без аксиомы "исключенного третьего" выводима:
# Если М - непустое множество, то множество всех <m1, m2,…, mk> - это:
# k-местной функцией на М является:
# Количество синонимов в списке ‹"арность", "местность", "валентность", "эквивалентность"› равна:
# Унарным предикатом на множестве М будет:
# Бинарным предикатом на множестве М будет:
# Тернарным (тренарным) предикатом на множестве М будет:
# Количество различных 0-местных предикатов равно:
# Количество различных 1-местных предикатов:
# Количество 2-местных предикатов:
# Набор символов-обозначений в формулах с неотрицательными числами называется:
# Конструктивно определяемая последовательность переменных, занятых, скобок и символов сигнатуры называется:
# Если А - предикатный символ валентности k, t1, t2, …, tk - термы, то выражение А(t1, t2, …, tk) - это:
# Формулу можно построить с использованием правила:
# Формулу можно построить с использованием правила:
# Формулу можно построить с использованием правила:
# Формулу можно построить с использованием правила:
# Формулу можно построить с использованием правила:
# Если А - формула, а x - ее индивидная переменная, то:
# Чтобы задать интерпретацию сигнатуры S, необходимо:
# Чтобы задать интерпретацию сигнатуры S, необходимо:
# Чтобы задать интерпретацию сигнатуры S, необходимо:
# Параметром формулы A может быть:
# Параметром формулы A может быть:
# Параметром формулы A может быть:
# Арифметические формулы определяются сигнатурой S, носителем N вида:
# Арифметическое множество - это множество:
# Множество натуральных чисел, не являющееся арифметическим:
# Предикат определяемый формулой :
# Предикат определяемый формулой x=const:
# Предикат определяемый формулой :
# Предикат определяемый формулой :
# Предикат :
# Предикат z=НОД(x,y), :
# Предикат "двоичное слово x состоит только из нулей":
# Предикат "двоичные слова x и y имеют одинаковую длину":
# Предикат "z=x+y", где "+" - конкатенация двоичных слов:
# Предикат "двоичное слово x - начало двоичного слова y":
# Предикат "двоичное слово x - конец двоичного слова y":
# Предикат "двоичное слово x входит в двоичного слова y":
# Предикат "x - простое число номер n":
# Предикат "x=2n", n - натуральное:
# Предикат "x=4n", n - натуральное:
# Предикат "x>y", x,y - целое:
# Биекция - автоморфизм интерпретации, если все функции и предикаты интерпретации:
# n - местный предикат P - устойчив относительно автоморфизма , если:
# Предикат, выразимый в данной интерпретации:
# Класс выразимых предикатов:
# Всякая формула в , где +1 - функция прибавления 1:
# В элиминация кванторов:
# Выразимые в арифметике Пресбургера предикаты - это бескванторные формулы из:
# В теории действительных чисел со сложением и умножением, элиминация кванторов:
# Если удалить символ < из сигнатуры , класс выразимых предикатов:
# Бескванторная формула сигнатуры :
# Бескванторная формула сигнатуры :
# Для всякой формулы F сигнатуры существует бескванторная формула, задающая F на R - это:
# Число возможных диаграмм семейства многочленов:
# Для семейства многочленов Pn(x), отбрасывание старшего члена:
# Для семейства многочленов Pn(x), взятие старшего коэффициента:
# Для семейства многочленов Pn(x), дифференцирование по X:
# Для сигнатуры и носителя С (комплексные числа) всякая формула:
# Для некоторой сигнатуры S две ее интерпретации называются элементарно эквивалентными, если:
# Верно утверждение:
# Две интерпретации - изоморфны, если между ними существует:
# Тождественное отображение:
# Отображение, обратное изоморфизму будет:
# Композиция двух изоморфизмов:
# Естественные интерпретации сигнатуры на носителе R:
# Если всякий многочлен Pn(x),n>0 имеет в поле X хотя бы один корень, то:
# Минимальное число слагаемых в сумме вида 1+1+…+1, при котором она обращается в нуль - это:
# Любые два алгебраически замкнутых поля характеристики О:
# Любые два алгебраически замкнутых поля конечной характеристики n:
# Если группа - интерпретация сигнатуры , то подструктуры - это:
# В игре Эренфойхта игроков:
# Игроки игры Эренфойхта называются:
# Игра Эренфойхта определяется:
# В игре Эренфойхта игроки:
# В игре Эренфойхта:
# В игре Эренфойхта:
# В игре Эренфойхта, если есть предикат сигнатуры, различающий помеченные элементы интерпретации, то:
# У Консерватора есть способ выиграть если интерпретации:
# Для упорядоченных множеств сигнатуры и носителей N и Z:
# Для упорядоченных множеств сигнатуры и носителей Z и Q:
# Для упорядоченных множеств сигнатуры и носителей Z и R:
# Для упорядоченных множеств сигнатуры и носителей R и Q:
# Число ходов Новатора соответствует:
# Глубина атомарных формул равна:
# Глубина формулы равна:
# Глубина формулы равна:
# Глубина формулы равна:
# Глубина формулы :
# Глубина формулы :
# Две формулы с параметрами эквивалентны, если они одновременно:
# Итерации A и B элементарно эквивалентны тогда и только тогда, когда в соответствующей игре Эренфойхта:
# Любые два плотно упорядоченных множества без первого и последнего элемента:
# Для счетной (конечной) сигнатуры и бесконечной ее интерпретации M:
# Для счетного (конечного) подмножество интерпретации M:
# Исчисление предикатов построено над:
# Формула, истинная в любой интерпретации сигнатуры называется:
# Если в тавтологию вместо пропозициональных переменных подставить формулы сигнатуры, получим:
# Общезначима формула:
# Общезначима формула:
# Общезначима формула:
# Общезначима формула:
# Не общезначима формула:
# Не общезначима формула:
# Формулы А и В эквивалентны, если формула:
# Формулы А и В эквивалентны, если они обе:
# Формулы А и В эквивалентны, если формула:
# Формула, истинная в некоторой интерпретации на некоторой оценке называется:
# Двойственна к выполнимости:
# Вхождение индивидной переменной, не из области действия одноименного квантора называется:
# Любое вхождение переменной в терм:
# Любое вхождение переменной в атомарную формулу:
# Если х - свободное вхождение в формулу А, то оно всегда:
# Если х - свободное вхождение в формулу А или В, то оно:
# Если х - свободное вхождение в формулу А или В, то оно:
# Если х - свободное вхождение в формулу А или В, то оно:
# Всякая выводимая в исчислении предикатов формула:
# Все теоремы теории Г:
# Если выводима формула А(с/х), где А - формула, х - переменная, с - константа не входящая в А, то тогда: