Игошин Математическая логика и теория алгоритмов (1019110), страница 28
Текст из файла (страница 28)
По- 110 этому, если |р(0, ..., 0) = а, то найдется такой набор ап ..., а„, что |р(ан ..4, а„) = а'. Построим функцию 74(х, у) по следующему правилу: 74(х, у) = х. ф(у) + |р(у), где х = х,, ф(у) = |р(у, ..., у'"), ф(у) = |р(у«|,...,у ), гле, в свою очередь, О,еслиа; = 0; у«У у, если а| = 1, лля 2 < 1 я и. (Заметим, что мы можем подставлять 0 вместо хь так как функция 0 нами уже получена.) Тогда ясно, что ф(0) = = |р(0, ..., 0) = а, |р(1) = |р (а|ь ..., а„) = а'.
Следовательно, ф(у) = у или ф(у) =у'. Заметим, что у' = у+ 1 (см. Задачник, № 4.47, а). Значит, ф(у) можно представить в виде ф(у) =у+ Ь4ь где Ьл = 0 или 1. Кроме того, ясно, что функцию одного аргумента |р(у) можно представить в виде линейного полинома Жегалкина: ф(у) = Ь,у+ Ь,. Таким образом, 14(х, у) имеет вид: 74(х, у) = х(у+ Ьл) + (Ь!у+ Ьз) = = ху+ Ьх+ су+ о. Рассмотрим всевозможные случаи для коэффициентов Ь, с, о.
Если Ь = с = с( = О, то ~4(х, у) = х . у. Если Ь = 1, то рассмотрим функцию Д(х,у) =~4(х,у) = ху'+ х+ + су'+ о' = х(у+ 1) + х+ с(у+ 1)о = ху+ х+ х+ су+ с+ а' = ху+ су+ сь (Заметим, что мы можем подставлять у' вместо у, так как функция «отрицание» нами уже получена.) Если с = с| = О, то у4(хру) = х |. Если с = 1, то рассмотрим функцию 14«(х,у) = 14(х,у)= ху+ у+ + с, = (Х4- 1)у 4- у+ с, = ху+ у+ у+ с| — — ху+ с|. Если в ней с| = О, то у4 (х, у) = х ',у. Если же с, = 1, то 74«(х, у) = ху+ 1 = (х. у)' = х ~ у (штрих Шеффера).
итак, из функций Де„Яп /н Я, г4, имеющихся в данной системе функций, мы получаем с помощью суперпозиций функции х' и х у или же функцию х ~ у. Поскольку на основании теоремы 11.2 каждая из систем булевых функций (', .) и ( ~ ) полна, то и данная система булевых функций Я, Я,, ..., г"„...) полна. Теорема полностью доказана. С) 5 12. Применение булевых функций к релейно-контактным схемам Булевы функции широко применяются при описании работы дискретных управляющих систем (контактных схем, схем из функциональных элементов, логических сетей и т.д.)„при исследовании некоторых электрических цепей, так называемых релейно- контактных схем.
Идея применения. Под релейно-контактной схемой понимается устройство из проводников и двухпозиционных контактов. Оно 111 Файл взят с сайта и и и.ко~фея.ги, на котором есть аде много интересной литературы может быть предназначено, например, лля соединения (или разъединения) полюсов источника тока с некоторым потребителем. Контакты релейно-контактной схемы могут быть двух типов: замыкающие и размыкающие. Каждый контакт подключен к некоторому реле (переключателю). К одному реле может быть подключено несколько контактов — как замыкающих, так и размыкающих. Технически реле представляет собой катушку с металлическим сердечником (магнитопроводом), вблизи которого находится соответствующий контакт. Когда через катушку пропускается электрический ток, металлический сердечник намагничивается и замыкает все находящиеся при нем замыкающие контакты.
Одновременно все размыкающие контакты, относящиеся к данному реле, размыкаются. Поскольку замыкающие контакты при отсутствии в реле электрического тока разомкнуты, то они называются также нормально разомкнутыми. Аналогично, размыкающие контакты называются также нормально замкнутыми. При обесточивании обмоток реле (т.е. когда реле отключается) все замыкающие контакты снова размыкаются, а все размыкающие, замыкаются. Каждому реле ставится в соответствие своя булева переменная хо или хз, ..., или х„, которая принимает значение 1, когда реле срабатывает, и принимает значение О при отключении реле.
На чертеже все замыкающие контакты, подключенные к реле х, обозначаются тем же символом х, а все размыкающие контакты, подключенные к этому реле, обозначаются отрицанием х'. Это означает, что при срабатывании реле х все его замыкающие контакты х проводят ток и им сопоставляется значение 1, а все размыкающие контакты к'не проводят электрический ток и им сопоставляется значение О.
При отключенном реле х создается противоположная ситуация: все его замыкающие контакты х разомкнуты, т.е. в этот момент им сопоставляется (переменная х принимает) значение О, а все его размыкающие контакты х' замкнуты, т.е. в этот момент им сопоставляется (другими словами, переменная х' принимает) значение !. Всей релейно-контактной схеме тогда ставится в соответствие булева переменная у, зависящая от булевых переменных хь хь ..., х„, сопоставленным тем реле, которые участвуют в схеме.
Если при данном наборе состояний реле хь хп ..., х„(некоторые из этих реле находятся в рабочем состоянии под током, остальные отключены, т.е. «обесточены«) вся релейно-контактная схема проводит электрический ток, то переменной у ставится в соответствие (другими словами, переменная у принимает) значение 1. Если же при этом наборе состояний реле х„х,, ..., х„схема не проводит электрический ток, то считаем, что переменная у принимает значение О. Поскольку каждый набор состояний реле х„ хъ ..., х„характеризуется набором, составленным из нулей и еди- 112 ниц и имеющим длину и, то данная релейно-контактная схема определяет некоторое правило, по которому каждому такому набору длины п, составленному из нулей и единиц, сопоставляется либо О, либо 1. Таким образом, кажлая релейно-контактная схема, в которой занято и независимых реле (контактов в ней может быть и или больше), определяет некоторую булеву функцию у от п аргументов. Она принимает значение 1 на тех и только тех наборах значений аргументов хь хъ ..., х„, которые соответствуют тем состояниям реле хп хъ ..., х„, при которых данная схема проводит электрический ток.
Такая булева функция у =Дхп хц ..., х„) называется функцией проводимости данной релейно-контактной схемы. Таким образом, теория булевых функций предоставляет математические модели реальных физических релейно-контактных схем. Рассмотрим некоторые релейно-контактные схемы и найдем их функции проводимости. П е р в а я схема состоит из двух последовательно соединенных контактов х и у, т.е. контактов, связанных с двумя независимыми реле х и у, каждое из которых срабатывает независимо от другого: Ясно, что данная схема проводит электрический ток тогда и только тогда, когда оба контакта х и у замкнуты, т.е. только тогда, когда оба переменных х и у принимают значение 1. Булева функция от двух аргументов х, у, удовлетворяющая такому условию, нам хорошо известна.
Это конъюнкция х у. Таким образом, функцией проводимости релейно-контактной схемы, состоящей из двух последовательно соединенных контактов х и у, является конъюнкция х у. Говорят, что поеледавательпое соединение двух контактов реализует конъюнкцию соответствующих этим контактам булевых переменных.
В т о р а я релейно-контактная схема состоит из двух параллельно соединенных контактов х и у: Ясно, что эта схема проводит электрический ток в том и только в том случае, когда по меньшей мере один из контактов (х или у) замкнут, т.е. лишь в случае, когда хотя бы одна из булевых переменных (х или у) принимает значение 1. Булева функция от двух 113 аргументов х и у, удовлетворяющая этому условию, также хорошо нам известна. Это, дизъюнкция х ~ у.
Таким образом, функцией проводимости релейно-контактной схемы, состоящей из двух параллельно соединенных контактов х и у„является дизъюнкция х ~ у. Говорят, что параллельное соединение двух контактов реализует дизьюнкцию соответствующих этим контактам булевых переменных. Итак, с помощью релейно-контактных схем можно реализовывать булевы функции: конъюнкцию, дизъюнкцию и отрицание. Возможна ли аналогичная реализация и других булевых функций? Ответ на поставленный вопрос позволяет дать теорема 10.5.
Поскольку всякая булева функция на основании этой теоремы может быть выражена через конъюнкцию, дизъюнкцию и отрицание, причем отрицание стоит лишь непосредственно около переменных и не стоит ни около каких внутренних скобок, а конъюнкция, дизъюнкция и отрицание, как показано только что, реализуются на релейно-контактных схемах, то и всякая булева функция может быть реализована с помощью релейно-контактной схемы, т.е. может быть построена такая схема, для которой данная булева функция служит функцией проводимости. Реализуем, например, в виде релейно-контактных схем булевы функции — импликацию и эквивалентность. Для этого выразим их через конъюнкцию, дизъюнкцию и отрицание.
Такие выражения известны (см. теорему 9 5): х-ь у = х' ~~ у, х ьь у = (х -> у) . (у -ь х) = (х' ~ у) . (у' г х). Предлагается самостоятельно нарисовать схему, реализуюшую функцию х — > у. Релейно-контактная схема, реализующая функцию х ~-> у, будет состоять из двух последовательно соединенных ветвей, первая из которых реализует булеву функцию х' ~ у, а вторая — булеву функцию у' ~ х. В свою очередь, первая из ветвей будет состоять из двух параллельных участков, один из которых содержит контакт х', а второй — контакт у. Аналогично, вторая ветвь также будет состоять из двух параллельных участков, один из которых содержит контакт х, а другой — контакт у'.
Изображаем полученную релейно-контактную схему (чтобы упростить рисунки, не будем изображать сами контакты, а ограничимся символом булевой переменной, соответствующей данному контакту): х' Ознакомьтесь с примерами № 7.2, л, 7.3, л, разобранными в Задачнике. !14 Две основные задачи теории релейно-контактных схем.
Составление релейно-контактных схем с заданными условиями работы называется задачей синвеза релейно-контактных схем и является первой важной задачей, состоящей в том, что требуется построить схему, которая проводила бы электрический ток лишь при вполне определенных задаваемых условиях.
Проанализируйте приведенные в Задачнике решения задач )чв 7.9 и 7.20. Естественно было бы выбирать для каждой булевой функции самую простую или одну из самых простых реализующих ее релейно-контактных схем. Поэтому упрощение релейно-контактных схем называется задачей анализа таких схем и является вт ор о й важной задачей теории релейно-контактных схем. Две релейно-контактные схемы, составленные из одних и тех же реле, называются равносильными, если одна из них проводит ток тогда и только тогда, когда другая схема проводит ток. Другими словами, две схемы, составленные из одних и тех же реле, равносильны, если они обладают одинаковыми функциями проводимости, зависящими от одних и тех же переменных. Из двух равносильных схем более простой считается та, которая содержит меньшее число контактов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
