Минимизация булевых функция

Минимальные дизъюнктивные формы . 3n Теорема. Число различных дизъюнктивных форм n переменных равно 2 . L( f ( x1, x2 ,..., xn )) - сложность f ( x1, x2 ,...,xn ) Геометрическая интерпретация задачи минимизации. (0,0,1,1)<(1,0,1,1)<(1,1,1,1)   (1, 2 ,..., n )     i  i , i  1, n (0,1,0,1) и (1,0,1,1) несравнимы   (1, 2 ,...,n ) Слои 1111 Булев куб 1 k 4 n 1 11 1101 1110 k 3 0111 1011 01 10 n2 00 111 011 001 n3 101 110 010 100 000 0011 0001 0101 0010 0110 1001 1010 1000 0100 n4 1100 k 2 k 1 k 0 0000 Грань куба размерности n-m (подкуб) - ребро (0000), (0001) Грань размерности 1 (0000), (0001), (0011), (0010) Грань размерности 2 (0000), (0001), (0011), (0010), Грань размерности 3 (0100), (0101), (0111), (0110) Единичный интервал 111 f ( x1, x2 ,..., xn ) - вершины, образующие подкуб, в которых 011 101 110 001 010 100 x00001111 y00110011 z01010101 g(x,y,z) 1 1 1 0 0 0 1 0 (001), (000) (000), (010) (010), (110) s(x,y,z) 1 1 1 1 0 0 1 0 (010), (110) y z (000),(010),(011),(001) x 000 Максимальный единичный интервал Простая импликанта f ( x1, x2 ,..., xn )  1 xy xz yz Сокращенная ДНФ g ( x, y, z )  x y  x z  y z s( x, y, z )  y z  x  ( x1, x2 ,...,xn )   ~  Конъюнкт  ( x1, x2 ,..., xn ) является импликантой  ( x, y)  x  y x y x  y x y xy x y x y x y импликанты: y, x, xy, x y, x y 0 0 1 1 1 0 1 0 0  ( x, y)  x  y простые импликанты: y, x 0 1 1 1 0 0 0 1 0 1 0 0 1 0 0 0 1 лишние импликанты 1 1 1 0 0 1 0 0 0 тупиковые ДНФ минимальная ДНФ Метод Квайна нахождения МДНФ Операция неполного склеивания: x   x    x   x x   x  x   x  x   x   ( x  x)  x   x    x   x Операция элементарного поглощения: x     Теорема Квайна. Если исходя из совершенной ДНФ произвести все возможные операции неполного склеивания, а затем элементарного поглощения, то в результате получится сокращенная ДНФ, т.е. дизъюнкция всех простых импликант. x   x    ( x, y, z )  x y z  x yz  x yz  xy z  xyz  x y  y z  yz  xz  xy  y  y  xz  y  xz  ( x, y, z )  x y z  x yz  x yz  xyz  x y  yz  xz конституенты единицы простые импликанты x y z xy yz xz 1 x yz x yz конституенты единицы импликанты x y z xyz 1 1  ( x, y, z )  x y  xz лишняя импликанта 1 1 y xz 1 x yz x yz 1 1 xy z xyz 1 1 1 1 L( x y  xz)  4  ( x, y, z )  y  xz L( y  xz)  3 yz x Карты Карно 00 01 11 10 1 1 1 1 1 1 x1x4 x3 x4 00 01 11 10 x1x2 y xz  ( x, y, z )  x y z  x yz  x yz  xy z  xyz  y  xz yz x 1 1 01 1 1 1 11 1 10 1 1 01 1 1 1  x1x2 x3 x4  x1x2 x3 x4  x1x2 x3 x4  x1 x3 1 x1x2 x4 x2 x4 1 11 1 x1 x2 x4  ( x1, x2 , x3 , x4 )  x1 x2 x3 x4  x1 x2 x3 x4  x1 x2 x3 x4  1 x3 x4 00 01 11 10 1 x1x3 x1 x3 x4 x y xz  ( x, y, z )  x y z  x yz  x yz  xyz  x y  xz 00 1 yz 1 1 10 1 00 01 11 10 1 x1x2 00 x2 x3 x4 1  x1x2 x3 x4  x1 x2 x3 x4  x1 x2 x3 x4  ( x1, x2 , x3, x4 )  x1x4  x1x3  x1 x3 x4  x2 x3 x4  ( x1, x2 , x3, x4 )  x1x4  x1x3  x1 x3 x4  x1 x2 x4 L=10  ( x1, x2 , x3, x4 )  x1 x3  x1x2 x4  x2 x4 L=7