Теория автоматов. Аралбаев Т.З - 9 стр.

Например, x1  x2  x3 - ЭК третьего ранга; x1  x2  x3  x4 - четвертого ранга.
      ДНФ представляет собой регулярное аналитическое выражение (формулу)
ЛФ в виде дизъюнкции (суммы) элементарных конъюнкций.
      Например:
                                     Y  x1  x2  x3  x4  x5

      В теории автоматов часто используют следующие виды ДНФ:
      1) совершенную ДНФ (СДНФ);
      2) сокращенную ДНФ (СкДНФ);
      3) тупиковую ДНФ (ТДНФ);
      4) минимальную ДНФ (МДНФ).
      Если в каждом члене ДНФ представлены все аргументы (или их инверсии)
функции, то такая форма называется СДНФ.
      Например:
                            Y  x1 x2 x3  x1 x2 x3  x1 x2 x3  x1 x2 x3

        СкДНФ - это ДНФ в виде дизъюнкции всех ее простых импликант.
        Импликантой ЛФ Y  f ( x1 , x2 ,....xn ) называется функция Y  f ( x1 , x2 ,....xn ) ,
которая обращается в 1 на некотором подмножестве единичных наборов функции
Y.
        Например, импликантами являются ЭК в ДНФ функции.
        Простой импликантой функции Y  f ( x1 , x2 ,....xn ) называется импликанта,
которая не поглощается никакой другой импликантой данной функции Y.
        Например, функция Y1  x1 x2 x3             является имликантой функции
Y  x1 x3  x1 x2 x3 , а функция Y2  x1 x3 является простой импликантой функции Y.
        ТДНФ - это СкДНФ, из которой нельзя исключить ни одной простой
импликанты без потери эквивалентности функции.
        МДНФ - это ТДНФ, содержащая минимальное число букв среди
возможных ТДНФ функции.
        КНФ - это регулярное аналитическое выражение ЛФ в виде (произведения)
элементарных дизъюнкций.
        Например:
                                  Y  x1 ( x2  x3  x4 )  ( x2  x4 )

СДНФ n-местной ЛФ является ДНФ, содержащая ЭК только ранга n.
CKНФ n-местной ЛФ является КНФ, содержащая ЭД только ранга n.
     Каждой ЛФ соответствует одна СДНФ и одна СКНФ.




                                                                                             9