Математическая логика. Часть 1

Идею использования рекурсии для решения задач, связанных с основаниями математики, предложил

Последовательное применение ряда формул теории, такое, что любая формула этого ряда есть либо аксиома этой теории, либо непосредственное следствие из применения предыдущих формул, называется

• парадоксом
• выводом
• выражением
• отношением

Правильность слова, записанного на ленте конечного автомата, определяется по состоянию автомата

• до прочтения слова
• после прочтения второго символа слова
• после прочтения последнего символа слова
• после прочтения первого символа слова

Язык, предложения (формулы) которого выражают суждения и отношения исследуемой математической теории, называется

• логико-математическим
• искусственным
• программирования
• формальным

Функция является примитивно рекурсивной, если она получается из набора исходных п.р.ф. с помощью операторов

• рекурсии
• ограниченной минимизации
• подстановки

Соотнесите понятия теории алгоритмов и их содержание:

• нормальный алгоритм
• способ решения задачи, точно предписывающий как и в какой последовательности получить результат, однозначно определяемый исходными данными
• примитивно рекурсивные функции
• модификация марковского алгоритма
• челночный алгоритм
• арифметические функции, которые сопоставляются по определенным правилам, примитивно рекурсивным описаниям
• алгоритм
• ряд предписаний в форме подстановок в определенном алфавите

Существуют следующие типы конечных автоматов:

• детерминированные
• перечислимые
• недетерминированные
• рекурсивные

Под термом имеются ввиду следующие понятия:

• имена предметов
• именные формы
• предложения
• слова

Установление соответствия между элементарными высказываниями формальной теории и содержательными высказываниями некоторой предметной области называется

• классом функторов
• порождающей грамматикой
• интерпретацией теории
• эффективной процедурой

В логике принято выделять следующие основные типы рассуждений:

• предикативные
• индуктивные
• информационные
• дедуктивные
• доказуемые

П.р.ф. S2 (х) = х + 2 вычисляется по формуле

• S2(x)
• S(х+3)
• S{х+2)
• S(S(x))

Примитивную рекурсивность не сохраняет оператор

• рекурсии
• минимизации
• подстановки
• сдвига

Класс примитивно рекурсивных функций ________________________ вычислимых функций

• содержит в себе класс
• дополняет класс
• входит в класс
• совпадает с классом

Любое повествовательное предложение, о котором имеет смысл говорить, что оно (его содержание) истинно или ложно, называется

• выводом
• отношением
• высказыванием
• выражением

Примером логического парадокса может служить парадокс

• лжеца
• Лейбница
• Рассела
• Берри

Установите соответствие между типом операции над высказывания: А = «на улице идет дождь» и В = «над моей головой раскрыт зонтик» и результирующим высказыванием:

• импликация А на В
• над моей головой раскрыт зонтик тогда и только тогда, когда на улице идет дождь
• дизъюнкция А и В
• на улице идет дождь и над моей головой раскрыт зонтик
• конъюнкция А и В
• или на улице идет дождь или над моей головой раскрыт зонтик
• эквиваленция В и А
• если на улице идет дождь, то над моей головой раскрыт зонтик

Множество простых чисел обладает свойствами

• рекурсивности
• перечислимости
• замкнутости
• ограниченности

Всякое непустое _________________ множество является ______________ некоторой всюду определенной вычислимой функции

• рекурсивное, областью определения
• рекурсивно перечислимое, множеством значений
• креативное, областью определения
• продуктивное, множеством значений

Геделевский номер функции S(х) равен _____ (ответ укажите цифрой)

Геделевский номер функции 0(х) равен ______ (ответ укажите цифрой)

Теория алгоритмов является частью

• теории чисел
• численных методов
• математического анализа
• математической логики

Соотнесите понятия, характеризующие теорию формальных систем, и их содержание:

• аксиоматический метод
• исходное положение научной теории, принимаемое без доказательств
• интерпретация теории
• способ рассмотрения объектов формальной системы как конкретных объектов при условии, что конкретные объекты сохраняют структуру формальных
• представление системы
• установление соответствия между высказываниями теории и содержательными высказываниями предметной области
• аксиома
• способ построения научной теории, когда в основу кладутся исходные положения, называемые аксиомами

Нечеткое отношение – это заданное определенным образом

• отношение
• высказывание
• отображение
• декартово произведение

Комбинация знаков, содержащая знаки переменных, которая превращается в высказывание при замене переменных именами предметов, называется _____________________ формой

• именной
• иносказательной
• высказывательной
• абстрактной

Вычислимая по Тьюрингу функция является

• общерекурсивной
• примитивно рекурсивной
• характеристической
• частично рекурсивной

Если f(x,y,z) = z•х+у и рекурсия проводится по переменной z, то функция h(х,у,z,m) равна

• m+x
• m+х+у+z
• mx
• my

Термин «некоторые» или «существует хотя бы одно значение» в логике предикатов обозначается через

• È
• Ú
• $
• «

К термам лингвистической переменной предъявляется лишь требование

• истинности
• не отрицательности
• не противоречивости
• упорядоченности

Если f(n) = cos(pn), то функция h(n,m) в рекуррентной формуле равна

• m+1
• –m
• sin(pn)
• 1– cos(pn)

Соотнесите понятия логики и их содержание:

• умозаключение
• мысль, отражающая в обобщенной форме предметы и явления действительности и связи между ними посредством фиксации общих и специфических признаков
• суждение
• строгая формулировка содержательного или интуитивного понятия
• экспликация
• умственный акт, выражающий отношение говорящего к содержанию высказанной мысли
• понятие
• умственное действие, связующее в ряд посылок и следствий мысли различного содержания

Усеченная разность чисел 5 и 8 (5÷8) равна _____ (ответ укажите цифрой)

Для вещественныех чисел x,y,z утверждению х Î[y,z] эквивалентна запись

• $t (x+t=z) Ù (y+t=x)
• «t (x+t=z) Ù (y+t=x)
• $t (y+t=z) Ù (y+t=x)
• $t (x+t=z) Ú (y+t=x)

Если f(х, у) = хy и рекурсия проводится по у, то функция g(х) равна _____ (ответ укажите цифрой)

В любой рекурсивно аксиоматизированной формальной системе множество доказуемых утверждений

• нерекурсивно
• рекурсивно перечислимо
• неперечислимо
• разрешимо

В систему аксиом Пеано входит ______ аксиом (ответ дайте цифрой)

Если f(х,y) = ху и рекурсия проводится по у, то функция h(х,y,z) равна

• x+z
• zx
• zy
• z

Основу метода парных сравнений составляет процедура обработки результатов опроса экспертов, представленных в виде

• матрицы
• уравнения
• функциональной зависимости
• отношения

Соотнесите понятия теории формальных грамматик и их содержание:

• грамматика
• средство соединения фраз для образования других фраз
• метаязык
• комбинации символов, образующие грамматические единицы
• фразы
• язык, на котором описывается другой язык
• функтор
• правила, определяющие предложения языка

Соотнесите название логической операции и ее обозначение:

• дизъюнкция
• ~
• конъюнкция
• ®
• импликация
• Ù
• эквиваленция
• Ú

Множество аксиом вместе с явным определением доказательства составляют

• рекурсивное множество
• машину Тьюринга
• теорию алгоритмов
• формальную систему

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

• предикатов
• Буля
• высказываний
• математической

_____________ называется способ понимания суждения об объекте, явлении или событии называется

• Выводом
• Отношением
• Модальностью
• Выражением

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

• выражения
• высказывательные формы
• отношения
• выводы
• высказывания

В модальную логику входят понятия

• перечислимости
• необходимости
• возможности
• рекусивности

Если f(x,y) = х+у и рекурсия проводится по переменной у, то функция g(x) равна

• x+2
• x
• 2x
• x+1

Если f(х, у, z) = х + у2 + z и рекурсия проводится по у , то функция g{х, z) равна

• e31(x, y, z) + e33(x, y, z)
• S(x) + S(y)
• 0
• x +y

В язык первого порядка входят множества

• функциональных символов
• предикатных символов
• констант
• натуральных чисел

Запись _________ служит для обозначения пересечения множеств А и В

• А В
• A Ç В
• А + В
• АÈВ

Соотнесите характеристики сложности алгоритмов и их содержание:

• классы сложности
• средства измерения объема ресурсов, потребляемых в процессе вычислений
• сложность
• временные или пространственные характеристики процесса вычислений
• вычислительные ресурсы
• трудность решения задачи, измеренная в терминах некоторого ресурса, потребляемого в процессе вычислений
• критерий сложности
• способ группировки алгоритмов в соответствии с их сложностью

Для присвоения, хранения, обработки и передачи информации используется способ обозначения определенного понятия, предмета, свойства, который называется

• языком
• выражением
• списком
• словом