Зарипова, Э.Р. Дискретная математика Часть II. Математическая логика

29 Определение. ДНФ i i k    функции f называют неизбыточной если: 1) все k i – простые импликанты; 2) удаление любой k i из  нарушает равенство f=  . Очевидно, что минимальная ДНФ является неизбыточной. Поэтому минимальные ДНФ следует искать среди неизбыточных. Таким образом задача минимизации может быть разделена на следующие этапы: 1) нахождение всех простых импликантов функции f ; 2) нахождение неизбыточных ДНФ функции f ; 3) выбор минимальных ДНФ функции f . Порождение простых импликантов Определение. Элементарная конъюнкция  покрывается элементарной конъюнкцией  , если каждая переменная, входящая в  , входит в  (с учетом отрицания). Пример 6.2. Покрывающие конъюнкции. Конъюнкция  = xyz покрывается конъюнкцией  = xy. Конъюнкция  = x y z не покрывается конъюнкцией  = x z . Определение. Элементарная конъюнкция  называется дополнением элементарной конъюнкции  по отношению к ДНФ  , если: 1) конъюнкция  покрывается конъюнкцией  , 2) в конъюнкцию  входят все переменные, входящие в  . Пример 6.3. Найти дополнительные конъюнкции  =xy по отношению к  . Пусть  = xy z  t  zt  x y . Тогда конъюнкции  1 =xyzt,  2 =xyz t ,  3 =xy z t,  4 =xy zt являются дополнениями конъюнкции  =xy по отношению к  .