Законы алгебры логики
Законы алгебры логики записываются в виде формул, которые позволяют проводить равносильные преобразования логических выражений.
Ниже приводятся основные законы для логических операций. Используя законы алгебры логики, можно осуществлять тождественные преобразования формул, упрощать такие формулы. Это необходимо при создании логических схем и конструировании BEAM-роботов.
Законы Де Моргана
Правила операций с константами
Законы инверсии (отрицания)
Снятие двойного отрицания
Кроме логических законов важное значение при упрощении выражений может иметь знание следствий из законов и правил логической алгебры.
Последнее следствие может быть представлено и следующим образом:
Знак отрицания над выражением дает возможность опустить скобки, в которые это выражение заключено (отрицание является самой старшей логической операцией).
При упрощении выражений следует помнить старшинство операций: инверсия, конъюнкция, дизъюнкция.
Сайт находится в разработке, поэтому, пожалуйста, проявите снисходительность к тому, что материалов, пока мало.
В скором времени материалы появятся.
Свободный монтаж в BEAM-робототехнике
Один из наиболее распространенных способов монтажа при создании BEAM-роботов.
beam-robot.ru
Оглавление:
История науки и техники Com New
Основные законы алгебры логики и правила преобразования логических выражений
В алгебре логики имеются законы, которые записываются в виде соотношений. Логические законы позволяют производить равносильные (эквивалентные) преобразования логических выражений. Преобразования называются равносильными, если истинные значения исходной и полученной после преобразования логической функции совпадают при любых значениях входящих в них логических переменных.
Для простоты записи приведем основные законы алгебры логики для двух логических переменных А и В. Эти законы распространяются и на другие логические переменные.
1. Закон противоречия:
2. Закон исключенного третьего:
3. Закон двойного отрицания:
4. Законы де Моргана:
5. Законы повторения: A & A = A; A v A = A; В & В = В; В v В = В.
6. Законы поглощения: A ? (A & B) = A; A & (A ? B) = A.
7. Законы исключения констант: A ? 1 = 1; A ? 0 = A; A & 1 = A; A & 0 = 0; B ? 1 = 1; B ? 0 = B; B & 1 = B; B & 0 = 0.
8. Законы склеивания:
9. Закон контрапозиции: (A ? B) = (B ? A).
Для логических переменных справедливы и общематематические законы. Для простоты записи приведем общематематические законы для трех логических переменных A, В и С:
1. Коммутативный закон: A & B = B & A; A ? B = B ? A.
2. Ассоциативный закон: A & (B & C) = (A & B) & C; A ? (B ? C) = (A ? B) ? C.
3. Дистрибутивный закон: A & (B ? C) = (A & B) ? (A & C).
Как уже отмечалось, с помощью законов алгебры логики можно производить равносильные преобразования логических выражений с целью их упрощения. В алгебре логики на основе принятого соглашения установлены следующие правила (приоритеты) для выполнения логических операций: первыми выполняются операции в скобках, затем в следующем порядке: инверсия (отрицание), конъюнкция ( & ), дизъюнкция (v), импликация (?), эквиваленция (?)
Выполним преобразование, например, логической функции
применив соответствующие законы алгебры логики.
comnew.ru
Все законы алгебры логики
§ 3. Законы алгебры логики
Итак, мы познакомились с понятием логического выражения и увидели, каким образом его строить по высказыванию на русском языке. Следующий шаг – изучение преобразований логических выражений.
Логические выражения, зависящие от одних и тех же логических переменных, называются равносильными, если на любом наборе значений переменных они принимают одинаковое значение (`0` или `1`). В дальнейшем для обозначения равносильности логических выражений мы будем использовать знак равенства.
это некоторые стандартные преобразования логических выражений, при которых сохраняется равносильность. Начнём с самых простых законов:
1) Законы поглощения констант
2) Законы поглощения переменных
3) Законы идемпотентности
4) Закон двойного отрицания
5) Закон противоречия
6) Закон исключённого третьего
Приведённые законы ещё называют аксиомами алгебры логики. Истинность этих и всех последующих законов легко можно установить, построив таблицу истинности для левого и правого логического выражения.
Переходим к группе законов, которые практически аналогичны законам алгебры чисел.
7) Законы коммутативности
Здесь стоит сделать замечание, что помимо конъюнкции и дизъюнкции свойством коммутативности также обладают эквивалентность и строгая дизъюнкция. Импликация – единственная из изучаемых операций, которая имеет два операнда и не обладает свойством коммутативности.
8) Законы ассоциативности
(x & y) & z = x & (y & z),
(x`vv`y) `vv` z = x `vv` (y `vv` z);
9) Законы дистрибутивности
Первый из законов дистрибутивности аналогичен закону дистрибутивности в алгебре чисел, если конъюнкцию считать умножением, а дизъюнкцию – сложением. Второй же закон дистрибутивности отличается от алгебры чисел, поэтому рекомендуется обратить на него особое внимание и в дальнейшем использовать при решении задач на упрощение выражений.
Кроме аксиом и алгебраических свойств операций ещё существуют особые законы алгебры логики.
10) Законы де Моргана
`bar(x & y)= barx vv bary` ,
11) Загоны поглощения (не путать с аксиомами поглощения переменных нулём или единицей)
Рассмотрим пример доказательства первого закона де Моргана при помощи построения таблицы истинности.
Так как результирующие столбцы совпали, то выражения, стоящие в левой и правой частях закона, равносильны.
В алгебре при решении задач на упрощение выражений большой популярностью пользовалась операция вынесения общего множителя за скобки. В алгебре логики эта операция также является легитимной, благодаря законам дистрибутивности и закону поглощения константы `1`. Продемонстрируем этот приём на простом примере: докажем первый закон поглощения, не используя таблицу истинности.
Наше начальное выражение: x `vv` (x & y) . Выносим x за скобки и получаем следующее выражение:
x &(1 `vv` y) . Используем закон поглощения переменной константой `1` и получаем следующее выражение: x & 1. И теперь используем закон поглощения константы и получаем просто x .
В заключение, следует сказать несколько слов об операции импликации. Как уже отмечалось выше, импликация не обладает свойством коммутативности. Её операнды неравноправны, поэтому каждый из них имеет уникальное название. Левый операнд импликации называется посылкой, а правый – следствием. Из таблицы истинности импликации следует, что она истинна, когда истинно следствие, либо ложна посылка. Единственный случай, когда импликация ложна – это случай истинной посылки и ложного следствия. Таким образом, мы подошли к последнему закону алгебры логики, который бывает полезен при упрощении выражений.
12) Закон преобразования импликации
Необходимо ещё отметить, что в сложных логических выражениях у операций есть порядок приоритетов.
3) Дизъюнкция, строгая дизъюнкция, эквивалентность
zftsh.online
Законы алгебры логики
Законы алгебры логики базируются на аксиомах и позволяют преобразовывать логические функции. Логические функции преобразуются с целью их упрощения, а это ведет к упрощению цифровой схемы.
АКСИОМЫ алгебры логики описывают действие логических функций «И» и «ИЛИ» и записываются следующими выражениями:
Всего имеется пять законов алгебры логики:
1. Закон одинарных элементов
1 * X = X
0 * X = 0
1 + X = 1
0 + X = X
Этот закон алгебры логики непосредственно следует из приведённых выше выражений аксиом алгебры логики.
Верхние два выражения могут быть полезны при построении коммутаторов, ведь подавая на один из входов элемента “2И” логический ноль или единицу можно либо пропускать сигнал на выход, либо формировать на выходе нулевой потенциал.
Второй вариант использования этих выражений заключается в возможности избирательного обнуления определённых разрядов многоразрядного числа. При поразрядном применении операции «И» можно либо оставлять прежнее значение разряда, либо обнулять его, подавая на соответствующие разряды единичный или нулевой потенциал. Например, требуется обнулить 6, 3 и 1 разряды. Тогда:
В приведённом примере использования законов алгебры логики отчётливо видно, что для обнуления необходимых разрядов в маске (нижнее число) на месте соответствующих разрядов записаны нули, в остальных разрядах записаны единицы. В исходном числе (верхнее число) на месте 6 и 1 разрядов находятся единицы. После выполнения операции «И» на этих местах появляются нули. На месте третьего разряда в исходном числе находится ноль. В результирующем числе на этом месте тоже присутствует ноль. Остальные разряды, как и требовалось по условию задачи, не изменены.
Точно так же при помощи закона одинарных элементов, одного из основных законов алгебры логики, можно записывать единицы в нужные нам разряды. В этом случае необходимо воспользоваться нижними двумя выражениями закона одинарных элементов. При поразрядном применении операции «ИЛИ» можно либо оставлять прежнее значение разряда, либо обнулять его, подавая на соответствующие разряды нулевой или единичный потенциал. Пусть требуется записать единицы в 7 и 6 биты числа. Тогда:
Здесь в маску (нижнее число) мы записали единицы в седьмой и шестой биты. Остальные биты содержат нули, и, следовательно, не могут изменить первоначальное состояние исходного числа, что мы и видим в результирующем числе под чертой.
Первое и последнее выражения закона одинарных элементов позволяют использовать логические элементы с большим количеством входов в качестве логических элементов с меньшим количеством входов. Для этого неиспользуемые входы в схеме «И» должны быть подключены к источнику питания, как это показано на рисунке 1:
Рисунок 1. Схема «2И-НЕ», реализованная на логическом элементе «3И-НЕ»
В то же самое время неиспользуемые входы в схеме «ИЛИ» в соответствии с законом одинарных элементов должны быть подключены к общему проводу схемы, как это показано на рисунке 2.
Рисунок 2. Схема «НЕ», реализованная на элементе «2И-НЕ»
Следующими законами алгебры логики, вытекающими из аксиом алгебры логики являются законы отрицания.
2. Законы отрицания
a. Закон дополнительных элементов
Выражения этого закона алгебры логики широко используется для минимизации логических схем. Если удаётся выделить из общего выражения логической функции такие подвыражения, то можно сократить необходимое количество входов элементов цифровой схемы, а иногда и вообще свести всё выражение к логической константе.
Еще одним широко используемым законом алгебры логики является закон двойного отрицания.
b. Двойное отрицание
Закон двойного отрицания используется как для упрощения логических выражений (и как следствие упрощения и удешевления цифровых комбинаторных схем), так и для устранения инверсии сигналов после таких логических элементов как «2И-НЕ» и «2ИЛИ-НЕ». В этом случае законы алгебры логики позволяют реализовывать заданные цифровые схемы при помощи ограниченного набора логических элементов.
c. Закон отрицательной логики
Закон отрицательной логики справедлив для любого числа переменных. Этот закон алгебры логики позволяет реализовывать логическую функцию «И» при помощи логических элементов «ИЛИ» и наоборот: реализовывать логическую функцию «ИЛИ» при помощи логических элементов «И». Это особенно полезно в ТТЛ схемотехнике, так как там легко реализовать логические элементы «И», но при этом достаточно сложно логические элементы «ИЛИ». Благодаря закону отрицательной логики можно реализовывать элементы «ИЛИ» на логических элементах «И». На рисунке 3 показана реализация логического элемента «2ИЛИ» на элементе «2И-НЕ» и двух инверторах.
Рисунок 3. Логический элемент «2ИЛИ», реализованный на элементе «2И-НЕ» и двух инверторах
То же самое можно сказать и о схеме монтажного «ИЛИ». В случае необходимости его можно превратить в монтажное «И», применив инверторы на входе и выходе этой схемы.
3. Комбинационные законы
Комбинационные законы алгебры логики во многом соответствуют комбинационным законам обычной алгебры, но есть и отличия.
a. закон тавтологии (многократное повторение)
Этот закон алгебры логики позволяет использовать логические элементы с большим количеством входов в качестве логических элементов с меньшим количеством входов. Например, можно реализовать двухвходовую схему «2И» на логическом элементе «3И», как это показано на рисунке 4:
Рисунок 4. Схема «2И-НЕ», реализованная на логическом элементе «3И-НЕ»
или использовать схему «2И-НЕ» в качестве обычного инвертора, как это показано на рисунке 5:
Рисунок 5. Схема «НЕ», реализованная на логическом элементе «2И-НЕ»
Однако следует предупредить, что объединение нескольких входов увеличивает входные токи логического элемента и его ёмкость, что увеличивает ток потребления предыдущих элементов и отрицательно сказывается на быстродействии цифровой схемы в целом.
Для уменьшения числа входов в логическом элементе лучше воспользоваться другим законом алгебры логики — законом одинарных элементов, как это было показано выше.
Продолжим рассмотрение законов алгебры логики:
b. закон переместительности
c. закон сочетательности
d. закон распределительности
4. Правило поглощения (одна переменная поглощает другие)
5. Правило склеивания (выполняется только по одной переменной)
Также как в обычной математике в алгебре логики имеется старшинство операций. При этом первым выполняется:
- Действие в скобках
- Операция с одним операндом (одноместная операция) — «НЕ»
- Конъюнкция — «И»
- Дизъюнкция — «ИЛИ»
- Сумма по модулю два.
Операции одного ранга выполняются слева направо в порядке написания логического выражения. Алгебра логики линейна и для неё справедлив принцип суперпозиции.
Вместе со статьей «Законы алгебры логики» читают:
Синтез комбинационных цифровых схем по произвольной таблице истинности Любая логическая схема без памяти полностью описывается таблицей истинности. Для реализации таблицы истинности достаточно рассмотреть только те строки.
http://digteh.ru/digital/SintSxem.php
Дешифраторы (декодеры) Декодеры (дешифраторы) позволяют преобразовывать одни виды бинарных кодов в другие. Например.
http://digteh.ru/digital/DC.php
Шифраторы (кодеры) Достаточно часто перед разработчиками цифровой аппаратуры встаёт обратная задача. Требуется преобразовать восьмиричный или десятичный линейный код в.
http://digteh.ru/digital/Coder.php
Мультиплексоры Мультиплексорами называются устройства, которые позволяют подключать несколько входов к одному выходу.
http://digteh.ru/digital/MS.php
Демультиплексоры Демультиплексорами называются устройства. Существенным отличием от мультиплексора является.
http://digteh.ru/digital/DMS.php
Автор Микушин А. В. All rights reserved. 2001 . 2017
digteh.ru
Основные законы алгебры логики
Для преобразования функций, упрощения формул, полученных при формализации условий логических задач, в алгебре логики производятся эквивалентные преобразования, опирающиеся на основные логические законы. Некоторые из этих законов формулируются и записываются так же, как аналогичные законы в арифметике и алгебре, другие выглядят непривычно.
Законы алгебры логики называют иногда теоремами.
В алгебре высказываний логические законы выражаются в виде равенства эквивалентных формул.
В справедливости всех законов можно убедиться, построив таблицы истинности для левой и правой частей записанного закона. После упрощения выражения с применением законов алгебры логики таблицы истинности совпадают.
Справедливость части законов можно доказать, применяя инструментарий таблиц истинности.
- Составим таблицу истинности для выражения
В первые два столбца таблицы запишем четыре возможных пары значений $x$ и $y$, в последующих столбцах — значения промежуточных выражений, а в последнем столбце — значение исходного выражения. В результате получим таблицу:
Упростим исходное выражение, используя основные законы алгебры логики:
(закон Де Моргана, распределительный закон для И, закон идемпотенции, операция переменной с её инверсией).
Из таблицы видно, что при всех наборах значений переменных $x$ и $y$ формула на рис.2 принимает значение $1$, то есть является тождественно истинной.
Составим таблицу истинности для выражения:
, которое содержит две переменные $x$ и $y$. В первые два столбца таблицы запишем четыре возможных пары значений $x$ и $y$, в последующих столбцах — значения промежуточных выражений, а в последнем столбце — значение исходного выражения. В результате получим таблицу:
Ничего непонятно?
Попробуй обратиться за помощью к преподавателям
Из таблицы видно, что Исходное выражение принимает такие же значения, что и Упрощенное выражение на соответствующих значениях переменных $x$ и $y$.
Упростим выражение на рис.5, применяя основные законы алгебры логики.
(закон Де Моргана, закон поглощения, распределительный закон для И).
-
Составим таблицу истинности для выражения
Из таблицы видно, что при всех наборах значений переменных $x$ и $y$ формула на рис.8 принимает значение $0$, то есть является тождественно ложной.
Упростим выражение, применяя законы алгебры логики:
(закон Де Могргана, распределительный).
Составим таблицу истинности для выражения на рис.11:
Из таблицы видно, что выражение на рис.11 в некоторых случаях принимает значение $1$, а в некоторых — $0$, то есть является выполнимым.
Лень читать?
Задай вопрос специалистам и получи
ответ уже через 15 минут!
(правило де Моргана, выносим за скобки общий множитель, правило операций переменной с её инверсией).
Упростить выражение используя законы алгебры логики:
(повторяется второй сомножитель, что возможно используя закон идемпотенции; затем комбинируются два первых и два последних сомножителя и используется закон склеивания).
(вводим вспомогательный логический сомножитель
spravochnick.ru