Булевы функции и формулы алгебры высказываний.
Основные формулы алгебры высказываний:
1. |
|
2. |
Законы |
3. |
де Моргана |
4. |
|
5. |
|
Эти фомулы могут быть доказаны сравнением соответствующих таблиц истинности.
Из двух высказываний А и В можно составить четыре импликации, которые носят название
A 
B прямая
теорема
B
A обратная
теорема
противоположная
теорема
теорема
противоположная к обратной
Из основных формул алгебры высказываний следует, что
( A
B ) 
(
)
( B
A )
(
)
Следует отметить, что из истинности прямой теоремы еще не следует истинность обратной к ней теоремы, как это видно из примера 1.1.1.
Доказать истинность теоремы ( A B ) можно, доказав истинность теоремы ( ) , так как эти теоремы эквивалентны. На этом основано доказательство от противного теоремы( A B ) , а именно, имея истинность , предполагая истинность , и доказав, что из следует , мы получаем противоречие ( A и одновременно истинны ), что не может быть, значит - ложно, тогда В - истинно и, значит, импликация A B - истинна.
Нормальные формы булевых функций.
Дизъюнктивная нормальная форма
Простой конъюнкцией или конъюнктом называется конъюнкция некоторого конечного набора переменных или их отрицаний, причём каждая переменная встречается не более одного раза. Дизъюнктивной нормальной формой или ДНФ называется дизъюнкция простых конъюнкций. Элементарная конъюнкция
правильная, если в неё каждая переменная входит не более одного раза (включая отрицание);
полная, если в неё каждая переменная (или её отрицание) входит ровно 1 раз;
монотонная, если она не содержит отрицаний переменных.
Например — является ДНФ.
Совершенной дизъюнктивной нормальной формой или СДНФ относительно некоторого заданного конечного набора переменных называется такая ДНФ, у которой в каждую конъюнкцию входят все переменные данного набора, причём в одном и том же порядке. Например: .
Легко убедиться, что каждой булевой функции соответствует некоторая ДНФ, а функции отличной от тождественного нуля — даже СДНФ. Для этого достаточно в таблице истинности этой функции найти все булевы векторы, на которых её значение равно 1, и для каждого такого вектора построить конъюнкцию , где . Дизъюнкция этих конъюнкций является СДНФ исходной функции, поскольку на всех булевых векторах её значения совпадают со значениями исходной функции. Например, для импликации результатом является , что можно упростить до .
Конъюнктивная нормальная форма
Конъюнктивная нормальная форма1 (КНФ) определяется двойственно к ДНФ. Простой дизъюнкцией или дизъюнктом называется дизъюнкция одной или нескольких переменных или их отрицаний, причём каждая переменная входит в неё не более одного раза. КНФ — это конъюнкция простых дизъюнкций.
Совершенной конъюнктивной нормальной формой (СКНФ), относительно некоторого заданного конечного набора переменных, называется такая КНФ, у которой в каждую дизъюнкцию входят все переменные данного набора, причём в одном и том же порядке. Поскольку (С)КНФ и (С)ДНФ взаимодвойственны, свойства (С)КНФ повторяют все свойства (С)ДНФ, грубо говоря, «с точностью до наоборот».
КНФ может быть преобразована к эквивалентной ей ДНФ путём раскрытия скобок по правилу:
которое выражает дистрибутивность конъюнкции относительно дизъюнкции. После этого необходимо в каждой конъюнкции удалить повторяющиеся переменные или их отрицания, а также выбросить из дизъюнкции все конъюнкции, в которых встречается переменная вместе со своим отрицанием. При этом результатом не обязательно будет СДНФ, даже если исходная КНФ была СКНФ. Точно также можно всегда перейти от ДНФ к КНФ. Для этого следует использовать правило
выражающее дистрибутивность дизъюнкции относительно конъюнкции. Результат нужно преобразовать описанным выше способом, заменив слово «конъюнкция» на «дизъюнкция» и наоборот.
Применение булевых функций к релейно-контактным схемам. Понятие релейно-контактная схема. Функция проводимости.
П р и м е н е н и е б у л е в ых ф у н к ц и й
к р е л е й н о - к о н т а к т н ым с х е м ам
П од релейно-контактной схемой п о н и м а е т ся у с т р о й с т во из
п р о в о д н и к ов и д в у х п о з и ц и о н н ых к о н т а к т о в, ч е р ез к о т о р ое п о л ю сы
и с т о ч н и ка с в я з а ны с н е к о т о р ым п о т р е б и т е л е м.
К о н т а к ты м о г ут б ы ть замыкающими и ли размыкающими. К а ж
д ый к о н т а кт п о д к л ю ч ен к н е к о т о р о му р е ле ( п е р е к л ю ч а т е л ю ). К о г да
р е ле с р а б а т ы в а ет ( н а х о д и т ся п од т о к о м ), в се п о д к л ю ч е н н ые к н е му
з а м ы к а ю щ ие к о н т а к ты з а м к н у т ы, а р а з м ы к а ю щ ие к о н т а к ты р а з о м к-н у т ы, в п р о т и в н ом с л у ч ае н а о б о р о т. К а ж д о му р е ле с т а в и т ся в с о о т
в е т с т в ие с в оя б у л е ва п е р е м е н н ая х, к о т о р ая п р и н и м а ет з н а ч е н ие 1,
е с ли р е ле с р а б а т ы в а е т, и 0 в п р о т и в н ом с л у ч а е.
На ч е р т е ж ах в се з а м ы к а ю щ ие к о н т а к т ы, п о д к л ю ч е н н ые к р е ле х,
о б о з н а ч ают ся т ем же с и м в о л ом х, а р а з м ы к а ю щ ие - с и м в о л ом х. Э то
означа е т, ч то п ри с р а б а т ы в а н ии ре ле х в се е го з а м ы к а ю щ ие к о н т а к ты х
п р о в о д ят т ок и им с о о т в е т с т в у ет 1, а. в се р а з м ы к а ю щ ие п е р е к л ю ч а т е
ли ( к о н т а к т ы) х не п р о в о д ят т ок и им с о о т в е т с т в у ет 0; п ри о т к л ю ч е
н ии р е ле с о з д а е т ся п р о т и в о п о л о ж н ая с и т у а ц и я.
В с ей с х е ме т а к же с т а в и т ся в с о о т в е т с т в ие б у л е ва п е р е м е н н ая у,
к о т о р ая р а в на 1, е с ли с х е ма п р о в о д ит т о к, и р а в на 0 в п р о т и в н ом с лу
ч а е. П е р е м е н н ая у, с о о т в е т с т в у ю щ ая с х е м е, о ч е в и д н о, я в л я е т ся б у л е
вой ф у н к ц и ей от п е р е м е н н ых х ь
х2
, х„, с о о т в е т с т в у ю щ их р е л е.
Д ве р е л е й н о - к о н т а к т н ые с х е мы н а з ы в а ю т ся равносильными,
е с ли о д на из н их п р о в о д ит т ок т о г да и т о л ь ко т о г д а, к о г да д р у г ая
с х е ма п р о в о д ит т о к, т . е. е с ли о бе с х е мы о б л а д а ют о д и н а к о в ы ми
ф у н к ц и я ми п р о в о д и м о с т и.
Из д в ух р а в н о с и л ь н ых с х ем б о л ее п р о с т ой с ч и т а е т ся т а, к о т о р ая
с о д е р ж ит м е н ь ш ее ч и с ло к о н т а к т о в.
Синтез релейно-контактных схем п р е д с т а в л я ет с о б ой п о с т р о е
н ие с х ем по а н а л и т и ч е с к им в ы р а ж е н и я м, п о л у ч е н н ым из н е к о т о р ых
у с л о в ий п о с ле их у п р о щ е н и я.
Анализ релейно-контактных схем п р е д с т а в л я ет с о б ой п о с т р о е
н ие ф у н к ц ий по д а н н ым с х е м а м. Р а с с м о т р им н е к о т о р ые п р и м е ры и на
их о с н о в а н ии п р о а н а л и з и р у ем р е л е й н о - к о н т а к т н ые с х е м ы.
Всей переключательной схеме также можно поставить в соответствие логическую переменную, равную единице, если схема проводит ток, и равную нулю — если не проводит. Эта переменная является функцией от переменных, соответствующих всем переключателям схемы, и называется функцией проводимости.
Применение булевых функций к релейно-контактным схемам. Функция проводимости. Простейшие релейно-контактные схемы (последовательное и параллельное соединение) и их функции проводимости. Реализация в виде релейно-контактной схемы импликации и эквиваленции.
Простейшие
релейно-контактные схемы (последовательное
и параллельное соединение) и их функции
проводимости
Реализация в виде релейно-контактной схемы импликации и эквиваленции Специальных логических элементов для импликации и эквивалентности нет, т.к. А => В можно заменить на ¬А V В ; А <=> В можно заменить на (A & B)V(¬A & ¬B).