Алгебра логики высказываний

Вид материала

Документы

Содержание Дизъюнктивная нормальная форма и совершенная дизъюнктивная нормальная форма Дизъюнктивной нормальной формой А основан на равносильных преобразованиях формулы и состоит в следующем: путем равносильных преобразований формулы А А входящая в нее эле­ментарная конъюнкция В Конъюнктивная нормальная форма и совершенная конъюнктивная нормальная форма Конъюнктивной нормальной формой А. Действительно, получив с помощью таблицы истин­ности СДНФ  А А получают одну из КНФ А А. Например, для формулы А

Подобный материал:

• Вопросы по курсу: Математическая логика и теория алгоритмов (2 курс), 30.21kb.
• Лекция Логические основы компьютеров , 369.25kb.
• Алгебра логики. Определение формы сложных высказываний, построение таблиц истинности, 132.48kb.
• Функции алгебры логики, 47.25kb.
• Алгебра логики и логические основы компьютера Алгебра логики (булева алгебра), 39.45kb.
• Программа дисциплины Математическая логика Семестр, 13.41kb.
• Логика высказываний. Основные понятия и определения. Логические функции одной и двух, 6.36kb.
• Основы математической логики. Алгебра логики (булева алгебра), 59.39kb.
• Программа курса «Математическая логика и теория алгоритмов», 37.76kb.
• 1. Введение в алгебру логики Прямое произведение множеств. Соответствия и функции., 38.38kb.

Дизъюнктивная нормальная форма и совершенная дизъюнктивная нормальная форма

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

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

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

Например, для формулы А = х  (х  y) имеем:

А = х  ( х  y) = (х   х)  (х  y) = х  y, то есть

ДНФ А = (х   х)  (х  y) и

ДНФ А = х  y.

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

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

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

1. путем равносильных преобразований формулы А получают одну из ДНФ А.
   
2. если в полученной ДНФ А входящая в нее эле­ментарная конъюнкция В не содержит переменную x_i, то, используя закон B  (x_i   x_i) = B, элемен­тарную конъюнкцию B заменяют на две элементарных конъюнкции (B  x_i) и (B   x_i), каждая из которых со­держит переменную x_i.
   
3. если в ДНФ А входят две одинаковых элементар­ных конъюнкции В, то лишнюю можно отбросить, пользу­ясь равносильностью В  В = В.
   
4. если некоторая элементарная конъюнкция В, вхо­дящая в ДНФ А, содержит переменную x_i и ее отрица­ние  x_i, то, на основании закона x_i   x_i = 0, В = 0 и В, таким образом, можно исключить из ДНФ А, как нулевой член дизъюнкции.
   
5. если некоторая элементарная конъюнкция, вхо­дящая в ДНФ А, содержит переменную x_i дважды, то одну переменную можно отбросить, пользуясь законом x_i  x_i = x_i.
   

Ясно, что после выполнения описанной процедуры будет получена СДНФ А. Например, для формулы А = x  y  (x   y) ДНФ А = x  (x  y)  (y   y). Так как элементарная конъюнкция В = х, входящая в ДНФ А, не содержит переменной у, то заменим ее на две элементарных конъюнкции (x  y) и (x   y), В результате получим ДНФ А = x  y  x   y  x  y  y   y.

Так как теперь ДНФ А содержит две одинаковых элементарных конъюнкции x  y, то отбросим лишнюю. В резуль­тате получим ДНФ A = x  y  x   y  y   y.

Так как элементарная конъюнкция y   y содержит переменную у и ее отрицание, то y   y = 0, и ее можно отбросить как нулевой член дизъюнкции.

Таким образом, получаем СДНФ А = x  y  x   y.

Конъюнктивная нормальная форма и совершенная конъюнктивная нормальная форма

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

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

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

Например, для формулы А =  (х  у)  х  у имеем:

А = ( (х  у)  х  у)  (х  у   (х  у)) =

= (х  у  х  у)  ( (х  у)   (х  у)) =

= (х  х  у)  (х  у  у)  ( х   у   х)  (  х   у   у) , то есть

КНФ А = (х  х  у)  (х  у  у)  ( х   у   х)  (  х   у   у).

Но так как х  х = х, у  у = у,  х   х =  х,  у   у =  у, то

КНФ A = (х  у)  (х  у)  ( х   у)  (  х   у).

А так как (х  у)  (х  у) = х  у, ( х   у)  (  х   у) = (  х   у), то

КНФ A = (х  у)  (  х   у).

КНФ А называется совершенной конъюнктивной нормальной формой формулы А (СКНФ А), если для нее выполнены условия:

• Все элементарные дизъюнкции, входящие в КНФ А , различны.
  
• Все элементарные дизъюнкции, входящие в КНФ А, содержат все переменные.
  
• Каждая элементарная дизъюнкция, входящая в КНФ А, не содержит двух одинаковых переменных.
  
• Каждая элементарная дизъюнкция, входящая в КНФ А, не содержит переменную и ее отрицание.
  

Можно доказать, что каждая не тождественно истин­ная формула имеет единственную СКНФ.

Один из способов получения СКНФ состоит в исполь­зовании таблицы истинности для формулы  А. Действительно, получив с помощью таблицы истин­ности СДНФ  А, мы получим СКНФ А, взяв отрицание  (СДНФ  А), то есть СКНФ А =  (СДНФ  А).

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

1. Путем равносильных преобразований формулы А получают одну из КНФ А.
   
2. Если в полученной КНФ А входящая в нее эле­ментарная дизъюнкция В не содержит переменную х_i, то, используя закон В  (x_i   x_i) = В, элементар­ную дизъюнкцию В заменяют на две элементарные дизъ­юнкции В  x_i и В   x_i, каждая из которых содержит переменную x_i.
   
3. Если в КНФ А входят две одинаковых элементар­ных дизъюнкции В, то лишнюю можно отбросить, пользуясь законом В  В = В.
   
4. Если некоторая элементарная дизъюнкция, вхо­дящая в КНФ А, содержит переменную x_i дважды, то лишнюю можно отбросить, пользуясь законом x_i  x_i = x_i.
   
5. Если некоторая элементарная дизъюнкция, вхо­дящая в КНФ А, содержит переменную x_i, и ее отрица­ние, то x_i   x_i = 1 и, следовательно, вся элементарная дизъюнкция имеет значение 1, а поэтому ее можно от­бросить, как истинный член конъюнкции.
   

Ясно, что после описанной процедуры будет получе­на СКНФ А. Например, для формулы А = x  y  (x   y) КНФ А = x  (y  (x   y)) = (x  y)  (x  x   y). Так как обе элементарные дизъюнкции содержат все переменные (x и y), то первое и второе условие СКНФ выполнены. Элементарная дизъюнкция x  x   y содержит переменную х дважды, но x  x = x, поэтому КНФ А = (x  y)  (x   y); причем, ни одна из элементарных дизъюнкций не содержит переменную и ее отрицание. Значит, все условия СКНФ выполнены, и, следовательно, СКНФ А = (x  y)  (x   y).