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

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

Основные понятия

Исходным понятием логики высказываний является простое высказывание. Это понятие не определяется через другие понятия, так как является базовым. Под высказыванием обычно понимают всякое повествовательно предположение, утверждающее что-либо о чем-либо. Если смысл, содержащийся в высказывании, соответствует действительности, то высказывание называют истинным. В противном случае – ложным.

Обычно  элементарные высказывания обозначают строчными буквами латинского алфавита a, b, c, x, y …, которые также являются логическими переменными. Истинные значения обозначаются буквой И или 1, а ложные – Л или 0.

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

Связки имеют следующий приоритет: Ø Ù Ú ® º. Приоритет операций, представленных логическими связками можно изменить с помощью скобок. Высказывания, построенные с помощью простых высказываний, связок и скобок, называют правильно построенными формулами или сокращённо формулами.

Замечательным свойством логики высказываний является то, что ее семантика близка к соответствующим высказываниям  на естественном языке. Так, например семантика формул содержащих связки Ø и Ù практически совпадает со смыслом фраз содержащих слова «не» и «и». Однако имеются и некоторые различия. Так формула х Ú у несколько шире, чем русское «х или у». Выражение «х или у» по смыслу ближе к формуле х Ù Øу Ú Øх Ù у. Еще больше различий между семантикой формулы х ® у в логике высказываний и выражению «из х следует у». В русском языке это выражение истинно, если истинны х и у, т.е. предложение русского языка по смыслу совпадает с формулой х Ù у. Логическое следствие истинно также, если х и у ложны или х ложна, а у истинна. Логическую формулу х ® у следует интерпретировать на естественном языке так: «Если х истинна, то у тоже истинна, а остальное неизвестно».

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

Очевидно, что если формула содержит n переменных, то в таблице истинности будет содержаться 2ⁿ строк. В приведенном примере формула содержит 2 переменные и 2² = 4 строки. Кроме того, данная формула истинна на любом наборе значений своих переменных. Такие формулы называются тождественно истинными или тавтологиями. В противоположной ситуации, формула является тождественно ложной или невыполнимой. Если две разные формулы принимают одинаковые значения на любом наборе значений переменных, то такие формулы называют равносильными. Равносильные формулы будем обозначать знаком равенства =.

Законы алгебры логики

В логике высказываний известно много общезначимых формул, которые также называются законами логики высказываний. Основными законами являются следующие:

• законы идемпотентности:
• x Ù x = x
• x Ú x = x
• x Ù 1 = x
• x Ú 1 = 1
• x Ù 0 = 0
• x Ú 0 = x
• x Ù Ø x = 0 – закон противоречия
• x Ú Ø x = 1 – закон исключения третьего
• Ø Ø x = x – закон снятия двойного отрицания
• законы поглощения
• x Ù (y Ú x) = x
• x Ú (y Ù x) = x

Доказательство этих и последующих законов элементарно осуществляется с помощью построения таблиц истинности или простейших логических рассуждений.

Следующая группа законов представляет взаимосвязь между логическими  операциями:

• (x º y) = (x ® y) Ù (y ® x)
• x ® y = Ø x Ú y
• законы Де Моргана
• Ø (y Ú x) = Ø y Ù Ø x
• Ø (y Ù x) = Ø y Ú Ø x

Замечательным следствием приведенных  выше законов является следующий факт. Любую логическую формулу можно заменить равносильной ей, но содержащую только две логические операции: конъюнкцию или отрицание или дизъюнкцию или отрицание. Дальнейшее исключение логических операций, очевидно, невозможно, то есть приведенные пары представляют минимальный базис для построения правильно построенных формул. Однако существует операция, с помощью которой можно представить любую логическую связку. Эта операция получила название «штрих Шеффера» и определяется следующим образом:

На основании этого определения  можно ввести следующие законы, выражающие взаимосвязь операции «штрих Шеффера» и других логических связок:

• Ø x =  x | x
• x Ù y = (x | y) | (x | y)

Также следует отметить, что x | y = Ø (x Ù y).

К основным законам алгебры логики также относятся следующие:

• коммутативные законы
• х Ù y = y Ù х
• х Ú y = y Ú х
• дистрибутивные законы
• х Ù (y Ú z) = (х Ù y) Ú (х Ù z)
• х Ú (y Ù z) = (х Ú y) Ù (х Ú z)
• ассоциативные законы
• х Ù (y Ù z) = (х Ù y) Ù z
• х Ú (y Ú z) = (х Ú y) Ú z

Еще одним важным законом алгебры  логики является закон двойственности. Пусть формула A содержит только операции конъюнкции, дизъюнкции и отрицания. Для операции конъюнкции двойственной считается дизъюнкция, а для дизъюнкции – конъюнкция. Тогда по определению формулы A и A* называются двойственными, если формула A* получается из A путем замены в ней каждой операции на двойственную. Например, для формулы (х Ú y) Ù z двойственной формулой будет (х Ù y) Ú z. Для двойственных формул справедлива следующая теорема: если формулы A и B равносильны, то равносильны и двойственные им формулы, то есть A* = B*. Данную теорему оставим без доказательства.

С помощью законов логики можно  осуществлять равносильные преобразования. Такие преобразования используются для доказательств, приведения формул к заданному виду, упрощения формул.

Под сложностью формул обычно понимается количество символов, используемых для  ее записи. То есть формула α проще  формулы b, если α содержит меньше букв и логических операций. Например, для формулы (Ø (x Ú y) ® x Ú y) Ù y можно записать следующую цепочку преобразований, приводящих ее к более простому виду:

(ØØ (x Ú y) Ú x Ú y) Ù y = (x Ú y Ú x Ú y) Ù y = (x Ú y) Ù y = y.

Функции алгебры логики

Значение формулы алгебры логики полностью зависит от значений входящих в нее высказываний. Поэтому такая формула может считаться функцией входящих в нее элементарных высказываний. Например, (x Ù y) ® Ø z является функцией f(x, y, z). Естественно, значения этой функции и входящих в нее элементов могут принимать значения истина или ложь. Тождественно истинные или тождественно ложные функции представляют собой константы.

Каждую функцию алгебры логики можно записать в виде формулы или представить таблицей истинности. Как уже было отмечено выше, таблица истинности для n переменных содержит 2ⁿ строк. Следовательно, каждая функция алгебры логики принимает 2ⁿ значений, состоящих из 0 или 1. Общее же число наборов значений, состоящих из 0 и 1, длины 2ⁿ равно 2²ⁿ. В частности, число различных функций от одной переменной равно четырем.

Из этой таблицы следует, что  две функции являются константами f₁(x) = 1 и – f₂(x) = x, а остальные f₃(x) = Ø x и f₄(x) = 0.

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

Пусть с помощью таблицы истинности задана произвольная функция алгебры  логики n переменных F(x₁, x₂, …, x_n). Рассмотрим формулу:

   F(1, 1, …, 1) Ù x₁ Ù x₂ Ù … Ù x_n Ú

Ú F(1, 1, …, 1, 0) Ù x₁ Ù x₂ Ù … Ù x_n-1 Ù Ø x_n Ú                                         (1)

Ú F(1, 1, …, 0, 1) Ù x₁ Ù x₂ Ù … Ù Ø x_n-1 Ù x_n Ú

Ú F(0, 0, …, 0) Ù Ø x₁ Ù Ø x₂ Ù … Ù Ø x_n

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

Ясно, что формула (1) полностью  определяет функцию F. Иначе говоря, значения функции F и формулы (1) совпадают на всех наборах значений переменных x_i. Например, если x₁ принимает значение 0, а остальные переменные принимают значение 1, то функция F принимает значение F(0, 1, 1, …, 1). При этом логическое слагаемое F(0, 1, …, 1) Ù Ø x₁ Ù x₂ Ù … Ù x_n = F(0, 1, …, 1) Ù Ø 0 Ù 1 Ù … Ù 1, входящее в формулу (1), принимает также значение F(0, l,..., l), а все остальные логические слагаемые формулы (1) имеют значение 0. Действительно, в них знаки отрицания перед переменными распределяются иначе, чем в рассмотренном слагаемом. Таким образом, при подстановке вместо переменных тех же значений в конъюнкцию войдет символ 0 без знака отрицания, а символ 1 под знаком отрицания. В таком случае один из членов конъюнкции будет иметь значение 0, и поэтому вся конъюнкция также будет иметь значение 0. В связи с этим на основании закона x Ú 0 = x значением формулы (1) является F(0, l,..., l).

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

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

• каждое логическое слагаемое формулы содержит все переменные, входящие в функцию F(x₁, x₂, …, x_n),
• все логические слагаемые формулы различны,
• ни одно логическое слагаемое формулы не содержит одновременно переменную и ее отрицание,
• ни одно логическое слагаемое формулы не содержит одну и ту же переменную дважды,

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

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

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

Для наборов значений переменных (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), которая определяется следующим образом:

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

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

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

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

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