Закон де моргана для операции или и операции и

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

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

В данной простой статейке рассмотрим такую популярную штуку из математической логики, как законы де Моргана, названные в честь английского логика 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

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

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

  1. Объяснение нового материала, с привлечением компьютера – 25 минут.
  2. Основные понятия и определения, выложенные в «learning» — 10 минут.
  3. Материал для любознательных – 5 минут.
  4. Домашнее задание – 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) Проверить на ПК доказательство законов де Моргана, построив таблицу истинности.

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

xn--i1abbnckbmcl9fb.xn--p1ai

Операции над множествами. Законы де Моргана

Дата добавления: 2015-07-23 ; просмотров: 2090 ; Нарушение авторских прав

Объединением двух множеств А и В называется множество вида:

Пересечением двух множеств А и В называется множество вида:

Если множества А и В не имеют общих элементов, то AÇB=Æ.

Свойства операций объединения и пересечения

Свойство 2 позволяет записывать без скобок объединение и пересечение любого количества множеств:

=A1È A2È. È Ak=<a/ aÎA1 или aÎA2 или . или aÎ Ak>,

=A1Ç A2Ç. Ç Ak=<a/ aÎA1 и aÎA2 и . и aÎ Ak>.

Объединение и пересечение связаны законами дистрибутивности:

Докажем первый из них (второй доказывается аналогично).

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

Для операции объединения множеств нейтральным является пустое множество Æ, а для операции пересечения множеств — универсальное множество U.

Таким образом, покрытие является разбиением, если его блоки не пусты и попарно не пересекаются.

Из определения разбиения следует, что порядок записи блоков, в силу коммутативности объединения, может быть произвольным. Например, два разбиения <1,2,9>È<5,7>=<5,7>È <1,2,9>множества <1,2,5,7,9>считаются совпадающими.

Пример 1.3. Составить все возможные разбиения множества <1,2,3>.

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

Разность множеств А и В определяется следующим образом:

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

Пользуясь понятием универсального множества, можно определить дополнение к множеству А,как разность вида: = U \ A (рис. 1.3, б).

Пример. Пусть в качестве универсального множества выступает множество целых чисел Z и пусть А — это множество всех чётных чисел. Тогда — это множество всех нечётных чисел.

Операции объединения, пересечения и дополнения множеств связаны между собой законами де Моргана:

, .

ÿ Если a Î , то a Ï AÇB. Это значит, что или aÎ , или aÎ , т.е. aÎ . Следовательно, .

С другой стороны, если aÎ , то или aÎ , или aÎ . Это значит, что aÏ AÇ B , т.е. a Î . Таким образом, Í .

Из этих двух включений следует первый закон де Моргана. ÿ

Второй закон доказывается аналогичным образом.

life-prog.ru

Тема : Преобразование логических выражений. Формулы де Моргана

Главная > Документ

© К. Поляков, 2009-2010

A10 (базовый уровень, время – 1 мин)

Тема: Преобразование логических выражений. Формулы де Моргана.

К сожалению, обозначения логических операций И, ИЛИ и НЕ, принятые в «серьезной» математической логике (,, ¬), неудобны, интуитивно непонятны и никак не проявляют аналогии с обычной алгеброй. Автор, к своему стыду, до сих пор иногда путает и . Поэтому на его уроках операция «НЕ» обозначается чертой сверху, «И» – знаком умножения (поскольку это все же логическое умножение), а «ИЛИ» – знаком «+» (логическое сложение).
В разных учебниках используют разные обозначения. К счастью, в начале задания ЕГЭ приводится расшифровка закорючек (,, ¬), что еще раз подчеркивает проблему.

Что нужно знать:

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

¬ A, не A (отрицание, инверсия)

A B, A и B (логическое умножение, конъюнкция)

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

AB импликация (следование)

операцию «импликация» можно выразить через «ИЛИ» и «НЕ»:

AB = ¬ A B или в других обозначениях AB =

если в выражении нет скобок, сначала выполняются все операции «НЕ», затем – «И», затем – «ИЛИ», и самая последняя – «импликация»

правила преобразования логических выражений (слайд из презентации «Логика»):

фактически это задание на применение законов де Моргана (хотя об этом нигде не говорится):

¬ (A B) = ¬ A ¬ B

¬ (A B) = ¬ A ¬ B

Пример задания:

Укажите, какое логическое выражение равносильно выражению A ¬(¬B C).

Решение (вариант 1, использование законов де Моргана):

перепишем заданное выражение и ответы в других обозначениях:
заданное выражение
ответы: 1) 2) 3) 4)

посмотрев на заданное выражение, видим инверсию (операцию «НЕ») для сложного выражения в скобках, которую раскрываем по формуле де Моргана,

а затем используем закон двойного отрицания по которому :

таким образом, правильный ответ – 3 .

Возможные ловушки и проблемы:

серьезные сложности представляет применяемая в заданиях ЕГЭ форма записи логических выражений с «закорючками», поэтому рекомендуется сначала внимательно перевести их в «удобоваримый» вид; при этом сразу становится понятно, что ответы 1 и 2 заведомо неверные

при использовании законов де Моргана часто забывают, что нужно заменить «И» на «ИЛИ» и «ИЛИ» на «И» (возможный неверный ответ )

расчет на то, что при использовании законов де Моргана инверсия сложного выражения по ошибке «просто пропадет», и все сведется к замене «ИЛИ» на «И» (неверный ответ )

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

Решение (вариант 2, через таблицы истинности, если забыли формулы де Моргана):

перепишем заданное выражение в других обозначениях:
заданное выражение
ответы: 1) 2) 3) 4)

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

здесь 3 переменных, каждая из которых принимает два возможных значения (всего 8 вариантов, которые в таблице истинности записывают по возрастанию двоичных кодов – см. презентацию «Логика»)

исходное выражение истинно только тогда, когда и , то есть только при . (в таблице истинности одна единица, остальные – нули)

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

аналогично выражение ложно только при , а в остальных случаях – истинно

выражение истинно только при , а в остальных случаях – ложно

выражение истинно только при , а в остальных случаях – ложно

объединяя все эти результаты в таблицу, получаем:

gigabaza.ru