Объяснил правила Демооргана
https://stackoverflow.com/questions/2168603
-
24-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Не могли бы вы объяснить Правила Демооргана Как можно просто (например, для кого-то с только средней школой математики)?
Решение
У нас есть два значения: T а также F.
Мы можем объединить эти значения тремя способами: NOT, AND, а также OR.
NOT самый простой:
NOT T = FNOT 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.
Правила Демооргана удобны уловки, которые позволяют преобразовать между эквивалентными выражениями, которые соответствуют определенным шаблонам:
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) эквивалентны.
Другие советы
Посмотрите на некоторые ответы, я думаю, что могу объяснить его лучше, используя условия, которые на самом деле связаны друг с другом.
Закон Демиргана относится к тому, что есть два одинаковых способа написания любого сочетания двух условий - в частности, 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 лет. Это, безусловно, менее запутано, чем вся эта глупость о таблицах истины (даже я путающуюся, глядя на всех тех).
Это просто способ восстановления заявлений истины, которые могут предоставить более простые способы написания условных условных.
По просто английскому языку:
Когда что-то не так или что, это тоже не так и не то.
Когда что-то не так и то, это тоже не так или не то.
Примечание: Учитывая неточность английского языка на слово «или», я использую его, чтобы означать неисключительную или в предыдущем примере.
Например, следующий псевдокод эквивалентен:
Если нет (A или B) ...
Если (не а) и (не б) ....
Если нет (а и б) ...
Если нет (а) или нет (б) ...
Если вы сотрудник полиции ищет пьющих несовершеннолетних, вы можете сделать одно из следующих действий, и закон Де Морган говорит, что они составляют то же самое:
Состав 1 (A и B)
Если они под возрастное ограничение и пить алкогольнапиток, арестовать их.
Состав 2 (не (не a или нет b))
Если они надвозрастное ограничение или пить безалкогольный напиток, пусть они пойдут.
Это, кстати, не мой пример. Насколько я знаю, это была часть научного эксперимента, в котором то же правило было выражено по-разному, чтобы выяснить, сколько разницы она сделана в способности народов, чтобы их понять.
«У него нет машины, ни на автобуса». Значит то же самое, что и «у него нет машины, и у него нет автобуса».
«У него нет машины и автобуса». Значит то же самое, что у него тоже нет машины, либо не имеет автобуса, я не уверен, что, может быть, у него нет ни.
Конечно, на простом английском "у него нет машины и автобуса". имеет сильное влияние, что у него есть хотя бы одна из этих двух вещей. Но, строго говоря, с логической точки зрения, утверждение также верно, если у него нет ни одного из них.
Формально:
- нет (автомобиль или автобус) = (не машина) и (не автобус)
- нет (автомобиль и автобус) = (не машина) или (не автобус)
На английском языке, «или», как правило, означают выбор, что у вас нет обоих вещей. В логике, «или» всегда означает то же самое, что и / или 'на английском языке.
Вот таблица правды, которая показывает, как это работает:
Первый случай: не (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
---+---++---------+---------------++---------+---------+--------------------
Нарисуйте простую диаграмму Venn, два пересекающихся кругах. Положить в левую и б в правой форме. Теперь (A и B), очевидно, пересекающийся бит. Итак, не (A и B) - это все, что не в пересекающейся бит, остальная часть обеих кругов. Цвет, который в.
Нарисуйте еще два круга, как ранее, A и B, пересекающиеся. Сейчас не (а) - это все, что в правильном круге (б), но не пересечение, потому что это, очевидно, а также, как B. цвета это в. Точно так же не (б) это все в левом круге, но не пересечение, Потому что это B, а также А. Цвет этого.
Две рисунки выглядят одинаково. Вы доказали, что не (A и B) = не (а) или нет (b). T'hote Case остается как упражнение для студента.
Закон Деморгана позволяет указывать строку логических операций по-разному. Это относится к логике и настроительной теории, где в теории набора вы используете дополнение к нему, пересечение и, а также союз или.
Закон Деморгана позволяет упростить логическое выражение, выполняя операцию, которая довольно похожа на распределительное свойство умножения.
Итак, если у вас есть следующее на C-похожем
if !(x || y || z) { /* do something */ }
Это логически эквивалентно:
if (!x && !y && !z)
Это также работает так:
if !(x && !y && z)
превращается в
if (!x || y || !z)
И можно, конечно, пойти в обратном порядке.
Эквивалентность этих утверждений легко видеть, используя что-то, называемое таблицей истины. В таблице правды вы просто выкладываете ваши переменные (x, y, z) и перечислите все комбинации входов для этих переменных. Затем у вас есть столбцы для каждого предиката или логического выражения, и вы определяете для данных входов, значение выражения. Любой университетская учебная программа для информатики, компьютерной техники или электротехники, скорее всего, водит вам Bonkers с номером и размером таблиц истинности, которые вы должны построить.
Так зачем узнать их? Я думаю, что самая большая причина в вычислении состоит в том, что она может улучшить читаемость более крупных логических выражений. Некоторые люди не любят использовать логику не ! Перед выражениями, как они думают, он может запутать кого-то, если они пропустит это. Влияние с использованием закона демиоргана на уровне ворот чипов полезно, однако, поскольку определенные типы ворот являются быстрее, дешевле, или вы уже используете целую интегральную цепь для них, чтобы вы могли уменьшить количество пакетов чипов, необходимых для исход.
Не уверен, почему я сохранил это все эти годы, но оно доказано полезно на ряде случаев. Благодаря мистеру Бэйли, моего учителя математики 10 класса. Он назвал это теоремой Демооргана.
!(A || B) <==> (!A && !B)
!(A && B) <==> (!A || !B)
Когда вы перемещаете отрицание в кронштейне или из кронштейнов, логический оператор (и или) меняется.
