Уравнение соответствующее правилу де моргана

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(A Ù B) = A Ú B

(A Ú B) = A Ù B

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

¬ ( A  B ) = ¬ A  ¬ B

¬ ( A  B ) = ¬ A  ¬ B

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

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

1) ¬A  ¬B  ¬C 2) A  ¬B  ¬C 3) A  B  ¬C 4) A  ¬B  C

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Как доказать законы Де Моргана

Как доказать законы Де Моргана — Науки

Содержание:

В математической статистике и вероятности важно знать теорию множеств. Элементарные операции теории множеств связаны с определенными правилами вычисления вероятностей. Взаимодействие этих элементарных множественных операций объединения, пересечения и дополнения объясняется двумя утверждениями, известными как законы Де Моргана. Изложив эти законы, мы увидим, как их доказать.

Заявление о законах Де Моргана

Законы Де Моргана относятся к взаимодействию союза, пересечения и дополнения. Напомним, что:

• Пересечение множеств А а также B состоит из всех элементов, общих для обоих А а также B. Пересечение обозначается через А ∩ B.
• Объединение множеств А а также B состоит из всех элементов, которые либо А или B, включая элементы в обоих наборах. Пересечение обозначается A U B.
• Дополнение набора А состоит из всех элементов, которые не являются элементами А. Это дополнение обозначается A C .

Теперь, когда мы вспомнили об этих элементарных операциях, мы увидим формулировку законов Де Моргана. Для каждой пары наборов А а также B

1. (А ∩ B) C = А C U B C .
2. (А U B) C = А C ∩ B C .

Схема стратегии доказательства

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

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

Доказательство одного из законов

Мы увидим, как доказать первый из приведенных выше законов Де Моргана. Начнем с того, что покажем, что (А ∩ B) C это подмножество А C U B C .

1. Сначала предположим, что Икс является элементом (А ∩ B) C .
2. Это значит, что Икс не является элементом (А ∩ B).
3. Поскольку пересечение — это совокупность всех элементов, общих для обоих А а также B, предыдущий шаг означает, что Икс не может быть элементом обоих А а также B.
4. Это значит, что Икс должен быть элементом хотя бы одного из множеств А C или B C .
5. По определению это означает, что Икс является элементом А C U B C
6. Мы показали включение желаемого подмножества.

Наше доказательство наполовину сделано. Чтобы завершить его, мы показываем включение противоположного подмножества. В частности, мы должны показать А C U B C является подмножеством (А ∩ B) C .

1. Начнем с элемента Икс в наборе А C U B C .
2. Это значит, что Икс является элементом А C или это Икс является элементом B C .
3. Таким образом Икс не является элементом хотя бы одного из множеств А или B.
4. Так Икс не может быть элементом обоих А а также B. Это значит, что Икс является элементом (А ∩ B) C .
5. Мы показали включение желаемого подмножества.

Доказательство иного закона

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