Halmazok, logika és gráfok

A∪B: legalább az egyikben; A∩B: mindkettőben; A\B: A-ban igen, B-ben nem. Ā=U\A.

De Morgan: az unió komplementere a komplementerek metszete, a metszet komplementere azok uniója. Ezt elemenként a „nem (P vagy Q)” állítás tagadásával ellenőrizheted.

|A∪B|=|A|+|B|−|A∩B|, mert a közös elemeket kétszer számoltuk. Három halmaznál a páronkénti metszeteket kivonjuk, a hármas metszetet visszaadjuk.

Az [a;b] zárt végpontokat, az ]a;b[ nyílt végpontokat jelöl; az egyenlőtlenség dönti el a befoglalást.

P⇒Q esetén P elégséges Q-hoz, Q szükséges P-hez. A megfordítás Q⇒P külön állítás.

A négyzet téglalap, ezért a négyzet tulajdonság elégséges a téglalap tulajdonsághoz, de nem szükséges. Az ekvivalencia a kétirányú következés.

A kontrapozíció ¬Q⇒¬P az eredetivel ekvivalens.

„Minden elemre P” tagadása: „létezik elem, amelyre nem P”. „Létezik P tulajdonságú elem” tagadása: „egyik elem sem P”.

A feltételes állítás tagadása P és nem Q. Egy univerzális állítást egyetlen ellenpélda cáfol, de néhány kedvező példa nem bizonyít.

A kezdő eset igazolása után feltételezzük az állítást n=k-ra, és ebből bizonyítjuk n=k+1-re. Az indukciós feltevés nem általános bizonyíték önmagában: meg kell mutatni az átmenetet.

Több kezdő eset is kellhet, ha a rekurzió több előző értéket használ.

A természetes és a páros természetes számok között n↦2n kölcsönösen egyértelmű megfeleltetés van: mindkettő megszámlálhatóan végtelen. A racionális számok is megszámlálhatók; a valós számok nem.

Cantor átlós érvelésében egy feltételezett felsorolás minden sorától eltérő tizedes számot alkotunk; a kettős tizedes alakot kerülő számjegyek biztosítják az eltérést.

A séta élek menti haladás; az útban a csúcsok nem ismétlődnek, a kör visszatér a kezdőponthoz más ismétlés nélkül. Összefüggő gráfban bármely két csúcs között van út.

A fa összefüggő és körmentes; n csúcsú fának n−1 éle van. Egy levél eltávolításával induktívan bizonyítható az élszám.

Teljes gráfban minden csúcspár össze van kötve: n(n−1)/2 él. A komplementerben pontosan a hiányzó élek szerepelnek.

Izomorf gráfok csúcsaik átnevezésével azonos szomszédsági szerkezetűek; az azonos fokszámsor szükséges, de nem elégséges. Legalább kétcsúcsú egyszerű gráfban két fokszám egyezik, mert a 0 és n−1 fokszám egyszerre nem fordulhat elő, így n csúcsra legfeljebb n−1 különböző érték jut.

A pozitív páros számokhoz n↦2n bijekció tartozik: minden páros számnak pontosan egy őse van. Az egész számokat 0,1,−1,2,−2,… sorrendben sorolhatjuk fel.

Pozitív racionális számoknál a p/q párokat p+q növekvő értéke szerint járjuk be, egy-egy átlón belül p növekvő sorrendjében. A már felsorolt törteket kihagyjuk.

Minden pozitív tört véges lépésben sorra kerül, és minden átló véges; ezért a pozitív racionális számok megszámlálhatók. A nulla és a negatív törtek beilleszthetők.

A véges halmaznak véges elemszáma van. ℕ, ℤ és ℚ megszámlálhatóan végtelen, a valós számok nem megszámlálhatóan végtelenek. Szemléltetés: egy feltételezett [0;1]-beli tizedestört-listában az n-edik szám n-edik jegyétől eltérő, 1 vagy 2 értékű jegyekből új szám készíthető.

Ez a szám a lista minden tagjától eltér legalább egy jegyben; a csak 1,2 jegyek kiküszöbölik a véges és csupa 9-es alak kettősségét. A lista ezért nem teljes.

Sétában csúcs és él is ismétlődhet; körséta ugyanabba a csúcsba érkezik. Útban nincs ismétlődő csúcs.

Kör legalább három élből álló zárt út egyszerű gráfban, csak a kezdő és végcsúcs azonos. Összefüggő gráf bármely két csúcsát út köti össze.

Teljes gráf minden csúcspárt összeköt; élszáma C(n,2). Komplementer azonos csúcsokon pontosan a hiányzó éleket tartalmazza.

Izomorfia olyan csúcsbijekció, amely a szomszédságot mindkét irányban megtartja.

Fa összefüggő, körmentes gráf. Legalább kétcsúcsú fában egy leghosszabb út végpontjának csak egy szomszédja lehet: másik szomszéd vagy kört adna, vagy meghosszabbítaná az utat.

E levél elhagyása kisebb fát ad. Egypontú fa 0 élű, indukcióval n csúcsú fa n−1 élű.

Legalább kétcsúcsú egyszerű gráfban a fokszámok 0,…,n−1 lehetnek, de 0 és n−1 egyszerre nem: az utóbbi csúcs mindenkivel szomszédos. Így n csúcsra legfeljebb n−1 különböző fokszám jut, legalább két fokszám egyenlő.

Az n≥2 feltétel szükséges: az egypontú gráfban nincs két különböző csúcs.

A=B pontosan akkor, ha A⊆B és B⊆A: ugyanazok az elemeik. A⊆B mellett egyenlőség is lehetséges; valódi részhalmaznál A≠B.

Az üres halmaznak nincs eleme, ezért ∅⊆A minden A-ra: nincs az állítást cáfoló elem. Ebből nem következik ∅∈A; az csak akkor igaz, ha az üres halmazt külön elemként tartalmazza A.

Például ∅∈{∅,2}, de ∅∉{2,4}.

Véges halmaz elemei egy nemnegatív egész számmal megszámlálhatók; az üres halmaz számossága 0. Végtelen halmaz nem sorolható fel véges sok elemmel: a pozitív páros egészek közül bármely véges lista legnagyobb eleménél 2-vel nagyobb is páros.

Az {1,2,3} számossága 3; az intervallumok általában végtelenek. A [2;2]={2} egy elemű, a ]2;2[ üres.

U rögzített alaphalmazban A komplementere U\A: az U-beli, A-ban nem szereplő elemek. U megváltoztatása megváltoztathatja a komplementert.

Ha U={1,2,3,4,5}, A={2,4}, akkor Ā={1,3,5}. Ha az alaphalmaz a pozitív egészek halmaza, minden további pozitív páratlan és a 4-nél nagyobb páros is a komplementerbe kerül.

x∈A∩B jelentése x∈A és x∈B. x∈A∪B azt jelenti, hogy legalább az egyik tagság igaz; a közös elemeket egyszer írjuk. x∈A\B azt jelenti, hogy A-ban igen, B-ben nem. Az elemeken végzett igazságvizsgálat műveleti azonosságok ellenőrzésére is alkalmas.

Az x+y=2 határhoz két pont elég: (0;2) és (2;0). Az (0;0) pont 0≤2 miatt a megengedett oldalon van; azt az oldalt satírozzuk.

A ≤ és ≥ jel mellett a határvonal is hozzátartozik, folytonos vonal jelzi. A < és > jel mellett kimarad, szaggatott vonal jelzi.

Határon fekvő próbapont nem dönti el az oldalt.

Az x≥0 és y≥0 a tengelyekkel együtt az első síknegyedet adja. Ha x+y≤2 is kell, a (0;0),(2;0),(0;2) csúcsú zárt háromszöglap a megoldás.

Az „és” metszet, a „vagy” unió. Például x=0 vagy y=0 a két teljes koordinátatengely uniója.

x²+y²=4 az origó középpontú, 2 sugarú körvonal; x²+y²≤4 a körlap. Az 1<x²+y²≤4 körgyűrű: a belső 1 sugarú határvonal kimarad, a külső 2 sugarú határvonal benne van.

A négyzetösszeg a távolság négyzete, ezért a 4 értékből 2 a sugár.

A rajzot a feltételekkel ellenőrizzük: válassz egy belső, egy külső és egy határpontot. A koordinátatengelyek beosztását és az egységet jelöld; a pontos egyenlőség eldöntéséhez a koordinátákat helyettesítsd be, ne a képernyős rajzból becsülj.

Egy csak egy halmazban szereplő elem egyszer számít. Egy pontosan kettőben levő elem 2−1=1-szer.

Egy mindháromban levő elem előbb 3-szor, a három páronkénti metszet kivonása után 0-szor; a hármas metszet hozzáadása után egyszer. Így minden unióbeli elem egyszer számít.

A∩B tartalmazza a C-be is tartozó elemeket. A csak A és B közös részének száma |A∩B|−|A∩B∩C|.

Pontosan két halmazban levők összesen a három páronkénti metszet számosságának összege mínusz a hármas metszet háromszorosa. Legalább kettőnél a hármas rész csak egyszer számítson: a páronkénti összegből a hármas rész kétszeresét vonjuk ki.

Csak A: |A|−|A∩B|−|A∩C|+|A∩B∩C|. A hármas részt az előző kivonások kétszer érintik, ezért egyet visszaadunk.

Egyik sem: |U|−|A∪B∪C|. A kizárólagos részek, a három pontosan-kettő rész, a hármas rész és a külső rész összege |U| legyen.

A „ha n osztható 4-gyel, akkor páros” állítás az osztható esetekre ír elő következményt; a nem osztható esetekre nem állít párosságot vagy páratlanságot. n=6-nál a feltétel hamis, a következmény igaz, az implikáció igaz. n=5-nél mindkettő hamis, az implikáció szintén igaz. A matematikai „vagy” alapértelmezésben megengedő; a hétköznapi „teát vagy kávét” kontextusban gyakran kizáró választást jelent.

P⇔Q jelentése P⇒Q és Q⇒P együtt. „Az egész n páros akkor és csak akkor, ha n² páros.”

Ha n=2k, akkor n²=2·2k². Ha n páratlan, n=2k+1, négyzete 2(2k²+2k)+1 páratlan; így páros négyzet esetén n nem lehet páratlan.

Ezzel mindkét irányt igazoltuk. A „4 osztja n-et ⇒ n páros” megfordítása hamis; n=6 ellenpélda.

„Minden egész n-re P(n)” tagadása „van egész n, amelyre nem P(n)”. „Van egész n-re P(n)” tagadása „minden egész n-re nem P(n)”.

Az alaphalmaz ugyanaz marad. „Minden pozitív egésznek van nála nagyobb pozitív egész” igaz: n-hez n+1 választható.

Tagadása: „van pozitív egész, amelynél nincs nagyobb pozitív egész”; ez hamis.

Az A∩B tagság P és Q, az A∪B tagság P vagy Q, A\B tagság P és nem Q. Az Ā∩B̄ tagság nem P és nem Q, ezért (A∪B)̄=Ā∩B̄.

A (A∩B)̄=Ā∪B̄ azonosság a „nem (P és Q)” megfelelője. A komplementerekhez közös U alaphalmaz kell.

Ha a=2r+1 és b=2s+1 páratlan egészek, a+b=2(r+s+1), tehát páros: direkt bizonyítás. Ha n² páros és n páratlanságát feltesszük, n=2k+1 miatt n²=2(2k²+2k)+1 páratlan, ellentmondás; ezért n páros.

Ez indirekt bizonyítás, illetve a kontrapozíció alkalmazása. Az alaphalmaz mindkét esetben az egészek halmaza.

Hat egész számot 5-tel osztva csak 0,1,2,3,4 maradékot kaphatunk. Legalább két számnak azonos a maradéka: a=5r+t,b=5s+t.

Különbségük 5(r−s), tehát 5-tel osztható. Nem szükséges megmondani, melyik két szám; a következtetés minden hatos választásra igaz.

Öt számra ez nem garantált: 0,1,2,3,4 ellenpélda.

Bizonyítsuk 1+3+…+(2n−1)=n²-et pozitív egész n-re. n=1-re 1=1². Ha n=k-ra igaz, a következő páratlan számot hozzáadva k²+(2k+1)=(k+1)².

Tehát k-ról k+1-re továbbadjuk az állítást, így minden n≥1-re igaz. A kezdő eset nélkül az átmenet nem indítja el az igazság továbbadását.

P⇒Q-ban P elégséges Q-hoz, Q szükséges P-hez. Ha a megfordítás is igaz, szükséges és elégséges kapcsolatot kapunk.

A „n² páros ⇔ n páros” egész n-re igaz; valós n-re a párosság fogalma itt nem alkalmazható. Egyetlen ellenpélda cáfolhat általános állítást, de sok jó számpélda sem helyettesíti a teljes bizonyítást.

A csúcs fokszáma az oda illeszkedő élvégek száma. Minden irányítatlan él két élvéget ad, így Σd(v)=2e.

Hurokél is kettőt ad ugyanannak a csúcsnak; egyszerű gráfban nincs hurok és többszörös él. A fokszámösszeg szükségképpen páros.

Ez szükséges feltétel, de egy fokszámlista létezését önmagában nem bizonyítja.

Négy csúcsnál a 3,3,1,1 fokszámlista összege 8, mégsem realizálható egyszerű gráffal. A két 3 fokú csúcs mindkét 1 fokúval is szomszédos lenne, ezért azok fokszáma legalább 2 volna.

A fokszámok egyenként legfeljebb n−1-ek, de ezt is teljesítő páros összeg még nem elég.

V={A,B,C,D}, élek AB,AC,BC,CD. Fokszámok: A:2, B:2, C:3, D:1; összegük8, az élszám4.

A–C–D út A és D közt; A–B–C–A kör. A rajzon az AB és CD él kereszteződése nem új csúcs, ha nincs új csúcsként megjelölve.

A csúcsok helye és az élek görbülete nem változtatja meg a szomszédságot.

Bajnokságban minden csapat egy csúcs, minden lejátszott páros mérkőzés egy él; a fokszám a csapat mérkőzésszáma. Kémiai szerkezeti modellben a csúcs atom, az él kötés lehet, de a kötéstípushoz további jelölés kell.

A gráf csak az előre meghatározott kapcsolatot tárolja: a barátság és a közös osztályba járás más élhalmazt ad ugyanazon embereken.

Az AB,BC,CA,CD élű gráfban A–B–C–A kör és körséta; A–B–C–B–A körséta, de nem kör; A–C–D út és séta. A–D nem séta, mert nincs AD él.

Összefüggő gráfban bármely két csúcs között van út. Fa összefüggő és körmentes gráf; a körmentes, de nem összefüggő gráf nem fa.

Az n csúcsú teljes gráf minden különböző csúcspár között pontosan egy élt tartalmaz. Élszáma C(n,2)=n(n−1)/2, mert egy él rendezetlen csúcspár.

Egy egyszerű gráf komplementere ugyanazokat a csúcsokat tartalmazza, és pontosan az eredetiben hiányzó különböző csúcspárokat köti össze. Eredeti és komplementer élszáma együtt C(n,2); hurokél egyikbe sem kerül.

Két gráf izomorf, ha van csúcsaik közt olyan bijekció, amely az élkapcsolatot mindkét irányban megőrzi. Az AB,BC,CD út és az XY,YZ,ZW út izomorfiája A↦X,B↦Y,C↦Z,D↦W.

Azonos fokszámsor szükséges, de nem elég: a hatcsúcsú kör és két különálló háromszög minden fokszáma2, de csak az első összefüggő. Egy valódi izomorf bijekció konkrét igazolása erősebb a néhány invariáns egyezésénél.

Egypontú fa élszáma0. Legalább kétcsúcsú fában egy leghosszabb út végpontja levél: további szomszédja vagy kört hozna létre, vagy hosszabb utat adna.

A levél és egyetlen éle eltávolításával összefüggő, körmentes kisebb gráf marad. Ha az n−1 csúcsú fa n−2 élű, visszaadva a levelet n−1 él keletkezik.

Így indukcióval minden n csúcsú fa n−1 élű. Fordítva az n−1 élszám egyedül nem garantál fát: háromszög és izolált csúcs négy csúcson három élű, de nem fa.

√(x−1) valós függvényének tartománya[1;∞[. Az(x−2)(x+3)=0 megoldáshalmaza{−3;2}.

A kör adott középponttól adott távolságú pontok halmaza. Kockán páros esemény{2,4,6}⊆Ω.

Az unió és metszet logikai vagy/és, illetve eseményösszeg/szorzat jelentést kap; a feltétel és a választott alaphalmaz mindig számít.

Egy függvény A→B olyan kapcsolat, amely A minden eleméhez B pontosan egy elemét rendeli. Leírható rendezett párok halmazaként; például{(1,2),(2,4),(3,6)}.

Matematikai struktúrában a hordozó halmazhoz műveletek/relációk és feltételek járulnak. A modern alapozás szabályozza a megengedett halmazképzést; nem állítjuk, hogy bármely leírt tulajdonság egy korlátlan „mindenből” halmazt ad.

A részhalmaz és elem reláció eltér:1∈{1,2}, de{1}⊆{1,2}.