Halmazok és logika

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.

n különböző elem teljes rendezése n!; k elem sorrendes választása ismétlés nélkül n!/(n−k)!, ismétléssel nᵏ. Sorrend nélküli k elem választása C(n,k)=n!/[k!(n−k)!].

Ismétlődő elemek teljes rendezése n!/(r₁!…rₛ!), mert az azonos elemek belső cseréje nem ad új sorrendet.

(a+b)ⁿ=Σ C(n,k)aⁿ⁻ᵏbᵏ. Az együttható annak száma, hányféleképpen választunk k darab b-t az n tényezőből.

C(n,k)=C(n−1,k−1)+C(n−1,k): a kijelölt elem vagy benne van, vagy nincs a választásban. „Legalább egy” feltételnél gyakran könnyebb az összesből kivonni az egyet sem tartalmazó eseteket.

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=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.

Hat különböző könyv teljes sorrendje 6!. Három különböző tisztség betöltése hat emberből 6·5·4, mert a tisztségek megkülönböztetettek.

Háromtagú bizottság 6 emberből C(6,3)=6·5·4/3!, mert egy hármas hatféle sorrendje ugyanazt a bizottságot adja. Négy helyes kód tíz számjegyből ismétléssel 10⁴, ha a nulla kezdőjegy is megengedett.

Nyolc fiú és öt lány közül négyfős bizottságban legalább egy lány: C(13,4)−C(8,4). Pontosan két lány: C(5,2)·C(8,2).

Legalább két lány: a pontosan 2,3,4 lányos esetek összege. A „legalább” feltételt ne cseréld „pontosan”-ra.

C(n,k)=n!/[k!(n−k)!] nemnegatív egész n,k, 0≤k≤n mellett; 0!=1. C(n,0)=C(n,n)=1 és C(n,k)=C(n,n−k), mert kiválasztott és kimaradó elemek kiegészítik egymást.

A Pascal-háromszög szélei 1-ek; minden belső elem a két fölötte levő összege: C(n,k)=C(n−1,k−1)+C(n−1,k). A két esetet egy kijelölt elem beválasztása, illetve kimaradása adja.

Az n-edik sor szimmetrikus, összege 2ⁿ, mert egy n elemű halmaznak ennyi részhalmaza van: minden elem bekerül vagy kimarad. n=4 sora 1,4,6,4,1; összegük 16. Az (a+b)ⁿ kifejtésében az aⁿ⁻ᵏbᵏ tag együtthatója C(n,k), mert az n tényező közül k-ból választunk b-t.

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.