Полезные статьи

Законы моргана в логике

Законы де Моргана, их следствия и применение

Сами законы де Моргана

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

1) Отрицание высказывания «x и y» — то же самое, что высказывание «не x или не y», или, научным языком, «отрицание конъюнкции эквивалентно дизъюнкции отрицаний». Небольшой примерчик, чтобы было понятно. Скажем, кто-то сказал «неверно говорить, что Дуся умна и красива». Для простоты разделим девушек на красивых и страшных))) Первая мысль, которая может прийти в голову «так Дуся тупа и страшна?». Согласно закону де Моргана правильно рассуждать «Дуся не умна или некрасива», или «она тупа или страшна». То есть возможно, что она ТОЛЬКО тупа или ТОЛЬКО страшна, а не одновременно. Но — заметим — не исключено, что одновременно)))

2) Отрицание высказывания «x или y» — то же самое, что высказывание «не x и не y», или: «отрицание дизъюнкции есть конъюнкция отрицаний». Скажем, если «неверно говорить, что Вася знает китайский или грузинский», то можно также сказать «правда в том, что Вася не знает китайский и грузинский тоже не знает». Или другой пример: «неверно, что Дуся умна или красива», тогда вполне можно сказать «Дуся тупа и страшна», хотя это будет неполиткорректно.

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

Следствия законов де Моргана

Как и у любого нормального закона, из законов де Моргана можно вывести некоторые интересные вещи.

Собственно напрашиваются в голову вот какие тождества:

Пример к первому: «неверно утверждать, что Джон — не курильщик и не алкаш» — это одно и то же, что «Джон — курильщик или алкаш» (именно ИЛИ, то есть может быть он одновременно и тот, и другой, а может, страдает только одной вредной привычкой).

Теперь к другому следствию законов де Моргана: «неверно утверждать, что Джон — не курильщик или не алкаш», это же можно высказать как «Джон курит и бухает».

Поюморили и хватит) Теперь более серьёзные вещи. Часто утверждается, что любые сложные (не атомарные) логические высказывания можно выразить с помощью лишь трёх операций — И (конъюнкция), ИЛИ (дизъюнкция), НЕ (отрицание), выбросив операции следствия, эквиваленции и «исключающего или». Правда, иногда такие выражения будут громоздки. Математики — не дураки, если бы был смысл, они бы с удовольствием выбросили 3 лишних операции))) «Не множить сущности без необходимости», как призывал английский философ У. Оккам.

Законы де Моргана позволяют выполнить ещё более изощрённую вещь: с помощью законов де Моргана вместо 6 основных логических операций можно использовать не 3, а только 2. На выбор: можно И + НЕ, а можно ИЛИ + НЕ. Алгоритм простой: 1) избавляемся от импликаций, эквиваленций и «исключающих или»; 2) далее избавляется от И или ИЛИ (ну смотря какую операцию мы выбрали «на вылет»).

Допустим, «z и (x => y)» = «z и (не x или y)» = «z и x и (не y)». Сначала избавились от следствия, затем от ИЛИ.

Зачем нужны законы де Моргана?

1. Как и знание логики вообще, это удобная штука для полемики и демагогии — народ часто путается в логических вещах. Скажем, Иванов говорит Петрову: «Вы говорите, что предлагаемая стратегия неэффективная и дорогостоящая. Но вы неправы!» Петров: «Но как вы можете утверждать, будто она дешёвая и эффективная?». [Попался. ))) Надо бы подружиться с логикой)))] Иванов: «А я этого и не говорил! Вы сейчас приписываете мне несколько другие мысли. «

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

3. Чтобы сдать экзамен по мат. логике, если кому-то из читателей его придётся сдавать.

crypto.hut2.ru

Законы моргана в логике

Тема 3. Основы математической логики 1. Логические выражения и логические операции.
2. Построение таблиц истинности и логических функций.
3. Законы логики и преобразование логических выражений.
Лабораторная работа № 3. Основы математической логики.

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

Закон двойного отрицания (двойное отрицание исключает отрицание):

А = .

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

    для логического сложения: А Ú B = B Ú A;

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

      для логического сложения: (А Ú B) Ú C = A Ú (B Ú C);

      для логического умножения:(A & B) & C = A & (B & C).

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

      для логического умножения:(A & B) Ú C = (A Ú C) & (B Ú C).

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

      Закон общей инверсии (законы де Моргана):

        для логического сложения: = & ;

        для логического умножения: = Ú
        Закон идемпотентности (от латинских слов idem — тот же самый и potens — сильный; дословно — равносильный):

        для логического сложения: А Ú A = A;

        для логического умножения:A & A = A.

        Закон означает отсутствие показателей степени.

        для логического умножения:A & 1 = A, A & 0 = 0.

        A & = 0.

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

        A Ú = 1.

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

        для логического умножения:A & (A Ú B) = A.

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

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

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

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

      • Аналогично предыдущему пункту вынесем за скобки высказывание А.
        A Ú B & A Ú B & C = A & (1 Ú B) Ú B & C = A Ú B & C.
      • Таким образом, мы доказали закон дистрибутивности.

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

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

        Решение:

        umk.portal.kemsu.ru

        закон де моргана

        Словарь по логике. — М.: Туманит, изд. центр ВЛАДОС . А.А.Ивин, А.Л.Никифоров . 1997 .

        Смотреть что такое «закон де моргана» в других словарях:

        закон де Моргана — De Morgano dėsnis statusas T sritis automatika atitikmenys: angl. law of De Morgan vok. De Morgansches Gesetz, n rus. закон де Моргана, m pranc. loi De Morgan, f ryšiai: sinonimas – Morgano dėsnis … Automatikos terminų žodynas

        закон экономии (канон Ллойд-Моргана) — закон зоопсихологиии, сформулированный Ллойд Морганом в 1894 г., суть которого заключается в следующем: нельзя объяснить поведение животного, исходя из более высокой психической способности, если оно может быть объяснено ниже стоящей в… … Энциклопедический словарь по психологии и педагогике

        закон моргана — ЭМБРИОЛОГИЯ ЖИВОТНЫХ ЗАКОН МОРГАНА – Гены одной хромосомы образуют группу сцепления и наследуются сцепленно. Сила сцепления обратно пропорциональна расстоянию между генами и нарушается при кроссинговере … Общая эмбриология: Терминологический словарь

        ЛОГИЧЕСКИЙ ЗАКОН — или Закон логики, выражение, содержащее только логические константы и переменные и являющееся истинным в любой (непустой) предметной области. Примерами Л.з. могут служить закон противоречия, закон исключенного третьего, закон де Моргана, закон… … Философская энциклопедия

        логический закон — выражение, содержащее только логические константы и переменные и явля ющееся истинным в любой (непустой) предметной области. Примером Л. з. может служить любой закон логики высказываний (скажем, непротиворечия закон, закон исключенного третьего,… … Словарь терминов логики

        Правила де Моргана — Законы де Моргана (правила де Моргана) логические правила, связывающие пары дуальных логических операторов при помощи логического отрицания. Определение Огастес де Морган первоначально заметил, что в классической пропозициональной логике… … Википедия

        Законы де Моргана — (правила де Моргана) логические правила, связывающие пары дуальных логических операторов при помощи логического отрицания. Открыты шотландским математиком Огастесом де Морганом Определение Огастес де Морган первоначально заметил, что в… … Википедия

        ЗАКОНЫ ДЕ МОРГАНА — законы логики высказываний, связывающие отрицание с операциями конъюнкции и дизъюнкции, соответствующими логич. союзам и и неразделительному или естеств. языка. З. де М. в словесной формулировке были известны еще схоластич. логикам. В математич.… … Философская энциклопедия

        Дизъюнктивная нормальная форма — (ДНФ) в булевой логике нормальная форма, в которой булева формула имеет вид дизъюнкции конъюнкций литералов. Любая булева формула может быть приведена к ДНФ.[1] Для этого можно использовать закон двойного отрицания, закон де Моргана, закон… … Википедия

        Конъюнктивная нормальная форма — (КНФ) в булевой логике нормальная форма, в которой булева формула имеет вид конъюнкции дизъюнкций литералов. Конъюнктивная нормальная форма удобна для автоматического доказательства теорем. Любая булева формула может быть приведена к… … Википедия

        dic.academic.ru

        МИР ЛОГИКИ

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

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

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

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

        Закон

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

        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

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

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

        1. Законы выражения одних логических союзов через другие:

        а) закон удаления знака импликации:

        p®q = Úq (1)

        б) законы удаления знака эквиваленции:

        p«q = (pÙq)Ú ( Ù ) (3)

        p«q= (pÚ )Ù ( Úq) (4)

        в) законы удаления знака строгой дизъюнкции:

        pÚq = (pÙ )Ú( Ùq) (5)

        pÚq = (pÚq)Ù( Ú ) (6)

        г) закон выражения эквиваленции через строгую дизъюнкцию:

        p«q = (7)

        д) закон выражения строгой дизъюнкции через эквиваленцию:

        pÚq = (8)

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

        = Л (9)

        Высказывание p и его отрицание одновременно никогда не выполняются. Нельзя что-то утверждать и отвергать одновременно.

        Например, высказывания «У Земли есть спутник» и «У Земли нет спутника» не могут одновременно быть истинными.

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

        = И (10)

        Хотя бы одно из высказываний p или всегда истинно; третьего не дано.

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

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

        Конъюнктивное присоединение логической константы И (тождественно-истинного высказывания) к нейтральному высказыванию p ничего не меняет; дизъюнктивное присоединение константы Л (тождественно-ложного высказывания) к нейтральному высказыванию p также ничего не меняет.

        5. Законы исключения логических переменных:

        Дизъюнктивное присоединение константы И делает всю дизъюнкцию истинной; конъюнктивное присоединение константы Л делает всю конъюнкцию ложной.

        6. Законы идемпотентности:

        Конъюнкция (дизъюнкция) высказывания с самим собой дает то же самое высказывание.

        Законы идемпотентности свидетельствуют об отсутствии в логике высказываний показателей степеней (15) и коэффициентов (16).

        7. Законы коммутативности (перестановки):

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

        Например, высказывание “Я учусь в институте и (или) занимаюсь спортом” равносильно высказыванию “Я занимаюсь спортом и (или) учусь в институте”.

        8. Законы ассоциативности (группировки):

        pÙ(qÙr) = (pÙq)Ùr = pÙqÙr (19)

        pÚ(qÚr) = (pÚq)Úr = pÚqÚr (20)

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

        9. Законы дистрибутивности (распределения):

        pÙ(qÚr) = (pÙq)Ú(pÙr) (21)

        pÚ(qÙr) = (pÚq)Ù(pÚr) (22)

        Закон (21) можно проиллюстрировать такой парой равносильных высказываний. Левая часть: “Я учусь в институте, и в тоже время занимаюсь спортом или играю в любительском театре ”. Правая часть: “Я учусь в институте и занимаюсь спортом, или я учусь в институте и играю в любительском театре”. Этот закон говорит о том, что в алгебре высказываний можно открывать скобки так же как и в обычной алгебре (сравните: а(в+с) = ав + ас).

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

        pÙ( Úq) = pÙq (25)

        pÚ( Ùq) = pÚq (26)

        Ù(pÚq) = Ùq (27)

        Ú(pÙq) = Úq (28)

        Высказывания q (23) (24), (25) (26), р (27) (28) как бы поглощаются в данных случаях. Это позволяет упрощать логические формулы и соответствующие высказывания.

        Например, высказывание “Я учусь в институте, и я учусь в институте или работаю на заводе” равносильно высказыванию “Я учусь в институте”.

        11. Законы операции отрицания:

        а) законы отрицания логических констант:

        И = Л (29)

        Л = И (30)

        б) закон двойного отрицания:

        = p (31)

        Отрицание отрицания какого-либо высказывания равносильно первоначальному высказыванию.

        Например, если высказывание “Сегодня состоится матч” (p) последовательно дважды отрицать “Сегодня не состоится матч” ( ), “Неверно, что сегодня не состоится матч” ( ), то мы возвратимся к исходному высказыванию “Сегодня состоится матч”.

        в) законы де Моргана:

        pÙq = Ú (32)

        = Ù (33)

        Отрицание конъюнкции равносильно дизъюнкции отрицаний (32) и отрицание дизъюнкции равносильно конъюнкции отрицаний (33).

        Например, высказывание “Неверно, что я учусь в институте и занимаюсь спортом” равносильно высказыванию “Я не учусь в институте, или я не занимаюсь спортом” (первый закон де Моргана); высказывание “Неверно, что я учусь в институте или занимаюсь спортом” равносильно высказыванию “Я не учусь в институте и не занимаюсь спортом” (второй закон де Моргана).

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

        znatock.org