.RU

§ 5.12: Релейно-контактные схемы - Приднестровский государственный университет им. Т. Г. Шевченко инженерно-технический...


^ § 5.12: Релейно-контактные схемы

Рассмотрим одно из приложений логических функций к релейно-контактным схемам.

Пусть x1, x2, ..., xn – набор контактов в электрической схеме. Контакты могут быть замыкающими и размыкающими. Контакт называется размыкающим, если он размыкается при подаче напряжения на обмотку реле, к которому он подключен, а когда напряжение не подается, контакт замкнут. Контакт называется замыкающим, если он замыкается при подаче напряжения на обмотку реле, к которому он подключен, а когда напряжение не подается, контакт разомкнут. В схеме один и тот же контакт может неоднократно быть как размыкающим, так и замыкающим. Будем считать, что xi=1, если на обмотку контакта подается напряжение и xi=0, если на обмотку контакта не подается напряжение.

Каждой последовательно-параллельной схеме с контактами x1, x2, ..., xn поставим в соответствие ее функцию проводимости:



Тогда функция проводимости схемы, состоящей из одного контакта xi, есть , где i=1, если контакт замыкающий, и i=0, если контакт размыкающий. Функция проводимости схемы из последовательно соединенных контактов xi и xj есть &(рис.5.2), а функция проводимости схемы из параллельно соединенных контактов xi и xj есть (рис.5.3).




xi xj : & ,

Рис. 5.2. Последовательное соединение контактов.




xi

:  .

xj


Рис. 5.3. Параллельное соединение контактов.


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

Пример: Упростить электрическую схему (рис.5.4):




Y Z


X Z


Z

Рис5.4. Исходная схема.


Функция проводимости: YZX Z  Z= YZ(Z) (X)= YZZ=

= Z(Y)=Z

Эквивалентная схема (рис.5.5):




Z


Рис.5.5. Упрощенная схема.


^ § 5.13: Минимизация булевых формул в классе дизъюнктивных нормальных форм

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

а) х1х2 х1=х1

б) х1х2х1=х1

в) х1х2х1х3=х1(х2х3).

Заметим что последнее преобразование выводит формулу из класса дизъюнктивных нормальных форм. Будем минимизировать формулы в классе ДНФ.

Дизъюнктивная нормальная форма называется минимальной, если она содержит наименьшее общее число вхождений переменных по сравнению со всеми равносильными ей дизъюнктивными нормальными формами.

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

Существуют эффективные способы нахождения минимальной ДНФ.
^ 5.13.1: Метод минимизирующих карт

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

Пусть булевая функция задана таблицей истинности или СДНФ. Составим следующую карту.

Утверждение 5.1: Если конъюнкция x11...хn n, i{0, 1}i=1,..., nпринадлежащая j-й строке табл.5.8не входит в СДНФ, выражающую функцию f(Х1,..., Хn) то любая конъюнкция j-й строки не входит ни в какую ДНФ, выражающую исходную функцию.

Замечание:

x =

Действительно, если конъюнкция x11...хnn не входит в СДНФ, выражающую функцию f(х1,...,хn) то по алгоритму построения СДНФ (см. §5.4) f(1,...,n)=0. Если бы какая-то конъюнкция j-й строки вошла в некоторую ДНФ функции fто f(1,...,n)=1.

Опишем способ построения минимальной ДНФ :

1. Отметим в табл. 5.8 строки в которых соответствующая им конъюнкция x11...хnn не принадлежит СДНФ выражающей функцию f(х1,..., хn). Вычеркнем все конъюнкции в этих строках.

2. Вычеркнутые в этих строках конъюнкции вычеркнем также во всех остальных строках таблицы.

3. В каждой строке выберем из оставшихся конъюнкций лишь конъюнкции с наименьшим числом сомножителей, а остальные вычеркнем

4. В каждой строке выберем по одному оставшемуся элементу и составим из них ДНФ

5. Из всех ДНФ, полученных в п.4, выберем минимальную.

Заметим что в п.5 предусматривает перебор различных ДНФ для нахождения минимальной из них Однако при этом число вариантов перебора, как правило, меньше чем в случае когда перебираются все равносильные.

Таблица 5.9


x1

x2



xn-1

xn

x1x2

x1x3



xn-2xn

xn-1xn



x1x2…xn-1 xn

x1

x2



xn-1



x1x2

x1x3





xn-1



x1x2…xn-1

x1

x2





xn

x1x2

x1x3



xn-2xn

xn



x1x2… xn


















































Действуя в соответствии с пп. 1-5получим минимальную ДНФ выражающую функцию f(х1,...,хn).Пусть F-формула в ДНФ полученная в п.5. Тогда еслиf(1,..., n)=1 то F(1,...,n)=1. Действительно если конъюнкция x11...хnn соответствует j-й строке табл5.8.то эта строка осталась невычеркнутой ; любая конъюнкция в этой строке на наборе <1,..., n > принимает значение 1. Следовательно и формула F содержащая одну из таких конъюнкций в качестве дизъюнктивного члена принимает на наборе <1,..., n > значение 1т е.F(1,..., n)=1.Если f (1,..., n)=0то на наборе <1,..., n > все не вычеркнутые в табл.5.1. конъюнкции принимают значение 0так как все конъюнкции которые на этой
оценке принимают значение 1вычеркнуты. Следовательно составленная из этих конъюнкций ДНФ принимает на этой оценке значение 0т.е. F(1,..., n)=0.

Пример:. Пусть f (х1, х2, х3)=х1 х2 х1 х3  х1  х3.

Составим табл.5.10.

Отметим значком * вычеркнутые строки. После применения пп.4 и 5 получим минимальную ДНФ  х1  х3.

Таблица 5.10.

х1

х2

х3

х1 х2

х1 х3

х2 х3

х1 х2 х3

*

х1

х2



х1 х2

х1

х2

х1 х2




х1



х3

х1

х1 х3

х3

х1 х3




х1





х1

х1



х1






х2

х3

х2

х3

х2 х3

х2 х3

*



х2



х2



х2

х2

*





х3



х3

х3

х3


















*


Таблица 5.11.


































х1
















х1




х3













х1

х1
































































х3


























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

Рассмотрим произвольную конъюнктивную нормальную форму исходной формулы. Воспользуемся законом обобщенной дистрибутивности (а1...  ar) & (b1...  bi)= =(a1 & b1)... (a1 & bi)...  (ar & bi) и "раскроем" скобки. Затем произведем упрощения полученной формулы; пользуясь равносильностями (a&b)a=aaa=a и удаляя тождественно ложные дизъюнктивные члены. В результате получим ДНФ которая называется сокращенной



1101-onkogematologiya-m-i-davidova-rezultati-nauchnih-issledovanij-gotovie-k-prakticheskomu-primeneniyu-obobsheni.html
11092008-g-s-23-tema-stroitelstvo-stroitelen-kontrol.html
111-viravnivanie-byudzhetnoj-obespechennosti-municipalnih-obrazovanij-respubliki-bashkortostan.html
112-na-kakuyu-loyalnost-mozhet-rasschitivat-prodavec-mihail-naumovich-dimshic.html
112-programmirovanie-v-obshej-sisteme-kursov-informatiki-v-visshej-shkole-zh-k-nurbekova.html
113-averkiev-fv-azniirh.html
  • lektsiya.bystrickaya.ru/programma-disciplini-po-kafedre-sociologii-politologii-i-socialnoj-raboti-pedagogika.html
  • paragraph.bystrickaya.ru/metodicheskie-rekomendacii-k-uchebnikam-a-n-saharova-i-v-i-buganova-istoriya-rossii-s-drevnejshih-vremen-do-konca-xvii-veka-stranica-2.html
  • predmet.bystrickaya.ru/soderzhanie-diska.html
  • knowledge.bystrickaya.ru/monitoring-uspevaemosti-uchashihsya-v-problemnih-gruppah-publichnij-doklad-municipalnogo-obsheobrazovatelnogo-uchrezhdeniya.html
  • abstract.bystrickaya.ru/34-trebovaniya-pri-obrashenii-s-edkimi-yadovitimi-veshestvami-kaliem-natriem.html
  • essay.bystrickaya.ru/chast-tretya-flag-kapitani--1-malchik-so-shpagoj.html
  • composition.bystrickaya.ru/plani-seminarskih-zanyatij-zadachi-i-uprazhneniya-dlya-studentov-zaochnoj-formi-obucheniyaotdeleniya.html
  • occupation.bystrickaya.ru/obrashenie-s-othodami-na-territorii-rso-alaniya-polozhenie-o-territorialnom-planirovanii-1.html
  • writing.bystrickaya.ru/grazhdanskoe-torgovoe-i-mezhdunarodnoe-chastnoe-pravo.html
  • obrazovanie.bystrickaya.ru/prava-i-obyazannosti-pobeditelya-aukciona-dokumentaciya-ob-aukcione-47.html
  • uchitel.bystrickaya.ru/referat-brak-i-semya-v-starovavilonskom-carstve.html
  • tetrad.bystrickaya.ru/uroki-dlya-iraka-60-letie-okonchaniya-vtoroj-mirovoj-vojni-odno-iz-naibolee-yarkih-politicheskih-sobitij-pervoj-polovini.html
  • laboratornaya.bystrickaya.ru/programmi-problemi-organizacii-vichislenij-na-mnogoprocessornih-vichislitelnih-sistemah-apparatnaya-realizaciya-isa-invariantnie-svojstva-isa.html
  • report.bystrickaya.ru/grammatikali-terminder-zerttelu-a-b-sarbalina.html
  • laboratornaya.bystrickaya.ru/razdel-vii-ispravitelnaya-penitenciarnaya-psihologiya-g-g-shihancev-yuridicheskaya-psihologiya.html
  • paragraph.bystrickaya.ru/medicinskie-programmi-komissiya-agentstv-8-check-up-obshij-stranica-8.html
  • textbook.bystrickaya.ru/internet-resursi-pervij-kanal-novosti-25-08-2005-18-00-00-9.html
  • essay.bystrickaya.ru/cikl-5-does-your-health-depend-on-you-rabochaya-programma-po-anglijskomu-yaziku-6-klass.html
  • institut.bystrickaya.ru/strimer-uchebnoe-posobie-po-kursu-organizaciya-evm-kompleksov-i-setej-chast.html
  • reading.bystrickaya.ru/korolevstvo-belgiya-informaciya-o-hode-vipolneniya-mezhdunarodnih-dogovorov-respubliki-kazahstan.html
  • college.bystrickaya.ru/-259-operator-po-obsluzhivaniyu-spravochnika-rabot-i-professij-rabochih-vipusk-1.html
  • testyi.bystrickaya.ru/administratori-fasilitatori-sredi-pravitelej-nailuchshij-tot-stranica-2.html
  • nauka.bystrickaya.ru/vi-obshie-trebovaniya-k-proizvodstvu-poletov-federalnie-aviacionnie-pravila.html
  • portfolio.bystrickaya.ru/ogranicheniya-analiza-chuvstvitelnosti-otchet-o-pribilyah-i-ubitkah-10-otchet-o-sovokupnih-dohodah-12.html
  • literatura.bystrickaya.ru/skazka-zoopark-skazka.html
  • school.bystrickaya.ru/joan-halifax-the-human-encounter-with-death-stranica-7.html
  • urok.bystrickaya.ru/pourochnoe-planirovanie-9-klassi-predmet-novejshaya-istoriya-zarubezhnih-stran-28-chasov-.html
  • uchebnik.bystrickaya.ru/uchrediteli-gorodskoj-konkurs-shkolnoj-ligi-kvn-g-minska-provoditsya-v-6-etapov-ietap.html
  • uchitel.bystrickaya.ru/programma-razvitiya-goroda-temirtau-na-2011-2015-godi-soderzhanie.html
  • literature.bystrickaya.ru/d-deyatelnost-socialnaya-50-dogovor-kollektivnij-318-dolya-oplati-truda-v-vvp-39-z.html
  • uchebnik.bystrickaya.ru/uchebno-metodicheskij-kompleks-disciplini-istoriya-mirovoj-i-otechestvennoj-kulturi.html
  • exchangerate.bystrickaya.ru/klassicheskij-koncert.html
  • composition.bystrickaya.ru/perechen-zakonoproektov-rassmotrennih-oblastnoj-dumoj-za-i-polugodie-2010-goda-1-zakonodatelnaya-deyatelnost-3.html
  • doklad.bystrickaya.ru/vneklassnoe-meropriyatie-na-puti-k-olimpu-2007.html
  • uchit.bystrickaya.ru/tehnicheskie-trebovaniya-na-okazanie-telekommunikacionnih-uslug-po-predostavleniyu-kanalov-svyazi-dlya-obektov-departamenta-kulturi-goroda-moskvi-stranica-4.html
  • © bystrickaya.ru
    Мобильный рефератник - для мобильных людей.