Из введенных простейших булевых функций можно строить с помощью суперпозиций более сложные булевы функции. Например, если в функцию х, ˅ t вставить вместо аргумента t функцию у • z, то получим следующую сложную функцию: х ˅ (у • z). Если в нее в свою очередь вставить вместо аргумента z функцию u → v, то получим сложную функцию х ˅ (у • (u → v)). И так далее. В результате получаются булевы функции от трех, четырех и большего числа аргументов. В следующих теоремах устанавливаются некоторые равенства одних булевых функций другим, выражающие свойства основных булевых функций.
Свойства дизъюнкции, конъюнкции и отрицания.
Для булевых функций выполняются следующие равенства:
a)x˅x = x, х•х = х(идемпотентность дизъюнкции и конъюнкции);
б) х ˅ у = у ˅ х, х • у = у • х (коммутативность дизъюнкции и конъюнкции);
в) (х ˅ у) ˅ z = х ˅ (у ˅ z), (x • у) • z = х • (у • z) (ассоциативность дизъюнкции и конъюнкции);
г) х ˅ 1 = 1, х • 1 = х;
д) х ˅ 0 = х, х • 0 = 0;
е) x v (у z) = (x v у) (x v z), x • (у v z) = (х • у) v (x z) (дистрибутивность дизъюнкции относительно конъюнкции и дистрибутивность конъюнкции относительно дизъюнкции);
ж) х ˅ (у • х) = х, х • (у ˅ х) = х (законы поглощения);
з) (х ˅ у)` = х` • у`, (х • у)` = х' ˅ у' (законы де Моргана);
и) х ˅ х` = 1, х • х` = 0;
к) х`` =x.
Свойства эквивалентности, импликации и отрицания.
Свойства эквивалентности и импликации только частично аналогичны свойствам дизъюнкции или конъюнкции.
Для булевых функций справедливы следующие равенства:
а) х ↔ х= 1, х ↔ х` = 0;
б) х ↔ у= у ↔ х (коммутативность эквивалентности);
в) (х ↔ у) ↔ 2 = х ↔ (у ↔ z) (ассоциативность эквивалентности);
г) 1 ↔ x = х, 0 ↔ х = х`;
д) х`↔ y` = х ↔ y;
е) х` → у` = y → х;
ж)х → х = 1;
з) х → х` = х`;
и) х` → х = х;
к) 1 → х = х;
л) 0 → х= 1;
м) х → 1 = 1;
н) х → 0 = х`.
