Тождества и законы алгебры логики

Тождества и законы алгебры логики

И

F7(x) (дизъюнкция илилогическое сложение),

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

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

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

Функция исключающее ИЛИ обозначается символом .

Ниже приведены таблицы истинности для этих четырех функций.

Инверсия
Конъюнкция Дизъюнкция Исключающее ИЛИ

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

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

сначала выполняется инверсия,

затем конъюнкция

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

Для изменения указанного порядка используют скобки.

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

Базируется алгебра логики на отношенииэквивалентности и трех упомянутых ранее операциях:

дизъюнкции (синонимы — логическое сложение, операция ИЛИ),

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

и отрицании (инверсия, операция НЕ).

Отношение эквивалентности обозначается знаком =.

Дизъюнкция обозначается знаком , а иногда символом + .

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

Отрицание обозначается чертой над переменной

Алгебра логики определяется следующей системойаксиом

Если в аксиомах произвести взаимную замену операций дизъюнкции и конъюнкции, а также элементов 0 и 1, то из одной аксиомы данной пары получается другая.

Это свойство называетсяпринципом двойственности .

С помощью аксиом можно получить рядтождеств:

Перечислимзаконы алгебры логики:

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

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

= распределительный(или дистрибутивный)

= законы двойственности(или де Моргана)

Дата добавления: 2014-01-06 ; Просмотров: 276 ; Нарушение авторских прав?

Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет

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

Читайте также:  Сменить формат файла pdf на jpg

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

Аксиома (1) является утверждением того, что в алгебре логики рассматриваются только двоичные переменные, аксиомы (2)…(5) определяют операции дизъюнкции и конъюнкции, а аксиома (5) — операцию отрицания. Если в аксиомах (2)…(5), заданных парами, произвести взаимную замену операций дизъюнкции и конъюнкции, а также элементов 0 и 1, то из одной аксиомы пары получится другая. Это свойство называется принципом двойственности.

С помощью аксиом алгебры логики можно доказать целый ряд теорем и тождеств. Одним из эффективных методов доказательства теорем является метод перебора всех значений переменных: если теорема истинна, то с учетом (2)…(5) уравнение, формулирующее утверждение теоремы, должно быть истинно при подстановке любых значений переменных в обе его части.

Метод перебора не слишком трудоемок, так как переменные могут иметь только два значения: 0 и 1.

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

Идемпотентные законы (законы тождества):

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

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

Законы двойственности (Теоремы де Моргана):

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

Законы поглощения (абсорбция):

Операции обобщенного склеивания:

Теоремы (6)…(13) и (15)…(18) записаны парами, причем каждая из теорем пары двойственна другой, так как из одной теоремы пары можно получить другую на основании принципа двойственности, то есть путем взаимной замены операций дизъюнкции и конъюнкции, а также элементов 0 и 1, если они имеются. Теорема (14) самодвойственна, так как она не изменяется по принципу двойственности (отсутствуют элементы 0 и 1 и операции дизъюнкции и конъюнкции). Все теоремы могут быть доказаны аналитически или методом перебора. В качестве примера приведем доказательство тождества (13) методом перебора (табл. 1).

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

Читайте также:  Фильм с трагическим концом

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

Но скобки нельзя опустить в выражении , поскольку

Некоторые теоремы и тождества алгебры логики имеют особое значение, так как позволяют упрощать логические выражения. Например, в соотношениях (6), (10)…(12) и (15)…(18) правая часть проще левой, поэтому, произведя в логических выражениях соответствующие преобразования, можно добиться существенного их упрощения. С этой целью особенно часто используются тождества (15)…(18).

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

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

Законы алгебры логики и правила преобразования логических выражений

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

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

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

Читайте также:  Монитор com порта windows 10

Закон

Формулировка

1. Закон тождества

Всякое высказывание тождественно самому себе.

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

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

3. Закон непротиворечия

Высказывание не может быть одновременно истинным и ложным. Если высказывание Х истинно, то его отрицание НЕ Х должно быть ложным. Следовательно, логическое произведение высказывания и его отрицания должно быть ложно.

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

Если дважды отрицать некоторое высказывание, то в результате получим исходное высказывание.

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

Результат операции над высказываниями не зависит от того, в каком порядке берутся эти высказывания.

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

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

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

(X / Y) / Z= (X / Z) / (Y / Z)

(X / Y) / Z = (X / Z) / (Y / Z)

Определяет правило выноса общего высказывания за скобку.

7. Закон общей инверсии Закон де Моргана

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

8. Закон равносильности (идемпотентности)

от латинских слов idem — тот же самый и potens —сильный

9. Законы исключения констант:

10. Закон поглощения:

11. Закон исключения (склеивания):

12. Закон контрапозиции

14. А В = (А / В) / (¬A / ¬B);

15. А В = (¬A / В) / (А /¬B).

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

1) (A/B) / (A/¬B) = A / (B / B)= A / 1 = A

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

¬ (X / Y) / (X / ¬Y) = ¬ X / ¬Y / (X / ¬Y) = ¬ X / X/¬Y /¬Y= 0 ¬Y /¬Y

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

4) ¬ X / Y / ¬ (X / Y) / X = ¬ X / Y / ¬ X / ¬Y / X= ¬ X / (Y / ¬Y) / X= ¬ X / X= 1

Ссылка на основную публикацию
Adblock detector