Представление в нормальных формах

элементарная конъюнкция (конъюнкт)  x,   1,  - литера x  элементарная дизъюнкция (дизъюнкт)  x,   0. дизъюнктивная нормальная форма (ДНФ) - дизъюнкция конъюнктов x y z  xy  z y x yz x y z конъюнктивная нормальная форма (КНФ) - конъюнкция дизъюнктов x  y  z y  xz  y  Теорема. Любая формула эквивалентна некоторой ДНФ. Любая формула эквивалентна некоторой КНФ. Алгоритм построения: 1. Выражаем все логические операции через дизъюнкцию и конъюнкцию. 2. Используя законы де Моргана, опускаем отрицание с формул на переменные; сокращаем двойные отрицания, используя инволютивность. 3. Используя закон дистрибутивности конъюнкции относительно дизъюнкции, получаем ДНФ. 3. Используя закон дистрибутивности дизъюнкции относительно конъюнкции, получаем КНФ  ( x, y, z )   x  y    y  z   x  y    y  z   x  y    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 КНФ ДНФ СДНФ (совершенная дизъюнктивная нормальная форма) СКНФ (совершенная конъюнктивная нормальная форма) Конституента единицы K1(1,  2 ,..., n )  x11  x2 2  ...  xn n Конституента нуля 11 K 0 (1,  2 ,..., n )  x1 1 2  x2  ...  x1n n K1(1,0,1)  x1x2 x3 K 0 (1,0,1)  x1  x2  x3 СДНФ – дизъюнкция конституент единицы, среди которых нет одинаковых x1 x 2 x3  x1x2 x3 – СДНФ x1 x 2 x3  x1x2 x3  x1 x 2 – не СДНФ СКНФ - конъюнкция конституент нуля, среди которых нет одинаковых x1  x2  x3 x1  x2  x3  – СКНФ x1  x2 x1  x2  x3  – не СКНФ Теорема 1. Любая булева функция f ( x1,..., xn ) представима в виде разложения Шеннона: f ( x1,..., xk , xk 1,..., xn )  k 2  по всем наборам 1 ,..., k  x00001111 y00110011 z01010101 f ( x, y, z ) 1 0 0 1 0 1 0 1 1 0 0 1 1 2 0 1 0 1    x1 1  x2 2  ...  xk k  f (1,..., k , xk 1,..., xn )       f ( x, y, z )  x0  y 0  f (0,0, z )  x0  y1  f (0,1, z )   x1  y 0  f (1,0, z )  x1  y1  f (1,1, z )     x  y  f (0,0, z )    x  y  f (0,1, z )     x  y  f (1,0, z )    x  y  f (1,1, z )   f ( x1,..., xk , xk 1,..., xn )    по всем наборам 1 ,..., k    x1 1  x2 2  ...  xk k  f (1,..., k , xk 1,..., xn ) * * * * Доказательство: x i  1  xi   i   (  ,  ,...,  ) 1 2 k i f ( x1,..., xk , xk 1,..., xn ) *  f (1*,..., k *, xk 1,..., xn )    x1 1  x2 2  ...  xk k  f (1,..., k , xk 1,..., xn ) 2k *1 * 2 * k 1   2  ...   k  f (1*,..., k* , xk 1,..., xn )  1  1  ...  1  f (1*,..., k*, xk 1,...,xn ) = i * * * *  f (  ,...,  , xk 1,..., xn ) a   a a   1 k i  i  i  0 * * * Замечание. x y z k n f  x, y, z  f ( x1,..., xn )   по всем наборам   x1 1  x2 2  ...  xn n 1 ,..., n  f (1 ,..., n ) 1 0 0 0 1 0 0 1 0 x0  y 0  z 0  f (0,0,0)  x  y  z  1 x  y  z x0  y 0  z1  f (0,0,1)  x  y  z  0  0 0 1 0 0 0 1 1 1 x0  y1  z 0  f (0,1,0)  x  y  z  0  0 x0  y1  z1  f (0,1,1)  x  y  z  1  x  y  z x1  y 0  z 0  f (1,0,0)  x  y  z  0  0 1 0 0 0 1 0 1 1 x1  y 0  z1  f (1,0,1)  x  y  z  1  x  y  z 1 1 0 0 1 1 1 1 x1  y1  z 0  f (1,1,0)  x  y  z  0  0 x1  y1  z1  f (1,1,1)  x  y  z  1  x  y  z f  x, y, z   xyz  x yz   x yz   x yz   xyz  xyz   xyz  xyz СДНФ k 3 1 1 1 1 1 2 1 1 1 1 3 1 1 1 1 Теорема 2. Любая булева функция f ( x1,..., xn ) представима в виде разложения Шеннона:  x11  x1 2  ...  x1 k  f ( ,..., , x ,..., x )  f ( x1,..., xk , xk 1,..., xn )   1 k k 1 n  1 2 k по всем наборам  1 ,..., k  Доказательство. Применяем теорему 1: f ( x1,..., xk , xk 1,..., xn )    по всем наборам 1 ,..., k    x1 1  x2 2  ...  xk k  f (1,..., k , xk 1,..., xn ) f ( x1,...,xk , xk 1,...,xn )  f ( x1,...,xk , xk 1,...,xn ) =    по всем наборам 1 ,..., k     x1 1  x2 2  ...  xk k  f (1,..., k , xk 1,..., xn ) =  x1  x 2  ...  x k  f ( ,..., , x ,..., x )  =  1 1 k k 1 n  2 k  по всем наборам   1 ,..., k    x11  x1 2  ...  x1 k  f ( ,..., , x ,..., x )  1 k k 1 n  1 2 k по всем наборам   1 ,..., k  Замечание. x y z k n f  x, y, z  0 0 0 1 0 0 1 0 x y z 0 1 0 0 x y z 0 1 1 1 1 0 0 0 x yz 1 0 1 1 1 1 0 0 x yz 1 1 1 1 f ( x1,..., xn )   по всем наборам x11  x12 1 2  ...  x1n n  СКНФ 1 ,..., n  f (1 ,..., n )  0 f  x, y, z    x  y  z    x  y  z    x  y  z    x  y  z  Следствие. Если f  0, то существует представляющая ее формула φ, находящаяся в СДНФ и такое представление единственно с точностью до порядка следования конституент единицы. Если f  1, то существует представляющая ее формула φ, находящаяся в СКНФ и такое представление единственно с точностью до порядка следования конституент нуля. Алгоритм построения СДНФ 1. Приводим данную формулу к ДНФ. 2. Исключаем лишние переменные из конъюнктов, используя формулы: a  a  a, a  1  a, a  0  0, a  a  0. 3. Если в некотором конъюнкте не хватает переменной, добавляем ее используя формулу:     a  a . 4. Применяем закон дистрибутивности конъюнкции относительно дизъюнкции. 5. Одинаковые конституенты единицы сокращаем до одной.  ( x, y, z )  x x  x  yzy  x  yz  x y  y   yz x  x   xy  x y  xyz  x yz = ДНФ 2) 4) 3)  xyz  z   x y z  z   xyz  x yz  xyz  xy z  x yz  x y z  xyz  x yz = 3) 4)  xy z  x yz  x y z  xyz  x yz 5) Алгоритм построения СКНФ 1. Приводим данную формулу к КНФ. 2. Исключаем лишние переменные из конъюнктов, используя формулы: a  a  a, a  1  1, a  0  a, a  a  1. 3. Если в некотором дизъюнкте не хватает переменной, добавляем ее используя формулу:     a  a . 4. Применяем закон дистрибутивности дизъюнкции относительно конъюнкции . 5. Одинаковые конституенты нуля сокращаем до одной.