База ответов ИНТУИТ

Языки и исчисления

<<- Назад к вопросам

Если A и B - полные наборы булевых функций, то для любой функции:

(Отметьте один правильный вариант ответа.)

Варианты ответа
size_A (f) \ge const + size_B (f)(Верный ответ)
size_A (f) \le const \cdot size_B (f)
size_A (f) = size_B (f)
Похожие вопросы
Нормальная интерпретация А сигнатуры S с равенством может быть расширена до нормальной модели теории Т, если:
Если все П1-формулы сигнатуры S с равенством, выводимые из теории Т, истинны в А, то:
Если выводима формула А(с/х), где А - формула, х - переменная, с - константа не входящая в А, то тогда:
Число а - предел ‹ai, i=0,1,…, если есть бесконечно далекий ak:
Если А - замкнутая формула сигнатуры непротиворечивого множества Г и выводима А, то:
Если существует бесконечно далекий ak из ряда ‹ai, I=0,1,… который бесконечно близок к а, то:
Теория Т - П1 аксиоматизируема, если существуют П1-формулы,из которых:
Если А - предикатный символ валентности k, t1, t2, …, tk - термы, то выражение А(t1, t2, …, tk) - это:
Если А - бесконечная нормальная интерпретация сигнатуры с равенством,то нормальная интерпретация В А большой мощности , является элементарным расширением А:
Для любой формулы А, формула А →​ А есть: