Булева алгебра. Часть 3. Контактные схемы

СОДЕРЖАНИЕ:

Упростить релейно-контактные схемы

30.03.2020, 11:22

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

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

Составить функцию проводимости релейно-компактной схемы и упростить
А тут верно решено? Дана релейно-компактная схема (1), нужно составить функцию ее проводимости и.

30.03.2020, 11:53 2 30.03.2020, 11:59 3 30.03.2020, 11:59

Релейно контактные цепи
Помогите Решить 1 и 2 задачу

Упростить релейно-контактную схему:
Помогите, пожалуйста, с этим заданием. Заранее благодарен!

Упростить релейно-контактную схему
Упростить ркс, на изображении схема которую нужно упростить, не обращайте внимания на другое

КОНТАКТНЫЕ СХЕМЫ — понятие и виды. Классификация и особенности категории «КОНТАКТНЫЕ СХЕМЫ» 2020, 2020.

Читайте также

11.1. Переключательные схемы.В качестве одной из интерпретаций булевых функций рассмотрим электрическую схему, состоящую из источника напряжения (батареи), лампочки и одного или двух ключей х1 и x2. Ключи управляются кнопками с двумя состояния­ми: кнопка нажата (1) и. [читать подробнее].

Алгебра Жегалкина Другая замечательная алгебра булевых функций строится на основе операций сложения по модулю 2 и конъюнкции. Она называется алгеброй Жегалкина по имени предло­жившего ее советского ученого. Непосредственной проверкой по таблицам. [читать подробнее].

11.1. Переключательные схемы.В качестве одной из интерпретаций булевых функций рассмотрим электрическую схему, состоящую из источника напряжения (батареи), лампочки и одного или двух ключей х1 и x2. Ключи управляются кнопками с двумя состояния­ми: кнопка нажата (1) и. [читать подробнее].

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

Пример решения задачи

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

  1. Нарисовать схему по имеющейся формуле;
  2. Упростить данную формулу, чтобы затем нарисовать упрощенную схему.

Есть следующее логическое выражение:

Соответственно, схема, исходя из этих данных, будет выглядеть вот так:

Выглядит относительно сложно. Нужно это дело уметь упрощать. Для этого понадобятся навыки упрощения логических выражений. Об этом есть отдельная статья со ссылкой во введении. Упростим нашу формулу, и она станет выглядеть так:

Теперь изобразим по упрощенному выражению схему.

Трудно не согласиться, что в таком виде схема смотрится намного проще. Как рисовать схемы и упрощать выражения – всё, что вам нужно знать.
При упрощении вам могут потребоваться основные тождества и законы алгебры логики. Их вы найдёте по ссылке. Нужно так же понимать смысл конъюнкции и дизъюнкции. С пониманием данных основ вы решите любую задачу. Всё это очень похоже на обычную алгебру, а точнее, на арифметику.
Эти галочки – это сложение и вычитание. Они аналогичны плюсам, точкам или звёздочкам. Только в математической логике есть лишь два слова – «да» и «нет». То есть, участвуют в вычислениях лишь нули и единицы.
Это означает «есть сигнал» и «нет сигнала». На этом построены все информационные технологии, и так работаю полупроводники.

На этом всё. Если устанете разбираться, оформляйте заказ, мы будем рады вам помочь. Можете так же ознакомиться с неплохим видеороликом по данной теме.

Однако не забывайте, что если вы самостоятельно постигли какое-либо знание, оно останется в голове намного дольше и принесёт двукратную пользу, нежели если вам всё преподнесут в готовом виде педагоги и сторонние люди.

ЗАКАЗАТЬ РЕШЕНИЕ ЗАДАЧ ПО РКС

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

Укажем на применение алгебры логики к анализу и синтезу релейно-контактных схем. Среди технических средств автоматизации значительное место занимают устройства релейно-контактного действия. Они находят широкое применение в телефонии, телеуправлении, автоматике и телемеханике, на железнодорожном транспорте, в вычислительной технике. Сейчас при конструировании таких устройств все больше и больше используется алгебра логики. Впервые идея использования алгебры логики для построения автоматических устройств была выдвинута в 1910 году известным физиком П.Эренфестом. Но только в 30-х годах эта идея нашла свое воплощение в работах советского физика В.И. Шестакова, американского математика К.Шеннона и японского инженера А.Накосима.

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

а) контакт разомкнут и тогда ему приписывают 0;

б) контакт замкнут и тогда ему приписывают 1.

Контакт «не » ( ) – это контакт, который работает в противоположном режиме с , т.е. когда контакт замкнут, контакт обязательно разомкнут.

Дизъюнкции ставится в соответствие схема, состоящая из параллельного соединения контактов X, Y, так как цепь будет замкнута тогда и только тогда, когда замкнут хотя бы один из контактов.

Конъюнкции ставится в соответствие схема, состоящего из последовательного соединения контактов X, Y, так как цепь будет замкнута тогда и только тогда, когда замкнуты оба контакта одновременно.

Каждый контакт подключен к некоторому реле. В схеме одинаковыми буквами обозначаются контакты, подключенные к одному и тому же реле. Всей схеме ставится в соответствие булева функция F, которая равна 1, если схема проводит ток, и 0 в противном случае. Эта функция называется функцией проводимости схемы, а ее таблица – условиями работы схемы. Две схемы с одинаковыми функциями проводимости называются равносильными. Средства алгебры высказываний позволяют упрощать схемы, используя отношение равносильности формул алгебры высказываний.

Пример. Упростить схему:

□ По данной схеме запишем формулу, определяющую функцию проводимости, и упростим ее:

Таким образом, – функция проводимости и

§5. Решение логических задач методами алгебры логики.

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

Покажем на ряде конкретных примеров, как использовать возможности алгебры логики для решения элементарных логических задач.

Пример 1. При составлении расписания уроков на некоторый день учителя просили, чтобы их уроки были:

1. математик – первым или вторым;

2. историк – первым или третьим;

3. литератор – вторым или третьим.

Можно ли удовлетворить просьбы всех учителей?

Тогда на языке алгебры эту задачу можно записать в виде формулы , после равносильных преобразований которой можно будет дать ответ на вопрос задачи:

Выяснили, что имеется две возможности:

Вопросы для самоконтроля по теме «Логика высказываний»

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).

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

Изображаем релейно-контактную схему, обладающую найденной функцией проводимости (рис.1).Любую схему можно задать формулой алгебры логики, при этом конъюнкции двух высказываний соответствует последовательное соединение двух переключателей, а дизъюнкции двух высказываний — параллельное соединение двух переключателей. При этом ток будет проходить через данные схемы тогда и только тогда, когда истинностное значение соответствующей формулы — «истина» .

В спортивном комитете, например заводском, собралось 5 судей. Каждый из них должен голосовать за принятие различных решений. Решение принимается большинством голосов, но только при том дополнительном условии, что за него голосует председатель комитета. Судьи голосуют путем нажатия кнопки, замыкающей переключатель, расположенный под столом, за которым они сидят. Замыкая переключатель, они голосуют «за», размыкая «против». Начертите наиболее простую схему, позволяющую автоматически видеть результаты голосования. В простейшем случае просто с помощью лампочки, — зажглась — решение принято, не зажглась,- нет .

Используя условия, которым должна удовлетворять искомая схема, составим сначала таблицу значений функции проводимости F этой схемы. В нее войдут пять неизвестных x, y,z,u, t, так как переключатели замыкают пять судей, где x — председатель, его выделяем особо в виду условий задачи. В последнем столбце таблицы указано условие, при котором свет не горит — 0, 1- свет включится (табл. 2).

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

В результате получаем искомую схему (рис.2).

  1. Игошин В. И. Задачи и упражнения по математической логике и теории алгоритмов: учеб. пособие для студ. высш. учебн. Заведений/ В. И. Игошин. — 3-е изд., стер. — М.: Издательский центр «Академия», 2007.- 304 с.
  2. Сангалова М. Е. Курс лекций по математической логике: учеб. пособие / М. Е. Сангалова; ГОУ ВПО, «Арзамас. гос. пед. ин-т им. А. П. Гайдара». Арзамас, 2006. 98 с.
  3. 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. Булева функция от двух аргументов х и у, удовлетворяющая этому условию – дизъюнкция xy. Таким образом, функцией проводимости релейно-контактной схемы, состоящей из двух параллельно соединенных контактов х и у, является дизъюнкция xy. Говорят, что параллельное соединение двух контактов реализует дизъюнкцию соответствующих этим контактам булевых переменных.

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

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

Реализуем, например, в виде релейно-контактной схемы булеву функцию эквивалентность:

Булева алгебра. Часть 3. Контактные схемы

В статье описаны главные принципы проектирования релейных схем в согласовании с данным методом их работы.

В 2-ух прошлых статьях было поведано об основах булевой алгебры и алгебры релейных схем. На этой базе были разработаны структурные формулы, а уже по ним типовые контактные схемы.

Составить структурную формулу по готовой схеме — дело несложное. Существенно сложнее по готовой структурной формуле представить электронную схему грядущего автомата. Тут нужна определенная тренировка!

На рисунке 1 показаны более распространенные варианты контактных схем и их эквиваленты. Они посодействуют при составлении электронных схем автоматов, также рассматривать уже готовые конструкции, к примеру в процессе их ремонта.

Как можно использовать разобранные выше варианты контактных схем?

Разглядим схему, приведенную на рисунке 2, а. Соответственная ей структурная формула имеет вид: (A + B)*(С + D).

Пользуясь распределительным законом алгебры Буля, раскроем скобки в этом выражении и получим: A*(С+D) + B*(С +D), что соответствует схеме, изображенной на рисунке 2, б. Дальше, за счет перемножения, можем получить формулу A*C + A*D + B*C + B*D, подобающую рисунку 2, в.

Все три схемы эквивалентны, другими словами оказываются замкнутыми при одних и тех же критериях. Но, по трудности они различные.

Набросок 1. Типовые контактные схемы

1-ая из схем, самая обычная, она просит 4 реле, каждое из которых обязано иметь по одному нормально разомкнутому контакту. (Для упрощения рисунков катушки реле не показаны).

Схема «б» просит реле с 2-мя контактными группами. Фактически, основной задачей алгебры контактных схем является отыскание всех эквивалентных схем с тем, чтоб можно было избрать из их более ординарную.

Набросок 2. Эквивалентные контактные схемы.

Для закрепления пройденного материала попытайтесь без помощи других решить последующие задачки.

1. Начертите электронную схему автомата, имеющего структурную формулу A*B*C*D + A*B*E + A*D.

2. Обоснуйте, что схемы, приведенные на рисунке 3, а и б, эквивалентны.

3. Упростите схему, показанную на рисунке 3, в.

4. Какой структурной формулой реализуется схема на рисунке 3, г?

После того, что мы уже успели изучить, можно будет приступить к решению задач, которые были заданы в самом начале первой статьи. Кратко их напомним.

1-ая задачка была о включении и выключении лампочки в комнате 3-мя тумблерами, расположенными в различных местах: у двери, у стола, у кровати.

2-ая задачка о голосовании спортивных арбитров: из 4 арбитров «ЗА» должны проголосовать хотя бы двое, при том условии, что «ЗА» проголосовал председатель комиссии.

3-я задачка была просто для учебных целей. В ней предлагалось то же, что и в первой, только для 6 тумблеров, будто бы в комнате 6 стенок. Подобные схемы как раз разрабатываются с помощью алгебры релейных схем.

Вообщем, если мы желаем создать схему, владеющую некими данными логическими качествами, то к решению схожей задачки можно подойти 2-мя различными способами. Условно эти пути могут быть названы «интуитивным» и «алгебраическим».

Некие задачки лучше решаются первым методом, а другие вторым. Интуитивный подход оказывается удобнее в случае, когда работа схемы управляется многими тумблерами, но имеется какая-то симметрия во обоюдном расположении этих реле. Мы увидим, что тут интуитивный подход резвее приводит к цели, тогда как применение аппарата релейной алгебры в случае многих переменных возможно окажется очень массивным. Полезно познакомиться с обоими вероятными подходами к решению обозначенной задачки.

Начнем с интуитивного подхода. Пусть нам потребовалось выстроить схему, которая замкнута тогда, когда сработали все n управляющих схемой реле.

Решение этой задачки не просит долгих раздумий: ясно, что поставленное условие будет выполнено, если соединить меж собой поочередно n нормально разомкнутых контактов реле.

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

Просто представить для себя такую схему, которая замыкается тогда, когда срабатывают некие, но не все реле. Такая схема изображена на рисунке 4, а. Справа приведена схема, действующая по принципу «все либо ничего». Она будет замкнута только тогда, когда сработают все реле либо реле отключены (набросок 4, 6).

Разглядим сейчас более непростой пример. Пусть имеется n контактов, расположенных в некой определенной последовательности: A, В, С, D, E, F… Построим схему, которая замыкается тогда, когда замкнуты какие или k поочередно включенных контактов, и только они. Такая схема для значений n = 7 и k = 3 изображена на рисунке 4, в. Способ построения таких схем для всех других значений n и k понятен из этого рисунка.

Перейдем к построению схем по данным условиям их работы при помощи релейной алгебры.

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

Пример 1. Допустим, что мы должны выстроить схему, содержащую 4 контакта A, B, C и D так, чтоб цепь была включена тогда, когда замкнуты контакт A, и какой-либо из других 3-х контактов. В этом ординарном случае работа схемы в словесной записи будет смотреться так: «Схема должна проводить ток, если замкнуты контакты A и B, либо контакты A и C либо контакты A и D. Согласитесь, что сейчас составить структурную формулу до боли просто. Она будет смотреться так:

A*B + A*C + A*D = 1 либо A* (B+C+D) = 1.

У схемы два варианта. Они показаны на рисунке 5. 2-ой вариант не просит реле с 3-мя нормально разомкнутыми контактами.

Пример 2. В первой статье была задачка №2 о голосовании спортивных арбитров. Прочтите ее условие повнимательней, оно схоже с только-только разобранным примером. Более точная словесная запись требований будет смотреться так: «Необходимо составить схему, содержащую 5 контактов A, B, C, D, E, так, чтоб она проводила ток и включала лампочку табло, если замкнуты последующие контакты:

A и B и C, либо A и B и D, либо A и B и E, либо A и C и D, либо A и C и E, либо A и D и E. Контакт A — это кнопка председателя. Если она не нажата, то каждое из 6 логических произведений будет равно 0, т.е. голосование не состоялось.

Структурная формула будет таковой:

либо A*(B*C + B*D + B*E + C*D + C*E + D*E) = 1.

Оба варианта схемы изображены на рисунке 5, в и г. Это и есть решение намеченной цели.

Имея некий навык в чтении структурных формул, просто представить схему самого автомата и все его способности. Любопытно то, что алгебра релейных схем дает больше инфы, чем даже сама схема. Она позволяет созидать, сколько и каких требуется реле. С ее помощью просто можно отыскать самый обычный вариант схемы автомата.

ПРИМЕР 3. Получив некий опыт в составлении структурных формул, попробуем решить задачку, с которой начиналась 1-ая статья: вам необходимо сконструировать тумблер, позволяющий включать свет при входе в подъезд и выключать после того, как вы поднялись на подходящий этаж, либо, напротив, включать при выходе из квартиры и выключать после того, как спуститесь вниз. Та же самая ситуация случается в длинноватом коридоре: в одном конце лампочку нужно зажечь, а пройдя до другого конца, погасить. Одним словом, задачка сводится к управлению одной лампочкой из различных мест 2-мя тумблерами.

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

Итак, чтоб лампочка горела (1), необходимо, чтоб было выполнено одно из 2-ух критерий:

1. Включить тумблер понизу (А) и выключить наверху (/В). Заходите в подъезд.

2. Включить тумблер наверху (В) и выключить понизу (/А) Выходите из квартиры.

С внедрением принятых обозначений структурная формула запишется так:

Схема тумблера показана на рисунке 6. В текущее время такие тумблеры выпускаются промышленно, это так именуемые проходные тумблеры. Потому рассмотрение данных схем тут приводится просто для понятия общих принципов их работы.

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

Схема, составленная по этой формуле, представлена на рисунке 7.

Сначала первой статьи была предложена просто учебная задачка №2: будто бы в комнате 6 стенок, и на каждой по тумблеру. Логика работы схемы вточности такая же, как и для 3-х тумблеров. Обозначим их знаками A, B, C, D, E, F. Напомним, что обозначение (/А), (/В) и т.д., это не символ деления, а логическое отрицание. Почаще обозначается подчеркиванием знаков и, даже целых выражений, сверху. В неких схемах это подчеркивание заменяется просто знаком «минус». Итак, структурная формула для 6 тумблеров имеет вид:

Полную электронную схему, реализующую данную структурную формулу, читателям предлагается составить без помощи других для приобретения практических способностей проектирования схем. Маленькая подсказка: для схемы пригодится 6 реле, каждое из которых имеет по одному нормально — разомкнутому контакту и по 5 нормально замкнутых. Подобные сложные реле по мере надобности можно собрать из нескольких более обычных, соединив их катушки параллельно.

На этом мы заканчиваем рассказ о булевой алгебре и алгебре релейных схем.

Булева алгебра и коммутационные схемы

В 1938 г. Клод Шеннон заметил связь между таблицами истинности и электрическими цепями.

В схеме представленной на левом рисунке лампочка загорается (имеет значение 1) если оба переключателя замкнуты (значения 1), что соответствует высказыванию pq.

В схеме на правом рисунке лампочка загорается (1) если хотя бы один из переключателей замкнут (т.е. хотя бы один имеет значение 1), что соответствует высказыванию p Ú q

Предполагается, что имеется схема в которой лампочка загорается, если выключатель разомкнут.

Анализ коммутационных схем

Анализ коммутационных схем заключается в определении булевой формулы соответствующей рассматриваемой схемы

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

Выход последнего элемента определяет итоговую

Синтез коммутационных схем

Синтез коммутационных схем заключается в построении схемы по заданной формуле

Пример: Муниципальный совет состоит из 3 человек. Каждый член совета имеет для голосования кнопку «за» и «против». Решение принимается если за него проголосует большинство. Построить коммутационную схему устройства, сигнализирующего о том, что решение принято.

Решение будет принято, если голосование пройдет по любому из вариантов pqr, ùpqr, pùqr, pqùr.Поэтому итоговая булевая функция:pqr Ú ùpqr Ú pùqr Ú pqùr

В дальнейшем, еслиэлементарная конъюнкция состоитиз n переменных,то ее функциональный элементимеет n входов.Аналогичное применяется дляэлементарной дизъюнкции.

Синтез коммутационных схем
Пример

Прежде чем строить коммутационную схему формулу следует максимально упростить, используя карту Карно или закону булевой алгебры pqr Ú ùpqr Ú pùqr Ú pqùr = pq Ú qr Ú pr = pq Ú r (qÚ p)

Проектирование полубитного сумматора

Полубитный сумматор складывает два одноразрядных числа (p, q), представленных в двоичном виде. На выходе получают двухразрядное число (d1d), где d0 — первый разряд d1- второй разряд (разряд переноса)

Построим СДНФ для d0 = pù q Ú ù pq, d1=pq

Проектирование полубитного сумматора

Построим схему

d0 = pùqÚùpq, d1=pq.

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

Проведем упрощение d0

d0 = pùqÚùpq =ùù(pùqÚùpq) =ù(ù(pùq) &ù(ùpq)) =ù((ùpÚq) & (pÚùq)) =ù(pùpÚqpÚùpùqÚqùq) =ù(qpÚùpùq ) =ù(qp) &ù(ùpùq ) = (ùpÚùq ) & (qÚp) =ù(pq ) & (qÚp)

Опора деревянной одностоечной и способы укрепление угловых опор: Опоры ВЛ — конструкции, предназначен­ные для поддерживания проводов на необходимой высоте над землей, водой.

Механическое удерживание земляных масс: Механическое удерживание земляных масс на склоне обеспечивают контрфорсными сооружениями различных конструкций.

Поперечные профили набережных и береговой полосы: На городских территориях берегоукрепление проектируют с учетом технических и экономических требований, но особое значение придают эстетическим.

Булева алгебра. Алгебра логики. Элементы математической логики

В современном мире мы все чаще используем разнообразные машины и гаджеты. И не только тогда, когда необходимо применить буквально нечеловеческую силу: переместить груз, поднять его на высоту, вырыть длинную и глубокую траншею и т. д. Автомобили сегодня собирают роботы, еду готовят мультиварки, а элементарные арифметические расчеты производят калькуляторы. Все чаще мы слышим выражение «булева алгебра». Пожалуй, пришло время разобраться в роли человека в создании роботов и умении машин решать не только математические, но и логические задачи.

Логика

В переводе с греческого логика – это упорядоченная система мышления, которая создает взаимосвязи между заданными условиями и позволяет делать умозаключения, основываясь на предпосылках и предположениях. Довольно часто мы спрашиваем друг друга: «Логично?» Полученный ответ подтверждает наши предположения либо критикует ход мысли. Но процесс не останавливается: мы продолжаем рассуждать.

Порой количество условий (вводных) настолько велико, а взаимосвязи между ними столь запутанны и сложны, что человеческий мозг не в состоянии «переварить» все сразу. Может понадобиться не один месяц (неделя, год) для понимания происходящего. Но современная жизнь не дает нам таких временных интервалов на принятие решений. И мы прибегаем к помощи компьютеров. И вот тут-то и появляется алгебра логики, со своими законами и свойствами. Загрузив все исходные данные, мы позволяем компьютеру распознать все взаимосвязи, исключить противоречия и найти удовлетворительное решение.

Математика и логика

Известнейший Готфрид Вильгельм Лейбниц сформулировал понятие «математическая логика», задачи которой были доступны для понимания только узкому кругу ученых. Особого интереса это направление не вызывало, и до середины XIX века о математической логике знали немногие.

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

Забегая вперед, скажем, что булева алгебра – самая используемая в современном мире часть математики. Так что спор свой Буль проиграл.

Джордж Буль

Сама личность автора заслуживает отдельного внимания. Даже учитывая то, что в прошлом люди взрослели раньше нас, все равно нельзя не отметить, что в 16 лет Дж. Буль преподавал в деревенской школе, а к 20 годам открыл собственную школу в Линкольне. Математик отлично владел пятью иностранными языками, а в свободное время зачитывался работами Ньютона и Лагранжа. И все это — о сыне простого рабочего!

В 1839 году Буль впервые послал свои научные работы в Кембриджский математический журнал. Ученому исполнилось 24 года. Работы Буля настолько заинтересовали членов Королевского научного общества, что в 1844 году он получил медаль за вклад в развитие математического анализа. Еще несколько опубликованных работ, в которых были описаны элементы математической логики, позволили молодому математику занять пост профессора в колледже графства Корк. Напомним, что у самого Буля образования не было.

В принципе, булева алгебра очень проста. Существуют высказывания (логические выражения), которые, с точки зрения математики, можно определить только двумя словами: «истина» или «ложь». Например, весной деревья расцветают – истина, летом идет снег – ложь. Вся прелесть этой математики заключается в том, что нет строгой необходимости использовать только числа. Для алгебры суждений вполне подходят любые высказывания с однозначным смыслом.

Таким образом, алгебра логики может быть использована буквально везде: в составлении расписаний и написании инструкций, анализе противоречивой информации о событиях и определении последовательности действий. Самое главное — понять, что совершенно неважно, как мы определили истинность или ложность высказывания. От этих «как» и «почему» нужно абстрагироваться. Значение имеет только констатация факта: истина-ложь.

Каждый электрик должен знать:  Полупроводниковые приборы

Безусловно, для программирования важны функции алгебры логики, которые записываются соответствующими знаками и символами. И выучить их – это значит освоить новый иностранный язык. Нет ничего невозможного.

Основные понятия и определения

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

  • высказываний;
  • логических операций;
  • функций и законов.

Высказывания – любые утвердительные выражения, которые не могут быть истолкованы двузначно. Они записываются в виде чисел (5 > 3) или формулируются привычными словами (слон – самое большое млекопитающее). При этом фраза «у жирафа нет шеи» также имеет право на существование, только булева алгебра определит её как «ложь».

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

Операции булевой алгебры

Мы уже помним, что операции в алгебре суждений – логические. Подобно тому, как алгебра чисел использует арифметические операции для сложения, вычитания или сравнения чисел, элементы математической логики позволяют составить сложные высказывания, дать отрицание или вычислить конечный результат.

Логические операции для формализации и простоты записываются формулами, привычными для нас в арифметике. Свойства булевой алгебры дают возможность записывать уравнения и вычислять неизвестные. Логические операции обычно записывают с помощью таблицы истинности. Её столбцы определяют элементы вычислений и операцию, которая над ними производится, а строки показывают результат вычислений.

Основные логические действия

Самыми распространенными в булевой алгебре операциями являются отрицание (НЕ) и логические И и ИЛИ. Так можно описать практически все действия в алгебре суждений. Изучим подробнее каждую из трех операций.

Отрицание (не) применяется только к одному элементу (операнду). Поэтому операцию отрицания называют унарной. Для записи понятия «не А» используют такие символы: ¬A, A¯¯¯ или !A. В табличной форме это выглядит так:

Для функции отрицания характерно такое утверждение: если А истинно, то Б – ложно. Например, Луна вращается вокруг Земли – истина; Земля вращается вокруг Луны – ложь.

Логические умножение и сложение

Логическое И называют операцией конъюнкции. Что это значит? Во-первых, что применить ее можно к двум операндам, т. е. И – бинарная операция. Во-вторых, что только в случае истинности обоих операндов (и А, и Б) истинно и само выражение. Пословица «Терпение и труд все перетрут» предполагает, что только оба фактора помогут человеку справиться со сложностями.

Для записи используются символы: A∧Б, A⋅Б или A&&Б.

Конъюнкция аналогична умножению в арифметике. Иногда так и говорят – логическое умножение. Если перемножить элементы таблицы по строкам, мы получим результат, аналогичный логическому размышлению.

Дизъюнкцией называют операцию логического ИЛИ. Она принимает значение истинности тогда, когда хотя бы одно из высказываний истинно (или А, или Б). Записывается это так: A∨Б, A+Б или A||Б. Таблицы истинности для этих операций такие:

Дизъюнкция подобна арифметическому сложению. Операция логического сложения имеет только одно ограничение: 1+1=1. Но мы же помним, что в цифровом формате математическая логика ограничена 0 и 1 (где 1 – истина, 0 — ложь). Например, утверждение «в музее можно увидеть шедевр или встретить интересного собеседника» означает, что можно посмотреть произведения искусства, а можно познакомиться с интересным человеком. В то же время, не исключен вариант одновременного свершения обоих событий.

Функции и законы

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

Ассоциативность означает, что в высказываниях типа «и А, и Б, и В» последовательность перечисления операндов не играет роли. Формулой это запишется так:

Как видим, это свойственно не только конъюнкции, но и дизъюнкции.

Коммутативность утверждает, что результат конъюнкции или дизъюнкции не зависит от того, какой элемент рассматривался вначале:

Дистрибутивность позволяет раскрывать скобки в сложных логических выражениях. Правила схожи с раскрытием скобок при умножении и сложении в алгебре:

Свойства единицы и нуля, которые могут быть одним из операндов, также аналогичны алгебраическим умножению на ноль или единицу и сложению с единицей:

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

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

Последовательность операций

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

3. Дизъюнкция, исключающее ИЛИ.

4. Импликация, эквивалентность.

Как видим, только отрицание и конъюнкция не имеют равных приоритетов. А приоритет дизъюнкции и исключающего ИЛИ равны, также как и приоритеты импликации и эквивалентности.

Функции импликации и эквивалентности

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

Импликация, или логическое следование – это высказывание, в котором одно действие является условием, а другое – следствием его выполнения. Иными словами, это предложение с предлогами «если. то». «Любишь кататься, люби и саночки возить». Т. е. для катания необходимо затянуть санки на горку. Если же нет желания съехать с горы, то и санки таскать не приходится. Записывается это так: A→Б или A⇒Б.

Эквивалентность предполагает, что результирующее действие наступает только в том случае, когда истиной являются оба операнда. Например, ночь сменяется днем тогда (и только тогда), когда солнце встает из-за горизонта. На языке математической логики это утверждение записывается так: A≡Б, A⇔Б, A==Б.

Другие законы булевой алгебры

Алгебра суждений развивается, и многие заинтересовавшиеся ученые сформулировали новые законы. Наиболее известными считаются постулаты шотландского математика О. де Моргана. Он заметил и дал определение таким свойствам, как тесное отрицание, дополнение и двойное отрицание.

Тесное отрицание предполагает, что перед скобкой нет ни одного отрицания: не (А или Б)= не А или НЕ Б.

Когда операнд отрицается, независимо от своего значения, говорят о дополнении:

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

Как решать тесты

Математическая логика подразумевает упрощение заданных уравнений. Так же, как и в алгебре, необходимо сначала максимально облегчить условие (избавиться от сложных вводных и операций с ними), а затем приступить к поиску верного ответа.

Что же сделать для упрощения? Преобразовать все производные операции в простые. Затем раскрыть все скобки (или наоборот, вынести за скобки, чтобы сократить этот элемент). Следующим действием должно стать применение свойств булевой алгебры на практике (поглощение, свойства нуля и единицы и т. д).

В конечном итоге уравнение должно состоять из минимального количества неизвестных, объединенных простыми операциями. Легче всего искать решение, если добиться большого количества тесных отрицаний. Тогда ответ всплывет как бы сам собой.

Уроки 8 — 12
§ 1.3. Элементы алгебры логики

Ключевые слова:

  • алгебра логики
  • высказывание
  • логическая операция
  • конъюнкция
  • дизъюнкция
  • отрицание
  • логическое выражение
  • таблица истинности
  • законы логики

1.3.1. Высказывание

Алгебра в широком смысле этого слова — наука об общих операциях, аналогичных сложению и умножению, которые могут выполняться над разнообразными математическими объектами. Многие математические объекты (целые и рациональные числа, многочлены, векторы, множества) вы изучаете в школьном курсе алгебры, где знакомитесь с такими разделами математики, как алгебра чисел, алгебра многочленов, алгебра множеств и т. д.

Для информатики важен раздел математики, называемый алгеброй логики; объектами алгебры логики являются высказывания.

Высказывание — это предложение на любом языке, содержание которого можно однозначно определить как истинное или ложное.

Например, относительно предложений «Великий русский учёный М. В. Ломоносов родился в 1711 году» и «Two plus six Is eight» можно однозначно сказать, что они истинны. Предложение «Зимой воробьи впадают в спячку» ложно. Следовательно, эти предложения являются высказываниями.

В русском языке высказывания выражаются повествовательными предложениями. Но не всякое повествовательное предложение является высказыванием.

Например, предложение «Это предложение является ложным» не является высказыванием, так как относительно него нельзя сказать, истинно оно или ложно, без того, чтобы не получить противоречие. Действительно, если принять, что предложение истинно, то это противоречит сказанному. Если же принять, что предложение ложно, то отсюда следует, что оно истинно.

Относительно предложения «Компьютерная графика — самая интересная тема в курсе школьной информатики» также нельзя однозначно сказать, истинно оно или ложно. Подумайте сами почему.

Побудительные и вопросительные предложения высказываниями не являются.

Например, не являются высказываниями такие предложения, как: «Запишите домашнее задание», «Как пройти в библиотеку?», «Кто к нам пришёл?».

Высказывания могут строиться с использованием знаков различных формальных языков — математики, физики, химии и т. п.

Примерами высказываний могут служить:

  1. «Na — металл» (истинное высказывание);
  2. «Второй закон Ньютона выражается формулой F=m•а» (истинное высказывание);
  3. «Периметр прямоугольника с длинами сторон a и b равен а • b» (ложное высказывание).

Не являются высказываниями числовые выражения, но из двух числовых выражений можно составить высказывание, соединив их знаками равенства или неравенства. Например:

  1. «3 + 5 = 2 • 4» (истинное высказывание);
  2. «II + VI > VIII» (ложное высказывание).

Не являются высказываниями и равенства или неравенства, содержащие переменные. Например, предложение «X n — 1;

  • провести заполнение таблицы по столбцам, выполняя логические операции в соответствии с установленной последовательностью.
  • Построим таблицу истинности для логического выражения A ∨ А & В. В нём две переменные, две операции, причём сначала выполняется конъюнкция, а затем — дизъюнкция. Всего в таблице будет четыре столбца:

    Наборы входных переменных — это целые числа от О до 3, представленные в двухразрядном двоичном коде: 00, 01, 10, 11. Заполненная таблица истинности имеет вид:

    Обратите внимание, что последний столбец (результат) совпал со столбцом А. В таком случае говорят, что логическое выражение A ∨ А & Б равносильно логическому выражению А.

    1.3.4. Свойства логических операций

    Рассмотрим основные свойства (законы) алгебры логики.

      Переместительный (коммутативный) закон

        для логического умножения:

    для логического сложения:

    Сочетательный (ассоциативный) закон

      для логического умножения:

    для логического сложения:

    (A ∨ B) ∨ C = A ∨(B ∨ C).

    При одинаковых знаках операций скобки можно ставить произвольно или вообще опускать.

    Распределительный (дистрибутивный) закон

      для логического умножения:

    для логического сложения:

    A ∨ (B & С) = (A ∨ В) & (A ∨ С).

    Двойное отрицание исключает отрицание.

    Закон исключения третьего

      для логического умножения:

      для логического сложения:

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

        для логического умножения:

      для логического сложения:

      Законы операций с 0 и 1

        для логического умножения:

      для логического сложения:

      A ∨ O = A; A ∨ l = l.

      Законы общей инверсии

        для логического умножения:

      для логического сложения:

      Законы алгебры логики могут быть доказаны с помощью таблиц истинности.

      Докажем распределительный закон для логическического сложения:

      A ∨ (В & С) = (А ∨ В) & (A ∨ С).

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

      Пример 2. Найдём значение логического выражения для числа Х = 0.

      Решение. При X = 0 получаем следующее логическое выражение: . Так как логические выражения 0 1 .

      1 С учётом того, что ваза разбита одним внуком, можно было составлять не всю таблицу, а только её фрагмент, содержащий следуюнще наборы входных переменных: 001, 010, 100.

      Исходя из того, что знает о внуках бабушка, следует искать в таблице строки, содержащие в каком-либо порядке три комбинации значений: 00, 11, 01 (или 10). Таких строк в таблице оказалось две (они отмечены галочками). Согласно второй из них, вазу разбили Коля и Вася, что противоречит условию. Согласно первой из найденных строк, вазу разбил Серёжа, он же оказался хитрецом. Шутником оказался Вася. Имя правдивого внука — Коля.

      Задача 2. В соревнованиях по гимнастике участвуют Алла, Валя, Сима и Даша. Болельщики высказали предположения о возможных победителях:

      1. Сима будет первой, Валя — второй;
      2. Сима будет второй, Даша — третьей;
      3. Алла будет второй, Даша — четвёртой.

      По окончании соревнований оказалось, что в каждом из предположений только одно из высказываний истинно, другое ложно. Какое место на соревнованиях заняла каждая из девушек, если все они оказались на разных местах?

      Решение. Рассмотрим простые высказывания:

      C1 = «Сима заняла первое место»;

      В2 = «Валя заняла второе место»;

      С2 = «Сима заняла второе место»;

      Д3 = «Даша заняла третье место»;

      А2 = «Алла заняла второе место»;

      Д4 = «Даша заняла четвёртое место».

      Так как в каждом из трёх предположений одно из высказываний истинно, а другое ложно, то можно заключить следующее:

      1. C1 + В2 = 1, С1 • В2 = 0;
      2. С2 + Д3 = 1, С2 • Д3 = 0;
      3. А2 + Д4 = 1, А2 • Д4 = 0.

      Логическое произведение истинных высказываний будет истинным:

      На основании распределительного закона преобразуем левую часть этого выражения:

      Высказывание С1 • С2 означает, что Сима заняла и первое, и второе места. Согласно условию задачи, это высказывание ложно. Ложным является и высказывание В2 • С2. Учитывая закон операций с константой 0, запишем:

      Дальнейшее преобразование левой части этого равенства и исключение заведомо ложных высказываний дают:

      Из последнего равенства следует, что С1 = 1, Д3 = 1, А2 = 1. Это означает, что Сима заняла первое место, Алла — второе, Даша — третье. Следовательно, Валя заняла четвёртое место.

      Познакомиться с другими способами решения логических задач, а также принять участие в Интернет-олимпиадах и конкурсах по их решению вы сможете на сайте «Математика для школьников» (http://www.kenqyry.com/).

      На сайте http://www.kaser.com/ вы сможете скачать демонстрационную версию очень полезной, развивающей логику и умение рассуждать логической головоломки Шерлок.

      1.3.6. Логические элементы

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

      Вы уже знаете, что любая информация может быть представлена в дискретной форме — в виде фиксированного набора отдельных значений. Устройства, которые обрабатывают такие значения (сигналы), называются дискретными. Дискретный преобразователь, который выдаёт после обработки двоичных сигналов значение одной из логических операций, называется логическим элементом.

      На рис. 1.5 приведены условные обозначения (схемы) логических элементов, реализующих логическое умножение, логическое сложение и инверсию.

      Рис 1.5.
      Логические элементы

      Логический элемент И (конъюнктор) реализует операцию логического умножения (рис. 1.5, а). Единица на выходе этого элемента появится только тогда, когда на всех входах будут единицы.

      Логический элемент ИЛИ (дизъюнктор) реализует операцию логического сложения (рис. 1.5, б). Если хотя бы на одном входе будет единица, то на выходе элемента также будет единица.

      Логический элемент НЕ (инвертор) реализует операцию отрицания (рис. 1.5, в). Если на входе элемента О, то на выходе 1 и наоборот.

      Компьютерные устройства, производящие операции над двоичными числами, и ячейки, хранящие данные, представляют собой электронные схемы, состоящие из отдельных логических элементов. Более подробно эти вопросы будут раскрыты в курсе информатики 10-11 классов.

      Пример 3. Проанализируем электронную схему, т. е. выясним, какой сигнал должен быть на выходе при каждом возможном наборе сигналов на входах.

      Решение. Все возможные комбинации сигналов на входах А к В внесём в таблицу истинности. Проследим преобразование каждой пары сигналов при прохождении их через логические элементы и запишем полученный результат в таблицу. Заполненная таблица истинности полностью описывает рассматриваемую электронную схему.

      Таблицу истинности можно построить и по логическому выражению, соответствующему электронной схеме. Последний логический элемент в рассматриваемой схеме — конъюнктор. В него поступают сигналы от входа Л и от инвертора. В свою очередь, в инвертор поступает сигнал от входа В. Таким образом,

      Составить более полное представление о логических элементах и электронных схемах вам поможет работа с тренажёром «Логика» (http://kpolyakov. narod. ru/prog/logic. htm).

      Самое главное

      Высказывание — это предложение на любом языке, содержание которого можно однозначно определить как истинное или ложное.

      Основные логические операции, определённые над высказываниями: инверсия, конъюнкция, дизъюнкция.

      Таблицы истинности для основных логических операций:

      При вычислении логических выражений сначала выполняются действия в скобках. Приоритет выполнения логических операций:

      Вопросы и задания

      Рассмотрите представленные на рисунке электрические схемы:

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

      Некоторый сегмент сети Интернет состоит из 1000 сайтов. Поисковый сервер в автоматическом режиме составил таблицу ключевых слов для сайтов этого сегмента. Вот её фрагмент:

      По запросу сомики & гуппи было найдено 0 сайтов, по запросу сомики & меченосцы — 20 сайтов, а по запросу меченосцы & гуппи — 10 сайтов.

      Сколько сайтов будет найдено по запросу сомики | меченосцы | гуппи?

      Для скольких сайтов рассматриваемого сегмента ложно высказывание «Сомики — ключевое слово сайта ИЛИ меченосцы — ключевое слово сайта ИЛИ гуппи — ключевое слово сайта»?
      Постройте таблицы истинности для следующих логических выражений:

    • Проведите доказательство рассмотренных в параграфе логических законов с помощью таблиц истинности.
    • Даны три числа в десятичной системе счисления: А = 23, B = 19, С = 26. Переведите А, B и С в двоичную систему счисления и выполните поразрядно логические операции (A ∨ B) & С. Ответ дайте в десятичной системе счисления.
    • Найдите значения выражений:

      Найдите значение логического выражения для указанных значений числа X:

      Пусть А = «Первая буква имени — гласная», В = «Четвёртая буква имени согласная». Найдите значение логического выражения для следующих имён:

      4) ФЁДОР

      Разбирается дело Джона, Брауна и Смита. Известно, что один из них нашёл и утаил клад. На следствии каждый из подозреваемых сделал два заявления:

      Смит: «Я не делал этого. Браун сделал это».

      Джон: «Браун не виновен. Смит сделал это».

      Браун: «Я не делал этого. Джон не делал этого».

      Суд установил, что один из них дважды солгал, другой дважды сказал правду, третий один раз солгал, один раз сказал правду. Кто из подозреваемых должен быть оправдан?

    • Алёша, Боря и Гриша нашли в земле старинный сосуд. Рассматривая удивительную находку, каждый высказал по два предположения:
      1. Алеша: «Это сосуд греческий и изготовлен в V веке».
      2. Боря: «Это сосуд финикийский и изготовлен в III веке».
      3. Гриша: «Это сосуд не греческий и изготовлен в IV веке».
        Учитель истории сказал ребятам, что каждый из них прав только в одном из двух предположений. Где и в каком веке изготовлен сосуд?
    • Выясните, какой сигнал должен быть на выходе электронной схемы при каждом возможном наборе сигналов на входах. Составьте таблицу работы схемы. Каким логическим выражением описывается схема?

      Национальная библиотека им. Н. Э. Баумана
      Bauman National Library

      Персональные инструменты

      Булева алгебра

      Содержание

      Определение

      Булева алгебра как предметная область определяется следующими критериями:

      1. Непустое множество А.
      2. Бинарные операции Конъюнкция(ʌ) и Дизъюнкция ( v)
      3. Унарная операция отрицания (¬ или не)
      4. Логические константы Истина (1) и Ложь (0)

      Происхождение

      Булева алгебра названа по имени великого английского математика Джорджа Буля (1815—1864), который в 1854 г. опубликовал ставшую впоследствии знаменитой книгу «Исследование законов мышления». В начале гл. 1 он написал: «Назначение настоящего трактата — исследовать основные законы тех операций ума, посредством которых производится рассуждение; выразить их на символическом языке некоторого исчисления и на этой основе установить науку логики и построить ее метод; сделать этот метод основой общего применения математической доктрины вероятностей; и, наконец, собрать из различных элементов истины, выявленных в ходе этих изысканий, некоторые правдоподобные указания относительно природы и строения человеческого ума».

      В этой книге Буль изложил большую часть новой алгебры, особенно пригодную для анализа классов и предложений (высказываний).

      Другие математики и логики, в том числе Джон Венн и Эрнст Шрёдер, впоследствии значительно усовершенствовали и расширили алгебру Буля.

      В 1938 г. Клод Э. Шеннон, в то время студент Массачусетсского технологического института, впоследствии известный математик и инженер Белловских телефонных лабораторий, а в настоящее время профессор Массачусетского технологического института, показал, что булеву алгебру можно прекрасно применять при синтезе переключательных электрических схем. Его статья «Символический анализ релейно-переключательных схем» представляет собой веху в развитии применений булевой алгебры.

      Аксиомы

      1) Булева переменная всегда равна либо нулю, либо единице

      2) Инверсное значение переменной x противоположно ее прямому значению

      3) Правила выполнения логического умножения (конъюнкции)

      4) Правила выполнения логического сложения (дизъюнкции)

      Законы

      1) Ассоциативный (сочетательный) закон

      Ассоциативность конъюнкции и дизъюнкции выражается следующими формулами:

      На практике это означает, что можно опускать те скобки, которые определяют, в каком порядке должна выполняться конъюнкция и дизъюнкция.

      2) Коммутативный (переместительный) закон Правила

      С помощью законов алгебры логики можно производить равносильные преобразования логических выражений с целью их упрощения. В алгебре логики на основе принятого соглашения установлены следующие правила (приоритеты) для выполнения логических операций:

      первыми выполняются операции в скобках, затем в следующем порядке:

      Обозначение на логических схемах

      Для обозначения логических элементов используется несколько стандартов. Наиболее распространёнными являются американский (ANSI), европейский (DIN), международный (IEC) и российский (ГОСТ). На рисунке ниже приведены обозначения логических элементов в этих стандартах.

      Булева алгебра. Часть 2. Основные законы и функции

      Продолжение рассказа о булевой алгебре, условные обозначения, правила, операции. Переход к основам контактных схем.

      В первой статье было рассказано о Джордже Буле как о создателе алгебры логики. Во второй статье будет рассказано об основных операциях булевой алгебры, методах упрощения булевых выражений. Итак, булева алгебра в качестве аргументов использует высказывания, причем не их смысл, а истинность или ложность высказывания.

      Форма записи выражений в булевой алгебре.

      Если высказывание истинно, то его записывают так: А = 1, если же оно ложно, то А = 0 (ведь неверно, что картошка — это фрукт). (Смотри окончание статьи №1). Для любого высказывания А либо истинно (А = 1), либо ложно (А = 0). Середины здесь быть не может. Об этом мы уже говорили.

      Если два простых высказывания соединить союзом И, то получится сложное высказывание, которое называют логическим произведением. Возьмем два простых высказывания: «Три больше двух» обозначим буквой А, «Три меньше пяти» — буквой В.

      Отсюда сложное высказывание «Три больше двух И меньше пяти» есть логическое (в данном случае заглавная буква И, говорит о том, что это «И» логическая операция, также как далее в тексте «ИЛИ» и «НЕ».) произведение высказываний А и В. Обозначается оно так: A^B или А*В.

      Логическое умножение (операция «И»).

      В элементарной алгебре А*А =А2. Но в алгебре Буля А*А = А2 = А, А * А = А так как знак умножения (*) теперь обозначает. И. в смысле И. И. Весь наш опыт подтверждает, что и А И А — это то же самое, что одно А. С этим нельзя не согласиться. Истинность высказывания не меняется, если его повторить сомножителем несколько раз.

      Произведение двух высказываний считается истинным (равным 1), тогда, и только тогда, когда оба сомножителя истинны, и ложным (равным 0), если хоть один из сомножителей ложен. Согласитесь, что эти правила не противоречат здравому смыслу, и, кроме того, они полностью соответствуют правилам элементарной алгебры:

      1*1 = 1, 1*0 = 0 = 0*1 = 0, 0*0 = 0.

      Первое равенство читается так: если и А и В истинны, то произведение А*В истинно. В алгебре Буля знак умножения (*) заменяет союз И.

      Логические произведения могут включать не два, а большее число высказываний — сомножителей. И в этом случае произведение бывает истинным только тогда, когда одновременно истинны все высказывания-сомножители.

      Логическое сложение (операция «ИЛИ»)

      Если два высказывания соединить союзом ИЛИ. то образованное сложное высказывание называется логической суммой.

      Рассмотрим пример логической суммы. Высказывание А: «Сегодня я пойду в кино».

      Высказывание В: «Сегодня я пойду на дискотеку». Складываем оба высказывания и получаем: «Сегодня я пойду в кино ИЛИ на дискотеку».

      Это сложное высказывание обозначается так: А + В = С или (А V В) = С.

      Через С мы обозначили сложное высказывание логической суммы.

      В рассматриваемом примере союз ИЛИ нельзя употреблять в исключающем смысле. Ведь в один и тот же день можно попасть И в кино И на дискотеку. А вот высказывание:

      «Председателем садового товарищества будет Петров или Иванов»—не является логической суммой, потому, что председателем будет только кто-то один, а другой простым рядовым садоводом — любителем.

      Знак V для обозначения логической суммы выбран потому, что это начальная буква латинского слова «vel», обозначающего «или», в отличие от латинского слова «aut>, обозначающего «и». Теперь всем должно быть ясно, почему логическое произведение обозначается знаком ^.

      В элементарной алгебре есть правило A + А = 2А. Это правило верно, какое бы число ни изображалось буквой А. В булевой алгебре ему соответствует правило А + А = А. Весь наш жизненный опыт говорит, что сказать А ИЛИ А ИЛИ оба А есть лишь другой и более длинный способ сказать просто А.

      Как и всякое сложное высказывание, сумма двух высказываний А и В может быть истинной или ложной. Сумма считается истинной, то есть равной единице, если хоть одно из слагаемых истинно:

      А + В = 1, если ИЛИ А = 1 ИЛИ В = 1, что согласуется с обычной арифметикой:

      Если оба складываемых высказывания истинны, то сумма считается также истинной, поэтому в алгебре Буля имеем: (1) + (1) = 1.

      Скобки здесь поставлены для того, чтобы подчеркнуть условный, смысл этого сложения, а не арифметический.

      Сумма двух высказываний считается ложной и равной нулю тогда, а только тогда, когда оба слагаемых ложны. Отсюда:

      Итак, сумма двух высказываний А + В считается истинной, если истинно ИЛИ А, ИЛИ В, ИЛИ оба слагаемых вместе. Таким образом, слово ИЛИ обозначается знаком +.

      Помня, что высказывания А и В могут быть только истинными или ложными и, следовательно, иметь меру истинности 1 или 0, результаты рассмотренных операций И и ИЛИ можно свести в таблицы 1 и 2.

      Третья операция, широко используемая алгеброй Буля, — операция отрицания — НЕ. Напоминаем, элементарная алгебра пользуется операциями СЛОЖИТЬ, ВЫЧЕСТЬ, УМНОЖИТЬ НА, РАЗДЕЛИТЬ НА и некоторыми другими.

      Для каждого высказывания А существует его отрицание НЕ А, которое мы будем обозначать символом /А. Это ни у кого не должно вызывать сомнения.

      Приведем примеры: «Мы поедем в лес» А, «Мы не поедем в лес» /А.

      Если высказывание А истинно, то есть А = 1, то его отрицание /А обязательно должно быть ложно /А = 0. И наоборот, если какое-либо высказывание ложно, то его отрицание истинно. Например: «Лошадь не ест сена» /А = 0, «Лошадь ест сено» (А = 1). Это можно выразить таблицей 3.

      Определяя смысл действия отрицания, и полагая, что из двух высказываний А и /А всегда одно истинно, следуют две новые формулы алгебры Буля:

      А + (/А) = 1 и А* (/А) = 0.

      Имеются еще и другие формулы, упрощающие логическую обработку высказываний. Например, 1+А = 1, так как, согласно определению сложения, в случае, когда одно слагаемое равно единице, сумма всегда равна единице. Полученный результат не зависит от того, будет ли А = 0 или А = 1.

      Каждая из трех рассмотренных нами логических операций (И, ИЛИ, НЕ) обладает определенными свойствами, близкими к правилам элементарной алгебры. Если все их сформулировать, то получим 25 правил булевой алгебры. Их вполне достаточно для решения почти любой логической задачи. Без этих правил решать логические задачи из-за их кажущейся запутанности становится довольно трудно. Пытаться найти правильный ответ, не пользуясь правилами, — значит заменять их смекалкой и общими рассуждениями. Правила значительно облегчают эту работу и экономят время.

      В рамках статьи невозможно рассмотреть все эти 25 правил, но желающие всегда могут найти их в соответствующей литературе.

      Как уже упоминалось в первой статье в 1938 году молодой американский ученый Клод Шеннон в статье «Символический анализ релейных и переключательных схем» впервые использует булеву алгебру для задач релейной техники. Открытие Шеннона состояло в том, что он понял, что метод конструирования релейных автоматов и электронных вычислительных машин представляет собой фактически раздел математической логики.

      Так часто бывает. Ученый долгие годы трудится над какой-либо проблемой, которая его соотечественникам кажется совершенно ненужной — просто забавой. Но проходят десятилетия, а иногда и века, и никому не нужная теория не только приобретает право на существование, но без нее уже становится немыслим дальнейший прогресс.

      Что помогло Шеннону вторично «открыть» булеву алгебру? Случай? Ничего подобного.

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

      Алгебра Буля очень подошла для анализа и синтеза релейных схем. Достаточно было в качестве истинного высказывания принять: «Сигнал в цепи есть», а в качестве ложного — «Сигнала в цепи нет», как появилась новая алгебра — алгебра сигналов, алгебра релейных схем.

      Новая алгебра справедлива только для рассмотрения релейных и переключательных цепей. Ведь только в таких схемах удовлетворяется условие «сигнал есть» и «сигнала нет». Там, где сигнал меняется непрерывно, приобретая сколь угодно большое число промежуточных условий (такой сигнал называется аналоговым), релейная алгебра неприменима. Об этом нужно всегда помнить. Но как раз большинство электронных вычислительных машин и кибернетических автоматов используют дискретный принцип обработки сигналов, в основу которого положены элементы «да — нет».

      Выражение «Контакт замкнут» Шеннон принял за истинное (1), а «Контакт разомкнут» — за ложное (0). Всю остальную «алгебру», включая операции И, ИЛИ и НЕ и 25 правил Шеннон заимствовал у Буля.

      Алгебра релейных схем получилась проще алгебры Буля, так как она имеет дело только с элементами типа «да — нет». Кроме того, новая алгебра более наглядна.

      Элементами в этой алгебре являются контакты, которые мы будем обозначать буквами А, В, С. Контакт замкнут— А, контакт разомкнут — /А (буква с черточкой).

      Система обозначений, как видите, полностью взята из алгебры Буля. Разомкнутый контакт является отрицанием замкнутого контакта. Один и тот же контакт не может быть одновременно замкнутым и разомкнутым.

      Условимся, что если в какой-либо схеме два контакта обозначены одной и той же буквой, то это значит, что они всегда принимают одни и те же значения.

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

      Если в некоторой цепи какой-либо контакт есть отрицание другого контакта, то их значения всегда противоположны. Например, контакты С и /С никогда не могут быть одновременно разомкнуты или одновременно замкнуты. А на схеме их можно представлять механически соединенными: если один из них размыкается, то другой замыкается.

      Знакомство с релейной алгеброй начнем с разбора простейших схем, соответствующих операциям И, ИЛИ и НЕ.

      Произведением двух контактов (операция И) будем называть схему, полученную в результате их последовательного соединения: она замкнута (равна 1) только тогда, когда оба контакта замкнуты (равны 1).

      Суммой двух контактов (операция ИЛИ) будем называть схему, образованную при их параллельном соединении: она замкнута (равна 1) тогда, когда замкнут (равен 1) хотя бы один из образующих схему контактов.

      Противоположный данному контакту (операция НЕ)—это контакт, равный 0 (разомкнутый), если данный контакт равен 1 (замкнут), и наоборот.

      Как и в алгебре Буля, если контакты обозначены буквами А и В, то произведение двух контактов мы будем обозначать через А*В, сумму — через А + В, а контакт, противоположный А, — через /А. Сказанное поясним рисунками 1, 2 и 3.

      Достоверность таблиц, соответствующих операциям И, ИЛИ и НЕ. теперь ни у кого не должна вызывать сомнений.

      Остановимся на двух примерах: 1*0 = 0 и 1+0=1.

      Из рисунка видно, что постоянно замкнутый контакт, последовательно соединенный с постоянно разомкнутым контактом, эквивалентен постоянно разомкнутому контакту (1*0 = 0) Постоянно замкнутый контакт, параллельно соединенный с постоянно разомкнутым контактом, эквивалентен постоянно замкнутому контакту.

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

      Если структурная формула какой-либо релейной схемы равна 1, то через нее сможет пройти сигнал — цепь замкнута. И наоборот, если структурная формула схемы равна 0, сигнал через нее не пройдет — цепь разорвана. Вывод: две релейные схемы эквивалентны друг другу тогда, когда равны их структурные формулы.

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

      Логические схемы

      Логические схемы в компьютерных и других электронных устройствах выполняют операции с входными и выходными данными указанных устройств. Эти данные представляются в виде двоичных кодов, т.е. последовательностей нулей и единиц. Именно поэтому булева алгебра является удобным математическим аппаратом для анализа и синтеза (конструирования) логических схем.

      Основой построения логических схем является набор логических элементов. Каждый элемент реализует некоторую логическую функцию. Его входы соответствуют булевым переменным, а выход — значению функции. Названия и графические символы наиболее часто используемых логических элементов представлены в таблице на рис. 4.7.

      Определение 4.14. Набор логических элементов полон, если с его помощью можно реализовать любую булеву функцию.

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

      Графический символ элемента

      Рис. 4.7. Основные логические элементы

      Рис. 4.8. Логическая схема, реализующая функцию F(x, у, z) = (х v у) л z

      ческая схема строится из элементов выбранного основного набора путем различных соединений этих элементов.

      Рассмотрим следующий пример. Необходимо построить логическую схему, реализующую функцию F(x, у, z) — (х v у) л z. Используя логические элементы «И», «ИЛИ», составляем схему, представленную на рис. 4.8.

      Логические элементы, которые реализуют операции, удовлетворяющие ассоциативному и коммутативному законам, на схемах могут изображаться с числом входов не более двух. Это означает многократное применение соответствующей операции. На рис. 4.9 изображен элемент «ИЛИ», имеющий три входа и реализующий функцию Р(х<, х2, х3) = х, ух2 ух3.

      Дхь Х2, Хз) = X] V Х2 V Хз

      Рис. 4.9. Логический элемент «ИЛИ» с тремя входами

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

      Другой путь состоит в том, что по элементам, входящим в логическую схему, сначала строится формула логической функции, а затем определяется таблица истинности функции.

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

      Рассмотрим следующий пример. Записать булеву функцию, которую реализует представленная на рис. 4.10 схема. Построить схему, содержащую минимальное количество элементов.

      Рис. 4.10. Логическая схема, реализующая функцию /'(х,, х2)

      Согласно соединению логических элементов приведенная схема реализует булеву функцию Р(х<, х2) = хх м(л:, лх2). Таблица истинности этой функции приведена ниже на рис. 4.11.

      Каждый электрик должен знать:  Что такое клетка Фарадея и где применяется этот принцип
    Добавить комментарий