Тест по "Математической логике"

Высказывание о предметных переменных X1, …, Xn – это:

• n-местный предикат

Дизъюнкт, не содержащий ни одного литерала, называется:

• пустым

Дизъюнкцией двух высказываний A и B называется такое высказывание, которое:

• истинно, когда истинно хотя бы одно из данных высказываний

Для слова 101 в алфавите А = {0 , 1} Гёделевским номером будет число:

• 300

Если f(x1,…, xn, 0 ) = g( x1,…, xn) ,f( x1,…,xn , y+1) = h(x1,…,xn , y, f(x1,…,xn , y)), то эта операция называется:

• примитивно рекурсивной

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

• линейной

Если система функций целиком не содержится ни в одном из классов Т0, Т1, S, M, L, то:

• эта система полна

Если сложное высказывание истинно при любых наборах значений элементарных высказываний, то оно называется:

• тавталогией

Если функция f(x1, …, xn) немонотонна, то из неё путём подстановки вместо аргументов xi констант и переменной x можно получить:

• отрицание x

Если функция f(x1, …, xn) несамодвойственна, то из неё путём подстановки вместо аргументов xi переменных x или x̅ можно получить:

• булеву константу (0 или 1)

Импликацией двух высказываний A → B называется такое высказывание, которое:

• ложно тогда и только тогда, когда А – истинно, а В – ложно

Какое свойство автомата не нужно для того, чтобы он был совершенным (полным) автоматом Мура?

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

Какое свойство не является характерным свойством алгоритмов?

• идемпотентность

Какой автомат обязательно содержит автоматно полная система автоматов?

• совершенный автомат Мура

Класс функций, вычислимых по Тьюрингу, совпадает с классом функций, вычислимых по Маркову, и совпадает с:

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

Конъюнкцией двух высказываний A и B называется такое высказывание, которое:

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

Любая булева функция, тождественно не равная нулю, представима и притом единственным образом в виде:

• СДНФ или полинома Жегалкина

Предикаты, определенные на предметной области,

• образуют булеву алгебру предикатов

Пусть C = A V L, D = B V L̅ тогда резольвентой дизъюнктов C и D называется дизъюнкт: