Законы поглощения алгебры логики

Законы поглощения алгебры логики

Законы алгебры логики

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

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

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

Правила операций с константами

Законы инверсии (отрицания)

Снятие двойного отрицания

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


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

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

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

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

В скором времени материалы появятся.

Свободный монтаж в BEAM-робототехнике
Один из наиболее распространенных способов монтажа при создании BEAM-роботов.

beam-robot.ru

Урок Законы алгебры логики

  • научиться применять законы алгебры логики для упрощения выражений;
  • развивать логическое мышлении;
  • прививать внимательность

Опрос законов алгебры логики ( на доске).

Перечислим наиболее важные из них:

  • X X Закон тождества.
  • Закон противоречия
  • Закон исключенного третьего
  • Закон двойного отрицания
  • Законы идемпотентности: X X X, X X C
  • Законы коммутативности (переместительности): X Y Y X, X Y Y X
  • Законы ассоциативности (сочетательности): (X Y) Z X (Y Z), (X Y) Z X (Y Z)
  • Законы дистрибутивности (распределительности): X (Y Z) (X Y) (X Z), X (Y Z) (X Y) (X Z)
  • Законы де Моргана ,
  • X 1 X, X 0 X
  • X 0 0, X 1 1
  • 1-й закон сформулирован древнегреческим философом Аристотелем. Закон тождества утверждает, что мысль, заключенная в некотором высказывании, остается неизменной на протяжении всего рассуждения, в котором это высказывание фигурирует.

    Закон противоречия говорит о том, что никакое предложение не может быть истинно одновременно со своим отрицанием. “Это яблоко спелое” и “Это яблоко не спелое”.

    Закон исключенного третьего говорит о том, что для каждого высказывания имеются лишь две возможности: это высказывание либо истинно либо ложно. Третьего не дано. “Сегодня я получу 5 либо не получу”. Истинно либо суждение, либо его отрицание.

    Закон двойного отрицания. Отрицать отрицание какого-нибудь высказывания — то же, что утверждать это высказывание.

    “ Неверно, что 2*2<>4”

    Законы идемпотентности. В алгебре логики нет показателей степеней и коэффициентов. Конъюнкция одинаковых “сомножителей” равносильна одному из них.

    Законы коммутативности и ассоциативности. Конъюнкция и дизъюнкция аналогичны одноименным знакам умножения и сложения чисел.

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

    Смысл законов де Моргана (Август де Морган (1806-1871) — шотландский математик и логик) можно выразить в кратких словесных формулировках:

    Читайте так же:  Удо фойгт

    — отрицание логического произведения эквивалентно логической сумме отрицаний множителей.

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

    1. Установить эквивалентны ли высказывания.

    3. С помощью таблиц истинности доказать законы поглощения и склеивания.

    I. Подача нового материала.

  • Законы поглощения: X (X Y) X, X (X Y) X
  • Законы склеивания: (X Y) ( Y) Y, (X Y) ( Y) Y
  • Доказать законы логики можно:

    1. с помощью таблиц истинности;
    2. с помощью равносильностей.
    3. Докажем законы склеивания и поглощения с помощью равносильностей:

      1. (X Y) ( Y) (X+Y) *( +Y) X* + Y* + Y*Y+ X*Y Y* + Y + X*Y Y* + Y(1+X) Y* +Y Y( +1) Y склеивания
      2. X (X Y) X*X+X*Y X+X*Y X(1+Y) X поглощения
      3. П. Практическая часть

        1. Упрощение формул.

        Пример 1. Упростить формулу (А+В)·* (А+С)

      4. Раскроем скобки ( A + B ) * ( A + C ) A * A + A * C + B * A + B * C
      5. По закону идемпотентности A*A A , следовательно , A*A + A*C + B*A + B*C A + A*C + B*A + B*C
      6. В высказываниях А и А*C вынесем за скобки А и используя свойство А+1 1, получим А+А*С+ B*A + B*C A*( 1 + С) + B*A + B*СA + B*A + B*С
      7. Аналогично пункту 3. вынесем за скобки высказывание А.
        A + B*A + B*С A ( 1 + B ) + B С A + B*С
        Таким образом, мы доказали закон дистрибутивности.

      2. Преобразования “поглощение” и “склеивание”

      Пример 2. Упростить выражение А+ A*B

      Решение. A+A*B A ( 1 + B ) A — поглощение

      Пример 3. Упростить выражение A*B+A*

      Решение . A*B + A* A ( B + ) A — склеивание

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

      Пример 4. Преобразовать формулу так, чтобы не было отрицаний сложных высказываний.

    4. Воспользуемся формулой де Моргана, получим:
    5. Для выражения применим еще раз формулу де Моргана, получим:
    6. 4. Любую формулу можно тождественно преобразовать так, что в ней не будут использованы:

    7. знаки логического сложения;
    8. знаки логического умножения,
    9. будут использованы:
    10. знаки отрицания и логического умножения
    11. знаки отрицания и логического сложения.
    12. Пример 5. Преобразовать формулу так, чтобы в ней не использовались знаки логического сложения.

      Решение. Воспользуемся законом двойного отрицания, а затем формулой де Моргана.

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

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

      Задание 1. Установить истинность высказывания .
      Задание 2 Установить является ли высказывание тавтологией?
      Задание 3. Установить эквивалентны ли высказывания.

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

      ;

      ;

      .

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

      ;

      ;

      .

      ;

      .

      lunina.21205s09.edusite.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. Закон тождества

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

      mir-logiki.ru

      Читайте так же:  Приказ на зам директора право подписи

    Обсуждение закрыто.