Теорем и построении схем

Эквиваленция и импликация играют важную роль в математике при построении логического вывода, в частности, при доказательстве различных высказываний (теорем).

Рассмотрим, например, следующую теорему: асимметричное бинарное отношение антирефлексивно. С точки зрения алгебры высказываний теорема имеет структуру следования

А Þ В,

где А = “отношение R асимметрично”,

В = “отношение R антирефлексивно”.

Следующая теорема – для связности графа необходимо и достаточно, чтобы в нем какая-нибудь фиксированная вершина v была достижима из всех вершин, имеет вид двойного следования

А Û В (А Þ В, В Þ А),

где А = “граф G – связный”,

В = “вершина v достижима из всех вершин”.

Согласно теоремам 2.1 и 2.2, следование А Þ В имеет место тогда и только тогда, когда импликация А ® В является ТИ-формулой, а двойное следование А • В выполняется, когда ТИ-формулой является эквиваленция А ~ В. Таким образом, для доказательства какой-либо теоремы надо доказать ТИ соответствующей импликации или эквиваленции. Рассмотрим основные приемы таких доказательств, использующие законы математической логики.

Определение 1. Если А®В является истинным высказыванием, то истинность А является достаточным условием истинности В, а истинность В – необходимым условием истинности А.

Определение 2. Теоремы, записанные в виде импликаций А®В и В®А называются взаимно-обратными. Если верны обе импликации, то истинность А является необходимым и достаточным условием истинности В, и наоборот.

Определение 3. Теоремы, записанные в виде импликаций А ® В и называются взаимно-противоположными.

Предположим, что утверждение А истинно и докажем, что в этом случае В тоже истинно. Так доказывается теорема вида А ® В. Однако такая схема доказательства “в лоб” не всегда удобна. Для доказательства истинности импликаций и эквиваленций часто используют свойства эквивалентности формул.

Известно, что

А ® В º В Ú º º Ø (А Ù ).

Следовательно, имеем три равносильных способа доказательства, т.к. вместо истинности импликации можно доказывать истинность эквивалентной формулы.

Например, А = “отношение R асимметрично”, В = “отношение R антирефлексивно”. Тогда доказательство по схеме выглядит так: R рефлексивно, т.е. (х, х) Î R, значит, (х, х) Î R^{– 1} , т.е. (х, х) Î R È R^{– 1} ¹ Æ. Это означает, что R не асимметрично.

Доказательство истинности (Ø (А Ù )), или, что то же самое, ложности (А Ù ), так называемое доказательство от противного, основано на предположении: А – истинно, а В – ложно. В результате должно быть получено ТЛ-высказывание, или противоречие.

Например, предположим, что R асимметрично и рефлексивно. В силу асимметричности неверно одно из следующих соотношений: (х, у) Î R и (у, х) Î R. Положим х = у. Тогда, включение (х, х) Î R неверно, т.е. утверждение – ложно, значит и (А Ù ) – ложно.

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

Каждой схеме ставится в соответствие формула алгебры высказываний, и каждая формула реализуется с помощью некоторой схемы. Покажем, как уста­новить такое соответствие. Каждому переключателю P ставится в соответствие высказывательная переменная P, которая истинна тогда и только тогда, когда переключатель P замкнут. Схеме с последовательным соединением переключа­телей P и Q соответствует формула, являющаяся конъюнкцией высказаватель­ных переменных, соответствующих этим переключателям, . Схеме с параллель­ным соединением переключателей P и Q соответствует формула, являющаяся дизъюнкцией высказавательных переменных, соответствующих этим переклю­чателям, . Два переключателя P и могут быть связаны так, что когда P замкнут, то разомкнут. Тогда переключателю ставится в соответствие переменная , являющаяся отрицанием P.

Булевы функции

Любую формулу алгебры логики можно рассматривать как функцию, определенную на множестве B = {1, 0}.

Функцией алгебры логики (логической функцией) или булевой функцией f (x ₁,..., x _n) называетсяотображение f: B ⁿ® B, определенное на множестве упорядоченных наборов элементов множества B и принимающее значения из этого множества. Обозначим через P _n – множество булевых функций n переменных.

Логическую функцию n переменных f (x ₁,..., x _n) можно задать таблицей, в левой части которой перечислены все 2 ⁿ наборов значений переменных, а в правой части – значения функции на этих наборах.

 

x1 x2 ... хn-1 xn	f(x1, x2 ,... хn-1 , xn)
0 0... 0 0 0 0... 0 1 0 0... 1 0 ................ 1 1... 1 0 1 1... 1 1	f(0,0,...,0,0) f(0,0,...,0,1) f(0,0,...,1,0) ........ f(1,1,...,1,0) f(1,1,...,1,1)

 

При любом фиксированном упорядочении наборов булева функция n переменных полностью определяется вектор-столбцом своих значений, размерность которого равна числу наборов значений функции, то есть 2 ⁿ . Поэтому число различных функций n переменных равно числу различных двоичных векторов длины 2 ⁿ, то есть , т.е. | | = .

Нулем (единицей) булевой функции назовем упорядоченный набор значений переменных, на котором значение функции равно 0 (1).

Пусть F={ } – некоторое множество булевых функций. Его можно выбрать в качестве основного набора, называемого базисом. Формулой над базисом F (обозначается [F]) называется выражение вида [F]= , где F, а либо переменная, либо формула над F. Таким образом, всякая формула является суперпозицией базисных функций, для её представления обычно применяется форма записи с логическими операциями ~. Каждой формуле однозначно соответствует некоторая булева функция f, в этом случае говорят, что формула реализует функцию f (обозначается func F = f). Как будет показано ниже, такая реализация не единственна.

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

Логических функций одной переменной четыре: две нуль-местные (j₀(х), j₃(х)) – константы 0 и 1, значения которых не зависят от значения переменной, и две одноместные функции – тождественная и отрицание.

 

x	j0	j1	j2	j3

Тождественная функция "повторяет" значение х: j₁(х)=х. Функция отрицание возвращает значение, противоположное значению х: j₂(х)=х.

Логических функций двух переменных шестнадцать:

х1

x2

j0

j1

j2

j3

j4

j5

j6

j7

j8

j9

j10

j11

j12

j13

j14

j15

Рассмотрим подробнее все эти функции.

s j₀(х₁,х₂) 0 и j₁₅ (х₁,х₂) 1.

s j₁(х₁,х₂) = х₁ Ù х₂ . Эта функция называется ещё логическим умножением и обозначается, также, х₁х₂.

s j₂(х₁.х₂) = Ø (х₁®х₂).

s j₃(х₁,х₂) = х₁.

s j₄(х₁.х₂) = Ø (х₂®х₁).

s j₅(х₁,х₂) = х₂.

s j₆(х₁,х₂) = (х₁~х₂) называются неравнозначностью, разделительной дизъюнкцией или сложением по модулю 2 и обозначается еще как х₁Å х₂.

s j₇(х₁.х₂) = х₁Ú х₂ .

s j₈(х₁.х₂) = (х₁Úх₂) – антидизъюнкция, которая называется, также, стрелка Пирса и обозначается х₁¯х₂.

s j₉(х₁.х₂) = х₁~х₂. Эту функцию называют еще равнозначностью и обозначают х₁ºх₂ .

s j₁₀(х₁.х₂) = _.

s j₁₁(х₁.х₂) = х₂®х₁.

s j₁₂(х₁.х₂) = .

s j₁₃(х₁.х₂) = х₁®х₂.

s j₁₄(х₁.х₂) = (х₁Ùх₂) – антиконъюнкция, которая называется еще штрих Шеффера и обозначается х₁ | х₂.

Формулы, реализующие одну и ту же функцию, называются равносильными. Отношение равносильности формул является отношением эквивалентности и обозначается º.

Фиктивной переменной (несущественной) функции f (x ₁,..._, x _n) называется переменная х_i, изменение значения которой не меняет значения функции, то есть f (x ₁,..., х _i-1, 1, x _i+1,..., x _n) = = f (x ₁,..., х _i-1, 0, x _i+1,..., x _n).

Например, в функциях j₃ и j₁₂ переменная х₂ фиктивна, а в функциях j₅ и j₁₀ фиктивна переменная х ₁.

Функция f (x ₁,..., x _n), имеющая фиктивную переменную x _i, по существу зависит от (n– 1)-й переменной, т.е. представляет собой функцию g (x ₁,..., х _i-1, x _i+1,..., x _n). В этом случае говорят, что функция g получена из функции f удалением фиктивной переменной, а функция f получена из функции g введением фиктивной переменной, причём эти функции считаются равными.

Пусть f (x ₁, ¼, x _n) Î P _n – булева функция. Тогда функция f ^*(x ₁, ¼, x _n), определенная следующим образом

f ^*(x ₁, ¼, x _n) = ,

называется двойственной к функции f.

Теорема (Принцип двойственности). Пусть F={ }. Тогда, если формула [F] реализует функцию f, то формула ^* над базисом F^*={ }, полученная из формулы заменой функций f_i на двойственные им функции f_i ^*, реализуют функцию f ^*.

Нормальные формы

Для решения проблемы выполнимости и опровержимости формул используется специальный вид приведённых формул, называемый нормальными формами, определим их.

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

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

Терема 5.1. 1) Элементарная конъюнкция тождественно ложна тогда и только тогда, когда она содержит некоторую высказывательную переменную вместе с её отрицанием.

2) Элементарная дизъюнкция тождественно истинна тогда и только тогда, когда она содержит некоторую высказывательную переменную вместе с её отрицанием.

Доказательство. Докажем утверждение 1. Пусть элементарная конъюнкция тождественно ложна, предположим противное, что она не содержит никакую высказывательную переменную вместе с её отрицанием. Тогда можно построить интерпретацию, на которой эта конъюнкция истинна, придав переменным входящим в неё без отрицаний значение 1, а с отрицанием – 0. Следовательно, получено противоречие с предположением о тождественной ложности элементарной конъюнкции.

Обратное утверждение непосредственно следует из закона противоречия 9 и свойств констант 6.

Утверждение 2 доказывается аналогично.

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

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

Примеры.

1. - КНФ.

2. - ДНФ.

3. приведенная формула, но не является ни ДНФ, ни КНФ.

4. является и ДНФ, и КНФ.

Теорема 5.2. Для всякой формулы U существуют эквивалентные ей КН-форма и ДН-форма.

Алгоритм построения нормальных форм.

1. Преобразовать формулу к приведенному виду (см. п.2).

2. Если полученная формула не является нормальной, то преобразовать ее к требуемой нормальной форме с помощью свойства взаимной дистрибутивности 5 операций конъюнкции и дизъюнкции.

Например ДНФ формулы примера 1 получим непосредственно по свойству 5 º . Упростив формулу примера 3 по закону обобщенного склеивания º , получим КН- и ДН-форму.

Задание 1. Построить нормальные формы формулы

.

Решение. Преобразуем формулу к приведенному виду и затем упростим ее.

º º º º º º

Полученная формула является КН- и ДН-формой.

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

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

Совершенной конъюнктивной нормальной формой (СКНФ) называется КНФ в каждой дизъюнкции которой содержатся точно одно вхождение всех переменных или их отрицаний. Такие дизъюнкции называются полными.

Теорема 5.3. 1) Всякая элементарная дизъюнкция высказывательных переменных , не являющаяся ТИ-формулой, эквивалентна некоторой СКН-форме от этих высказывательных переменных.

2) Всякая элементарная конъюнкция высказывательных переменных , не являющаяся ТЛ-формулой, эквивалентна некоторой СДН-форме от этих высказывательных переменных.

Доказательство. Докажем утверждение 1. Так как элементарная дизъюнкция не является тождественно истинной, то в силу теоремы 4.1 она не содержит никакую высказывательную переменную вместе с её отрицанием. Если некоторая переменная (или её отрицание ) входит в элементарную дизъюнкцию несколько раз, то в силу идемпотентности операции дизъюнкции, оставим только одно её вхождение. Если же некоторая переменная не содержится в элементарной дизъюнкции, то, воспользовавшись законом склеивания 13

º º Ù

Ù ,

получим КНФ. Если полученная форма не является совершенной, то для каждой её элементарной дизъюнкции повторим данную операцию. Таким образом, за конечное число применений закона склеивания получим СКНФ.

Утверждение 2 доказывается аналогично.

Следствие. Для всякой формулы, образованных из высказывательных переменных не являющейся тождественно истинной и тождественно ложной, существуют эквивалентные им СКН-форма и СДН-форма.

Доказательство теоремы 4.3 содержит алгоритм построения совершенных нормальных форм. Для этого нужно построить соответствующую нормальную форму, а если она не является совершенной, то расщепить конъюнкции (дизъюнкции), которые содержат не все переменные, по свойству 13.

Обе нормальные формы, построенные в задании 1, не являются совершенными. Приведем их к совершенному виду.

º – СКН-форма.

º º

º Ú Ú

Ú Ú º

º Ú Ú – СДН-форма.

С помощью совершенных нормальных форм можно решить проблему выполнимости или опровержимости формулы.

Для того чтобы найти, при каких значениях высказывательных переменных формула является выполнимой, необходимо построить ее СДН-форму. Количество таких наборов равно числу полных элементарных конъюнкций, так как, если одна из них истинна, то истинна и вся формула. Элементарная конъюнкция истинна, когда истинны все её составляющие, следовательно, если переменная входит в неё без отрицания, то она принимает значение 1, а если с отрицанием, то – 0. Аналогично, для решения задачи опровержимости строится СКН-форма.

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

Легко проверить, что , .

Теорема 5.4 (о разложении булевых функций). Любую булеву функцию можно представить в виде

(5.1)

где дизъюнкции берутся по всем возможным наборам ().

Доказательство. Покажем, что правая часть равенства (5.1) совпадает с левой на произвольном фиксированном наборе значений переменных (). Подставив эти значения в левую часть (5.1), получим

,

так как, если хотя бы одно из значений отличается от , то , а, следовательно, обращается в 0 и вся конъюнкция. Таким образом, отличной от 0 будет только конъюнкция на наборе () = (), а так как , то

.

Положив в (5.1) m = n, получим

f (x₁ , …, х_n) = Ú (x₁ ~ s₁) Ù…Ù (x_n ~ s_n) Ù f (s₁ , …, s_n).

s₁,.., s_n

Очевидно, среди всех дизъюнкций нужно оставить только те, в которых f (s₁ , …, s_n) = 1. Окончательно получим

(5.2)

Полученная формула разложения является совершенной дизъюнктивной нормальной формой булевой функции.

Теорема 5.5. Всякая булева функция (кроме 0) имеет единственную СДН-форму

.

С помощью принципа двойственности легко доказать представление функции СКН-формой.

Теорема 5.6. Всякая булева функция (кроме 1) имеет единственную СКН-форму

. (5.3)

Совершенные нормальные формы используются также для решения задачи, обратной задаче разрешимости – построение реализации булевой функции, заданной таблицей. Нули функции определяют полные элементарные дизъюнкции, входящие в СКН-форму функции. Такая дизъюнкция строится так, чтобы все составляющие ее переменные или их отрицания обращались в нуль, т.е. если значение переменной 0, то переменная входит в дизъюнкцию без отрицания, если – 1, то – с отрицанием. Соответственно, по единицам булевой функции можно построить ее СДН-форму.

Например, функция f переменных x₁, x₂, x₃, заданная в таблице

x1	x2	x3	f

 

имеет следующие совершенные нормальные формы:

– СКН-форма;

– СДН-форма.

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

Для вычисления значений булевых функций в общем случае надо использовать сложную рекурсивную процедуру (см. [3], п. 3.2.1.), т.к. надо определить все подформулы вплоть до Х_i или . При использовании совершенных форм алгоритм вычисления будет намного проще и эффективнее.

В ЭВМ совершенные формы представляются в виде матрицы размера k´n, состоящей из нулей и единиц, где k – число членов разложения (элементарных конъюнкций или дизъюнкций); n – число пропозиционных переменных. Матрица F представляет собой часть общей таблицы истинности, определяющей булеву функцию f. Для представления СДНФ берутся строки, соответствующие единицам f, а для СКНФ – строки, соответствующие нулям f.

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

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

Например, вычислим значение функции f(x₁, x₂) = x₁ ~ x₂ при x₁ = 0; x₂ = 1. Запишем таблицу истинности функции f:

x1	x2	f

Тогда F_СДНФ = ; F_СКНФ = . Поскольку ни одна из строк F_СДНФ, которая определяет наборы значений переменных, соответствующие 1 функции, не совпала с заданными значениями х_j, то f (0, 1) = 0.

Тоже самое можно определить и по СКНФ, так как первая строка F_СКНФ совпадает со значениями х_j, то f (0, 1) = 0.

Определение. Булеву функцию называют импликантой булевой функции , если для любых наборов значений переменных из следует .

Если функция представлена ДНФ, то любая её элементарная конъюнкция будет её импликантой.

Определение. ДНФ называется минимальной, если она содержит наименьшее число вхождений переменных среди всех ДНФ, эквивалентных ей.

Определение. Длиной ДНФ называют число входящих в неё элементарных конъюнкций. ДНФ называют кратчайшей, если она имеет наименьшую длину среди всех эквивалентных ей ДНФ.

Минимальная ДНФ всегда является кратчайшей, обратное неверно.