Главная / Алгоритмы и дискретные структуры /
Языки и исчисления / Тест 5
Языки и исчисления - тест 5
Упражнение 1:
Номер 1
Если М
- непустое множество, то множество всех <m1, m2,…, mk>
- это:
Ответ:
 (1) Mk
 
 (2) Mk
 
 (3) М(k)
 
Номер 2
k
-местной функцией на М
является:
Ответ:
 (1) f: Mk→M
 
 (2) f: X→M, X - подмножество Mk
 
 (3) f: M→Mk
 
Номер 3
Количество синонимов в списке ‹"арность", "местность", "валентность", "эквивалентность"› равна:
Ответ:
 (1) 2 
 (2) 3 
 (3) 4 
Упражнение 2:
Номер 1
Унарным предикатом на множестве М
будет:
Ответ:
 (1) М → ‹И, Л›
 
 (2) М2 → ‹И, Л›
 
 (3) М3 → ‹И, Л›
 
Номер 2
Бинарным предикатом на множестве М
будет:
Ответ:
 (1) М → ‹И, Л›
 
 (2) М2 → ‹И, Л›
 
 (3) М3 → ‹И, Л›
 
Номер 3
Тернарным (тренарным) предикатом на множестве М
будет:
Ответ:
 (1) М → ‹И, Л›
 
 (2) М2 → ‹И, Л›
 
 (3) М3 → ‹И, Л›
 
Упражнение 3:
Номер 1
Количество различных 0-местных предикатов равно:
Ответ:
 (1) 0 
 (2) 1 
 (3) 2 
Номер 2
Количество различных 1-местных предикатов:
Ответ:
 (1) равно 1 
 (2) равно 2 
 (3) равно 3 
Номер 3
Количество 2-местных предикатов:
Ответ:
 (1) равно 2 
 (2) равно 4 
 (3) больше 4 
Упражнение 4:
Номер 1
Набор символов-обозначений в формулах с неотрицательными числами называется:
Ответ:
 (1) сигнатурой 
 (2) носителем 
 (3) термом 
Номер 2
Конструктивно определяемая последовательность переменных, занятых, скобок и символов сигнатуры называется:
Ответ:
 (1) термом 
 (2) термином 
 (3) терминалом 
Номер 3
Если А
- предикатный символ валентности k, t1, t2, …, tk
- термы, то выражение А(t1, t2, …, tk)
- это:
Ответ:
 (1) терминальная функция 
 (2) характеристическая функция 
 (3) атомарная функция 
Упражнение 5:
Номер 1
Формулу можно построить с использованием правила:
Ответ:
 (1) атомарная - формула 
 (2) сигнатура - формула 
 (3) символ валентности - формула  
Номер 2
Формулу можно построить с использованием правила:
Ответ:
 
(1) если
А
- формула, то
- формула 
 
(2) если
- формула, то
А и В
- формулы 
 
(3) если
- формула, то
А и В
- формулы 
Номер 3
Формулу можно построить с использованием правила:
Ответ:
 
(1) если
А, В
- формулы, то
- формула 
 
(2) если
- формулы, то
- формула 
 
(3) если
А, В
- формулы, то
- формула 
Упражнение 6:
Номер 1
Формулу можно построить с использованием правила:
Ответ:
 
(1) если
А, В
- формулы, то
- формула 
 
(2) если
А, В
- формулы, то
- формула 
 
(3) если
А, В
- формулы, то
- формула 
Номер 2
Формулу можно построить с использованием правила:
Ответ:
 
(1) если
А, В
- формулы, то
- формула 
 
(2) если
А, В
- формулы, то
- формула 
 
(3) если
А, В
- формулы, то
- формула 
Номер 3
Если А
- формула, а x
- ее индивидная переменная, то:
Ответ:
 
(1) - формула  
 
(2) - формула  
 
(3) - формула  
Упражнение 7:
Номер 1
Чтобы задать интерпретацию сигнатуры S
, необходимо:
Ответ:
 (1) указать ее носитель 
 (2) определить ее мощность 
 (3) перечислить ее элементы 
Номер 2
Чтобы задать интерпретацию сигнатуры S
, необходимо:
Ответ:
 (1) для каждого предикатного символа S
указать предикат  
 (2) для каждого символа указать ее носитель 
 (3) перечислить все формулы 
Номер 3
Чтобы задать интерпретацию сигнатуры S
, необходимо:
Ответ:
 (1) для каждого функционального символа S
указать функцию 
 (2) для каждого символа указать ее сигнатуру 
 (3) указать валентность всех функции 
Упражнение 8:
Номер 1
Параметром формулы A
может быть:
Ответ:
 (1) все его индивидуальные переменные A
 
 (2) все символы A
 
 (3) всевозможные комбинации символов A
 
Номер 2
Параметром формулы A
может быть:
Ответ:
 
(1) параметры формулы
 
 
(2) параметры формулы
 
 (3) все части A
 
Номер 3
Параметром формулы A
может быть:
Ответ:
 
(1)  
 
(2)  
 
(3) параметры
- формула