Законы алгебры буля

Основные законы алгебры Буля

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

а) Переместительный закон а + в = в + а; ав = ваб) Сочетательный закон (а + в) + с = а + (в + с); (ав)с = а(вс)в) Распределительный закон а(в + с) = ав + ас; а + вс = (а + в)(а + с)г) Закон поглощения а + ав = а(1 + в) = а; а(a + в) = а + ав = ад) Закон склеивания ав + ав’ = а; (а + в)(а + в’) = ае) Идемпотентный закон a + a = a; a & a = aё) Правила де Моргана Эти правила справедливы для любого числа аргументов. а + в + с + . + z = ( а’в’с’. z’ )’ авс. = ( а’ + в’ + с’ + . + z’ )’

Эти правила можно описать таким алгоритмом.

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

  1. проинвертировать все слагаемые в отдельности;
  2. заменить знаки дизъюнкции на знаки конъюнкции;
  3. проинвертировать получившееся выражение.

Аналогично выполняется переход от логического произведения к логической сумме.В инженерной практике используются лишь правила де Моргана и закон склеивания(в виде карт Карно).

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

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

, сумма по модулю 2 — . Содержание этих функций отражено в таблице .

Дискретная математика. Математическая логика

Лекция 8. Минимизация булевых функций.

2008 г. Метод Квайна-

МакКласки Проф., д.т.н. Гусева А.И. , доцент Порешин П.П.,

аспирант Цыплаков А.C.

Алгебра Буля

Алгебраическая система, содержащая в качестве сигнатуры логическое умножение, логическое сложение и отрицание, которые позволяет производить тождественные преобразования логических выражений, и множество <0, 1>в качестве носителя, называется алгеброй Буля

Законы алгебры Буля (1)

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

Закон коммутативности a + b = b + a

a + (b + c) = (a + b) + c a (b c) = (a b) c

Законы алгебры Буля (2)

Законы дистрибутивности Дистрибутивность конъюнкции относительно дизъюнкции

a (b + c) = a b + a c

Дистрибутивность дизъюнкции относительно конъюнкции

a + b c = (a + b) (a + c)

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

Законы алгебры Буля (3)

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

Законы поглощения a+ a b = a

Законы алгебры Буля (4)

Законы, определяющие действия с логическими константами 0 и 1

a + 0 = a a 0 = 0 a + 1 = 1 a 1 = 1

Дополнительные законы

Закон склеивания a b + a b = b

Закон Блейка-Порецкого a + a b = a + b

Закон свертки логического выражения

a b + a c + b c = a b + a c

Упрощение логических функций

Упростить СДНФ функции ( a b) c

Представим функцию в совершенной дизъюнктивной форме и упростим ее с помощью законов алгебры логики:

СДНФ = a b c + a b c + a b c + a b c + a b c = b c + b c +a b c = c +a b c = c +a

Метод Квайна-МакКласки

1. Представим наборы, на которых функция истинна, в виде двоичных эквивалентов

2. Упорядочим двоичные эквиваленты по ярусам и проведем склейку наборов в соседних ярусах, получая максимальные интервалы до тех пор, пока это возможно; помечаем каждый набор, участвовавший в склейке. Склеиваются только те наборы или интервалы, различие в которых заключается только в значении одного разряда: 001 и 000, 001- и 101-, и т.д.

Метод Квайна-МакКласки

3. Построим таблицу Квайна, столбцы которой соответствуют двоичные наборы истинности функции, а строки – максимальным интервалам. Если i-ый набор покрывается j-ым интервалом, то ставим 1 на пересечении соответствующих строки и столбца, в противном случае ставим 0 или ничего

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

Законы алгебры буля

Пусть M – непустое множество элементов любой природы , в котором определены отношение равенства и три операции – сложение, умножение, отрицание, подчиняющиеся следующим аксиомам:

4) Законы идемпотентности: а) x + x = x ; б) x ∙ x = x .

5) Закон двойного отрицания: .

6) Законы де-Моргана : а) ; б) .

7) Законы поглощения: а) ; б) .

Множество M называется булевой алгеброй.

Замечание 1. Если под основными элементами x , y , z … множества M подразумевать высказывания, под операциями сложения, умножения, отрицания – дизъюнкцию, конъюнкцию и отрицание соответственно, а знак равенства рассматривать как знак равносильности, то, как следует из равносильностей групп 1–3, все аксиомы булевой алгебры выполняются. Алгебра логики является моделью булевой алгебры или ее интерпретацией.

Замечание 2. Если под основными элементами x , y , z … множества M подразумевать множества, под операциями сложения, умножения, отрицания – объединение, пересечение, дополнение множеств соответственно, а знак равенства рассматривать как знак равенства множеств, приходим к алгебре множеств. В алгебре множе ств вс е аксиомы алгебры Буля выполняются.

Замечание 3. Таблица соответствия между понятиями теории множеств и математической логики имеет вид:

Законы и правила алгебры Буля;

Элементы алгебры Буля

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

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

Переместительный (коммутативный) закон. Закон справедлив как для конъюнкции, так и для дизъюнкции.

х1 + х2 + х3 + х4 .= х4 + х3 + х2+ х1 — от перемены мест логических слагаемых сумма не меняется.

х1 х2 х3 х4 .= х4 х3 х2 х1 — от перемены мест логических сомножителей их произведение не меняется.

Этот закон справедлив для любого количества логических операндов.

Сочетательный (ассоциативный) закон. Закон справедлив как для конъюнкции, так и для дизъюнкции.

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

Правило де Моргана:

-отрицание суммы равно произиедению отрицаний

— отрицание произведения равно сумме отрицаний

— операция склеивания для конъюнкций, где А — переменная или любое логическое выражение.

— операция склеивания для дизъюнкций.

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

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

Операции с отрицаниями:

— двойное отрицание равносильно отсутствию отрицания.

Операции с константами:

Операции с одинаковыми операндами:

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

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

Доказать справедливость распределительного закона в интерпретации выражением

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

Помня, что логическая сумма с одним слагаемым, равным константе «1», равна «1», можно записать

12х3.
Используем таблицу истинности для доказательства правила де Моргана в варианте

— отрицание суммы равно произведению отрицаний.

Составим таблицу истинности для правой и левой частей и составляющих их функций, табл. 2.2-1.

Малый математический факультет

Кубанского государственного университета

Основы алгебры логики

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

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

Термин «логика» происходит от древнегреческого “logos”, означающего «слово, мысль, понятие, рассуждение, закон».

Алгеброй логики называется аппарат, который позволяет выполнять действия над высказываниями.

Алгебру логику называют также алгеброй Буля, или булевой алгеброй, по имени английского математика Джорджа Буля, разработавшего в XIX веке ее основные положения. В булевой алгебре высказывания принято обозначать прописными латинскими буквами: A, B, X, Y. В алгебре Буля введены три основные логические операции с высказываниями? Сложение, умножение, отрицание. Определены аксиомы (законы) алгебры логики для выполнения этих операций. Действия, которые производятся над высказываниями, записываются в виде логических выражений.

Логические выражения могут быть простыми и сложными.

Простое логическое выражение состоит из одного высказывания и не содержит логические операции. В простом логическом выражении возможно только два результата — либо «истина», либо «ложь».

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

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

• НЕ (логическое отрицание, инверсия);

• ИЛИ (логическое сложение, дизъюнкция);

• И (логическое умножение, конъюнкция).

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

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

  • таблица истинности одноместной логической операции состоит из двух строк: два различных значения аргумента — «истина» (1) и «ложь» (0) и два соответствующих им значения функции;
  • в таблице истинности двуместной логической операции — четыре строки: 4 различных сочетания значений аргументов — 00, 01, 10 и 11 и 4 соответствующих им значения функции;
  • если число высказываний в логическом выражении N, то таблица истинности будет содержать 2 N строк, так как существует 2 N различных комбинаций возможных значений аргументов.
  • Операция НЕ — логическое отрицание (инверсия)

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

    • если исходное выражение истинно, то результат его отрицания будет ложным;

    • если исходное выражение ложно, то результат его отрицания будет истинным.

    Для операции отрицания НЕ приняты следующие условные обозначения:

    Результат операции отрицания НЕ определяется следующей таблицей истинности:

    2.8.1. Законы алгебры Буля

    В математической логике определяется специальная алгебра, алгебра Буля, содержащая операции логического умножения, логического сложения и отрицания < ,+, - >, которые позволяет производить тождественные преобразования логических выражений. К этим законам относятся

    Закон идемпотентности (одинаковости):

    a + ( b + c ) = ( a + b ) + c, a ( b c ) = ( a b ) c .

    — дистрибутивность конъюнкции относительно дизъюнкции:

    а ( b + c ) = a b + a c.

    — дистрибутивность дизъюнкции относительно конъюнкции:

    а + b c = ( a + b ) ( a + c ) .

    Закон двойного отрицания:

    Законы де Моргана:

    a + b = a b , a b = a + b .

    a + a b = a, a (a + b) = a.

    Законы, определяющие действия с логическими константами 0 и 1 :

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

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

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

    a b+ a b =b ( a+a ) = b 1 = b .

    2) ( a + b ) ( a + b ) = b .

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

    ( a + b ) ( a + b ) = a a + b = b .

    a + a b = a + b , a + a b = a + b .

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

    a+ a b = a 1 + a b = a ( b + b ) + a b =

    = a b + a b + a b = a b + a b + a b + a b = a+b .

    Закон свертки логического выражения:

    a b+a c+ b c = a b+ a c .

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

    = a b ( c + c ) + a c ( b + b ) + b c ( a + a ) =

    = a b c + a b c + a b c + a b c + a b c + a b c =

    = ( a b c + a b c )+( a b c + a b с ) + ( a b с+ a b c ) =

    = a b + a c + a c = a b + a c .

    2.8.2. Упрощение логических функций

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

    Задача 2.11 . Упростить СДНФ функции ( a b ) c.

    СДНФ = a b c + a b c + a b c + a b c + a b c = b c + b c +a b c =

    Задача 2.12. Упростить СДНФ функции ( a ↓ b ) ↓ c.

    Решение. Представим функцию в совершенной дизъюнктивной форме и упростим ее с помощью законов алгебры логики:

    СДНФ = a b c + a b c + a b c = b c + a c .

    Задача 2.13. Упростить СДНФ функции ( a b ) c .

    СДНФ = a b c + a b c .

    Дальнейшее упрощение невозможно.

    Задача 2.14. Упростить СДНФ функции ( a → b ) → c .

    СДНФ = a b c + a b c + a b c + a b c + a b c + a b c =

    Задача 2.15. Упростить СДНФ функции a b + a b .

    СДНФ = a b c + a b c + a b c +a b c = a b + a b .

    2.8.3. Метод Квайна – МакКласки

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

    1. Представить наборы (конституенты), на которых функция истинна, в виде двоичных эквивалентов;

    2. Упорядочить двоичные эквиваленты по ярусам (по числу единиц двоечных эквивалентов) и провести склейку (применить правило склеивания к соответствующим конституентам) наборов в соседних ярусах, получая максимальные интервалы до тех пор, пока это возможно; пометить каждый набор, участвовавший в склейке. Склеиваются только те наборы или интервалы, различие в которых заключается только в значении одного разряда: 001 и 000, 001-

    3. Построить таблицу Квайна, столбцы которой соответствуют двоичным наборам истинности функции, а строки – максимальным интервалам. Если i -й набор покрывается j -м интервалом, то ставим 1 на пересечении соответствующих строки и столбца, в противном случае ставим 0 или ничего;

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

    Рассмотрим функцию F 1 , которая истинна на наборах <1, 3, 5, 7, 11, 13, 15>. Совершенная дизъюнктивная нормальная форма данной функции равна:

    СДНФ = x 1 x 2 x 3 x 4 + x 1 x 2 x 3 x 4 + x 1 x 2 x 3 x 4 + + x 1 x 2 x 3 x 4 + x 1 x 2 x 3 x 4 + x 1 x 2 x 3 x 4 + x 1 x 2 x 3 x 4 .

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

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

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

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

    Если высказывание истинно, то его записывают так: А = 1, если же оно ложно, то А = 0 (ведь неверно, что картошка — это фрукт). Для любого высказывания А либо истинно (А = 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, сигнал через нее не пройдет — цепь разорвана. Вывод: две релейные схемы эквивалентны друг другу тогда, когда равны их структурные формулы.

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

    Смотрите еще:

    • Правила умножения и деления чисел в степени Свойства степени Напоминаем, что в данном уроке разбираются свойства степеней с натуральными показателями и нулём. Степени с рациональными показателями и их свойства будут рассмотрены в уроках для 8 классов. Степень с натуральным […]
    • Спор пароль Надежность пароля [Комикс разбит на 6 панелей расположенных сеткой 3х2.] [В каждом ряду первая панель объясняет, из чего состоит пароль; вторая панель показывает, сколько времени может потребоваться компьютеру для его подбора; а третья […]
    • Построить график функции правила Построить график функции правила ПЕРЕНОС ВДОЛЬ ОСИ ОРДИНАТ f(x) => f(x) - b Пусть требуется построить график функции у = f(х) - b. Нетрудно заметить, что ординаты этого графика для всех значений x на |b| единиц меньше соответствующих […]
    • Жертва преступления на английском Секреты английского языка Сайт для самостоятельного изучения английского языка онлайн The Language of Crime Posted on 2015-07-18 by admin in Разговорник // 0 Comments Предлагаем вам несколько слов на тему «преступление» (crime). Лицо, […]
    • Ночь страшного суда 1993 Ночь страшного суда (1993) Judgment Night Продолжительность: 110 мин. Жанр:Боевик , Триллер , Криминал . Страна:США, Япония. Кинокомпании:Universal, Largo. Слоган: "In a deadly game of cat and mouse, they must fight to […]
    • Разрешение квинтсекстаккорда S o l F a theory 10. Септаккорды Септаккордом называется 4-звучие, располагающееся по терциям. Септаккорд образуется в результате прибавления к трезвучию сверху еще одной – большой или малой – терции. В септаккорде 4 звука: прима, […]
    • Авито работа юрист спб О компaнии: Нaша кoмпания занимает лидирующиe позиции нa рынке юpидичеcкиx услуг по вeдeнию дeл в Apбитpажном судe в Caнкт-Пeтepбургe. Зa годы paбoты сфopмирoвана бoльшая клиентская база с пoстоянными клиeнтaми. У кoмпaнии pазнообразнaя […]
    • Выдача удостоверений на право управления самоходными маломерными судами выдача удостоверения - 10 рабочих дней выдача дубликата - 2 рабочих дней при истечения срока действия удостоверения - 3 рабочих дня Как получить услугу онлайн Авторизоваться на портале и пройти по разделу "Заказaть услугу онлайн". […]