Электронный экзамен

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

"uIA? : mA (u) ? ?

x, y,z – вещественные числа. Эквивалентна утверждению х ?y запись

$z (x+z=y)

x, y,z – вещественные числа. Эквивалентна утверждению х I[y, z] запись

$t (x+t=z) U (y+t=x)

Автомат, однократно считывающий входную строку слева направо, называется

конечным

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

общего к частному

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

литерой

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

предложением

В 1–й строке матрицы переходов конечного автомата находятся

символы алфавита

В 1–м столбце матрицы переходов конечного автомата находятся

все возможные состояния автомата

В алфавит формального логического языка входят символы

1) ",2) $,3) U,

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

1) математическую логику,2) формальную логику,

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

$

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

рекурсивно перечислимо

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

1) необходимости,2) возможности,

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

матрицы

В основе описания нечеткой логики лежит теория нечетких

множеств

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

1) высказывания,2) высказывательные формы,

В системе арифметики натуральных чисел Пеано единственным неопределимым отношением является

y = x/

В состав конечного автомата входят следующие элементы

1) читающая головка,2) лента, разбитая на ячейки,

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

1) констант,2) функциональных символов,3) предикатных символов,

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

состояние, в которое переходит автомат

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

вычислительными ресурсами

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

рекурсивно перечислимое, множеством значений

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

высказыванием

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

именной

Выражение «множество А содержится в множестве В» записывается как

AIB

Выражение qi, аj Пql является ___________ машины Тьюринга

командой

Высказывание – это

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

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

алгоритмом

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

23

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

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

Даны два числовых множества А={1,2,3,4,5} и B={2,5,9}. Установите соответствие между типом операции над данными множествами и ее результатом:

AEB >>>> {1,2,3,4,5,9},ACB >>>> {2,5},A/B >>>> {1,3,4},

Даны два числовых множества А={3,5,7} и B={2,4,6,8}. Установите соответствие между типом операции над данными множествами и ее результатом:

AEB >>>> {2,3,4,5,6,7,8},ACB >>>> {?},A/B >>>> {3,5,7},

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

эпистемологический

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

2m

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

–m

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

m(n+1)

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

m+1

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

m+y

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

x

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

m+x

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

у

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

0

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

1

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

e31(x, y, z) + e33(x, y, z)

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

m + 1

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

zx

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

0

Если А и В – рекурсивные множества, то рекурсивны также множества 1) AEB; 2) ACB

1 и 2

Если А рекурсивно, а В – рекурсивно перечислимо, то множество _________ рекурсивно

В\А

Если высота нечеткого множества меньше 1, то оно называется

субнормальным

Если высота нечеткого множества равна 1, то оно называется

нормальным

Если множество рекурсивно, то оно ___________________ всюду определенной вычислимой функции

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

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

словом

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

переменная

Знаком принадлежности элемента некоторому множеству является символ

I

Интерес к логике оживился в ______ столетии под влиянием открытия неевклидовых геометрий (ответ укажите римскими цифрами)

XIX

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

упорядоченности

Каждая п. р.ф. (примитивно–рекурсивная функция) имеет число геделевских номеров

бесконечное

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

входит в класс

Количество типов команд машины Тьюринга равно ________ (ответ укажите цифрой)

3

Команда машины Тьюринга состоит из __________ элементарных действий (ответ укажите цифрой)

2

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

высказывательной

Конечному автомату соответствует грамматика, порождающая

регулярный язык

Конечные автоматы могут быть следующих типов:

1) детерминированные,2) недетерминированные,

Концептуальное отличие нечеткой логики от классической заключается в том, что она оперирует

не только значениями "истина" и "ложь", но и промежуточными значениями

Логика Буля основывается на

отношении эквивалентности

Логика высказываний и логика предикатов базируются на

отношении порядка

Логику можно определять как науку о(об)

правильных способах рассуждения

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

нечеткой

Логическая связка дизъюнкция высказываний А и В обозначается как

А U В

Логическая связка импликация обозначается как

А®В

Логическая связка конъюнкция высказываний А и В обозначается как

А U В

Логическая связка эквивалентность обозначается

А ~ В

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

предикатом

Логическое выражение A, где А – высказывание, обозначает

отрицание

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

неразрешимого

Марковский алгоритм носит также название ___________ алгоритма

нормального

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

1) Тьюринг,2) Пост,

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

Гильберт

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

отношением

Множество A есть подмножество множества В в том и только в том случае, если каждый элемент множества А является

элементом множества B

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

формальную систему

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

неперечислимым

Множество всех истинных утверждений языка L является

неразрешимым и неперечислимым

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

неразрешимо

Множество истинных утверждений

не выводится из системы аксиом

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

1) рекурсивности,2) перечислимости,

Множество номеров самоприменимой машины Тьюринга

1) рекурсивно перечислимо,2) неразрешимо,

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

1) рекурсивности,2) перечислимости,

Множество, если его характеристический предикат является вычислимым, называется

рекурсивным

Множество, если оно является множеством значений некоторой вычислимой функции, называется

рекурсивно перечислимым

Наиболее часто на практике используется опрос экспертов

индивидуальный косвенный

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

логикой

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

точными

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

минимизации

Нечеткая логика – это надмножество логики

Буля

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

отображение

Объединение множеств А и В обозначается как

АEВ

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

множеством

Одним из самых распространенных методов опросов экспертов является метод парных сравнений, лежащий в основе метода анализа иерархий, предложенного

М. Саати

Осмысленные конечные последовательности символов из алфавита L называются

утверждениями

Основные типы рассуждений, которые принято выделять в логике называются

1) индуктивными,2) дедуктивными,

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

S(S(x))

Переменные, фигурирующие в кванторах всеобщности и существования, называются ___________________ переменными

связанными

Пересечение множеств А и В обозначается как

A C В

Переход конечного автомата происходит

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

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

1) имена предметов,2) именные формы,

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

доказуемо

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

выводом

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

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

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

Рассела

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

1) лжеца,2) Берри,

Пусть R обозначает свойство рекурсивности, а Р – рекурсивной перечислимости. Тогда

R®P

Разность между множествами А и В обозначается

А \ В

Свойства, которыми может обладать не рекурсивное множество:

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

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

непротиворечивостью

Символы, которые машина Тьюринга читает и пишет на ленте, образуют

внешний алфавит

Символы, которые определяют внутреннее состояние машин Тьюринга, образуют

внутренний алфавит

Система аксиом Пеано содержит ______ аксиом (ответ дайте цифрой)

5

Система теоретико-множественных операций над высказываниями, которые являются элементами множества, называется ________________ высказываний

алгеброй

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

формальным

Создателем формальной логики был

Аристотель

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

представлением

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

языком

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

модальностью

Существуют следующие классы фраз:

1) функторы,2) предложения,3) имена,

Существуют следующие формы записи работы конечного автомата:

1) набор команд,2) матрица переходов,3) граф состояний,

Теорема – «Множество тогда и только тогда разрешимо, когда оно само и его дополнение рекурсивно перечислимы», называется теоремой

Поста

Теорема о том, что не существует формальной системы арифметики, удовлетворяющей условиям полноты и непротиворечивости, носит имя ______ (укажите фамилию)

Геделя

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

математической логики

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

"

Укажите ограничения, накладываемые на базовые термы лингвистической переменной,

1) упорядоченность,2) полнота,3) согласованность,4) нормальность,5) ограниченность,

Укажите соответствие между названием логической операции и ее обозначением:

дизъюнкция >>>> U,конъюнкция >>>> U,импликация >>>> ®,эквиваленция >>>> ~,

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

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

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

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

Укажите соответствие между понятиями теории конечных автоматов и их содержанием:

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

Укажите соответствие между понятиями теории множеств и их содержанием:

множество >>>> объединение произвольного количества определенных отличных друг от друга объектов, подмножество >>>> множество А есть подмножество множества В в том и только в том случае, если каждый элемент множества А есть также элемент множества В, мощность множества >>>> критерий оценки размерности множества, пустое множество >>>> множество, не содержащее элементов,

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

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

Укажите соответствие между понятиями, характеризующими машину Тьюринга, и их содержанием:

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

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

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

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

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

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

заключением

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

0

Установите соответствие логических выражений их равносильным выражениям:

xUx >>>> x, xU1 >>>> 1,xU0 >>>> 0,xUy >>>> y U x,

Установите соответствие логических выражений их равносильным выражениям:

x U y >>>> y U x,x U y >>>> y U x,x U (y U z) >>>> (x U y) U z,x U (y U z) >>>> (x U y) U z,

Установите соответствие между п. р.ф. и ее геделевским номером:

0(x) >>>> 2,S(x) >>>> 3,e11(x) >>>> 5,e21(x, y) >>>> 7,

Установите соответствие между предикатом и областью истинности предиката:

x + 5 = 1 >>>> –4,x2 < 0 >>>> ?,x2 – 1 = 0 >>>> +1; –1,

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

интерпретацией теории

Утверждение, что всякая вычислимая функция является вычислимой по Тьюрингу, называется тезисом _________ (укажите фамилию в родительном падеже)

Черча

Формализованный язык для однозначной записи алгоритмов называется ________________ языком

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

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

порождающей

Формула в теории, для которой существует механизм вывода в рамках этой теории, называется

разрешимой

Формула, которая истинна при всех интерпретациях, называется

общезначимой

Функция 0(х) имеет геделевский номер, равный ______ (ответ укажите цифрой)

2

Функция e11 имеет геделевский номер, равный ______ (ответ укажите цифрой)

5

Функция e31(x, y, z) + e32(x, y, z) равна

x + y

Функция e33 имеет геделевский номер, равный ______ (ответ укажите цифрами)

19

Функция S(х) имеет геделевский номер, равный _____ (ответ укажите цифрой)

3

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

1) подстановки,2) рекурсии,3) минимизации,

Функция х+у: 1); 2); 3) обладает следующими свойствами:

1) примитивно рекурсивна,2) частично рекурсивна,

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

1) рекурсии,2) подстановки,

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

частично рекурсивной

Функция, вычисляемая некоторой машиной Тьюринга, называется

вычислимой

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

временным ресурсом

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

вычислимой

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

характеристической

Частично вычислимая функция может быть продолжена до

вычислимой

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

математическая

Челночный алгоритм является модификацией ___________ алгоритма

марковского

Число компонент машины Тьюринга равно _____ (ответ укажите цифрой)

5

Число символов, которое может находиться в ячейке ленты конечного автомата, равно _____ (ответ укажите цифрой)

1

Язык логики предикатов является расширением языка логики

высказываний

Язык, на котором описывается другой язык, называется

метаязыком

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

логико-математическим