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

admin

История науки и техники 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

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


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

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

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

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

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

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

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


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

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

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

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

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

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

beam-robot.ru

Законы логики на уроках информатики и ИКТ

Урок по информатике рассчитан на учащихся 10-х классов общеобразовательной школы, в учебном плане которой входит раздел «Алгебра логики». Учащимся очень нелегко дается эта тема, поэтому мне, как учителю, захотелось заинтересовать их в изучении законов логики, упрощении логических выражений и с интересом подойти к решению логических задач. В обычной форме давать уроки по этой теме нудно и хлопотно, да и ребятам не всегда понятны некоторые определения. В связи с предоставлением информационного пространства, у меня появилась возможность выкладывать свои уроки в оболочке «learning». Учащиеся, зарегистрировавшись в ней, могут в свое свободное время посещать этот курс и перечитывать то, что было непонятно на уроке. Некоторые учащиеся, пропустив уроки по болезни, наверстывают дома или в школе пропущенную тему и всегда готовы к следующему уроку. Такая форма преподавания очень устроила многих ребят и те законы, которые им были непонятны, теперь в компьютерном виде ими усваиваются гораздо легче и быстрее. Предлагаю один из таких уроков информатики, который проводится интегративно с ИКТ.

  • Объяснение нового материала, с привлечением компьютера – 25 минут.
  • Основные понятия и определения, выложенные в «learning» — 10 минут.
  • Материал для любознательных – 5 минут.
  • Домашнее задание – 5 минут.
  • 1. Объяснение нового материала

    Законы формальной логики

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

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

    Закон тождества: в процессе определенного рассуждения всякое понятие и суждение должны быть тождественны самим себе.

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

    Закон исключенного третьего: из двух противоречащих суждений одно истинно, другое ложно, а третьего не дано.

    Закон достаточного основания: всякая истинная мысль должна быть достаточно обоснована.

    Последний закон говорит о том, что доказательство чего-либо предполагает обоснование именно и только истинных мыслей. Ложные же мысли доказать нельзя. Есть хорошая латинская пословица: «Ошибаться свойственно всякому человеку, но настаивать на ошибке свойственно только глупцу». Формулы этого закона нет, так как он имеет только содержательный характер. В качестве аргументов для подтверждения истинной мысли могут быть использованы истинные суждения, фактический материал, статистические данные, законы науки, аксиомы, доказанные теоремы.

    Законы алгебры высказываний

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

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

    Законы алгебры высказываний (алгебры логики) — это тавтологии.

    Иногда эти законы называются теоремами.

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

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

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

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

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

    В рассуждении: Движение вечно. Хождение в школу — движение. Следовательно, хождение в школу вечно слово «движение» используется в двух разных смыслах (первое — в философском смысле — как атрибут материи, второе — в обыденном смысле — как действие по перемещению в пространстве), что приводит к ложному выводу.

    Не могут быть одновременно истинными суждение и его отрицание. То есть если высказывание А — истинно, то его отрицание не А должно быть ложным (и наоборот). Тогда их произведение будет всегда ложным.

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

    Иногда этот закон формулируется так: два противоречащих друг другу высказывания не могут быть одновременно истинными. Примеры невыполнения закона непротиворечия:

    1. На Марсе есть жизнь и на Марсе жизни нет.

    2. Оля окончила среднюю школу и учится в X классе.

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

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

    1. Число 12345 либо четное, либо нечетное, третьего не дано.

    2. Предприятие работает убыточно или безубыточно.

    3. Эта жидкость является или не является кислотой.

    Закон исключенного третьего не является законом, признаваемым всеми логиками в качестве универсального закона логики. Этот закон применяется там, где познание имеет дело с жесткой ситуацией: «либо — либо», «истина—ложь». Там же, где встречается неопределенность (например, в рассуждениях о будущем), закон исключенного третьего часто не может быть применен.

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

    Парадокс (греч. paradoxos — неожиданный, странный) в этом примере возникает из-за того, что предложение ссылается само на себя. Другим известным парадоксом является задача о парикмахере: В одном городе парикмахер стрижет волосы всем жителям, кроме тех, кто стрижет себя сам. Кто стрижет волосы парикмахеру? В логике из-за ее формальности нет возможности получить форму такого ссылающегося самого на себя высказывания. Это еще раз подтверждает мысль о том, что с помощью алгебры логики нельзя выразить все возможные мысли и доводы. Покажем, как на основании определения эквивалентности высказываний могут быть получены остальные законы алгебры высказываний.

    Например, определим, чему эквивалентно (равносильно) А (двойное отрицание А, т. е. отрицание отрицания А). Для этого построим таблицу истинности:

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

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

    Если отрицать дважды некоторое высказывание, то в результате получается исходное высказывание. Например, высказывание А = Матроскинкот эквивалентно высказыванию А = Неверно, что Матроскин не кот.

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

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

    Операнды А и В в операциях дизъюнкции и конъюнкции можно менять местами.

    A v(B v C) = (A v B) v C;

    А & (В & C) = (A & В) & С.

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

    A v (B & C) = (A v B) &(A v C)

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

    А & (B v C) = (A & B) v (А & C)

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

    Закон дистрибутивности конъюнкции относительно дизъюнкции ана­логичен дистрибутивному закону в алгебре, а закон дистрибутивности дизъюнкции относительно конъюнкции аналога не имеет, он справедлив только в логике. Поэтому необходимо его доказать. Доказательство удобнее всего провести с помощью таблицы истинности:

    Проведите доказательство законов поглощения самостоятельно.

    Словесные формулировки законов де Моргана:

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

    Примеры выполнения закона де Моргана:

    1) Высказывание Неверно, что я знаю арабский или китайский язык тождественно высказыванию Я не знаю арабского языка и не знаю китайского языка.

    2) Высказывание Неверно, что я выучил урок и получил по нему двойку тождественно высказыванию Или я не выучил урок, или я не получил по нему двойку.

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

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

    Так, заменить операцию импликации можно в соответствии со следующим правилом:

    Для замены операции эквивалентности существует два правила:

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

    Знание правил замены операций импликации и эквивалентности помогает, например, правильно построить отрицание импликации.

    Рассмотрим следующий пример.

    Пусть дано высказывание:

    Е = Неверно, что если я выиграю конкурс, то получу приз.

    Пусть А = Я выиграю конкурс,

    В = Я получу приз.

    Отсюда, Е = Я выиграю конкурс, но приз не получу.

    Интерес представляют и следующие правила:

    Доказать их справедливость можно также с помощью таблиц истинности.

    Интересно их выражение на естественном языке.

    Если Винни-Пух съел мед, то он сыт

    Если Винни-Пух не сыт, то меда он не ел.

    Задание: придумайте фразы-примеры на данные правила.

    2. Основные понятия и определения в Приложении 1

    3. Материал для любознательных в Приложении 2

    4. Домашнее задание

    1) Выучить законы логики, используя курс «Алгебры логики», размещенный в информационном пространстве (www.learning.9151394.ru).

    2) Проверить на ПК доказательство законов де Моргана, построив таблицу истинности.

    1. Основные понятия и определения (Приложение 1).
    2. Материал для любознательных (Приложение 2).

    xn--i1abbnckbmcl9fb.xn--p1ai

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

    § 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

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

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

    Законы алгебры логики называют иногда теоремами.

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

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

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

    • Составим таблицу истинности для выражения
    • В первые два столбца таблицы запишем четыре возможных пары значений $x$ и $y$, в последующих столбцах — значения промежуточных выражений, а в последнем столбце — значение исходного выражения. В результате получим таблицу:

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

    (закон Де Моргана, распределительный закон для И, закон идемпотенции, операция переменной с её инверсией).

    Из таблицы видно, что при всех наборах значений переменных $x$ и $y$ формула на рис.2 принимает значение $1$, то есть является тождественно истинной.

    Составим таблицу истинности для выражения:

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

    Ничего непонятно?

    Попробуй обратиться за помощью к преподавателям

    Из таблицы видно, что Исходное выражение принимает такие же значения, что и Упрощенное выражение на соответствующих значениях переменных $x$ и $y$.

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

    (закон Де Моргана, закон поглощения, распределительный закон для И).

      Составим таблицу истинности для выражения

    Из таблицы видно, что при всех наборах значений переменных $x$ и $y$ формула на рис.8 принимает значение $0$, то есть является тождественно ложной.

    Упростим выражение, применяя законы алгебры логики:

    (закон Де Могргана, распределительный).

    Составим таблицу истинности для выражения на рис.11:

    Из таблицы видно, что выражение на рис.11 в некоторых случаях принимает значение $1$, а в некоторых — $0$, то есть является выполнимым.

    Лень читать?

    Задай вопрос специалистам и получи
    ответ уже через 15 минут!

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

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

    Упростить выражение используя законы алгебры логики:

    (вводим вспомогательный логический сомножитель

    spravochnick.ru

    Это интересно:

    • Восстановить коллектор Выпускной коллектор Мерседес Выпускной коллектор – одна из наиболее надёжных и прочных элементов выхлопной системы. И это несмотря на то, что он принимает на себя основные выхлопные газы. Потому бывает, что в результате постоянного сильного воздействия температуры, давления и вибраций […]
    • Коллегия адвокатов 1 челябинск Список коллегий 1. ФИЛИАЛ № 1 г. ЧЕЛЯБИНСК Адрес: 454091 Челябинск ул. Пушкина 73-7 Телефон: т. 65-76-62 2. КОЛЛЕГИЯ АДВОКАТОВ № 1 г. ЧЕЛЯБИНСКА Адрес: 454080 Челябинск ул. Володарского 32 Телефон: 265-31-71 265-31-27 3. ФИЛИАЛ № 2 г. ЧЕЛЯБИНСК Адрес: 454007 Челябинск пр-т Ленина […]
    • Оформить займ у частного лица без предоплаты Взять займ у частного лица под расписку срочно в москве без предоплаты Сыктывкар, Ставрополь, Калининград, Смоленск, Астрахань, Березники, Калуга, Томск, Камышин, Курган, Чита, Белогорск, Магадан, Петропавловск-Камчатский, Красноярск, Южно-Сахалинск, Великий Новгород, Новосибирск, […]
    • Пребывание значительной части народа вне страны своего происхождения Пребывание значительной части народа вне страны своего происхождения Тема 1: Политическая карта мира. Историко – географические регионы. Вариант 1 1. Наука о территориальной дифференциации политических явлений и процессов: A) Социальная география. B) Политическая география. C) […]
    • Найти определитель по правилу треугольника Найти определитель по правилу треугольника Определитель(он же determinant(детерминант)) находится только у квадратных матриц. Определитель есть ничто иное, как значение сочетающее в себе все элементы матрицы, сохранающееся при транспонировании строк или столбцов. Обозначаться он может […]
    • Опека фрунзенского района минска Опека фрунзенского района минска По адресу: г. Минск, ул.Притыцкого, 78 осуществляется набор на дневные, вечерние и группы выходного дня по подготовке водителей категорий «А» и «В» . Наши контакты: +375(17) 244 17 71 - Учебная часть (запись на обучение) +375(17)236 28 98 - Зам. […]
    • Конвенция о внешнеторговом арбитраже Конвенция о внешнеторговом арбитраже ДОЛЖНЫМ ОБРАЗОМ уполномоченные, СОБРАВШИСЬ под эгидой Европейской Экономической Комиссии Организации Объединенных Наций, КОНСТАТИРУЯ, что 10 июня 1958 г. на Конференции Организации Объединенных Наций по международному торговому арбитражу была […]
    • Приказы мз в 1999 году Основные Приказы по фармацевтической деятельности (последнее обновление 15.9.2017) Данный сборник Приказов по фармацевтической деятельности был подготовлен сайтом citofarm a .ru. Все приказы можно скачать с нашего сайта не только по отдельности но и целым архивом. Приказы для удобства […]