Диаграмма Эйлера - Euler diagram

Диаграмма Эйлера, показывающая, что набор «животных с четырьмя ногами» является подмножеством «животных», но набор «минералов» не пересекается (не имеет общих членов) с «животными»

Диаграмма Эйлера, показывающая отношения между разными Солнечная система объекты

An Диаграмма Эйлера (/ˈɔɪлər/, OY-lər ) это схематический средства представления наборы и их отношения. Они особенно полезны для объяснения сложных иерархий и пересекающихся определений. Они похожи на другую технику построения диаграмм, Диаграммы Венна. В отличие от диаграмм Венна, которые показывают все возможные отношения между различными наборами, диаграмма Эйлера показывает только релевантные отношения.

Первое использование «кругов Эйлера» обычно приписывают швейцарскому математику. Леонард Эйлер (1707–1783). В Соединенных Штатах и ​​диаграммы Венна, и диаграммы Эйлера были включены как часть инструкции в теория множеств как часть новая математика движение 1960-х гг. С тех пор они также были приняты в других областях учебной программы, таких как чтение^[1] а также организации и предприятия.

Диаграммы Эйлера состоят из простых замкнутых фигур на двухмерной плоскости, каждая из которых изображает набор или категорию. Как или если эти формы перекрываются, демонстрирует отношения между наборами. Каждая кривая делит плоскость на две области или «зоны»: внутреннюю часть, которая символически представляет собой элементы набора и внешний вид, который представляет все элементы, не являющиеся членами набора. Кривые, которые не перекрываются, представляют непересекающиеся множества, у которых нет общих элементов. Две перекрывающиеся кривые представляют наборы, которые пересекаться, у которых есть общие элементы; зона внутри обеих кривых представляет собой набор элементов, общих для обоих наборов ( пересечение наборов). Кривая полностью внутри другого - это подмножество этого.

Диаграммы Венна представляют собой более ограниченную форму диаграмм Эйлера. Диаграмма Венна должна содержать все 2^п логически возможные зоны перекрытия между его п кривые, представляющие все комбинации включения / исключения составляющих его множеств. Области, не входящие в набор, обозначаются черным цветом, в отличие от диаграмм Эйлера, где принадлежность к набору обозначается как перекрытием, так и цветом.

История

Страница из Гамильтона Лекции по логике. Символизм A, E, I и O относятся к категориальным утверждениям, которые могут произойти в силлогизм. Небольшой текст слева ошибочно заявляет: «Первое использование круговых диаграмм в логике, неправильно приписываемое Эйлеру. Можно найти в Кристиан Вайсе», книге, фактически написанной Иоганном Кристианом Ланге.^[2][3]

Справа - страница 74 из Couturat 1914, на которой он помечает 8 областей диаграммы Венна. Современное название этих «регионов» - минтермы. Они показаны слева с переменными x, y и z на рисунке Венна. Символика следующая: логическое И (&) представлено арифметическим умножением, а логическое НЕ (~) представлено знаком "'" после переменной, например область x'y'z читается как "НЕ x И НЕ y И z", то есть ~ x & ~ y & z.

И диаграмма Вейча, и карта Карно показывают все минтермы, но Veitch не особенно полезен для сокращения формул. Обратите внимание на сильное сходство между диаграммами Венна и Карно; цвета и переменные x, y и z соответствуют примеру Венна.

Как показано на рисунке справа, Сэр Уильям Гамильтон в его посмертно опубликованном Лекции по метафизике и логике (1858–60) ошибочно утверждает, что первоначальное использование кругов для «чувственности ... абстракций логики» (стр. 180) не было Леонард Пол Эйлер (1707–1783) а скорее Кристиан Вайсе (1642–1708) в его Nucleus Logicae Weisianae вышедшая в 1712 году посмертно, однако последняя книга была написана Иоганном Христианом Ланге, а не Вайсе.^[2][3] Он ссылается на Письма к немецкой принцессе [Часть II, Lettre XXXV, 17 февраля 1791 г., изд. Курно (1842), стр. 412-417. - Ред.]^{[nb 1]}

В иллюстрации Гамильтона четыре категоричные предложения что может произойти в силлогизм как показано на рисунках A, E, I и O:^[4]

• A: Универсальный утвердительный, Пример: «Все металлы - элементы».
• E: The Универсальный негатив, Пример: «Никакие металлы не являются составными веществами».
• Я: Особо положительный, Пример: «Некоторые металлы хрупкие».
• O: The Особо отрицательный, Пример: «Некоторые металлы не являются хрупкими».

В его 1881 г. Символическая логика Глава V «Схематическое изображение», Джон Венн (1834–1923) комментирует замечательную распространенность диаграммы Эйлера:

«... из первых шестидесяти трактатов по логике, опубликованных в течение последнего столетия или около того, к которым обращались с этой целью: - несколько случайно, поскольку они оказались наиболее доступными: - оказалось, что тридцать четыре обратились к помощи диаграммы, почти все они используют схему Эйлера ». (Сноска 1, стр. 100)

Состоит из двух страниц 115–116 из книги Венна 1881 года, показывающих его пример того, как преобразовать силлогизм из трех частей в его тип диаграммы. Венн называет круги «кругами Эйлера» (ср. Sandifer 2003, Venn 1881: 114 и т.д.) в «схеме Эйлера» (Venn 1881: 100) «старомодных диаграмм Эйлера» (Venn 1881: 113).

Но, тем не менее, он утверждал, что «неприменимость этой схемы для целей действительно общей логики» (стр. 100), и на странице 101 заметил, что «она плохо согласуется даже с четырьмя положениями общей логики, которым она соответствует. обычно применяется ". Венн заканчивает свою главу наблюдением, проиллюстрированным в приведенных ниже примерах, - что их использование основано на практике и интуиции, а не на строгих алгоритмический упражняться:

«Фактически ... эти диаграммы не только не вписываются в обычную схему предложений, которую они используют для иллюстрации, но и, похоже, не имеют какой-либо признанной схемы предложений, к которой они могли бы быть последовательно связаны». (стр. 124–125)

Наконец, в главе XX «ИСТОРИЧЕСКИЕ ЗАПИСИ» Венн обращается к решающей критике (выделенной курсивом в приведенной ниже цитате); обратите внимание на иллюстрацию Гамильтона, что O (Особо отрицательный) и я (Особо положительный) просто поворачиваются:

"Теперь мы переходим к хорошо известным кругам Эйлера, которые впервые были описаны в его Lettres a une Princesse d'Allemagne (Письма 102–105). Слабое место в них состоит в том, что они лишь четко иллюстрируют действительные отношения классов друг с другом, а не несовершенное знание этих отношений, которым мы можем обладать или желаем передать посредством предложения. Соответственно, они не согласятся с положениями общей логики, но потребуют создания новой группы соответствующих элементарных предложений ... Этот недостаток должен был быть замечен с самого начала. в случае конкретного утвердительного и отрицательного, поскольку одна и та же диаграмма обычно используется для обозначения их обоих, что одинаково хорошо". (курсив добавлен: стр. 424)

(Sandifer 2003 сообщает, что Эйлер тоже делает такие наблюдения; Эйлер сообщает, что его фигура 45 (простое пересечение двух кругов) имеет 4 различных интерпретации). В любом случае, вооруженный этими наблюдениями и критикой, Венн затем демонстрирует (стр. 100–125), как он получил то, что стало известно как его Диаграммы Венна из «... старомодных диаграмм Эйлера». В частности, он приводит пример, показанный слева.

К 1914 г. Луи Кутюра (1868–1914) обозначили термины, как показано на рисунке справа. Более того, он обозначил внешний регион (показано как a'b'c '). Он лаконично объясняет, как пользоваться диаграммой - нужно вычеркнуть регионы, которые должны исчезнуть:

"Метод Венна воплощен в геометрических диаграммах, которые представляют все составляющие, так что для получения результата нам нужно только зачеркнуть (затенением) те, которые исчезли из-за данных проблемы »(курсив добавлен с. 73)

Таким образом, учитывая задания Венна, незатененные области внутри круги можно сложить, чтобы получить следующее уравнение для примера Венна:

«Нет Y - это Z, а ВСЕ X - это Y: следовательно, X - это Z» имеет уравнение x'yz '+ xyz' + x'y'z для незатененной области внутри кружки (но это не совсем правильно; см. следующий абзац).

У Венна 0-й член x'y'z ', то есть фон, окружающий круги, не появляется. Это нигде не обсуждается и не упоминается, но Кутура исправляет это в своем рисунке. Правильное уравнение должно включать эту незатененную область, выделенную жирным шрифтом:

«Нет Y - это Z, а ВСЕ X - это Y: следовательно, Нет X - это Z» имеет уравнение x'yz '+ xyz' + x'y'z + x'y'z ' .

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

Кутюра теперь замечает, что в прямом алгоритмический (формально, систематически) нельзя вывести редуцированные булевы уравнения, и при этом не показано, как прийти к выводу «Нет X есть Z». Кутюра пришел к выводу, что этот процесс «имеет ... серьезные неудобства как метод решения логических задач»:

"Он не показывает, как данные отображаются путем исключения определенных составляющих, и не показывает, как объединить оставшиеся составляющие для получения искомых результатов. Короче говоря, он служит лишь для демонстрации одного единственного шага в аргументе, а именно уравнение проблемы; он не обходится ни с предыдущими шагами, т. е. "перебрасыванием проблемы в уравнение" и преобразованием предпосылок, ни с последующими шагами, т. е. комбинациями, которые приводят к различным последствиям. от этого очень мало пользы, поскольку составляющие могут быть представлены алгебраическими символами так же хорошо, как и плоскими областями, и с ними гораздо легче работать в этой форме »(стр. 75).

Таким образом, дело оставалось до 1952 года, когда Морис Карно (1924–) адаптировал и расширил метод, предложенный Эдвард В. Вейч; эта работа будет опираться на таблица истинности метод, точно определенный в Эмиль Пост докторскую диссертацию 1921 г. "Введение в общую теорию элементарных предложений" и применение логики высказываний к логика переключения от (среди прочего) Клод Шеннон, Джордж Стибиц, и Алан Тьюринг.^{[nb 2]} Например, в главе «Булева алгебра» Хилл и Петерсон (1968, 1964) представляют разделы 4.5ff «Теория множеств как пример булевой алгебры», и в ней они представляют диаграмму Венна с затенением и всем остальным. Они приводят примеры диаграмм Венна для решения примеров проблем с коммутационной схемой, но в итоге приводят следующее утверждение:

«Для более чем трех переменных основная иллюстративная форма диаграммы Венна неадекватна. Возможны расширения, однако наиболее удобной из них является карта Карно, которую мы обсудим в главе 6.» (стр.64)

В разделе 6.4 главы 6 «Представление булевых функций картой Карно» они начинаются с:

"Карта Карно¹ [¹Karnaugh 1953] - один из самых мощных инструментов в арсенале разработчика логики. ... Карту Карно можно рассматривать либо как наглядную форму таблицы истинности, либо как расширение диаграммы Венна »(стр. 103–104).

История развития Карно своего метода «диаграммы» или «карты» неясна. Карно в своем 1953 году ссылается на Veitch 1951, Veitch ссылается на Клод Э. Шеннон 1938 г. (по существу магистерская диссертация Шеннон в M.I.T. ), а Шеннон, в свою очередь, ссылался, среди других авторов логических текстов, на Couturat 1914. В методе Вейтча переменные располагаются в прямоугольнике или квадрате; как описано в Карта Карно, Карно в своем методе изменил порядок переменных, чтобы он соответствовал тому, что стало известно как (вершины) a гиперкуб.

Связь диаграмм Эйлера и Венна

Примеры малых Диаграммы Венна (слева) с заштрихованными областями, представляющими пустые наборы, показывая, как их легко преобразовать в эквивалентные диаграммы Эйлера (правильно)

Диаграммы Венна представляют собой более ограниченную форму диаграмм Эйлера. Диаграмма Венна должна содержать все 2^п логически возможные зоны перекрытия между его п кривые, представляющие все комбинации включения / исключения составляющих его множеств. Области, не входящие в набор, обозначаются черным цветом, в отличие от диаграмм Эйлера, где принадлежность к набору обозначается как перекрытием, так и цветом. Когда количество наборов превышает 3, диаграмма Венна становится визуально сложной, особенно по сравнению с соответствующей диаграммой Эйлера. Разницу между диаграммами Эйлера и Венна можно увидеть в следующем примере. Возьмите три комплекта:

• ${ Displaystyle А = {1, , 2, , 5 }}$
• ${ Displaystyle В = {1, , 6 }}$
• ${ Displaystyle C = {4, , 7 }}$

Диаграммы Эйлера и Венна этих множеств:

• 

  Диаграмма Эйлера

• 

  Диаграмма Венна

В логической обстановке можно использовать теоретико-модельную семантику для интерпретации диаграмм Эйлера в пределах вселенная дискурса. В приведенных ниже примерах диаграмма Эйлера показывает, что множества Животное и Минеральная не пересекаются, поскольку соответствующие кривые не пересекаются, а также то, что множество Четыре ноги является подмножеством множества Животноес. Диаграмма Венна, в которой используются те же категории Животное, Минеральная, и Четыре ноги, не инкапсулирует эти отношения. Традиционно пустота набора на диаграммах Венна отображается штриховкой в ​​области. Диаграммы Эйлера представляют пустота либо штриховкой, либо отсутствием области.

Часто налагается набор условий корректности; это топологические или геометрические ограничения, накладываемые на структуру диаграммы. Например, может быть принудительно установлена ​​связность зон или может быть запрещено параллелизм кривых или нескольких точек, а также касательное пересечение кривых. На соседней диаграмме примеры небольших диаграмм Венна преобразованы в диаграммы Эйлера последовательностями преобразований; некоторые из промежуточных диаграмм имеют параллелизм кривых. Однако такое преобразование диаграммы Венна с штриховкой в ​​диаграмму Эйлера без штриховки не всегда возможно. Есть примеры диаграмм Эйлера с 9 наборами, которые невозможно нарисовать с помощью простых замкнутых кривых без создания нежелательных зон, поскольку они должны иметь неплоские двойственные графы.

Пример: диаграмма Эйлера-Венна и отображение Карно

В этом примере показаны диаграммы Эйлера и Венна и карта Карно, выводящая и проверяющая вывод «Нет. Иксs есть Zs ". На рисунке и в таблице использованы следующие логические символы:

• 1 можно прочитать как «истина», 0 как «ложь»
• ~ для НЕ и сокращается до 'при иллюстрации минтермов, например х '=_{определены} НЕ х,
• + для логического ИЛИ (от Булева алгебра: 0+0=0, 0+1 = 1+0 = 1, 1+1=1)
• & (логическое И) между предложениями; в mintems И опускается аналогично арифметическому умножению: например, x'y'z =_{определены} ~ x & ~ y & z (из булевой алгебры: 0 * 0 = 0, 0 * 1 = 1 * 0 = 0, 1 * 1 = 1, где * показан для ясности)
• → (логическое ПОСЛЕДСТВИЕ): читается как ЕСЛИ ... ТО ... или "ПОДРАЗУМЕВАЕТСЯ", п → Q =_{определены} НЕ п ИЛИ Q

Прежде чем его можно будет представить в диаграмме Венна или карте Карно, силлогизм диаграммы Эйлера "Нет Y является Z, Все Икс является Y"необходимо сначала переформулировать на более формальный язык пропозициональное исчисление: "'Это не так: Y И Z ' И 'Если Икс затем Y ' ". Как только предложения сведены к символам и пропозициональной формуле (~ (y & z) & (x → y)), можно построить формулу таблица истинности; из этой таблицы легко получить карту Венна и / или Карно. Используя смежность «1» на карте Карно (обозначенную серыми овалами вокруг членов 0 и 1 и вокруг членов 2 и 6) можно «уменьшить» пример Булево уравнение т.е. (x'y'z '+ x'y'z) + (x'yz' + xyz ') всего до двух членов: x'y' + yz '. Но средства вывода понятия, что «X не есть Z», и то, как сокращение соотносится с этим выводом, не вытекают из этого примера.

Учитывая предлагаемый вывод типа «Нет Икс это Z", можно проверить, является ли это правильным вычет с помощью таблица истинности. Самый простой способ - поставить слева начальную формулу (обозначьте ее как п) и поместите (возможный) вычет справа (обозначьте его как Q) и соедините их с логическое следствие т.е. п → Q, читается как ЕСЛИ п ТОГДА Q. Если вычисление таблицы истинности дает все единицы под знаком импликации (→, так называемый главная связка) тогда п → Q это тавтология. Учитывая этот факт, можно «отделить» формулу справа (сокращенно Q) способом, описанным ниже в таблице истинности.

В приведенном выше примере формула диаграмм Эйлера и Венна следующая:

"Нет Ys есть Zs "и" Все Иксs есть Ys ": (~ (y & z) & (x → y)) =_{определены} п

И предлагаемый вычет:

"Нет Иксs есть Zs ": (~ (x & z)) =_{определены} Q

Итак, теперь формулу, которую нужно оценить, можно сократить до:

(~ (y & z) & (x → y)) → (~ (x & z)): п → Q

Если нет Ys есть Zs "и" Все Иксs есть Ys ") THEN (" Нет Иксs есть Zs ")

На данный момент указанное выше значение п → Q (т.е. ~ (y & z) & (x → y)) → ~ (x & z)) по-прежнему является формулой, и дедукция - "отстранение" Q снаружи п → Q - не произошло. Но учитывая демонстрацию того, что п → Q является тавтологией, теперь готовится почва для использования процедуры modus ponens "отсоединить" Q: "Нет Иксs есть Zs "и обойтись без терминов слева.^{[№ 3]}

Modus ponens (или «фундаментальное правило вывода»^[5]) часто записывается следующим образом: два члена слева, п → Q и п, называются предпосылки (по соглашению, соединенного запятой), символ ⊢ означает «дает» (в смысле логической дедукции), а термин справа называется вывод:

п → Q, п ⊢ Q

Чтобы modus ponens был успешным, обе посылки P → Q и P должны быть истинный. Поскольку, как показано выше, предпосылка п → Q является тавтологией, «истина» всегда имеет место, независимо от того, как оцениваются x, y и z, но «истина» имеет место только для п в тех обстоятельствах, когда п оценивается как "истина" (например, строки 0 ИЛИ 1 ИЛИ 2 ИЛИ 6: x'y'z '+ x'y'z + x'yz' + xyz '= x'y' + yz ').^{[№ 4]}

п → Q , п ⊢ Q

• то есть: (~ (y & z) & (x → y)) → (~ (x & z)), (~ (y & z) & (x → y)) ⊢ (~ (x & z))
• то есть: ЕСЛИ "Нет Ys есть Zs "и" Все Иксs есть Ys " ТОГДА "Нет Иксs есть Zs "," Нет Ys есть Zs "и" Все Иксs есть Ys "⊢" Нет Иксs есть Zs "

Теперь можно «отсоединить» вывод «Нет. Иксs есть Zs ", возможно, чтобы использовать его в последующем выводе (или как тему разговора).

Использование тавтологического импликации означает, что существуют и другие возможные дедукции, кроме «Нет. Иксs есть Zs "; критерием успешного вычета является то, что единицы под основной связкой справа включают все единицы под основной связкой слева ( главный соединительное слово - импликация, которая приводит к тавтологии). Например, в таблице истинности справа от импликации (→, главный соединительный символ) выделенный жирным шрифтом столбец под второстепенным соединительным символом " ~ "имеет все те же единицы, которые отображаются в столбце, выделенном жирным шрифтом, под левой подмажорной связкой & (строки 0, 1, 2 и 6), плюс еще два (ряды 3 и 4).

Галерея

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

• 

  А Диаграмма Венна показывает все возможные пересечения.

• 

  Диаграмма Эйлера, визуализирующая реальную ситуацию, взаимосвязь между различными наднациональные европейские организации. (кликабельная версия)

• 

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

• 

  Диаграмма Эйлера типов треугольники, используя определение, что равнобедренные треугольники имеют как минимум (а не ровно) 2 равные стороны.

• 

  Диаграмма Эйлера терминологии Британские острова.

• 

  22 (из 256) существенно разных диаграмм Венна с 3 кругами (верх) и соответствующие им диаграммы Эйлера (Нижний)
  Некоторые диаграммы Эйлера нетипичны, а некоторые даже эквивалентны диаграммам Венна. Области закрашены, чтобы указать, что они не содержат элементов.

Смотрите также

• Диаграмма паука - расширение диаграмм Эйлера, добавляющее существование пересечений контуров.

Примечания

использованная литература

дальнейшее чтение

По дате публикации:

• Сэр Уильям Гамильтон 1860 Лекции по метафизике и логике Отредактировано Генри Лонгвиль Мансель и Джон Вейтч, Уильям Блэквуд и сыновья, Эдинбург и Лондон.
• У. Стэнли Джевонс 1880 Элементарные уроки логики: дедуктивный и индуктивный. С множеством вопросов и примеров, а также словарем логических терминов, M. A. MacMillan and Co., Лондон и Нью-Йорк.
• Альфред Норт Уайтхед и Бертран Рассел 1-е издание 1913 г., 2-е издание 1927 г. Principia Mathematica до * 56 Кембридж в Университетское издательство (Издание 1962 г.), Великобритания, без ISBN.
• Луи Кутюра 1914 Алгебра логики: авторизованный английский перевод Лидии Гиллингем Робинсон с предисловием Филипа Э. Б. Журдена, Издательская компания Open Court, Чикаго и Лондон.
• Эмиль Пост 1921 г. "Введение в общую теорию элементарных предложений" перепечатано с комментарием Жан ван Хейеноорт Жан ван Хейенорт, редактор 1967 От Фреге до Гёделя: Справочник по математической логике, 1879–1931 гг., Издательство Гарвардского университета, Кембридж, Массачусетс, ISBN  0-674-32449-8 (pbk.)
• Клод Э. Шеннон 1938 "Символьный анализ реле и схем переключения", Сделки Американский институт инженеров-электриков vol 57, pp. 471–495. Происходит от Клод Элвуд Шеннон: Сборник статей под редакцией N.J.A. Солан и Аарон Д. Уайнер, IEEE Press, Нью-Йорк.
• Ганс Райхенбах 1947 Элементы символической логики переиздано в 1980 г. Dover Publications, Inc., Нью-Йорк, ISBN  0-486-24004-5.
• Вейтч, Эдвард Уэстбрук (1952-05-03) [1952-05-02]. «Диаграмма метода для упрощения функций истины». Труды Ежегодного собрания ACM 1952 года. Ежегодная конференция / ежегодное собрание ACM: Материалы ежегодного собрания ACM 1952 г. (Питтсбург, Пенсильвания, США). Нью-Йорк, США: Ассоциация вычислительной техники (ACM): 127–133. Дои:10.1145/609784.609801.
• Карно, Морис (Ноябрь 1953 г.) [1953-04-23, 1953-03-17]. «Метод отображения для синтеза комбинационных логических схем» (PDF). Труды Американского института инженеров-электриков, часть I: Связь и электроника. 72 (5): 593–599. Дои:10.1109 / TCE.1953.6371932. Документ 53-217. Архивировано из оригинал (PDF) на 2017-04-16. Получено 2017-04-16.
• Фредерик Дж. Хилл и Джеральд Р. Петерсон 1968, 1974 Введение в теорию переключения и логический дизайн, Джон Уайли и сыновья, Нью-Йорк, ISBN  978-0-471-39882-0.
• Сандифер, Эд (январь 2004 г.). "Как это сделал Эйлер" (PDF). maa.org. Архивировано из оригинал (PDF) на 26.01.2013.

внешние ссылки

• Диаграммы Эйлера. Брайтон, Великобритания (2004 г.).Что такое диаграммы Эйлера?