← Все тренажёры Функциональная полнота и теорема Поста

Функциональная полнота и теорема Поста

Замкнутые классы и критерий полноты Поста.

22 задания · Булева алгебра и логика

Как будете решать?

Режим
Режим

Блок 1. Один верный вариант

1

Сколько предполных классов существует во множестве всех булевых функций P2P_2 согласно теореме Эмиля Поста?

2

Какому условию удовлетворяет функция ff, принадлежащая классу T0T_0?

3

Какое свойство выполняется для самодвойственной функции f∈Sf \in S?

4

Какая из следующих функций НЕ является монотонной (f∉Mf \notin M)?

5

Что называется шефферовой функцией?

6

Каково необходимое и достаточное условие функциональной полноты системы булевых функций FF по теореме Поста?

7

Какое свойство отличает базис от произвольной функционально полной системы?

8

Почему система функций {x∧y,x∨y}\{x \land y, x \lor y\} НЕ является функционально полной?

9

К каким из классов Поста принадлежит тождественная константа 00?

10

Какая из следующих систем функций образует базис Жегалкина?

Блок 2. Краткий ответ

11

Сколько функций от 2 переменных принадлежат классу T0T_0 (сохраняющих 0)?

целое число

12

Сколько самодвойственных функций существует от n=3n = 3 переменных?

целое число

13

Сколько линейных функций существует от n=2n = 2 переменных?

целое число

14

Какова минимальная мощность функционально полного базиса в P2P_2?

целое число

15

Сколько функций от 1 переменной являются шефферовыми (полными сами по себе)?

целое число

16

Каково минимально необходимое число минусов в каждом столбце таблицы Поста для функциональной полноты системы?

целое число

Блок 3. Несколько верных вариантов

17

Какие из перечисленных функций являются шефферовыми (образуют одноэлементный базис)?

Отметьте все верные варианты

18

Какие из следующих систем булевых функций являются функционально полными?

Отметьте все верные варианты

19

Какие свойства оператора замыкания [F][F] выполняются для любых систем булевых функций?

Отметьте все верные варианты

20

Какие утверждения о монотонных функциях (f∈Mf \in M) верны?

Отметьте все верные варианты

21

Дана система функций F={x⊕y,1}F = \{x \oplus y, 1\}. Каким классам Поста принадлежит вся система FF?

Отметьте все верные варианты

22

Какие утверждения о классах Поста верны?

Отметьте все верные варианты

Завершение теста

Все ответы сохраняются автоматически. Нажмите для отправки на проверку.

Карта заданий (22)

Вход на платформу

Обратная связь

Сообщите об ошибке, задайте вопрос или предложите, что добавить.