Eulerův diagram -Euler diagram

Eulerův diagram znázorňující, že množina „zvířat se čtyřmi nohami“ je podmnožinou „zvířat“, ale množina „minerálů“ je disjunktní (nemá žádné společné členy) se „zvířaty“
Eulerův diagram ukazující vztahy mezi různými objekty sluneční soustavy

Eulerův diagram ( / ˈ ɔɪ l ər / , OY -lər ) je schématický prostředek pro reprezentaci množin a jejich vztahů. Jsou zvláště užitečné pro vysvětlení složitých hierarchií a překrývajících se definic. Jsou podobné jiné technice vytváření diagramů, Vennovým diagramům . Na rozdíl od Vennových diagramů, které zobrazují všechny možné vztahy mezi různými množinami, Eulerův diagram zobrazuje pouze relevantní vztahy.

První použití „eulerovských kruhů“ je běžně připisováno švýcarskému matematikovi Leonhardu Eulerovi (1707–1783). Ve Spojených státech byly Vennovy i Eulerovy diagramy začleněny jako součást výuky teorie množin jako součást nového matematického hnutí v 60. letech. Od té doby je přijaly i další obory, jako je čtení, stejně jako organizace a podniky.

Eulerovy diagramy se skládají z jednoduchých uzavřených tvarů ve dvourozměrné rovině, z nichž každý zobrazuje sadu nebo kategorii. Jak nebo zda se tyto tvary překrývají, ukazuje vztahy mezi množinami. Každá křivka rozděluje rovinu na dvě oblasti nebo „zóny“: interiér, který symbolicky představuje prvky souboru, a exteriér, který představuje všechny prvky, které nejsou členy souboru. Křivky, které se nepřekrývají, představují disjunktní množiny , které nemají žádné společné prvky. Dvě křivky, které se překrývají, představují množiny, které se protínají , které mají společné prvky; zóna uvnitř obou křivek představuje množinu prvků společných pro obě množiny ( průnik množin). Křivka zcela uvnitř jiné je její podmnožinou .

Vennovy diagramy jsou restriktivnější formou Eulerových diagramů. Vennův diagram musí obsahovat všech 2 n logicky možných zón překrytí mezi jeho n křivkami, které představují všechny kombinace zahrnutí/vyloučení jeho základních množin. Oblasti, které nejsou součástí množiny, jsou označeny černou barvou, na rozdíl od Eulerových diagramů, kde je příslušnost k množině indikována překrytím i barvou.

Dějiny

Stránka z Hamiltonových přednášek o logice . Symbolika A, E, I a O odkazuje na kategorická tvrzení, která se mohou vyskytovat v sylogismu . Malý text nalevo chybně uvádí: "První použití kruhových diagramů v logice nesprávně připisované Eulerovi. K nalezení u Christiana Weise", knihy skutečně napsané Johannem Christianem Langem.
Vpravo je strana 74 z Couturat 1914, kde označuje 8 oblastí Vennova diagramu. Moderní název pro tyto „regiony“ je minterms . Ty jsou zobrazeny vlevo s proměnnými x, y a z podle Vennova výkresu. Symbolika je následující: logické AND ( & ) je reprezentováno aritmetickým násobením a logické NOT ( ~ ) je reprezentováno " ' " za proměnnou, např. oblast x'y'z se čte jako "NOT x AND NOT". y AND z" tj. ~x & ~y & z.
Veitchův diagram i Karnaughova mapa zobrazují všechny mintermy , ale Veitch není zvláště užitečný pro redukci vzorců. Pozorujte silnou podobnost mezi Vennovým a Karnaughovým diagramem; barvy a proměnné x, y a z jsou podle Vennova příkladu.

Jak je znázorněno na obrázku vpravo, Sir William Hamilton ve svých posmrtně publikovaných přednáškách o metafyzice a logice (1858–60) chybně tvrdí, že původní použití kruhů k „senzualizaci... abstrakcí logiky“ (str. 180) nebyl Leonhard Paul Euler (1707–1783), ale spíše Christian Weise (1642–1708) ve svém Nucleus Logicae Weisianae , který se objevil v roce 1712 posmrtně, nicméně druhou knihu ve skutečnosti napsal spíše Johann Christian Lange než Weise. Odkazuje na Eulerovy dopisy německé princezně [Partie II, Lettre XXXV, 17. února 1791, ed. Cournot (1842), s. 412–417. – ED.]

V Hamiltonově ilustraci jsou čtyři kategorické výroky , které se mohou vyskytnout v sylogismu symbolizovaném kresbami A, E, I a O:

  • A: The Universal Afirmative , Příklad: "Všechny kovy jsou prvky".
  • E: Univerzální zápor , Příklad: "Žádné kovy nejsou složené látky".
  • I: Zvláštní potvrzení , Příklad: "Některé kovy jsou křehké".
  • O: Zvláštní zápor , Příklad: "Některé kovy nejsou křehké".

John Venn (1834–1923) ve své kapitole V symbolické logiky z roku 1881 „Diagrammatic Representation“ komentuje pozoruhodný výskyt Eulerova diagramu:

"...z prvních šedesáti logických pojednání, vydaných v průběhu minulého století nebo tak nějak, která byla za tímto účelem konzultována: - poněkud náhodně, protože byly náhodou nejdostupnější: - zdálo se, že třicet čtyři se odvolalo na pomoc diagramy, téměř všechny využívají Eulerovské schéma." (Poznámka 1 strana 100)
Složený ze dvou stran 115–116 od Venna z roku 1881, který ukazuje jeho příklad, jak převést sylogismus tří částí do jeho typu diagramu. Venn nazývá kruhy „eulerovské kruhy“ (srov. Sandifer 2003, Venn 1881:114 atd.) v „eulerovském schématu“ (Venn 1881:100) „staromódních eulerovských diagramů“ (Venn 1881:113).

Ale přesto tvrdil, že „nepoužitelnost tohoto schématu pro účely skutečně obecné logiky“ (strana 100) a na straně 101 poznamenal, že „zapadá, ale špatně dokonce i se čtyřmi návrhy společné logiky, ke kterým se běžně používá." Venn končí svou kapitolu pozorováním ilustrovaným v příkladech níže – že jejich použití je založeno na praxi a intuici, nikoli na striktní algoritmické praxi:

"Ve skutečnosti... tyto diagramy nejenže nezapadají do běžného schématu výroků, které se používají k ilustraci, ale zdá se, že nemají žádné uznávané schéma výroků, ke kterým by mohly být konzistentně přidruženy." (str. 124–125)

Konečně se Venn ve své kapitole XX HISTORICKÉ POZNÁMKY dostává k zásadní kritice (v citaci níže uvedeno kurzívou); v Hamiltonově ilustraci si všimněte, že O ( konkrétní zápor ) a I ( konkrétní kladné ) jsou jednoduše otočeny:

„Nyní se dostáváme ke známým Eulerovým kruhům, které byly poprvé popsány v jeho Lettres a une Princesse d'Allemagne (Dopisy 102–105). k sobě navzájem, spíše než k nedokonalé znalosti těchto vztahů, které můžeme mít nebo si přejeme zprostředkovat, pomocí výroku. V souladu s tím nebudou zapadat do výroků běžné logiky, ale vyžadují vytvoření nové skupiny vhodné elementární věty.... Tento nedostatek musel být zaznamenán od prvního v případě konkrétního kladného a záporného čísla, protože pro oba se běžně používá stejný diagram, což dělá lhostejně dobře “. (přidáno kurzívou: strana 424)

(Sandifer 2003 uvádí, že Euler také provádí taková pozorování; Euler uvádí, že jeho číslo 45 (prostý průnik dvou kruhů) má 4 různé interpretace). Ať už je to jakkoli, vyzbrojen těmito pozorováními a kritikami, Venn pak demonstruje (str. 100–125), jak odvodil to, co se stalo známým jako jeho Vennovy diagramy , ze „...staromódních Eulerových diagramů“. Zejména uvádí příklad, znázorněný vlevo.

V roce 1914 Louis Couturat (1868–1914) označil termíny, jak je znázorněno na obrázku vpravo. Navíc označil i vnější oblast (zobrazenou jako a'b'c'). Stručně vysvětluje, jak používat diagram – je třeba vyškrtnout oblasti, které mají zmizet:

"VENNOVA metoda je přeložena do geometrických diagramů, které reprezentují všechny složky, takže abychom získali výsledek, potřebujeme pouze vyškrtnout (zastíněním) ty, které zmizely díky datům problému." (kurzíva přidána str. 73)

Vzhledem k Vennovým úkolům lze tedy nestínované oblasti uvnitř kruhů sečíst a získat pro Vennův příklad následující rovnici:

„Ne Y je Z a VŠECHNO X je Y: tedy žádné X je Z“ má rovnici x'yz' + xyz' + x'y'z pro nevyšrafovanou oblast uvnitř kruhů (ale není to úplně správné; viz. další odstavec).

Ve Vennovi se 0. člen, x'y'z', tj. pozadí obklopující kruhy, neobjevuje. Nikde se o tom nemluví ani neoznačuje, ale Couturat to ve své kresbě opravuje. Správná rovnice musí zahrnovat tuto nevystínovanou oblast zobrazenou tučně:

„Ne Y je Z a VŠECHNO X je Y: proto žádné X je Z“ má rovnici x'yz' + xyz' + x'y'z + x'y'z' .

V moderním použití Venn diagram obsahuje “krabice” to obklopí všechny kruhy; toto se nazývá vesmír diskursu nebo doména diskurzu .

Couturat nyní poznamenává, že přímým algoritmickým (formálním, systematickým) způsobem nelze odvodit redukované booleovské rovnice, ani neukazuje, jak dospět k závěru „Ne X je Z“. Couturat dospěl k závěru, že proces „má... vážné nepříjemnosti jako metoda řešení logických problémů“:

"Neukazuje, jak se data projevují zrušením určitých složek, ani neukazuje, jak zkombinovat zbývající složky tak, aby se dosáhlo požadovaných důsledků. Stručně řečeno, slouží pouze k prokázání jediného kroku v argumentaci, a to rovnice problému, neobchází se ani předchozích kroků, tj. „přehození problému do rovnice“ a transformace premis, ani kroků následujících, tj. kombinací, které vedou k různým důsledkům. je velmi málo použitelná, protože složky mohou být reprezentovány algebraickými symboly stejně dobře jako rovinnými oblastmi a v této formě se s nimi mnohem snáze manipuluje.“ (str. 75).

Záležitost tedy spočívala až do roku 1952, kdy Maurice Karnaugh (1924–) přizpůsobil a rozšířil metodu navrženou Edwardem W. Veitchem ; tato práce by se opírala o metodu pravdivostní tabulky přesně definovanou v dizertační práci Emila Posta z roku 1921 „Úvod do obecné teorie elementárních výroků“ a aplikaci výrokové logiky na logiku přepínání od (mimo jiné) Clauda Shannona , George Stibitze a Alan Turing . Například v kapitole "Booleovská algebra" Hill a Peterson (1968, 1964) prezentují oddíly 4.5ff "Teorie množin jako příklad booleovské algebry" a v nich představují Vennův diagram se stínováním a tak dále. Uvádějí příklady Vennových diagramů pro řešení příkladů problémů se spínacími obvody, ale končí tímto prohlášením:

"Pro více než tři proměnné je základní ilustrativní forma Vennova diagramu neadekvátní. Rozšíření jsou však možná, z nichž nejpohodlnější je Karnaughova mapa, o které pojednáme v kapitole 6." (str. 64)

V kapitole 6, části 6.4 „Reprezentace booleovských funkcí na Karnaughově mapě“ začínají:

"Karnaughova mapa 1 [ 1 Karnaugh 1953] je jedním z nejmocnějších nástrojů v repertoáru logických návrhářů. ... Karnaughovu mapu lze považovat buď za obrazovou formu pravdivostní tabulky, nebo za rozšíření Vennovy diagram." (str. 103–104)

Historie Karnaughova vývoje jeho metody „graf“ nebo „mapa“ je nejasná. Karnaugh ve svém roce 1953 odkazoval na Veitche 1951, Veitch odkazoval na Clauda E. Shannona 1938 (v podstatě na Shannonovu magisterskou práci na MIT ) a Shannon zase odkazoval mezi jinými autory logických textů na Couturat 1914. Ve Veitchově metodě jsou proměnné uspořádány do obdélníku nebo čtverec; jak je popsáno v Karnaughově mapě , Karnaugh ve své metodě změnil pořadí proměnných tak, aby odpovídaly tomu, co se stalo známým jako (vrcholy) hyperkrychle .

Vztah mezi Eulerovými a Vennovými diagramy

Příklady malých Vennových diagramů (vlevo) se stínovanými oblastmi představujícími prázdné množiny , které ukazují, jak je lze snadno převést na ekvivalentní Eulerovy diagramy (vpravo)

Vennovy diagramy jsou restriktivnější formou Eulerových diagramů. Vennův diagram musí obsahovat všech 2 n logicky možných zón překrytí mezi jeho n křivkami, které představují všechny kombinace zahrnutí/vyloučení jeho základních množin. Oblasti, které nejsou součástí množiny, jsou označeny černou barvou, na rozdíl od Eulerových diagramů, kde je příslušnost k množině indikována překrytím i barvou. Když počet sad překročí 3, Vennův diagram se stává vizuálně složitým, zvláště ve srovnání s odpovídajícím Eulerovým diagramem. Rozdíl mezi Eulerovým a Vennovým diagramem je vidět na následujícím příkladu. Vezměte tři sady:

Eulerovy a Vennovy diagramy těchto množin jsou:

V logickém prostředí lze použít modelově teoretickou sémantiku k interpretaci Eulerových diagramů v rámci vesmíru diskurzu . V níže uvedených příkladech Eulerův diagram znázorňuje, že množiny Zvíře a Nerost jsou disjunktní, protože odpovídající křivky jsou disjunktní, a také že množina Čtyři nohy je podmnožinou množiny Zvířat s. Vennův diagram, který používá stejné kategorie Animal , Mineral a Four Legs , tyto vztahy nezapouzdřuje. Tradičně je prázdnota množiny ve Vennových diagramech znázorněna stínováním v oblasti. Eulerovy diagramy představují prázdnotu buď stínováním, nebo nepřítomností oblasti.

Často je kladen soubor podmínek dobré formace; to jsou topologická nebo geometrická omezení uložená na strukturu diagramu. Může být například vynuceno propojení zón nebo může být zakázáno souběh křivek nebo více bodů, stejně jako tangenciální průnik křivek. V sousedním diagramu jsou příklady malých Vennových diagramů transformovány na Eulerovy diagramy sekvencemi transformací; některé mezilehlé diagramy mají souběžnost křivek. Tento druh transformace Vennova diagramu se stínováním na Eulerův diagram bez stínování však není vždy možný. Existují příklady Eulerových diagramů s 9 sadami, které nelze kreslit pomocí jednoduchých uzavřených křivek bez vytvoření nežádoucích zón, protože by musely mít nerovinné duální grafy.

Příklad: Eulerův až Vennův diagram a Karnaughova mapa

Tento příklad ukazuje Eulerovy a Vennovy diagramy a Karnaughovu mapu odvozující a ověřující dedukce „Žádná X jsou Z s“. Na obrázku a v tabulce jsou použity následující logické symboly:

  • 1 lze číst jako „pravda“, 0 jako „nepravda“
  • ~ pro NOT a zkráceno na ' při ilustraci mintermů, např. x' = definované NOT x,
  • + pro booleovský OR (z booleovské algebry : 0 + 0 = 0, 0 + 1 = 1 + 0 = 1, 1 + 1 = 1)
  • & (logické AND) mezi výroky; v mintermech se AND vynechává způsobem podobným aritmetickému násobení: např. x'y'z = definované ~x & ~y & z (z Booleovy algebry: 0·0 = 0, 0·1 = 1·0 = 0, 1·1 = 1, kde "·" je uvedeno pro srozumitelnost)
  • → (logická IMPLIKACE): čtěte jako POKUD ... POTOM ... nebo " IMPLIKUJE ", PQdefinováno NE P NEBO Q
Než bude moci být prezentován ve Vennově diagramu nebo Karnaughově mapě, musí být sylogismus Eulerova diagramu „Ne Y je Z , všechno X je Y “ nejprve přeformulován do formálnějšího jazyka výrokového počtu : „Není to tak, : Y AND Z' AND 'Pokud X , pak Y' “. Jakmile jsou výroky zredukovány na symboly a výrokovou formuli ( ~(y & z) & (x → y) ), lze sestrojit pravdivostní tabulku formule ; z této tabulky lze snadno vytvořit Vennovu a/nebo Karnaughovu mapu. Použitím sousedství "1" v Karnaughově mapě (označené šedými ovály kolem členů 0 a 1 a kolem členů 2 a 6) lze "redukovat" booleovskou rovnici příkladu, tj. (x'y'z' + x'y'z) + (x'yz' + xyz') na pouhé dva výrazy: x'y' + yz'. Ale prostředky pro vyvození představy, že „č. X je Z“, a jak se snížení vztahuje k tomuto odpočtu, z tohoto příkladu nevyplývá.

Daný navrhovaný závěr takový jak “ne X je Z ”, jeden může testovat zda to je nebo ne to je správná dedukce použitím pravdivostní tabulky . Nejjednodušší metodou je umístit počáteční vzorec nalevo (zkrátit jej jako P ) a (možnou) dedukce umístit napravo (zkrátit to jako Q ) a spojit oba s logickou implikací, tj . PQ , číst jako IF P THEN Q . Pokud vyhodnocení pravdivostní tabulky produkuje všechny 1 pod implikačním znaménkem (→, tzv. hlavní spojka ), pak PQ je tautologie . Vzhledem k této skutečnosti lze vzorec napravo (zkráceně Q ) "odpojit" způsobem popsaným pod pravdivostní tabulkou.

Vzhledem k výše uvedenému příkladu je vzorec pro Eulerův a Vennův diagram:

„Žádná Y jsou Z “ a „Všechna X jsou Y “: ( ~(y & z) & (x → y) ) = definováno P

A navrhovaný odpočet je:

"Žádné X nejsou Z ": ( ~ (x & z) ) = definované Q

Takže nyní vzorec, který má být vyhodnocen, může být zkrácen na:

( ~(y & z) & (x → y) ) → ( ~ (x & z) ): PQ
IF ( "Žádná Y jsou Z " a "Všechna X jsou Y " ) TAK ( "Žádná X jsou Z " )
Pravdivostní tabulka ukazuje, že vzorec ( ~(y & z) & (x → y) ) → ( ~ (x & z) ) je tautologie, jak ukazují všechny jedničky ve žlutém sloupci.
Náměstí # Venn, oblast Karnaugh X y z (~ (y & z) & (X y)) (~ (X & z))
0 x'y'z'   0 0 0   1 0 0 0 1 0 1 0 1 1 0 0 0
1 x'y'z   0 0 1   1 0 0 1 1 0 1 0 1 1 0 0 1
2 x'yz'   0 1 0   1 1 0 0 1 0 1 1 1 1 0 0 0
3 x'yz   0 1 1   0 1 1 1 0 0 1 1 1 1 0 0 1
4 xy'z'   1 0 0   1 0 0 0 0 1 0 0 1 1 1 0 0
5 xy'z   1 0 1   1 0 0 1 0 1 0 0 1 0 1 1 1
6 xyz'   1 1 0   1 1 0 0 1 1 1 1 1 1 1 0 0
7 xyz   1 1 1   0 1 1 1 0 1 1 1 1 0 1 1 1

V tomto bodě je výše uvedená implikace PQ (tj. ~(y & z) & (x → y) ) → ~(x & z) ) stále vzorcem a dedukce – „oddělení“ Q od PQ – nenastalo. Ale vzhledem k demonstraci, že PQ je tautologie, je nyní připravena fáze pro použití postupu modus ponens k „odpojení“ Q: „Žádná X nejsou Z “ a upustíme od termínů vlevo.

Modus ponens (neboli „základní pravidlo vyvozování“) se často píše takto: Dva termíny nalevo, PQ a P , se nazývají premisy (podle konvence spojené čárkou), symbol ⊢ znamená „výnosy“ (ve smyslu logické dedukce) a výraz vpravo se nazývá závěr :

PQ , PQ

Aby modus ponens uspěl, musí platit oba premisy P → Q a P . Protože, jak je ukázáno výše, premisa PQ je tautologie, „pravda“ je vždy platná bez ohledu na to, jak jsou x, y a z hodnoceny, ale „pravda“ je pouze případem P za těch okolností, kdy se P vyhodnotí jako „ true" (např. řádky 0 NEBO 1 NEBO 2 NEBO 6 : x'y'z' + x'y'z + x'yz' + xyz' = x'y' + yz').

PQ , PQ
  • tj.: ( ~(y & z) & (x → y) ) → ( ~ (x & z) ), ( ~(y & z) & (x → y) ) ⊢ ( ~ (x & z) )
  • tj.: POKUD „Žádná Y jsou Z “ a „Všechna X jsou YPAK „Žádná X jsou Z “, „Žádná Y jsou Z “ a „Všechna X jsou Y “ ⊢ „Ne X s jsou Z s"

Nyní je možné „oddělit“ závěr „Žádná X jsou Z “, možná jej použít v následné dedukci (nebo jako téma konverzace).

Použití tautologické implikace znamená, že existují další možné dedukce kromě „žádná X nejsou Z “; kritériem úspěšné dedukce je, že jedničky pod vedlejším hlavním spojovacím výrazem napravo zahrnují všechny jedničky pod hlavním spojovacím výrazem vlevo ( hlavní spojovací výraz je implikace, která vede k tautologii). Například v pravdivostní tabulce na pravé straně implikace (→, hlavní spojovací symbol) má sloupec s tučným písmem pod hlavním vedlejším spojovacím symbolem „ ~ “ všechny stejné jedničky, které jsou uvedeny tučně- čelní sloupec pod levým vedlejším hlavním spojovacím výrazem & (řádky 0 , 1 , 2 a 6 ), plus dva další (řádky 3 a 4 ).

Galerie

Council of Europe Schengen Area European Free Trade Association European Economic Area Eurozone European Union European Union Customs Union Agreement with EU to mint euros GUAM Central European Free Trade Agreement Nordic Council Baltic Assembly Benelux Visegrád Group Common Travel Area Organization of the Black Sea Economic Cooperation Union State Switzerland Iceland Norway Liechtenstein Sweden Denmark Finland Poland Czech Republic Hungary Slovakia Greece Estonia Latvia Lithuania Belgium Netherlands Luxembourg Italy France Spain Austria Germany Portugal Slovenia Malta Cyprus Ireland United Kingdom Croatia Romania Bulgaria Turkey Monaco Andorra San Marino Vatican City Georgia Ukraine Azerbaijan Moldova Armenia Russia Belarus Serbia Albania North Macedonia Bosnia and Herzegovina Montenegro Kosovo (UNMIK)Nadnárodní evropské orgány-en.svg
O tomto obrázku
Klikací Eulerův diagram [soubor] zobrazující vztahy mezi různými nadnárodními evropskými organizacemi a dohodami.

Viz také

Poznámky

Reference

Další čtení

Podle data zveřejnění:

externí odkazy