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

Закон одинарных элементов

Этот закон непосредственно следует из приведенных выше выражений аксиом алгебры логики (таблицы истинности логических
элементов). Верхние два выражения могут быть полезны при построении коммутаторов, ведь подавая на один из входов элемента
«2И» логический ноль или единицу можно либо пропускать сигнал на выход, либо формировать на выходе нулевой потенциал.

Второй вариант использования этих выражений заключается в возможности избирательного обнуления определённых разрядов
многоразрядного числа. При поразрядном применении операции «И» можно либо оставлять прежнее значение разряда, либо
обнулять его, подавая на соответствующие разряды единичный или нулевой потенциал. Например, в восьмиразрядном двоичном
числе требуется обнулить 6, 3 и 1 разряды. Тогда, при выполнении операции поразрядного логического умножения получим:

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

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

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

Логические основы работы компьютера

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

Логические элементы имеют один или несколько входов и один выход, через которые проходят электрические сигналы, обозначаемые условно 0, если «отсутствует» электрический сигнал, и 1, если «имеется» электрический сигнал.

Базовые логические элементы реализуют три основные логические операции: «И», «ИЛИ», «НЕ».

Логический элемент «НЕ» (инвертор)

Простейшим логическим элементом является инвертор, выполняющий функцию отрицания. Если на вход поступает сигнал, соответствующий 1, то на выходе будет 0. И наоборот.

У этого элемента один вход и один выход. На функциональных схемах он обозначается:

Говорят также, что элемент «НЕ» инвертирует значение входной двоичной переменной.

Проверь соответствие логического элемента «НЕ» логическому элементу «НЕ». Воспользуйся тренажером Логические элементы.xlsx

Логический элемент «И» (конъюнктор)

Логический элемент «И» (конъюнктор) выдает на выходе значение логического произведения входных сигналов.

Он имеет один выход и не менее двух входов. На функциональных схемах он обозначается:

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

Проверь соответствие логического элемента «И» логическому элементу «И».  Воспользуйся тренажером Логические элементы.xlsx

Логический элемент «ИЛИ» (дизъюнктор)

Логический элемент «ИЛИ» (дизъюнктор) выдает на выходе значение логической суммы входных сигналов. Он имеет один выход и не менее двух входов. На функциональных схемах он обозначается:

Сигнал на выходе дизъюнктора не появляется тогда и только тогда, когда на все входы не поданы сигналы.

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

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

Проверь соответствие логического элемента «ИЛИ» логическому элементу «ИЛИ».  Воспользуйся тренажером Логические элементы.xlsx

Пример 1.Составьте логическую схему для логического выражения: F=A \/ B /\ A.

1.Две переменные – А и В.

2.Две логические операции: 1-/\, 2-\/.

3.Строим схему:

Пример 2.Постройте логическую схему, соответствующую логическому выражению F=А/\В\/ ¬(В\/А). Вычислить значения выражения для А=1,В=0.

1.Переменных две: А и В; 1 4 3 2

2.Логических операций три: /\ и две \/; А/\В\/ ¬ (В\/ А).

3.Схему строим слева направо в соответствии с порядком логических операций:

4.  Вычислим значение выражения: F=1 /\ 0 \/ ¬(0 \/ 1)=0

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

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

При этом под высказыванием (суждением) понимают повествовательное предложение, относительно которого можно сказать, истинно или ложно.

Алгебра логики возникла в середине ХIХ века в трудах английского математика Джорджа Буля. Её создание представляло собой попытку решать традиционные логические задачи алгебраическими методами.

Долгое время алгебра логики была известна достаточно узкому классу специалистов. Прошло почти 100 лет со времени создания алгебры логики Дж. Булем, прежде чем в 1938 Клод Шеннон (1916 — 2001) показал, что алгебра логики применима для описания самых разнообразных процессов, в том числе функционирования релейно-контактных и электронно-ламповых схем.

Алгебра логики явилась математической основой теории электрических и электронных переключателей схем, используемых в ЭВМ. В компьютерных науках её предпочитают называть не алгеброй логики, а Булевой алгеброй — по имени её создателя.

READ  Выпрямители (часть 1). виды и устройство. структура и особенности

Алгебра логики изучает свойства функций, у которых и аргументы, и значения принадлежат заданному двухэлементному множеству (например, {0,1}). Иногда вместо термина «алгебра логики»  употребляют термин «двузначная логика».

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

операциями арифметики для реализации различных алгоритмов.

Таким образом, алгебра логики — это область математики. Она оперирует величинами, которые могут принимать два значения (булевых значения). Эти два значения могут быть обозначены как угодно, лишь бы по-разному. Самые распространенные варианты:

0, 1        F, T        false, true        ложь, истина        Л, И

При применении булевой алгебры в вычислительной технике, булевы значения — это 0 и 1. Они представляют собой состояние ячейки памяти объёмом в 1 бит или наличие/отсутствие напряжения в электрической схеме. Алгебра логики позволяет строить сложные электронные узлы, элементы которых работают согласно этой математической теории. При применении булевой алгебры в логических построениях в математике, булевы значения — это «ложь» и «истина». Они определяют истинность или ложность некоторого высказывания. Под высказываниями понимаются математические формулы. При применении булевой алгебры в повседневных рассуждениях, булевы значения — это также «ложь» и «истина». Они представляют собой оценку истинности или ложности некоторого высказывания. Под высказываниями понимаются фразы, которые удовлетворяют строго определенному списку свойств.

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

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

5.12. Что такое переключательная схема?

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

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

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

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

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

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

Найдем функции проводимости F некоторых переключательных схем:

a)  
Схема не содержит переключателей и проводит ток всегда, следовательно
F=1
б)  
Схема содержит один постоянно разомкнутый контакт, следовательно
F=0
в)  
Схема проводит ток, когда переключатель х замкнут, и не проводит, когда
х разомкнут, следовательно, F(x) = x
г)  
Схема проводит ток, когда переключатель х разомкнут, и не проводит,
когда х замкнут, следовательно, F(x) =
д)  
Схема проводит ток, когда оба переключателя замкнуты, следовательно,
F(x) = x . y
е)  
Схема проводит ток, когда хотя бы один из переключателей замкнут,
следовательно, F(x)=x v y; 
ж)  
Схема состоит из двух параллельных ветвей и описывается функцией

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

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

Задача нахождения среди равносильных схем наиболее простых является очень
важной. Большой вклад в ее решение внесли российские учёные Ю.И

Журавлев,
С.В. Яблонский и др.

При рассмотрении переключательных схем возникают две основные задачи:
синтез и анализ схемы.

СИНТЕЗ СХЕМЫ по заданным условиям ее работы сводится к следующим
трём этапам:

  1. составлению функции проводимости по таблице истинности, отражающей эти
    условия;
  2. упрощению этой функции;
  3. построению соответствующей схемы.

АНАЛИЗ СХЕМЫ сводится к

  1. определению значений её функции проводимости при всех возможных
    наборах входящих в эту функцию переменных.
  2. получению упрощённой формулы.

Примеры.

1. Построим схему, содержащую 4
переключателя x, y, z и t, такую, чтобы она проводила ток тогда и только
тогда, когда замкнут контакт переключателя t и какой-нибудь из остальных
трёх контактов.

Решение. В этом случае можно обойтись без построения таблицы
истинности. Очевидно, что функция проводимости имеет вид
F(x, y, z, t) = t . (x v y v z), а схема
выглядит так:

READ  Законодательная база российской федерации

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

Схема имеет вид:

3. Найдем функцию проводимости схемы:

Решение. Имеется четыре возможных пути прохождения тока при
замкнутых переключателях a, b, c, d, e : через переключатели a, b; через
переключатели a, e, d; через переключатели c, d и через переключатели
c, e, b. Функция проводимости F(a, b, c, d, e) =
a . b   v   a . e . d   v  
c . d   v   c . e . b.

4. Упростим переключательные схемы:

а)  

Решение:   

Упрощенная схема:

б)  

.

Здесь первое логическое слагаемое является отрицанием второго логического слагаемого
, а дизъюнкция
переменной с ее инверсией равна 1.

Упрощенная схема :

в)  

Упрощенная схема:

г)  

Упрощенная схема:

д)  

(по закону склеивания)

Упрощенная схема:

е)  

Решение:

Упрощенная схема:

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

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

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

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

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

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

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

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

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

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

Задача о минимизации контактной схемы[править]

Определение:
Две контактные схемы называются эквивалентными (англ. equivalent contact circuits), если они реализуют одну и ту же булеву функцию.
Определение:
Сложностью контактной схемы (англ. the complexity of the contact circuit) называется число
ее контактов.
Определение:
Минимальная контактная схема (англ. minimal contact circuit) — схема, имеющая наименьшую сложность среди эквивалентных ей схем.
Определение:
Дерево конъюнктов для переменных — двоичное ориентированное дерево глубиной , такое что: поддеревья на одном и том же уровне одинаковы; и левое ребро любого узла помечено символом переменной , а правое помечено символом отрицания переменной .

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

  • Осуществляем переход от контактной схемы к её булевой функции .
  • Упрощаем , то есть отыскиваем функцию (на том же базисе, что и , равносильную и содержащую меньше вхождений операций дизъюнкции и конъюнкции. Для этой операции удобно использовать карты Карно.
  • Строим схему , реализующую функцию .
Теорема:
Любую булеву функцию можно представить контактной схемой, сложностью
Доказательство:

Пусть дана функция и она представлена в ДНФ

Дерево конъюнктов для 2-х переменных

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

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

В результате можно построить контактную схему для любой функции со сложностью

1.4. Применение алгебры логики в информатике

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

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

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

Из этого следует два вывода:

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

2) на этапе конструирования аппаратных средств алгебра логики позволяет

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

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

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

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

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

 Итак, алгебра логики применяется: 1) для упрощения сложных логических формул и доказательств тождеств; 2) при решении логических задач; 3) в контактных схемах; 4) при доказательствах теорем; 5) в базах данных при составлении запросов.

Законы отрицания

Существуют следующие законы отрицания:

Закон дополнительных элементов

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

Закон отрицательной логики (Де Моргана)

Закон отрицательной логики справедлив для любого числа переменных. Этот закон алгебры логики позволяет реализовывать
при помощи логических элементов «ИЛИ» и наоборот: реализовывать
логическую функцию «ИЛИ» при помощи логических элементов «И». Это особенно полезно в ТТЛ схемотехнике, так как там легко
реализовать логические элементы «И», но при этом достаточно сложно логические элементы «ИЛИ». Благодаря закону отрицательной
логики можно реализовывать элементы «ИЛИ» на логических элементах «И». На рисунке 3 показана реализация логического
элемента «2ИЛИ» на элементе «2И-НЕ» и двух инверторах.

1.3. Логические формулы. Законы алгебры логики

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

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

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

Логической формулой является: 1) любая логическая переменная, а также каждая из двух логических констант – 0 (ложь) и 1 (истина).  2) Если А и В – формулы, то В и А*В – тоже формулы, где знак «*» означает любую из логических бинарных операций. Формулой является, например, выражение: (x&y) → z. Каждой формуле при заданных значениях входящих в неё переменных приписывается одно из двух значений – 0 или 1. Формулы А и В, зависящие от одного и того же набора переменных , называют равносильными или эквивалентными, если на любом наборе значений переменных  они имеют одинаковые значения. Для обозначения равносильности формул используется знак равенства, например А=В.

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

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

Определение логической формулы:

1. Всякая логическая переменная и символы  «истина» (1) и «ложь (0) —  формулы.

2. Если  А и В — формулы, то , АВ, АvВ, А→B, АВ — формулы.

3. Никаких других формул в алгебре логики нет.

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

1) Законы коммутативности

х & y = y & x, x ∨ y = y ∨ x;

2) Законы ассоциативности

(x & y) & z = x & (y & z), (x ∨ y) ∨ z = x ∨ (y ∨ z);

3)Законы поглощения (нуля и единицы)

х ∨ 0 = x,  x & 1= x;

4) Законы дистрибутивности

х & (y ∨ z) = (x & y) ∨ (x & z), x ∨ (y & z) = (x ∨ y) & (x ∨z);

5) Закон противоречия

х ∨  = 0;

6) Закон исключённого третьего

х ∨ = 1;

7) Закон идемпотентности

х & x = x,  x ∨ x = x;

8) Закон двойного отрицания;

=

9) Законы де Моргана

−−−−                  −−−−

 = ,      = ,

9) Законы поглощения

х ∨ (x & y) = x, x & (x ∨ y) = x.

Любой из этих законов может быть доказан с помощью таблиц истинности.

Таблица истинности — табличное представление логической схемы (операции), в котором перечислены все возможные сочетания значений истинности входных сигналов (операндов) вместе со значением истинности выходного сигнала (результата операции) для каждого из  этих сочетаний. Таблица истинности от n переменных состоит из 2n  +1 строк и n +1 столбцов.

Пример. Составить таблицу истинности для функции f трех переменных x1, x2, x3, которая равна единице в случае, если только одна из входных переменных равна 1.

Таблица истинности для функции f

Входные переменные

Выходная переменная

х1

х2

х3

f

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

 Переменная х в функции f называется фиктивной (несущественной), если значение переменной х не влияет на значение булевой функции. Фиктивные переменные могут быть удалены или введены в набор переменных функций. Количество булевых функций определяется числом n  переменных

READ  Гост 31946-2012 провода самонесущие изолированные и защищенные для воздушных линий электропередачи. общие технические условия (с изменением n 1)
Рейтинг
( Пока оценок нет )
Понравилась статья? Поделиться с друзьями:
Добавить комментарий

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: