Понятие функциональной полноты и замкнутости

Глава 2. ЗАМКНУТЫЕ КЛАССЫ И ПОЛНОТА СИСТЕМ ФУНКЦИЙ АЛГЕБРЫ ЛОГИКИ

Понятие функциональной полноты и замкнутости

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

Задачи

Задачи

2.2.1. Перечислить все булевы функции:

1) от одной переменной, сохраняющие 0;

2) от одной переменной, сохраняющие 1;

3) от одной переменной, сохраняющие обе константы;

4) от двух переменных, сохраняющие 0;

5) от двух переменных, сохраняющие 1;

6) от двух переменных, сохраняющие обе константы;

7) от двух переменных, сохраняющие 0, но не сохраняющие 1;

8) от двух переменных, сохраняющие 1, но не сохраняющие 0.

2.2.3. Доказать, что если булева функция сохраняет 0, то двойственная для нее функция сохраняет 1.

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

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

Дата добавления: 2015-07-17