Математическая логика и теория алгоритмов

Утверждение image059.gif формально записывается как
image060.gif
image061.gif
image062.gif
image063.gif
Два вида правил, называемых правилами образования и правилами преобразования, содержит теория, которая называется
дедуктивная теория
теория парадоксов
теория множеств
аксиоматическая теория
Когда image028.gif и рекурсия проводится по image029.gif, функцияimage030.gif равна
image031.gif
1
0
image021.gif
Функция является примитивно рекурсивной, если она получается из набора исходных функций с помощью оператора: 1) рекурсии; 2) ограниченной минимизации; 3) подстановки - из перечисленного
1, 2 и 3
1 и 3
1 и 2
1
Экспликация - строгая (математическая) формулировка понятия
содержательного
интуитивного
содержательного или интуитивного
содержательного и интуитивного
Рекурсивное множество является ______ всюду определенной вычислимой функции
ни множеством значений, ни областью определения
только множеством значений
только областью определения
множеством значений и областью определения
Теорема, связывающая рекурсивности множества с рекурсивной перечислимостью этого множества и его дополнения, называется теоремой
Гёделя
Тьюринга
Клини
Поста
При image098.gif функция image002.gif(n,m) в рекуррентной формуле равна
(m+n)/2
m+n+1
2m
m+n-1
Дедуктивные рассуждения преобладают в науках, которые принято называть
точными
гуманитарными
естественно-научными
техническими
Для каждой рекурсивно аксиоматизированной формальной системы множество доказуемых утверждений
рекурсивно перечислимо
нерекурсивно
разрешимо
неперечислимо
Правилами употребления характеризуется знак, который носит название
переменная
постоянная
константа
предикат
Входной алфавит определяется как
image075.gif
image074.gif
image072.gif
image073.gif
Принадлежность элемента некоторому множеству обозначается знаком
image080.gif
Î
image081.gif
Ï
Множество доказуемых утверждений формальной системы арифметики
разрешимо
замкнуто
неразрешимо
открыто
Высказывание - это предикатная
константа
постоянная
переменная
выражение
Логику, являющуюся многозначной логикой, что позволяет определить промежуточные значения для таких общепринятых оценок, как да|нет, истинно|ложно, черное|белое, называют
модальной
математической
нечеткой
логикой высказываний
Соединяемые функтором фразы называются
аргументами
регулярными
предложениями
формульными
Машина Тьюринга есть совокупность компонент
пяти
трех
двух
четырех
Нечеткое множество, высота которого меньше 1, называется
субнормальным
нормальным
одиночным
единичным
Примером семантического парадокса может(-гут) служить
парадокс Берри
парадокс лжеца
парадоксы лжеца и Берри
парадокс Рассела
Множество натуральных чисел является
только рекурсивным
рекурсивным и перечислимым
только перечислимым
простейшим
Примем, что R - рекурсивность, а P - рекурсивная перечислимость. Тогда
image113.gif
image111.gif
image114.gif
image112.gif
Комбинация знаков, содержащая знаки переменных, которая превращается в высказывание при замене переменных именами предметов, называется
именная форма
иносказательная форма
высказывательная форма
абстрактная форма
С целью составления предикатных функций используют
множества
выражения
высказывания
отношения
Согласно_________ всякая вычислимая функция является вычислимой по Тьюрингу
теореме Поста
лемме Тьюринга
тезису Чёрча
теореме Гёделя
Интуитивное представление о «вычислительной процедуре» существовало давно, и за этими процедурами был закреплен специальный термин
парадокс
алгоритм
высказывание
множество
Функция image043.gif имеет гёделевский номер, равный
5
4
2
1
Множество составных чисел является
только перечислимым
порождающим
только рекурсивным
рекурсивным и перечислимым
Умозаключения - элементарные рассуждения, в которых из одного или нескольких суждений получается еще одно суждение, называемое
суждением
посылками
заключением
экспликацией
Функция image044.gif имеет гёделевский номер, равный
3
13
9
19
Существуют три основных класса фраз: имена, предложения и
дизъюнкты
предикаты
функторы
кванторы
Пространственные или временные характеристики процесса вычисления называются
вычислительными ресурсами
интерпретацией системы
представлением системы
классом сложности
Логику можно разделить на формальную и
математическую
логику высказываний
логику предикатов
логику Буля
Дополнение к области определения некоторой вычислимой функции _________ рекурсивно перечислимым
не может быть
разъединено с
может не быть
должно быть
a-уровнем нечеткого подмножества А универсального множества U называется такое подмножество image092.gifуниверсального множества U, для которого верно
image093.gif
image096.gif
image095.gif
image094.gif
Выражение (комбинация знаков), содержащее знаки «переменных», которое превращается в имя предмета, если вместо «переменных» поставить надлежащим образом выбранные имена предметов, называется
иносказательная форма
именная форма
высказывательная форма
абстрактная форма
Когда image102.gif и рекурсия проводится по переменной image021.gif, функция image101.gif равна
m+x
2+m
m+1
m+y
Любая неразрешимая алгоритмическая проблема дает пример множества
неперечислимого
неразрешимого
несчетного
невычислимого
Класс примитивно рекурсивных функций
расширяет класс вычислимых функций
содержит в себе класс вычислимых функций
совпадает с классом вычислимых функций
входит в класс вычислимых функций
Согласно _______________не существует формальной системы арифметики, удовлетворяющей условиям полноты и противоречивости
теореме Поста
теории Гильберта
тезису Черча
теореме Геделя
Атомарная формула или ее отрицание называется
дизъюнктом
литерой
конъюктом
предикатом
Возможность существования универсальной вычислительной машины, способной выполнить любую эффективную процедуру, показал
А. Марков
А. Тьюринг
К. Гёдель
Д. Гильберт
Способ выбора подкласса истинных высказываний, принадлежащих классу элементарных высказываний, - это
теория
теорема
выражение
предложение
Если множество нерекурсивно, то оно _______ областью определения и ______ множеством значений всюду определенной вычислимой функции
может быть, может быть
не может быть, может быть
не может быть, не может быть
может быть, не может быть
Полнота - это условие, что для любого утверждения s одно из утверждений s и Øs
доказуемо
истинно
ложно
опровержимо
Для обозначения какой-либо связи между предметами или понятиями используется математический термин, который называется
суждение
отношение
выражение
вывод
Функция, равная единице тогда и только тогда, когда предикат истинен, называется
вычислимой
характеристической
примитивно вычислимой
частично рекурсивной
Другое название семантических парадоксов-
порадоксамы теории множеств
порадоксамы Рассела
эпистемологические
логические
Функция image009.gif вычисляется по формуле
image012.gif
image011.gif
image013.gif
image010.gif
В рекурсивно аксиоматизированной формальной системе, в которой все доказуемые утверждения истинны, существует истинное утверждение s, так что: 1) s опровержимо; 2) Øs опровержимо
1
2
ни 1, ни 2
1 и 2