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

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

Два вида правил, называемых правилами образования и правилами преобразования, содержит теория, которая называется

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

Когда  и рекурсия проводится по , функция равна

• 1
• 0

Функция является примитивно рекурсивной, если она получается из набора исходных функций с помощью оператора: 1) рекурсии; 2) ограниченной минимизации; 3) подстановки — из перечисленного

• 1, 2 и 3
• 1 и 3
• 1 и 2
• 1

Экспликация — строгая (математическая) формулировка понятия

• содержательного
• интуитивного
• содержательного или интуитивного
• содержательного и интуитивного

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

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

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

• Гёделя
• Тьюринга
• Клини
• Поста

При  функция (n,m) в рекуррентной формуле равна

• (m+n)/2
• m+n+1
• 2m
• m+n-1

Дедуктивные рассуждения преобладают в науках, которые принято называть

• точными
• гуманитарными
• естественно-научными
• техническими

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

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

Правилами употребления характеризуется знак, который носит название

• переменная
• постоянная
• константа
• предикат

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

Принадлежность элемента некоторому множеству обозначается знаком

• Î
• Ï

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

• разрешимо
• замкнуто
• неразрешимо
• открыто

Высказывание — это предикатная

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

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

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

Соединяемые функтором фразы называются

• аргументами
• регулярными
• предложениями
• формульными

Машина Тьюринга есть совокупность компонент

• пяти
• трех
• двух
• четырех

Нечеткое множество, высота которого меньше 1, называется

• субнормальным
• нормальным
• одиночным
• единичным

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

• парадокс Берри
• парадокс лжеца
• парадоксы лжеца и Берри
• парадокс Рассела

Множество натуральных чисел является

• только рекурсивным
• рекурсивным и перечислимым
• только перечислимым
• простейшим

Примем, что R — рекурсивность, а P — рекурсивная перечислимость. Тогда

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

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

С целью составления предикатных функций используют

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

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

• теореме Поста
• лемме Тьюринга
• тезису Чёрча
• теореме Гёделя

Интуитивное представление о «вычислительной процедуре» существовало давно, и за этими процедурами был закреплен специальный термин

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

Функция  имеет гёделевский номер, равный

• 5
• 4
• 2
• 1

Множество составных чисел является

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

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

• суждением
• посылками
• заключением
• экспликацией

Функция  имеет гёделевский номер, равный

• 3
• 13
• 9
• 19

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

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

Пространственные или временные характеристики процесса вычисления называются

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

Логику можно разделить на формальную и

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

Дополнение к области определения некоторой вычислимой функции _________ рекурсивно перечислимым

• не может быть
• разъединено с
• может не быть
• должно быть

a-уровнем нечеткого подмножества А универсального множества U называется такое подмножество универсального множества U, для которого верно

Выражение (комбинация знаков), содержащее знаки «переменных», которое превращается в имя предмета, если вместо «переменных» поставить надлежащим образом выбранные имена предметов, называется

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

Когда  и рекурсия проводится по переменной , функция  равна

• m+x
• 2+m
• m+1
• m+y

Любая неразрешимая алгоритмическая проблема дает пример множества

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

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

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

Согласно _______________не существует формальной системы арифметики, удовлетворяющей условиям полноты и противоречивости

• теореме Поста
• теории Гильберта
• тезису Черча
• теореме Геделя

Атомарная формула или ее отрицание называется

• дизъюнктом
• литерой
• конъюктом
• предикатом

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

• А. Марков
• А. Тьюринг
• К. Гёдель
• Д. Гильберт

Способ выбора подкласса истинных высказываний, принадлежащих классу элементарных высказываний, — это

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

Если множество нерекурсивно, то оно _______ областью определения и ______ множеством значений всюду определенной вычислимой функции

• может быть, может быть
• не может быть, может быть
• не может быть, не может быть
• может быть, не может быть

Полнота — это условие, что для любого утверждения s одно из утверждений s и Øs

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

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

• суждение
• отношение
• выражение
• вывод

Функция, равная единице тогда и только тогда, когда предикат истинен, называется

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

Другое название семантических парадоксов-

• порадоксамы теории множеств
• порадоксамы Рассела
• эпистемологические
• логические

Функция  вычисляется по формуле

В рекурсивно аксиоматизированной формальной системе, в которой все доказуемые утверждения истинны, существует истинное утверждение s, так что: 1) s опровержимо; 2) Øs опровержимо

• 1
• 2
• ни 1, ни 2
• 1 и 2