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

Конъюнктивная нормальная форма1 (КНФ) определяется двойственно к ДНФ. Простой дизъюнкцией или дизъюнктом называется дизъюнкция одной или нескольких переменных или их отрицаний, причём каждая переменная входит в неё не более одного раза. КНФ — это конъюнкция простых дизъюнкций.

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

КНФ может быть преобразована к эквивалентной ей ДНФ путём раскрытия скобок по правилу:

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

выражающее дистрибутивность дизъюнкции относительно конъюнкции. Результат нужно преобразовать описанным выше способом, заменив слово «конъюнкция» на «дизъюнкция» и наоборот.

22. Применение булевых функций к релейно-контактным схемам. Понятие релейно-контактная схема. Функция проводимости.

П р и м е н е н и е б у л е в ых ф у н к ц и й

к р е л е й н о - к о н т а к т н ым с х е м ам

П од релейно-контактной схемой п о н и м а е т ся у с т р о й с т во из

п р о в о д н и к ов и д в у х п о з и ц и о н н ых к о н т а к т о в, ч е р ез к о т о р ое п о л ю сы

и с т о ч н и ка с в я з а ны с н е к о т о р ым п о т р е б и т е л е м.

К о н т а к ты м о г ут б ы ть замыкающими и ли размыкающими. К а ж­

д ый к о н т а кт п о д к л ю ч ен к н е к о т о р о му р е ле ( п е р е к л ю ч а т е л ю ). К о г да

р е ле с р а б а т ы в а ет ( н а х о д и т ся п од т о к о м ), в се п о д к л ю ч е н н ые к н е му

з а м ы к а ю щ ие к о н т а к ты з а м к н у т ы, а р а з м ы к а ю щ ие к о н т а к ты р а з о м к-н у т ы, в п р о т и в н ом с л у ч ае н а о б о р о т. К а ж д о му р е ле с т а в и т ся в с о о т­

в е т с т в ие с в оя б у л е ва п е р е м е н н ая х, к о т о р ая п р и н и м а ет з н а ч е н ие 1,

е с ли р е ле с р а б а т ы в а е т, и 0 в п р о т и в н ом с л у ч а е.

На ч е р т е ж ах в се з а м ы к а ю щ ие к о н т а к т ы, п о д к л ю ч е н н ые к р е ле х,

о б о з н а ч ают ся т ем же с и м в о л ом х, а р а з м ы к а ю щ ие - с и м в о л ом х. Э то

означа е т, ч то п ри с р а б а т ы в а н ии ре ле х в се е го з а м ы к а ю щ ие к о н т а к ты х

п р о в о д ят т ок и им с о о т в е т с т в у ет 1, а. в се р а з м ы к а ю щ ие п е р е к л ю ч а т е­

ли ( к о н т а к т ы) х не п р о в о д ят т ок и им с о о т в е т с т в у ет 0; п ри о т к л ю ч е­

н ии р е ле с о з д а е т ся п р о т и в о п о л о ж н ая с и т у а ц и я.

В с ей с х е ме т а к же с т а в и т ся в с о о т в е т с т в ие б у л е ва п е р е м е н н ая у,

к о т о р ая р а в на 1, е с ли с х е ма п р о в о д ит т о к, и р а в на 0 в п р о т и в н ом с лу­

ч а е. П е р е м е н н ая у, с о о т в е т с т в у ю щ ая с х е м е, о ч е в и д н о, я в л я е т ся б у л е­

вой ф у н к ц и ей от п е р е м е н н ых х ь

х2

, х„, с о о т в е т с т в у ю щ их р е л е.

Д ве р е л е й н о - к о н т а к т н ые с х е мы н а з ы в а ю т ся равносильными,

е с ли о д на из н их п р о в о д ит т ок т о г да и т о л ь ко т о г д а, к о г да д р у г ая

с х е ма п р о в о д ит т о к, т . е. е с ли о бе с х е мы о б л а д а ют о д и н а к о в ы ми

ф у н к ц и я ми п р о в о д и м о с т и.

Из д в ух р а в н о с и л ь н ых с х ем б о л ее п р о с т ой с ч и т а е т ся т а, к о т о р ая

с о д е р ж ит м е н ь ш ее ч и с ло к о н т а к т о в.

Синтез релейно-контактных схем п р е д с т а в л я ет с о б ой п о с т р о е­

н ие с х ем по а н а л и т и ч е с к им в ы р а ж е н и я м, п о л у ч е н н ым из н е к о т о р ых

у с л о в ий п о с ле их у п р о щ е н и я.

Анализ релейно-контактных схем п р е д с т а в л я ет с о б ой п о с т р о е­

н ие ф у н к ц ий по д а н н ым с х е м а м. Р а с с м о т р им н е к о т о р ые п р и м е ры и на

их о с н о в а н ии п р о а н а л и з и р у ем р е л е й н о - к о н т а к т н ые с х е м ы.

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