Содержание
Пример решения задачи
РКС нужны, чтобы упрощать цепи, избавляться от лишнего, но при этом не терять функциональности устройства. В СССР делали радиоприёмники, в которых можно было избавиться от некоторых деталей, находящихся внутри, но при этом остаться с работающим устройством.
Итак, нам нужно уметь:
- Нарисовать схему по имеющейся формуле;
- Упростить данную формулу, чтобы затем нарисовать упрощенную схему.
Есть следующее логическое выражение:
Соответственно, схема, исходя из этих данных, будет выглядеть вот так:
Выглядит относительно сложно. Нужно это дело уметь упрощать. Для этого понадобятся навыки упрощения логических выражений. Об этом есть отдельная статья со ссылкой во введении. Упростим нашу формулу, и она станет выглядеть так:
Теперь изобразим по упрощенному выражению схему.
Трудно не согласиться, что в таком виде схема смотрится намного проще. Как рисовать схемы и упрощать выражения – всё, что вам нужно знать.
При упрощении вам могут потребоваться основные тождества и законы алгебры логики. Их вы найдёте по ссылке. Нужно так же понимать смысл конъюнкции и дизъюнкции. С пониманием данных основ вы решите любую задачу. Всё это очень похоже на обычную алгебру, а точнее, на арифметику.
Эти галочки – это сложение и вычитание. Они аналогичны плюсам, точкам или звёздочкам. Только в математической логике есть лишь два слова – «да» и «нет». То есть, участвуют в вычислениях лишь нули и единицы.
Это означает «есть сигнал» и «нет сигнала». На этом построены все информационные технологии, и так работаю полупроводники.
На этом всё. Если устанете разбираться, оформляйте заказ, мы будем рады вам помочь. Можете так же ознакомиться с неплохим видеороликом по данной теме.
Однако не забывайте, что если вы самостоятельно постигли какое-либо знание, оно останется в голове намного дольше и принесёт двукратную пользу, нежели если вам всё преподнесут в готовом виде педагоги и сторонние люди.
ЗАКАЗАТЬ РЕШЕНИЕ ЗАДАЧ ПО РКС
Релейно-контактные схемы
Укажем на применение алгебры логики к анализу и синтезу релейно-контактных схем. Среди технических средств автоматизации значительное место занимают устройства релейно-контактного действия. Они находят широкое применение в телефонии, телеуправлении, автоматике и телемеханике, на железнодорожном транспорте, в вычислительной технике. Сейчас при конструировании таких устройств все больше и больше используется алгебра логики. Впервые идея использования алгебры логики для построения автоматических устройств была выдвинута в 1910 году известным физиком П.Эренфестом. Но только в 30-х годах эта идея нашла свое воплощение в работах советского физика В.И. Шестакова, американского математика К.Шеннона и японского инженера А.Накосима.
Контактная схема представляет собой устройство из проводников и контактов, связывающих полюса источника тока. Контакт бывает в двух состояниях:
а) контакт разомкнут и тогда ему приписывают 0;
б) контакт замкнут и тогда ему приписывают 1.
Контакт «не » ( ) – это контакт, который работает в противоположном режиме с , т.е. когда контакт замкнут, контакт обязательно разомкнут.
Дизъюнкции ставится в соответствие схема, состоящая из параллельного соединения контактов X, Y, так как цепь будет замкнута тогда и только тогда, когда замкнут хотя бы один из контактов.
Конъюнкции ставится в соответствие схема, состоящего из последовательного соединения контактов X, Y, так как цепь будет замкнута тогда и только тогда, когда замкнуты оба контакта одновременно.
Каждый контакт подключен к некоторому реле. В схеме одинаковыми буквами обозначаются контакты, подключенные к одному и тому же реле. Всей схеме ставится в соответствие булева функция F, которая равна 1, если схема проводит ток, и 0 в противном случае. Эта функция называется функцией проводимости схемы, а ее таблица – условиями работы схемы. Две схемы с одинаковыми функциями проводимости называются равносильными. Средства алгебры высказываний позволяют упрощать схемы, используя отношение равносильности формул алгебры высказываний.
Пример. Упростить схему:
□ По данной схеме запишем формулу, определяющую функцию проводимости, и упростим ее:
Таким образом, – функция проводимости и
упрощенная схема.
§5. Решение логических задач методами алгебры логики.
Под логической задачей будем понимать задачу, где основным видом деятельности является выявление отношений между объектами задачи, а не нахождение количественных характеристик объектов. Суть применения алгебры логики к решению логических задач состоит в том, что, имея конкретные условия логической задачи, стараются записать их в виде формулы алгебры логики. В дальнейшем путем равносильных преобразований упрощают полученную формулу. Простейший вид формулы, как правило, приводит к ответу на все вопросы задачи.
Покажем на ряде конкретных примеров, как использовать возможности алгебры логики для решения элементарных логических задач.
Пример 1. При составлении расписания уроков на некоторый день учителя просили, чтобы их уроки были:
1. математик – первым или вторым;
2. историк – первым или третьим;
3. литератор – вторым или третьим.
Можно ли удовлетворить просьбы всех учителей?
□ Введем обозначения:
={Математика будет первым уроком};
= {Математика будет вторым уроком};
= {История будет первым уроком};
= {История будет третьим уроком};
= {Литература будет вторым уроком};
= {Литература будет третьим уроком}.
Тогда на языке алгебры эту задачу можно записать в виде формулы , после равносильных преобразований которой можно будет дать ответ на вопрос задачи:
Выяснили, что имеется две возможности:
1. , , ;
2. , , .
Вопросы для самоконтроля по теме «Логика высказываний»
1. Что понимается под высказыванием? Привести примеры.
2. Являются ли высказываниями следующие предложения:
а) два плюс два равно пяти;
б) функция – периодическая;
в) существует рациональное число такое, что х > 7.
3. Определить операции отрицания, дизъюнкции, конъюнкции, импликации, эквиваленции и задать их с помощью таблиц истинности.
4. Найти истинностные значения следующих высказываний:
а)
б) ;
в) .
5. Что понимается под формулой алгебры высказываний?
6. Найти значения формул при заданных значениях высказывательных переменных:
а) для , , ;
б) для , .
7. Построить таблицу истинности формулы .
8. Что называется тождественно истинной (ложной) формулой? Проверить, является ли каждая из формул тождественно истинной:
а)
б) .
9. Какие формулы называются равносильными? Как доказать равносильность формул? Проверить равносильность
10. Записать первые десять основных равносильностей алгебры высказываний. Доказать законы поглощения и законы де Моргана.
11. Записать законы двойного отрицания; исключения импликации; введения дизъюнкции; введения конъюнкции; замены эквиваленции; контрапозиции; противоположностей; доказательства от противного; транзитивности импликации; транзитивности эквиваленции. Обосновать законы доказательства от противного и закон контрапозиции.
12. Упростить формулу .
13. Преобразовать формулу в равносильную ей формулу так, чтобы в ней не было операции импликации, а отрицание относилось только к высказывательным переменным.
14. Перевести предложение на логический язык и построить его отрицание: «Если вечером я буду не занята, то пойду в кино или на дискотеку».
15. Упростить релейно-контактную схему:
16. Ввести понятие функции проводимости для релейно-контактной схемы. Найти функцию проводимости и условия работы для схемы:
17. Один из братьев Витя, Толя, Коля разбил окно. В разговоре участвуют еще двое братьев – Андрей и Дима.
– Это мог сделать только Витя или Толя – сказал Андрей.
– Я окно не разбивал, – возразил Витя, – Коля тоже.
– Вы оба говорите неправду, – заявил Толя.
– Нет, Толя, один из них сказал правду, а другой неправду, – возразил Дима.
–Ты, Дима, неправ, – вмешался Коля.
Их отец, которому, конечно, можно доверять, уверен, что трое братьев сказали правду. Кто разбил окно?
Применение булевых функций к релейно-контактным схемам
На данный момент наиболее актуальна проблема анализа и синтеза релейно-контактных схем при проектировании различных электронных приборов, в системе водоснабжения. Из этого можно сделать вывод, что методы логического анализа и синтеза релейно-контактных схем находят широкое применение в разных бытовых жизненных ситуациях.
Целью данной статьи является — исследовать применение релейно-контактных схем при решении профессиональных и жизненных ситуаций с помощью обращения к булевым функциям.
Релейно-контактной схемой называется устройство из проводников и двухпозиционных контактов, через которые полюсы источника тока связаны с некоторым потребителем. Контакты могут быть замыкающими и размыкающими. Каждый контакт подключен к некоторому реле (переключателю). Когда реле находится под током, все подключенные к нему замыкающие контакты замкнуты, а размыкающие контакты разомкнуты; в противном случае — наоборот. Каждому реле ставится в соответствие своя пропозициональная переменная x Она принимает значение 1, если через реле проходит ток, и 0 в противном случае. На чертежах все замыкающие контакты, подключенные к реле x, обозначаются символом x, а размыкающие — символом . Это означает, что при срабатывании реле x все его размыкающие контакты не проводят ток и им сопоставляется 0. При отключении реле создается противоположная ситуация. Всей схеме также ставится в соответствие булева переменная y, которая равна 1, если схема проводит ток, и 0 в противном случае. Переменная y, соответствующая схеме, очевидно, является булевой функцией от переменных , , …, реле. Эта функция называется функцией проводимости схемы, а ее таблица — условиями работы схемы .
В теории релейно-контактных схем важнейшим являются следующие задачи:
задача синтеза релейно-контактных схем — это составление релейно-контактных схем с заданными условиями работы, которые зависят от функций, которые эта схема должна выполнять;
задача анализа релейно-контактных схем — это получение наиболее простой схемы, реализующей данную формулу .
Теперь перейдем непосредственно к решению практических задач на применение булевых функций к релейно-контактным схемам.
Задача № 1. Составить схему, позволяющую включать и выключать свет в вашей комнате любым из трех различных выключателей. Выключатели расположены у входа в комнату, над постелью и у письменного стола .
Используя условия, которым должна удовлетворять искомая схема, составим сначала таблицу значений функции проводимости F этой схемы. В нее войдут три неизвестных x, y,z, которые будут соответствовать трем выключателям. В последнем столбце таблицы.будем указывать 1, если свет горит и 0, если света нет. Рассмотрим набор переменных (0,0,0) (все выключатели в положении «выключен»), свет в этот момент также не горит — значение функции проводимости F будет равно 0. При наборе переменных (1,1,1) (все выключатели в положении «включен»), свет в этот момент горит — значение функции проводимости F будет равно 1. По условию задачи, при изменении положения любого из выключателей должен загореться свет, то есть на наборах (1,0,0), (0,1,0) и (0,0,1) функция F равна 1. При следующем изменении положения любого из выключателей свет должен выключиться, то есть на наборах (1,1,0), (1,0,1) и (0,1,1) функция F равна 0 (табл.1).
Таблица 1
Зная теперь все наборы значений аргумента, на которых функция F обращается в 1, запишем выражение для нее, используя алгоритм приведения функции к совершенной дизъюнктивной нормальной форме по таблице истинности , а уже затем упростим его:
Изображаем релейно-контактную схему, обладающую найденной функцией проводимости (рис.1).Любую схему можно задать формулой алгебры логики, при этом конъюнкции двух высказываний соответствует последовательное соединение двух переключателей, а дизъюнкции двух высказываний — параллельное соединение двух переключателей. При этом ток будет проходить через данные схемы тогда и только тогда, когда истинностное значение соответствующей формулы — «истина» .
Рис. 1.
Задача № 2.
В спортивном комитете, например заводском, собралось 5 судей. Каждый из них должен голосовать за принятие различных решений. Решение принимается большинством голосов, но только при том дополнительном условии, что за него голосует председатель комитета. Судьи голосуют путем нажатия кнопки, замыкающей переключатель, расположенный под столом, за которым они сидят. Замыкая переключатель, они голосуют «за», размыкая «против». Начертите наиболее простую схему, позволяющую автоматически видеть результаты голосования. В простейшем случае просто с помощью лампочки, — зажглась — решение принято, не зажглась,- нет .
Решение.
Используя условия, которым должна удовлетворять искомая схема, составим сначала таблицу значений функции проводимости F этой схемы. В нее войдут пять неизвестных x, y,z,u, t, так как переключатели замыкают пять судей, где x — председатель, его выделяем особо в виду условий задачи. В последнем столбце таблицы указано условие, при котором свет не горит — 0, 1- свет включится (табл. 2).
Таблица 2
Зная теперь все наборы значений аргумента, на которых функция F обращается в 1, запишем выражение для нее, используя совершенную дизъюнктивную нормальную форму, а уже затем упростим его:
В результате получаем искомую схему (рис.2).
Рис. 2.
Литература:
- Игошин В. И. Задачи и упражнения по математической логике и теории алгоритмов: учеб. пособие для студ. высш. учебн. Заведений/ В. И. Игошин. — 3-е изд., стер. — М.: Издательский центр «Академия», 2007.- 304 с.
- Сангалова М. Е. Курс лекций по математической логике: учеб. пособие / М. Е. Сангалова; ГОУ ВПО, «Арзамас. гос. пед. ин-т им. А. П. Гайдара». Арзамас, 2006. 98 с.
- http://electrik.info/main/fakty/229-buleva-algebra-chast-1-nemnogo-istorii.html
Применение булевых функций
Над возможностями применения логики в технике ученые и инженеры задумывались уже давно. Например, голландский физик Пауль Эренфест (1880-1933), еще в 1910 году писал: «… Пусть имеется проект схемы проводов автоматической телефонной станции. Надо определить:
-
будет ли она правильно функционировать при любой комбинации, могущей встретиться в ходе деятельности станции;
-
не содержит ли она излишних усложнений.».
Созданная позднее российским ученым М. А. Гавриловым (1903-1979), стоявшим у истоков информатики в нашей стране, теория релейно-контактных схем показала, что это вовсе не утопия.
Булевы функции широко применяются при описании работы дискретных управляющих систем (контактных схем, схем из функциональных элементов, логических сетей и т. д.), при исследовании некоторых электрических цепей, так называемых релейно-контактных схем.
Контактный элемент – это техническое устройство, замыкающее и размыкающее электрическую цепь. К контактным элементам относятся кнопки (клавиши), электромагнитные реле, шаговые искатели, различные переключатели и др. Принцип их работы носит четко выраженный двоичный характер (включено – выключено), благодаря чему при синтезе контактных сетей широкое применение нашла булева алгебра, явившаяся существенным подспорьем в руках инженера, разрабатывающего переключательные схемы. С логической точки зрения совершенно безразлично, какие рассматриваются элементы, – реле, кнопки или переключатели, поэтому можно говорить об абстрактных электрических контактах, обладающих только одним свойством – замыкать и размыкать электрическую цепь на некотором участке.
Под релейно-контактной схемой понимается устройство из проводников и двухпозиционных контактов, подключенных к некоторым реле (переключателям). Оно может быть предназначено, например, для соединения (или разъединения) полюсов источника тока с некоторым потребителем. Контакты релейно-контактной схемы могут быть двух типов: замыкающие и размыкающие. К одному реле может быть подключено несколько контактов – как замыкающих, так и размыкающих. Технически реле представляет собой катушку с металлическим сердечником (магнитопроводом), вблизи которого находится соответствующий контакт. Когда через катушку пропускается электрический ток, металлический сердечник намагничивается и замыкает все находящиеся при нем замыкающие контакты. Одновременно все размыкающие контакты, относящиеся к данному реле, размыкаются. Поскольку замыкающие контакты при отсутствии в реле электрического тока разомкнуты, то они называются также нормально разомкнутыми. Аналогично, размыкающие контакты называются также нормально замкнутыми. При обесточивании обмоток реле (т. е. когда реле отключается) все замыкающие контакты снова размыкаются, а все размыкающие, замыкаются.
Каждому реле ставится в соответствие своя булева переменная, которая принимает значение 1, когда реле срабатывает, и принимает значение 0 при отключении реле. На чертеже все замыкающие контакты, подключенные к реле х, обозначаются тем же символом х, а все размыкающие контакты, подключенные к этому реле, обозначаются отрицанием х’. Это означает, что при срабатывании реле x все его замыкающие контакты х проводят ток и им сопоставляется значение 1, а все размыкающие контакты х’ не проводят электрический ток и им сопоставляется значение 0. При отключенном реле х создается противоположная ситуация: все его замыкающие контакты х разомкнуты, т. е. в этот момент им сопоставляется (переменная х принимает) значение 0, а все его размыкающие контакты х’ замкнуты, т. е. в этот момент им сопоставляется (другими словами, х’ принимает) значение 1.
Всей релейно-контактной схеме тогда ставится в соответствие булева переменная у, зависящая от булевых переменных x1, x2, …, xn, сопоставленным тем реле, которые участвуют в схеме. Если при данном наборе состояний реле x1, x2, …, xn (некоторые из этих реле находятся в рабочем состоянии под током, остальные отключены, т. е. «обесточены») вся релейно-контактная схема проводит электрический ток, то переменной у ставится в соответствие (другими словами, переменная у принимает) значение 1. Если же при этом наборе состояний реле x1, x2, …, xn схема не проводит электрический ток, то считаем, что переменная у принимает значение 0. Поскольку каждый набор состояний реле x1, x2, …, xn характеризуется набором, составленным из нулей и единиц и имеющим длину n, то данная релейно-контактная схема определяет некоторое правило, по которому каждому такому набору длины n, составленному из нулей и единиц, сопоставляется либо 0, либо 1. Таким образом, каждая релейно-контактная схема, в которой занято n независимых реле (контактов в ней может быть n или больше), определяет некоторую булеву функцию у от n аргументов. Она принимает значение 1 на тех и только тех наборах значений аргументов x1, x2, …, xn, которые соответствуют тем состояниям реле x1, x2, …, xn, при которых данная схема проводит электрический ток. Такая булева функция у=f(x1, x2, …, xn) называется функцией проводимости данной релейно-контактной схемы.
Таким образом, теория булевых функций предоставляет математические модели реальных физических релейно-контактных схем.
Рассмотрим основные релейно-контактные схемы и найдем их функции проводимости. Первая схема состоит из двух последовательно соединенных контактов х и у, т. е. контактов, связанных с двумя независимыми реле х и у, каждое из которых срабатывает независимо от другого:
Ясно, что данная схема проводит электрический ток тогда и только тогда, когда оба контакта х и у замкнуты, т. е. только тогда, когда обе переменные х и у принимают значение 1. Булева функция от двух аргументов x, у, удовлетворяющая такому условию – конъюнкция х•у. Таким образом, функцией проводимости релейно-контактной схемы, состоящей из двух последовательно соединенных контактов х и у, является конъюнкция х•у. Говорят, что последовательное соединение двух контактов реализует конъюнкцию соответствующих этим контактам булевых переменных.
Вторая релейно-контактная схема состоит из двух параллельно соединенных контактов х и у:
Ясно, что эта схема проводит электрический ток в том и только в том случае, когда по меньшей мере один из контактов (х или у) замкнут, т. е. лишь в случае, когда хотя бы одна из булевых переменных (х или у) принимает значение 1. Булева функция от двух аргументов х и у, удовлетворяющая этому условию – дизъюнкция xy. Таким образом, функцией проводимости релейно-контактной схемы, состоящей из двух параллельно соединенных контактов х и у, является дизъюнкция xy. Говорят, что параллельное соединение двух контактов реализует дизъюнкцию соответствующих этим контактам булевых переменных.
Вид релейно-контактной схемы можно упростить, если удалить графическое изображение контактов, а в образовавшиеся разрывы вписать соответствующие буквы.
Итак, с помощью релейно-контактных схем можно реализовывать булевы функции: конъюнкцию, дизъюнкцию и отрицание, а значит, любую б. ф.
Реализуем, например, в виде релейно-контактной схемы булеву функцию эквивалентность: