Спирина, М.С. Дискретная математика

Так, в рассмотренном примере v х,х2 • х3является ДНФ. Для того чтобы привести ее к СДНФ, необходимо в первой элемен­ тарной конъюнкции иметь переменные х2 и х3или их отрицания. Для этого дважды умножим х х на 1,_с тем чтобы затем эти еди­ ницы заменить дизъюнкциями х2 v ~х2 и_Хз v ~х2 соответственно: F x( x Xj_X i , Х3) = Х х V = Xj_ 1 • 1 V_ XjXjjtj =_Xj(x2 V х2)(х3 V xi) V VХ]^ 2 Х 3 = Х|Х2Хз VХ]Х 2 Х 3 VX,Х 2 Х 3 VХ,Х 2 Х 3 VХ,Х 2 Х 3 = Х]Х 2 Х 3 VХ,Х 2 Х 3 V V Х]Х2Х3 V Х[х2х3. Полученная ДНФ является совершенной, так как соответству­ ет всем перечисленным требованиям. Аналогично любую формулу, имеющую вид ДНФ , можно при­ вести к совершенной конъюнктивной нормальной форме (КНФ), для которой выполняются требования: • формула не является тождественно-ложной; • формула приведена к одному из видов КНФ; • из формулы удалены одинаковые элементарные дизъюнкции, кроме одной; • каждая элементарная дизъюнкция в КНФ включает все логи­ ческие переменные, входящие в эту формулу. Если логическая функция имеет вид КНФ , то привести ее к виду совершенной КНФ (сокращенно СКНФ) можно, дополнив каждую элементарную дизъюнкцию логическим нулем, который в следующем шаге заменяется на конъюнкцию недостающей пе­ ременной и ее отрицание. _Для примера рассмотрим F2(xx, х2, х3) = (xj v х3) • (х2 v xj) • (х, v v х2 v х3). Она имеет вид КНФ , но в первой скобке нет перемен­ ной х2, а во второй — X]. Воспользовавшись приведенным прави­ лом, приведем ее квиду СКНФ. Тогда имеем: Jp2(xb xb_x3) = (xj v V ОV Х^) • (О V Х2 \^Х3) • (Х[ V Х2 V_X3) =_(х, VХ2Х2 V Х3) • (Х]Х] VXj V х3) • • (xq V Х 2 VX 3 j_= (X! VХ 2 VХ3) ■(X! V Х 2 VХ3) • (Х! VХ 2 V хД • (х[ VХ 2 V V х3) • (х, V Х2 V х3). Полученная конъюнктивная нормальная форма является со­ вершенной. Для сравнения приведем примеры нормальных форм (табл. 4.19). Для того чтобы привести булеву функцию к совершенной нор­ мальной форме, надо выполнить операции в следующем порядке. Т а б л и ц а 4.19 Примеры нормальных форм Формы Конъюнктивные Дизъюнктивные Нормальные КНФ (х, v х2) • (х , v х3) Д Н Ф _ х х 2 v Х ]Х3 Совершенные нормальные СКНФ (х, v х2 v х3) • (х, v х2 v х3) СДНФ Х ,Х 2Х3 V Х ,Х 2Х3 V Х Х & ) 172