Подтвердить что ты не робот

Изменились правила deMorgan

Не могли бы вы как можно проще объяснить правила deMorgan (например, для кого-то, у кого есть только исходная математическая школа)?

4b9b3361

ОТВЕТЫ

Ответ 1

У нас есть два значения: T и F.

Мы можем объединить эти значения тремя способами: NOT, AND и OR.

NOT является самым простым:

  • NOT T = F
  • NOT F = T

Мы можем записать это как таблицу истинности:

when given.. | results in...
============================
           T | F
           F | T

Для краткости

x | NOT x
=========
T | F
F | T

Вспомните NOT как дополнение, то есть оно превратит одно значение в другое.

AND работает с двумя значениями:

x y | x AND y
=============
T T | T
T F | F
F T | F
F F | F

AND является T, только если оба его аргумента (значения x и y в таблице истинности) в противном случае T - и F.

OR равен T, когда хотя бы один из его аргументов T:

x y | x OR y
=============
T T | T
T F | T
F T | T
F F | F

Мы можем определить более сложные комбинации. Например, мы можем написать таблицу истинности для x AND (y OR z), а первая строка ниже.

x y z | x AND (y OR z)
======================
T T T | ?

Как только мы узнаем, как оценить x AND (y OR z), мы можем заполнить остальную часть таблицы.

Чтобы оценить комбинацию, оцените части и отработайте оттуда. В скобках указаны части, которые необходимо оценить в первую очередь. То, что вы знаете из обычной арифметики, поможет вам разобраться. Скажем, у вас есть 10 - (3 + 5). Сначала вы оцениваете часть в круглых скобках, чтобы получить

10 - 8

и оцените, как обычно, чтобы получить ответ, 2.

Оценка этих выражений работает аналогично. Мы знаем, как работает OR сверху, поэтому мы можем немного расширить нашу таблицу:

x y z | y OR z | x AND (y OR z)
===============================
T T T | T      | ?

Теперь почти так же, как мы вернулись в таблицу x AND y. Мы просто подставляем значение y OR z и оцениваем. В первой строке мы имеем

T AND (T OR T)

что совпадает с

T AND T

который просто T.

Повторяем тот же процесс для всех 8 возможных значений x, y и z (2 возможных значения x раз 2 возможных значения y раз 2 возможных значения z), чтобы получить

x y z | y OR z | x AND (y OR z)
===============================
T T T | T      | T
T T F | T      | T
T F T | T      | T
T F F | F      | F
F T T | T      | F
F T F | T      | F
F F T | T      | F
F F F | F      | F

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

x | NOT (NOT x)
===============
T | T
F | F

Другими словами, NOT (NOT x) эквивалентно просто x.

Правила DeMorgan - это удобные трюки, которые позволяют нам конвертировать между эквивалентными выражениями, которые соответствуют определенным шаблонам:

  • NOT (x AND y) = (NOT x) OR (NOT y)
  • NOT (x OR y) = (NOT x) AND (NOT y)

(Вы можете подумать об этом как о том, как NOT распространяется через простые выражения AND и OR.)

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

NOT (here AND there)

Применяя правило, это другой способ сказать: "вас здесь нет, или вас там нет".

Упражнение:. Как вы можете выразить второе правило на простом английском языке?

Для первого правила рассмотрим таблицу истинности для выражения в левой части знака равенства.

x y | x AND y | NOT (x AND y)
=============================
T T | T       | F
T F | F       | T
F T | F       | T
F F | F       | T

Теперь правая сторона:

x y | NOT X | NOT Y | (NOT x) or (NOT y)
========================================
T T | F     | F     | F
T F | F     | T     | T
F T | T     | F     | T
F F | T     | T     | T

Конечные значения одинаковы в обеих таблицах. Это доказывает, что выражения эквивалентны.

Упражнение: Докажите, что выражения NOT (x OR y) и (NOT x) AND (NOT y) эквивалентны.

Ответ 2

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

DeMorgan Law ссылается на то, что существует два одинаковых способа записи любой комбинации двух условий - в частности, комбинация AND (оба условия должны быть истинными) и комбинация OR (любой из них может быть правдой). Примерами являются:

Часть 1 Закона ДеМорга

Заявление: У Алисы есть родной брат.
Условия: У Алисы есть брат OR У Алисы есть сестра.
Противоположно: Алиса - единственный ребенок (у NOT есть родной брат).
Условия: У Алисы NOT есть брат, AND у нее NOT есть сестра.

Другими словами: NOT [A OR B] = [NOT A] AND [NOT B]

Часть 2 Закона ДеМорга

Заявление: Боб - водитель автомобиля.
Условия: У Боба есть автомобиль AND У Боба есть лицензия.
Противоположно: Боб - NOT водитель автомобиля.
Условия: У Боба NOT есть автомобиль, OR У Боба NOT есть лицензия.

Другими словами: NOT [A AND B] = [NOT A] OR [NOT B].

Я думаю, что это было бы немного менее запутанным для 12-летнего. Это, конечно, менее запутанно, чем вся эта глупость об истинных таблицах (даже я смущаюсь, глядя на все эти).

Ответ 3

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

Простой английский:
Когда что-то не так или нет, это тоже не это, а не то. Когда что-то не то-то и то-то, это тоже не так или нет.

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

Например, следующий псевдокод эквивалентен:
Если НЕ (A ИЛИ B)...
ЕСЛИ (НЕ А) И (НЕ Б)....

ЕСЛИ НЕ (А И В)...
ЕСЛИ НЕ (A) ИЛИ НЕ (B)...

Ответ 4

"У него нет ни машины, ни автобуса". означает то же самое, что "у него нет машины, и у него нет автобуса".

"У него нет машины и автобуса". означает то же самое, что "у него либо нет машины, либо нет автобуса, я не уверен, что, может быть, у него нет".

Конечно, в простом английском "У него нет машины и автобуса". имеет сильное влияние на то, что у него есть хотя бы одна из этих двух вещей. Но, строго говоря, с логической точки зрения утверждение также верно, если у него нет ни одного из них.

Формально:

  • нет (автомобиль или автобус) = (не автомобиль) и (не автобус)
  • нет (автомобиль и автобус) = (не автомобиль) или (не автобус)

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

Вот таблица истинности, которая показывает, как это работает:

Первый случай: нет (cor или шина) = (не автомобиль) и (не автобус)

 c | b || c or b | not (c or b) || (not c) | (not b) | (not c) and (not b)
---+---++--------+--------------++---------+---------+--------------------
 T | T ||    T   |      F       ||    F    |    F    |        F
---+---++--------+--------------++---------+---------+--------------------
 T | F ||    T   |      F       ||    F    |    T    |        F
---+---++--------+--------------++---------+---------+--------------------
 F | T ||    T   |      F       ||    T    |    F    |        F
---+---++--------+--------------++---------+---------+--------------------
 F | F ||    F   |      T       ||    T    |    T    |        T
---+---++--------+--------------++---------+---------+--------------------

Второй случай: нет (автомобиль и автобус) = (не автомобиль) или (не автобус)

 c | b || c and b | not (c and b) || (not c) | (not b) | (not c) or (not b)
---+---++---------+---------------++---------+---------+--------------------
 T | T ||    T    |       F       ||    F    |    F    |        F
---+---++---------+---------------++---------+---------+--------------------
 T | F ||    F    |       T       ||    F    |    T    |        T
---+---++---------+---------------++---------+---------+--------------------
 F | T ||    F    |       T       ||    T    |    F    |        T
---+---++---------+---------------++---------+---------+--------------------
 F | F ||    F    |       T       ||    T    |    T    |        T
---+---++---------+---------------++---------+---------+--------------------

Ответ 5

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

ФОРМУЛИРОВАНИЕ 1 (A И B)

Если они не достигли возраста предел И выпивать алкоголь напиток, арестовать их.

ФОРМУЛИРОВАНИЕ 2 (НЕ (НЕ ИЛИ НЕ Б))

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

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

Ответ 6

Нарисуйте простую диаграмму Венна, две пересекающиеся окружности. Положите A влево и B вправо. Теперь (A и B), очевидно, является пересекающимся битом. Таким образом, NOT (A и B) - это все, что не в пересекающемся бите, остальные оба круга. Цвет, который в.

Нарисуйте еще два круга, как раньше, A и B, пересекающиеся. Теперь NOT (A) - это все, что в правом круге (B), но не пересечение, потому что это очевидно A, а также B. Цвет этого дюйма. Аналогично NOT (B) - это все в левом круге, но не пересечение, потому что это B, а также A. Color this in.

Два рисунка выглядят одинаково. Вы доказали, что NOT (A и B) = NOT (A) или NOT (B). Другим случаем остается упражнение для ученика.

Ответ 7

Закон DeMorgan позволяет вам указывать последовательность логических операций по-разному. Это относится к логике и теории множеств, где в теории множеств вы используете дополнение для не, пересечение для и, и union для или.

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

Итак, если на C-подобном языке есть следующее:

if !(x || y || z) { /* do something */ }

Это логически эквивалентно:

if (!x && !y && !z)

Он также работает так:

if !(x && !y && z)

превращается в

if (!x || y || !z)

И вы можете, конечно, пойти в обратном направлении.

Эквивалентность этих утверждений легко увидеть, используя что-то, называемое таблицей истинности. В таблице истинности вы просто выкладываете свои переменные (x, y, z) и перечисляете все комбинации входов для этих переменных. Затем у вас есть столбцы для каждого предиката или логическое выражение, и вы определяете для данных входных значений значение выражения. Любая учебная программа университета по информатике, вычислительной технике или электротехнике, вероятно, привлечет вас к бонкерам с количеством и размерами таблиц правды, которые вы должны построить.

Так зачем их учиться? Я думаю, что самая большая причина в вычислении заключается в том, что он может улучшить читаемость более крупных логических выражений. Некоторым людям не нравится использовать логические не ! перед выражениями, поскольку они думают, что это может смутить кого-то, если они его пропустит. Однако влияние использования закона DeMorgan на уровень ворот чипов полезно, поскольку некоторые типы ворот быстрее, дешевле или вы уже используете целую интегральную схему для них, чтобы сократить количество пакетов чипов, необходимых для исход.

Ответ 8

Не уверен, почему я сохранил это все эти годы, но он оказался полезным в ряде случаев. Благодаря г-ну Бейли, моему учителю по математике 10-го класса. Он назвал ее теоремой deMorgan.

!(A || B) <==> (!A && !B)
!(A && B) <==> (!A || !B)

Когда вы перемещаете отрицание в скобки или из них, изменяется логический оператор (AND, OR).