Eulerův diagram

Euler diagram  je prostředkem pro znázornění schematického  ze sad a vztahů uvnitř nich. První použití „euleriánských kruhů“ se běžně připisuje švýcarskému matematikovi Leonhardovi Eulerovi (1707–1783). Úzce souvisí s Vennovými diagramy .

Vennovy a Eulerovy diagramy byly začleněny do výuky teorie množin v moderní matematice v 60. letech 20. století. Od té doby byly přijaty také v jiných oblastech učebních osnov, jako je čtení.

Přehled

Eulerovy diagramy jsou tvořeny jednoduchými uzavřenými křivkami (obvykle kruhy ) v rovině, která představuje množiny . Velikosti nebo tvary křivek nejsou důležité: význam diagramu je ve způsobu, jakým se kruhy překrývají. Prostorové vztahy mezi oblastmi ohraničenými každou křivkou odpovídají teoretickým vztahům s množinami ( průnik , podmnožiny a disjunkce).

Každá Eulerova křivka rozděluje rovinu na dvě oblasti nebo „zóny“: interiér, který symbolicky představuje prvky obsažené v sadě, a exteriér, který představuje všechny prvky, které nejsou členy jednoho celku. Křivky, jejichž vnitřní zóny se neprotínají, představují nesouvislé množiny . Dvě křivky, jejichž vnitřní zóny se protínají, představují množiny, které mají společné prvky; oblast uvnitř dvou křivek představuje množinu prvků společných pro dvě množiny ( průsečík množin). Křivka, která je zcela obsažena ve vnitřní oblasti jiné, představuje její podmnožinu .

Vennovy diagramy jsou přísnější formou Eulerových diagramů. Vennův diagram musí obsahovat 2 n možných zón odpovídající počtu kombinací zahrnutí nebo vyloučení v každé ze sad. Oblasti, které nejsou součástí sady, jsou označeny černou barvou, na rozdíl od Eulerových diagramů, kde je členství v sadě indikováno překrytím i barvou. Když se počet sad zvýší na více než 3, Vennův diagram se stane vizuálně složitým, zejména ve srovnání s odpovídajícím Eulerovým diagramem. Rozdíl mezi Vennovými a Eulerovými diagramy lze vidět v následujícím příkladu. Nebo tři sady:

Vennovy a Eulerovy diagramy těchto sad jsou:

V logickém rámci lze teoretickou sémantiku interpretovat Eulerovy diagramy ve vesmíru diskurzu . Ve výše uvedených příkladech ukazuje Eulerův diagram, že sady zvířat a minerálů jsou disjunktní, protože odpovídající křivky jsou disjunktní a že sada čtyř nohou je podmnožinou sady zvířat . Vennův diagram, který používá stejné kategorie zvířat , minerálů a čtyřnohých , tyto vztahy nezahrnuje. Vakuum sestavy ve Vennově diagramu je tradičně představováno stínováním příslušné oblasti. Eulerovy diagramy představují prázdnotu, buď zastíněním, nebo absencí oblasti.

Dějiny

Sir William Hamilton ve své posmrtně vydané knize Přednášky o metafyzice a logice (1858-1860) tvrdí, že použití kruhů za účelem „srozumitelnosti ... abstrakce logiky“ ( str.  180 ) nepochází od Leonharda Paula Euler (1707-1783), ale spíše Christian Weise  (in) (1642-1708) ve svém Nucleus Logicae Weisianae, který se objevil v roce 1712 posmrtně. Odkazuje na dopisy od Eulera německé princezně [část ii., Písmeno XXXV., Ed. Cournot. - ED].

V Symbolické logice z roku 1881, v kapitole V („Schématické znázornění “), John Venn komentuje pozoruhodnou prevalenci Eulerova diagramu:

"Z prvních šedesáti logických pojednání vydaných během minulého století, které byly za tímto účelem konzultovány: - poněkud náhodně, protože byly nejdostupnější: - zdálo se, že třicet čtyři vyžaduje pomoc diagramů, téměř všechny tyto využívají Eulerianův diagram. "

- (Poznámka 1 s.  100 )

Tvrdil však „nepoužitelnost tohoto diagramu z důvodu velmi obecné logiky“ ( str.  100 ). Venn končí svou kapitolu pozorováním ilustrovaným v níže uvedených příkladech, že jejich použití je založeno na praxi a intuici, nikoli na přísné algoritmické praxi :

"Ve skutečnosti ... tyto diagramy nejenže neodpovídají (sic) běžnému diagramu, ale nezdá se, že by měly uznávaný systém propozic, se kterými by mohly být neustále spojovány." "

- ( str.  124-125 )

V moderním použití obsahuje Vennův diagram „krabici“, která obklopuje všechny kruhy a představuje vesmír řeči .

Couturat nyní poznamenává, že v algoritmické (formální systematice) přímým způsobem nelze čerpat redukované booleovské rovnice ani důkaz k závěru „Ne X je Z“. Couturat dospěl k závěru, že proces „má ... vážné nevýhody jako metoda řešení logických problémů“  :

"Neukazuje, jak jsou data vystavena zrušením určitých složek, ani jak kombinovat zbývající složky tak, aby bylo dosaženo požadovaných důsledků." Stručně řečeno, slouží pouze k představení jednoho kroku argumentu, a to rovnice problému. Má tedy velmi malé využití, protože složky mohou být reprezentovány algebraickými symboly i oblastmi a v této formě je jejich zpracování mnohem snazší. "

- ( str.  75 )

V roce 1952 Maurice Karnaugh upravil a vyvinul metodu navrženou Edwardem W. Veitchem  (en)  ; tato práce je založena na metodě pravdivostních tabulek přesně definované v roce 1921 v práci Emila Posta Úvod do obecné teorie elementárních výroků a aplikace výrokové logiky na logiku obvodů (mimo jiné) Claude Shannon , George Stibitz  (in) a Alan Turing . Například v kapitole „Booleova algebra“ uvádějí Hill a Peterson (1968, 1964) části 4.5ff „teorie množin jako příklad booleovské algebry“ a v ní představují Vennův diagram s stínování. Uvádějí příklady Vennových diagramů k řešení například problémů s okruhy, ale končí tímto tvrzením:

"Pro řadu proměnných větších než tři již ilustrační forma Vennova diagramu není vhodná." Rozšíření jsou možná, nejvhodnější je však Karnaughova tabulka, o níž pojednává kapitola 6. “

- ( str.  64 )

V kapitole 6, části 6.4 („Karnaughovo mapové znázornění booleovských funkcí“) začínají:

"Aplikace Karnaugh 1 [ 1 Karnaugh 1953] je jedním z nejmocnějších nástrojů v repertoáru logiky ... Karnaughovu tabulku lze chápat buď jako obrazovou formu pravdivé tabulky, nebo jako rozšíření Vennovy diagram. "

- ( str.  103-104 )

Historie Karnaughova vývoje jeho stolu je nejasná. Karnaugh ve svém článku z roku 1953 odkazuje na Veitch 1951 , Veitch odkazuje na Shannona 1938 (v podstatě Shannonova diplomová práce na MIT ) a Shannon zase odkazuje, kromě jiných autorů logických textů, na Couturat 1914 . Ve Veitchově metodě jsou proměnné uspořádány do obdélníku nebo čtverce; jak je popsáno v Karnaughově tabulce , Karnaugh změnil pořadí proměnných v jeho metodě tak, aby odpovídalo tomu, co je nyní známé jako hyperkrychle.

Příklad: Euler-Vennův diagram a Karnaughův stůl

Tento příklad ukazuje Eulerovy diagramy Venna a Karnaugha ověřující dedukci „no X is Z“. V následující tabulce jsou použity následující logické symboly:

1 lze číst jako „true“, 0 jako „false“; ~ pro NO a ve zkratce „. Například x '= definováno  NE x; + pro logické OR (z booleovské algebry  : 0 + 0 = 0, 0 + 1 = 1 + 0 = 1, 1 + 1 = 1); & ( Logické AND ) mezi propozicemi; někdy je vynechán stejným způsobem jako znaménko násobení: například x'y'z = definované  ~ x & ~ y & z (z booleovské algebry: 0 * 0 = 0, 0 * 1 = 0, 1 * 0 = 0, 1 * 1 = 1, kde * údaj pro přehlednost); → ( logická ZAPOJENÍ ): čte se IF ... PAK ... nebo „ZAPOJENO“, P → Q = definováno  NE P NEBO Q.

Vezmeme-li v úvahu závěr nabízený jako „Ne X je Z“, lze pomocí tabulky pravdivosti vyzkoušet, zda je dedukce správná . Nejjednodušší metodou je dát vzorec nalevo (zkratka „P“) a dát odpočet (možný) napravo (zkratka „Q“) a spojit je díky logické implikaci, konkrétně P → Q, čten jako IF P POTOM Q. Pokud vyhodnocení pravdivostní tabulky vyprodukuje pod znamením implikace pouze 1 s, pak P → Q je tautologie . Vzhledem k této skutečnosti můžeme „  oddělit  “ vzorec vpravo, jak je popsáno níže v tabulce pravdivosti.

Vzhledem k výše uvedenému příkladu je vzorec pro Eulerovy a Vennovy diagramy:

„No Y is Z“ a „All X is Y“: (~ (y & z) & (x → y)) = definované  P

a navrhovaný odpočet je:

„No X is Z“: (~ (x & z)) = definované  Q

Takže vzorec, který má být hodnocen, lze nyní zkrátit:

(~ (y & z) & (x → y)) → (~ (x & z)): P → Q KDYŽ  („Ne Y je Z“ a „Vše X je Y“)  POTOM  („Ne X je Z“). Tabulka pravdivosti ukazuje, že vzorec (~ (y & z) & (x → y)) → (~ (x & z)) je tautologie, jak je naznačeno všemi 1 s ve žlutém sloupci
 # Venn, Karnaugh  X y z (~ (r & 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 Y Z ' 0 1 0 1 1 0 0 1 0 1 1 1 1 0 0 0
3 X Y Z 0 1 1 0 1 1 1 0 0 1 1 1 1 0 0 1
4 X Y Z ' 1 0 0 1 0 0 0 0 1 0 0 1 1 1 0 0
5 X Y Z 1 0 1 1 0 0 1 0 1 0 0 1 0 1 1 1
6 X Y Z ' 1 1 0 1 1 0 0 1 1 1 1 1 1 1 0 0
7 X Y Z 1 1 1 0 1 1 1 0 1 1 1 1 0 1 1 1

V tomto bodě je výše uvedená implikace P → Q (~ (y & z) & (x → y)) → ~ (x & z)) stále vzorcem a dedukce - „oddělení“ Q od P → Q - neuskutečnilo se. Ale vzhledem k důkazu, že P → Q je tautologie, je dalším krokem postup modus ponens za  účelem „odpojení“ Q: „Ne X je Z“ a rozdělení výrazů vlevo.

Tyto modus ponens (nebo „základní pravidlo inference“ ) je často uvedeno následovně: dva termíny na levé straně, „P → Q“ a „P“, se nazývají  prostor (podle konvence jsou spojeny čárkou), symbol ⊢ znamená „dokázat“ (ve smyslu logické dedukce) a termín vpravo se nazývá závěr  :

P → Q, P ⊢ Q.

Aby modusové poneny uspěly, musí být obě premisy P → Q a P pravdivé . Protože, jak bylo prokázáno výše, předpoklad P → Q je tautologie, „pravda“ je vždy případ, bez ohledu na to, jaké hodnoty x, y a z mají, ale „pravda“ nebude platit pro P v za těchto okolností pouze tehdy, když P bude hodnoceno jako „pravdivé“ (například sloupce 0 NEBO  1 NEBO 2 NEBO  6: x'y'z '+ x'y'z + x'yz' + xyz '= x' y '+ yz ').

P → Q, P ⊢ Q to znamená: (~ (y & z) & (x → y)) → (~ (x & z)), (~ (y & z) & (x → y)) ⊢ (~ (x & z)) tj. KDYŽ „Ne Y je Z“ a „Vše X je Y“ POTOM „Ne X je Z“ („Ne Y je Z“ a „Vše X je Y“ ⊢ „Ne X je Z“).

Nyní máme možnost „oddělit“ závěr „No X is Z“, který lze použít pro pozdější odpočet.

Použití tautologické implikace znamená, že kromě „No X is Z“ existují i ​​další možné dedukce.

Galerie

Poznámky a odkazy

(fr) Tento článek je částečně nebo zcela převzat z článku anglické Wikipedie s názvem „  Eulerův diagram  “ ( viz seznam autorů ) .

Podívejte se také

Související články

Bibliografie

Řazeno podle data vydání:

externí odkazy