Каталог@Mail.ru - каталог ресурсов интернет HitMeter - счетчик посетителей сайта, бесплатная статистика

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

На главную Математический раздел Криптография и т.д. Новости

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

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

copyright © Исканцев Н.В., 2012

К математическому разделу
На главную
X