Дистанционный практикум по программированию

Булевой функцией называется функция, у которой входные переменные (аргументы) и результат могут принимать только два значения — 1 или 0 (истина или ложь). Один из способов задания булевой функции — записать в таблицу все значения этой функции для всех комбинаций значений входных переменных. Полученная таблица называется таблицей истинности. Ниже приведён пример таблицы истинности для некоторой булевой функции от трёх переменных:

$$$$$$ \begin{array}{|c|c|c|c|} \hline x & y & z & f(x,y, z)\cr \hline 0 & 0 & 0 & 0\cr \hline 0 & 0 & 1 & 0\cr \hline 0 & 1 & 0 & 0\cr \hline 0 & 1 & 1 & 1\cr \hline 1 & 0 & 0 & 0\cr \hline 1 & 0 & 1 & 1\cr \hline 1 & 1 & 0 & 1\cr \hline 1 & 1 & 1 & 1\cr \hline \end{array} $$$$$$

Несложно сосчитать, что всего существует 256 различных булевых функций от трёх переменных — это количество различных комбинаций ноликов и единичек в последнем столбце таблицы истинности.

В данной задаче вам нужно найти ответы на следующие вопросы:

1. Сколько существует таких булевых функций от двух переменных, что от перестановки переменных местами ответ не меняется? То есть, $$$f(x,y) = f(y,x)$$$.
2. Сколько существует таких булевых функций от трёх переменных, что последний столбец их таблицы истинности содержит больше единиц, чем нулей?
3. Обозначим символом $$$\neg$$$ операцию инверсии: $$$\neg 0 = 1$$$, $$$\neg 1 = 0$$$. Сколько существует таких булевых функций от трёх переменных, что $$$f(x, y, z) = f(\neg x, \neg y, \neg z)$$$?
4. Пусть некоторая булева функция от десяти переменных возвращает единицу тогда и только тогда, когда ровно половина её аргументов равны нулю, а другая половина — единице. Сколько единиц содержит последний столбец таблицы истинности этой функции?