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

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

x1	X2	x3	F(x1, x2, x3)
0	0	0	1
0	0	1	0
0	1	0	1
0	1	1	0
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	0

Для наборов значений переменных (1, 1, 0), (1,0,1), (0,1,0), (0, 0, 0), на которых функция принимает значение 1, запишем конъюнкции x₁ Ù x₂ Ù Ø x₃, x₁ Ù Ø x₂ Ù x₃, Ø x₁ Ù x₂ Ù Ø x₃, Ø x₁ Ù Ø x₂ Ù Ø x₃. а искомая формула, обладающая свойствами совершенства, будет иметь вид:

x₁ Ù x₂ Ù Ø x₃   Ú x₁ Ù Ø x₂ Ù x₃   Ú   Ø x₁ Ù x₂ Ù Ø x₃   Ú   Ø x₁ Ù Ø x₂ Ù Ø x₃.

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

 

Элементарной конъюнкцией 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).

 

Минимизация булевых функций. Карты Карно

 

Сложность логической функции, как уже было отмечено выше, определяется сложностью ее аналитической записи. Минимальной формой логической функции на некотором множестве фиксированных операций (базисе) можно считать такую, которая содержит минимальное число суперпозиций функций базиса, допуская и скобки. Однако построить эффективный алгоритм такой минимизации с получением минимальной скобочной формы трудно.

Более простой задачей минимизации является нахождение минимальная ДНФ функции. Для этой задачи существуют простые эффективные алгоритмы. Один из них основан на применении карт Карно.

Карта Карно – это двумерная табличная форма представления булевой функции, позволяющая в наглядной графической форме легко отыскать минимальные ДНФ логических функций. Каждой клетке в таблице сопоставляется дизъюнкт СДНФ минимизируемой функции, причем так, что любым осям симметрии таблицы соответствуют зоны, взаимно инверсные по какой-либо переменной. Такое расположение клеток в таблице позволяет легко определить склеивающиеся термы СДНФ (отличающиеся знаком инверсии только одной переменной): они располагаются в таблице симметрично. Например, следующая карта Карно построена для импликации двух переменных х ® у. В ячейки карты вписываются значения из таблицы истинности функции, при этом, если перед соответствующей переменной стоит знак отрицания, то в таблице истинности выбирается строка с ложным значением данной переменной, иначе – с истинным значением.

 

 

Все четыре клетки соответствуют всем возможным конъюнкциям СДНФ функции 2 переменных. Единичные значения функции показывают те дизъюнкты, которые присутствуют в СДНФ этой функции. Расположения элементов в картах Карно функции 2 переменных таково, что в один конъюнкт эта переменная входит без отрицания, а в другой – с отрицанием. Алгоритм поиска минимальной ДНФ по карте Карно основан на выявлении на карте минимального количества максимальных квадратов или прямоугольников со сторонами, равными степени двойки, так, чтобы они состояли только из ячеек, содержащих единицы. Для приведенной карты Карно единичные значения покрывают ячейки с координатами Ø х и у, соответственно искомая минимальная ДНФ будет Ø х Ú у.

Рассмотрим  другую логическую функцию f = Ø p Ú q Å r Ù q Ù (p Ú r). Знаком Å обозначается операция сложения по модулю 2 или «исключающее или» (XOR – eXclusive OR), которая определяется следующим образом:

 

х	у	х Å у
0	0	0
0	1	1
1	0	1
1	1	0

 

Таблица истинности для данной формулы имеет следующий  вид:

 

p	q	r	f
0	0	0	1
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	0
1	0	1	0
1	1	0	1
1	1	1	0

 

Карта Карно  для функции трех переменных должна содержать, очевидно, 8 ячеек. Подобную карту можно изобразить следующим образом:

 

 

Для этой карты Карно единичные  значения присутствуют в ячейках  с координатами q Ù Ø r и Ø q Ù Ø p, соответственно минимальная ДНФ будет q Ù Ø r Ú Ø q Ù Ø p.

В силу симметрии карт Карно при  построении прямоугольников возможно объединение ячеек, находящихся  в крайних позициях, так как  при ином расположении координат строк или столбцов (переменных без отрицания и с отрицанием) крайние ячейки окажутся внутри карты. Следующие две карты Карно эквивалентны (местами поменялись координаты r и Ø r) и на них указано корректное объединение ячеек в прямоугольные области:

  

 

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

 

x	y	z	f
0	0	0	-
0	0	1	1
0	1	0	1
0	1	1	1
1	0	0	0
1	0	1	-
1	1	0	1
1	1	1	-