Тема 7.Дизъюнктивная нормальная форма(днф)

▪ Представление произвольной функции алгебры логики в виде формулы алгебры логики.

▪ Закон двойственности.

▪ Элементарная дизъюнкция. Дизъюнктивная нормальная форма.

▪Минимальная ДНФ. Два правила поглощения.

▪Совершенная дизъюнктивная нормальная форма(СДНФ).

▪Два способа получения СДНФ.

Пусть F() - произвольная функция алгебры логики п переменных. Рассмотрим формулу которая составлена следующим образом: каждое слагае­мое этой логической суммы представляет собой конъюн­кцию, в которой первый член является значением функ­ции F при некоторых определенных значениях перемен­ных , остальные же члены конъюнкции пред­ставляют собой переменные или их отрицания. При этом под знаком отрицания находятся те и только те переменные, которые в первом члене конъюнкции имеют зна­чение 0.

Вместе с тем данная формула содержит в виде логичес­ких слагаемых всевозможные конъюнкции указанного вида.

Ясно, что эта формула полностью определяет функцию F(). Иначе говоря, значения функции F и такой формулы совпадают на всех наборах значений пере­менных .

Например, если принимает значение 0, а осталь­ные переменные принимают значение 1, то функция F принимает значение F(0,l,l, . . .1) . При этом логическое слагаемое F(0,1,...1)˄ , входящее в нашу формулу, принимает также значение F(0,1, . . .,1) , все остальные логические слагаемые формулы (1) имеют зна­чение 0. Действительно, в них знаки отрицания над переменными распределяются иначе, чем в рассмотрен­ном слагаемом, но тогда при замене переменных теми же значениями в конъюнкцию войдет символ 0 без знака от­рицания, символ 1 под знаком отрицания. В таком слу­чае один из членов конъюнкции имеет значение 0, а по­этому вся конъюнкция имеет значение 0. В связи с этим на основании равносильности х ˅ 0 = х значением нашей фор­мулы является F(0,1, ...,1).

Ясно, что вид формулы рассматриваемой нами может быть значительно упрощен, если в ней отбросить те логические слагаемые, в которых первый член конъюнкции имеет значение 0 (и, следовательно, вся конъюнкция имеет значение 0). Если же в логическом слагаемом первый член конъюнк­ции имеет значение 1, то, пользуясь равносильностью 1˄ х = х, этот член конъюнкции можно не выписывать.

Таким образом, в результате получается формула, которая содержит только элементарные переменные выс­казывания и обладает следующими свойствами:

1) Каждое логическое слагаемое формулы содержит все переменные, входящие в функцию F().

2. Все логические слагаемые формулы различны.

3. Ни одно логическое слагаемое формулы не содержит одновременно переменную и ее отрицание.

4. Ни одно логическое слагаемое формулы не содер­жит одну и ту же переменную дважды.

Перечисленные свойства будем называть свойства­ми совершенства или, коротко, свойствами (С).

Из приведенных рассуждений видно, что каждой не тождественно ложной функции соответствует единствен­ная формула указанного вида.

Если функция F() задана таблицей ис­тинности, то соответствующая ей формула алгебры ло­гики может быть получена просто. Действительно, для каждого набора значений переменных, на котором фун­кция F() принимает значение 1, запишем конъюнкцию элементарных переменных высказываний, взяв за член конъюнкции х_k, если значение x_k на ука­занном наборе значений переменных есть 1 и отрицание x_k, если значение x_k есть 0. Дизъюнкция всех записан­ных конъюнкций и будет искомой формулой.

Пусть, например, функция F(x₁,x₂,x₃) имеет следу­ющую таблицу истинности:

Для наборов значений переменных (1,1,0), (l,0,l), (0,1,0), (ОД0), на которых функция принимает значение 1, запишем конъюнкции , , , а искомая формула, обладающая свойствами (С) , имеет вид:

˅ ˅ ˅ .

Определение 1. Элементарной конъюнкцией п пере­менных называется конъюнкция переменных или их от­рицаний.

Определение 2. Дизъюнктивной нормальной формой (ДНФ) формулы А называется равносильная ей форму­ла, представляющая собой дизъюнкцию элементарных конъюнкций.

Для любой формулы алгебры логики путем равно­сильных преобразований можно получить ее ДНФ, при­чем не единственную.

Например, для формулы имеем: , то есть ДНФ А = (х˄ х)˅(х˄ у) ,

ДНФ А = х˄ y.

Среди многочисленных ДНФ А существует единствен­ная ДНФ А, для которой выполняются перечисленные выше четыре свойства совершенства (свойства (С)).

Такая ДНФ А называется совершенной дизъюнктив­ной нормальной формой формулы А ( СДНФ А ).

Как уже указывалось, СДНФ А может быть получе­на с помощью таблицы истинности.

Другой способ получения СДНФ формулы А основан на равносильных преобразованиях формулы и состоит в следующем:

1. Путем равносильных преобразований формулы А получают одну из ДНФ А.

2. Если в полученной ДНФ А входящая в нее элементарная конъюнкция В не содержит переменную x_i , то, используя равносильность , элемен­тарную конъюнкцию В заменяют на две элементарных конъюнкции (В˄) и (В˄), каждая из которых содержит переменную x_i .

3. Если в ДНФ А входят две одинаковых элементар­ных конъюнкции В, то лишнюю можно отбросить, пользу­ясь равносильностью B˅ В = В .

4. Если некоторая элементарная конъюнкция В, входящая в ДНФ А, содержит переменную x_i и ее отрица­ние , то В = 0, и В можно исключить из ДНФ А, как нулевой член дизъюнкции.

5. Если некоторая элементарная конъюнкция, вхо­дящая в ДНФ А, содержит переменную x_i дважды, то одну переменную можно отбросить, пользуясь равносильностью x_i ˄x_i = x_t.

Ясно, что после выполнения описанной процедуры будет получена СДНФ А.