Задачи для самостоятельной работы.

1) Сколько имеется различных двоичных наборов длины ?

2) Сколько имеется различных функций алгебры логики от переменных?

3) Сколько имеется различных функций от переменных, сохраняющих 0 (т.е. равных нулю на нулевом наборе: )?

4) Доказать равносильности алгебры логики:

;

;

;

;

;

;

;

;

;

;

;

;

;

;

;

;

.

5) Показать, что функция является самодвойственной.

6) Найти все самодвойственные функции от двух переменных.

7) Сколько имеется самодвойственных функций от переменных?

8) Дать определение несамодвойственной функции.

9) Дана произвольная несамодвойственная функция. Отождествить у нее переменные так, чтобы получилась несамодвойсвенная функция от возможно меньшего числа переменных. Каким может быть это число?

10) Представить функцию в виде СДНФ, СКНФ; найти .

11) Представить многочленами Жегалкина:

а) основные логические операции;

б) ;

в) ;

г)..

12) Сколько имеется линейных функций от переменных?

13) Какие из линейных функций являются самодвойственными?

14) Доказать, что функция, представленная полиномом Жегалкина, существенно зависят от всех входящих в них переменных.

15) Дать определение немонотонной функции.

16) Какие из основных логических операций являются монотонными?

17) Какие из линейных функций являются монотонными?

18) Перечислить все монотонные функции от двух переменных.

19) Какие из указанных функций являются монотонными:

а) ;

б) ;

в) ;

г) ;

д) .

20) Доказать полноту следующих систем функций:

а) ;

б)

в) ;

г) ;

д) ;

е) ;

ж) ;

з) ;

и) .

21) Решить задачу, используя таблицы Поста. Какие из следующих систем функций являются функционально замкнутыми классами:

а) функции от одной переменной;

б) функции от двух переменных;

в) все функции алгебры логики;

г) линейные функции;

д) самодвойственные функции;

е) монотонные функции;

ж) монотонно убывающие функции;

з) функции, сохраняющие ноль;

и) функции, сохраняющие единицу;

к) функции, сохраняющие и нуль, и единицу;

л) функции, сохраняющие нуль, но не сохраняющие единицу?

22) Доказать, что пересечение функционально замкнутых классов — функционально замкнутый класс.

23) Является ли объединение функционально замкнутых классов функционально замкнутым классом?

24) Доказать, что дополнение собственного функционально замкнутого класса (совокупность функций, в него не входящих) не может быть функционально замкнутым классом.