Булевы функции от n аргументов (определение, равенство булевых функций, суперпозиция булевых функций). Булевы функции от n переменных

Булевы функции ¹⁾ названы в честь английского математика ХIХ века Дж. Буля, который впервые применил алгебраические методы для решения логических задач. Они образуют самый простой нетривиальный класс дискретных функций - их аргументы и значения могут принимать всего два значения (если мощность множества значений функции равна 1, то это тривиальная функция - константа !). С другой стороны, этот класс достаточно богат и его функции имеют много интересных свойств. Булевы функции находят применение в логике, электротехнике, многих разделах информатики.

Обозначим через B двухэлементное множество {0,1}. Тогда

это множество всех двоичных последовательностей (наборов, векторов) длины n. Булевой функцией от n переменных (аргументов) называется любая функция f(x₁, x_n): Bⁿ -> B . Каждый из ее аргументов x_i, 1 <= i <= n , может принимать одно из двух значений 0 или 1 и значением функции на любом наборе из B_n также может быть 0 или 1. Обозначим через   множество всех булевых функций от n переменных. Нетрудно подсчитать их число.

Теорема 3.1.  .

Доказательство.Действительно, по теореме 1.1 число функций из k -элементного множества A в m -элементное множество B равно m^k . В нашем случае B={0, 1}, а A = Bⁿ . Тогда m=2 и k= |Bⁿ| = 2ⁿ . Отсюда следует утверждение теоремы.

 Суперпозицией булевых функций f0 и f1,...,f_n называется функция f(x1,...,x_m) = f0(g1(x1,...,x_m),...,g_k(x1,...,x_m)), где каждая из функций g_i(x1,...,x_m) либо совпадает с одной из переменных (тождественная функция), либо – с одной из функций f1,...,f_n.

19. Число булевых функций от n аргументов. Выражение булевых функций через конъюнкцию, дизъюнкцию и отрицание (теорема о разложении функции по переменной и теорема о представлении булевых функций через конъюнкцию, дизъюнкцию и отрицание).

 Дизъюнктивная нормальная форма

Простой конъюнкцией или конъюнктом называется конъюнкция некоторого конечного набора переменных или их отрицаний, причём каждая переменная встречается не более одного раза. Дизъюнктивной нормальной формой или ДНФ называется дизъюнкция простых конъюнкций. Элементарная конъюнкция

• правильная, если в неё каждая переменная входит не более одного раза (включая отрицание);

• полная, если в неё каждая переменная (или её отрицание) входит ровно 1 раз;

• монотонная, если она не содержит отрицаний переменных.

Например    — является ДНФ.

Совершенной дизъюнктивной нормальной формой или СДНФ относительно некоторого заданного конечного набора переменных называется такая ДНФ, у которой в каждую конъюнкцию входят все переменные данного набора, причём в одном и том же порядке. Например:  .

Легко убедиться, что каждой булевой функции соответствует некоторая ДНФ, а функции отличной от тождественного нуля — даже СДНФ. Для этого достаточно в таблице истинности этой функции найти все булевы векторы, на которых её значение равно 1, и для каждого такого вектора   построить конъюнкцию  , где    . Дизъюнкция этих конъюнкций является СДНФ исходной функции, поскольку на всех булевых векторах её значения совпадают со значениями исходной функции. Например, для импликации   результатом является  , что можно упростить до  .

 Конъюнктивная нормальная форма

Конъюнктивная нормальная форма1 (КНФ) определяется двойственно к ДНФ. Простой дизъюнкцией или дизъюнктом называется дизъюнкция одной или нескольких переменных или их отрицаний, причём каждая переменная входит в неё не более одного раза. КНФ — это конъюнкция простых дизъюнкций.

Совершенной конъюнктивной нормальной формой (СКНФ), относительно некоторого заданного конечного набора переменных, называется такая КНФ, у которой в каждую дизъюнкцию входят все переменные данного набора, причём в одном и том же порядке. Поскольку (С)КНФ и (С)ДНФ взаимодвойственны, свойства (С)КНФ повторяют все свойства (С)ДНФ, грубо говоря, «с точностью до наоборот».

КНФ может быть преобразована к эквивалентной ей ДНФ путём раскрытия скобок по правилу:

которое выражает дистрибутивность конъюнкции относительно дизъюнкции. После этого необходимо в каждой конъюнкции удалить повторяющиеся переменные или их отрицания, а также выбросить из дизъюнкции все конъюнкции, в которых встречается переменная вместе со своим отрицанием. При этом результатом не обязательно будет СДНФ, даже если исходная КНФ была СКНФ. Точно также можно всегда перейти от ДНФ к КНФ. Для этого следует использовать правило

выражающее дистрибутивность дизъюнкции относительно конъюнкции. Результат нужно преобразовать описанным выше способом, заменив слово «конъюнкция» на «дизъюнкция» и наоборот.