Главная /
Языки и исчисления
Языки и исчисления - ответы на тесты Интуит
В курсе рассказывается об основных понятиях математической логики (логика высказываний, языки первого порядка, выразимость, исчисление высказываний, разрешимые теории, теорема о полноте, начала теории моделей).
Список вопросов:
- # Если 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:
- # Исчисление предикатов построено над:
- # Формула, истинная в любой интерпретации сигнатуры называется:
- # Если в тавтологию вместо пропозициональных переменных подставить формулы сигнатуры, получим:
- # Общезначима формула:
- # Общезначима формула:
- # Общезначима формула:
- # Общезначима формула:
- # Не общезначима формула:
- # Не общезначима формула:
- # Формулы А и В эквивалентны, если формула:
- # Формулы А и В эквивалентны, если они обе:
- # Формулы А и В эквивалентны, если формула:
- # Формула, истинная в некоторой интерпретации на некоторой оценке называется:
- # Двойственна к выполнимости:
- # Вхождение индивидной переменной, не из области действия одноименного квантора называется:
- # Любое вхождение переменной в терм:
- # Любое вхождение переменной в атомарную формулу:
- # Если х - свободное вхождение в формулу А, то оно всегда:
- # Если х - свободное вхождение в формулу А или В, то оно:
- # Если х - свободное вхождение в формулу А или В, то оно:
- # Если х - свободное вхождение в формулу А или В, то оно:
- # Всякая выводимая в исчислении предикатов формула:
- # Все теоремы теории Г:
- # Если выводима формула А(с/х), где А - формула, х - переменная, с - константа не входящая в А, то тогда: