2.3. СВЯЗЬ МЕЖДУ БУЛЕВЫМИ ФУНКЦИЯМИ ДВУХ

ПЕРЕМЕННЫХ

Шесть из приведённых в таблице 2.3 функций не зависят от аргументов X] или х2 (или от обоих вместе) [2] :

Уо = 0 - константа нуля;

у is = 1 - константа единицы;

Уз = xi, У5 = х2 - функции повторения;

У ю = х2 ; у и = xi - функции отрицания. Из оставшихся десяти функций две у4,уц отличаются от соответствующих им уз,у1з лишь порядком следования символов аргументов (крайние аргументы имеют одинаковое значение, а средние взаимно-обратное). Поэтому эти функции не являются самостоятельными.

Таким образом, из 16 булевых функций двух переменных только восемь являются ортогональными :

У1>У2>УбУтУ8У9У13>У14

Из таблицы 2.3 видно, что между функциями имеются зависимости

yt = yi5-t 0=0,5).

Из этих зависимостей следует, что любая функция двух переменных (включая константы) выражается в аналитической форме через совокупность шести функций, содержащих отрицание х, и любую функцию каждой их пары :

{Уо>У1з}>{У1>У14}>{У2>У1з}>{Уб>У9}>{У7>У8}

Например, такой совокупностью могут служить функции:

у о = 0-константа 0;

yi=X]X2-конъюнкция;

У в = Х]->х2 -импликация;

У9-Х1~х2 -эквиваленция;

Уу - Xj vx2 -дизъюнкция;

У12= х1,у10= х2 -отрицание.

Выбранная таким образом совокупность шести функций является избыточной, т.к. импликация и эквиваленция выражается через остальные функции этой совокупности:

Cl ~ Х2 = (Х7 V Х2Х1 V Х2 ]

Для доказательства этого достаточно построить таблицу соответствия и сравнить ее с таблицей 2.3.

Таблица 2.4

Таблица соответствия булевых функций импликации и эквиваленции

Таким образом, комплект элементарных функций сокращается до четырёх:

-константа 0;

-конъюнкция;

-дизъюнкция;

-отрицание.

Этот комплект обладает существенными удобствами и часто применяется на практике, но и он может быть сокращен. Так, из законов де Моргана и свойства двойного отрицания вытекают тождества:

у0 = 0

yi =XiX2 у7 = Xj VX2 Xi, х2

XjX2 i 2

Отсюда следует, что булевы функции двух переменных выражаются

через:

Xj >Х2

- отрицание Xj л х2 - конъюнкция j

либо

хпх2 -отрицание xi v х2 - дизъюнкция J

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

y8 - стрелки Пирса или у14- штриха Шефера.