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

Булевы функции f : E2  E2 x 0 f ( x)  0 0 f ( x)  x 0 x, x, x 1 f ( x)  1 1 22  4 1 1 1 x  y  x  y x  y  x  y  x  y  x  y  x  y   x  y  x  y  x  y  x y  x y x | y  x  y  x  y   z x 00001111 y 00110011 z 01010101 x y0 0 0 0 0 0 1 1 x  y   z 1 1 1 1 1 1 0 1 f : E2n  E2 , E2  0,1 22 f : E22  E2 2  16 x y f ( x, y)  0 x  y, x & y, x  y, xy f ( x, y)  x f ( x, y)  y x  y, xy, x  y, x  y x y x y x  y, x  y, x  y, x ~ y f ( x, y)  y f ( x, y)  x x  y, x  y, x  y x| y f ( x, y)  1 1 1 1 1 1 1 1 1 лексикографический 0 1 1 1 0 1 0 0 0 тождественный нуль 0 0 1 конъюнкция 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 сложение по модулю 2 1 1 1 дизъюнкция 0 0 0 стрелка Пирса 0 0 1 эквивалентность 0 1 0 отрицание y 0 1 1 1 0 0 отрицание x 1 0 1 импликация 1 1 0 штрих Шеффера 1 1 1 тождественная единица Приоритет операций Переключательные функции       x1 x2 xn … f f ( x1,..., xn ) x1 x2 x1  x2  x  y   z реализует f ( x, y, z ) =(1 1 1 1 1 1 0 1) равносильные, (эквивалентные) формулы существенная переменная x00001111 y00110011 z01010101 x  y   z 1 1 1 1 1 1 0 1 g ( x, y, z ) 1 0 1 1 1 0 1 1 - x - фиктивная y0011 z0101 ~ g ( y, z ) 1 0 1 1 x1,..., xk 1, xk 1,..., xn f ( x1,..., xk 1,0, xk 1,..., xn )  f ( x1,..., xk 1,1, xk 1,..., xn ) f (0,0,0)  f (0,0,1) - z -существенная f (0,0,1)  f (0,1,1) - y -существенная f (0,0,1)  f (1,0,1) - x -существенная Основные эквивалентности булевых формул x00001111 y00110011 1) ассоциативность a  b  c  a  b  c , a  b  c  a  b  c  z01010101 2) коммутативность a  b  b  a, a  b  b  a x 11110000 3) дистрибутивность конъюнкции относительно дизъюнкции x y 1 1 1 1 0 0 1 1 a  b  c   a  b  a  c , b  c   a  b  a   c  a  z 10101010 4) дистрибутивность дизъюнкции относительно конъюнкции yz 0 0 1 0 0 0 1 0 a  b  c   a  b  a  c , b  c   a  b  a   c  a  00001100 5) поглощение a  b  a  a, a  b  a  a y11001100 6) идемпотентность a  a  a, a  a  a xy 0 0 0 0 1 1 0 0 7) свойства 0 и 1 a  1  1, a  1  a, a  0  a, a  0  0 x yz 0 0 0 0 0 0 0 0 8) инволютивность a  a  00001100 9) законы де Моргана a  b   a  b, a  b   a  b 10) свойства отрицания a  a  1, a  a  0 Теорема. Для любых двух равносильных формул существует последовательность эквивалентных преобразований с помощью данных эквивалентностей      ( x, y, z )  x  y    y  z   x  y    y  z   x  y  y  z   x y  y  z   x y y  x yz  x y  x yz,  ( x, y, z )  x y  x yz   ( x, y, z ) ~  ( x, y, z ) выполнимая формула, опровержимая формула тавтология (тождественно истинная), противоречие (тождественно ложная) x x xx Теорема 1 (о замене переменных). Если в равносильных формулах вместо всех вхождений переменной xk подставить одну и ту же формулу, то получатся равносильные формулы. F1( x1, x2 ,...,xk ,...,xn )  F1( x1, x2 ,...,xk ,...,xn ) G( x1, x 2 ,...,xn ) F1( x1, x2 ,...,G,...,xn )  F1( x1, x2 ,...,G,...,xn )  ( x, y, z )  x  y  y z 1( x, y, z )  xy z  y  y z ~ ~  ( x, y, z )  x y  x yz  ( x, y, z )  xy z 1( x, y, z )  xy z y  xy z yz Теорема 2 (о замене переменных). Если в формуле заменить некоторую подформулу на равносильную, то получится равносильная формула. G1( x1, x2 ,...,xn )  G2 ( x1, x2 ,...,xn ) F ( x1, x2 ,...,G1 x1, x2 ,...,xn ,...,xn )  F ( x1, x2 ,...,G2  x1, x2 ,...,xn ,...,xn )  ( x, y, z )  xy z  x  y  y z  y  xy z  x y  x yz   y  ( x, y, z ) *  ( x, y, z ) Двойственная функция: f ( x1, x2 ,..., xn )  f ( x1, x2 ,..., xn )  * ( x, y , z )  x  y  y z  x  y  y z x0011 y0101 x y 0 1 1 1 x 1100 y 1010  x  y *1 0 0 0 x  y *  x  y x0011 y0101 x y 0 0 0 1 свойства двойственности: f **  f - инволютивность f *  g  g *  f - симметричность x  y *  x  y f* f x10 * x 01 x01 x10 - самодвойственная x01 * x 10 * x x Теорема (принцип двойственности). Если функция  ( x1, x2 ,..., xn ) реализуется фомулой f ( f1( x1, x2 ,...,xn ),..., f 2 ( x1, x2 ,...,xn )), то формула f * ( f1* ( x1, x2 ,..., xn ),..., f m* ( x1, x2 ,..., xn )) реализует функцию  * ( x1, x2 ,..., xn ). Двойственная суперпозиции функций есть суперпозиция двойственных функций.  ( x, y, z )  x  y  y z  * ( x, y , z )  x  y  y z  x  y  y z    * ( x, y , z )  x  y   y  z   x  y  y  z  x  y   y  z  Доказательство:  * ( x1, x2 ,..., xn )   ( x1, x2 ,...,xn )  f ( f1( x1, x2 ,..., xn ), f 2 ( x1, x2 ,..., xn ),..., f m ( x1, x2 ,..., xn )) = определение двойственности  инволютивность f1, f2 ,..., fm * *  f ( f 1( x1, x2 ,..., xn ),..., f m ( x1, x2 ,..., xn ))  f ( f 1 ( x1, x2 ,..., xn ),..., f m ( x1, x2 ,..., xn )) = определение двойственности f1, f2 ,..., fm определение двойственности  f * ( f1* ( x1, x2 ,..., xn ),..., f m* ( x1, x2 ,..., xn )) f