Булевы функции

Функции f: Eⁿ₂ →E₂ , где Е₂={0;1} называются функциями алгебры логики или булевыми функциями.

Множество булевых функций от n переменных обозначим Р_n, Р_n:={f | f: Eⁿ₂ →E₂}

Булеву функцию от n переменных можно задать таблицей истинности:

Таблица содержит 2ⁿ строк, соответствующих всем различным комбинациям значений переменных.

Если функция fÎR_n существенно зависит от x_i, если существует такой набор значений а₁, …, а_i-1, а_i+1, …, а_n, что f(а₁, …, а_i-1, 0, а_i+1, …, а_n) ¹ f(а₁, …, а_i-1, 1, а_i+1, …, а_n), x_i в этом случае называется существенной переменной, в противном случае x_i – фиктивная переменная.

Например, значения функций f₁ и f₂ заданы таблицей.

Для обеих функций x₁ – существенная переменная, а x₂ – фиктивная.

Составим таблицу основных булевых функций одной переменной:

		x
название	обозначение			фиктивная
нуль				x
тождественная	x
отрицание	x, , x’
единица				x