(->)
Implikáció: Csak akkor hamis, ha a B hamis az A igaza ellenére

(+)
Diszjunkció: Egyik vagy mindkettő igaz

(*)
Konjukció: Mindkét feltétel igaz

(/)
Negáció: Tagadás, thát hamis

(<->)
Ekvivalencia: Ha A igaz, B-nek is igaznak kell lennie VAGY A hamis, akkor B-nek is annak kell kennie (I-I/H-H)

Így egyszerűbben meglehet vizsgálni a teljes formula igazságát, valamint azt, hogy (8.) tautológia-e (minden végkimenet igaz)

Haladjunk a(z első, ha több van) legbelső zárójeltől kifelé, és vizsgáljuk meg, hogy mi a kimenet

Az igazságtáblázat részformulákból és azoknak igazságvizsgálatával készül el

Ha egy logikai kifejezésben ezeket felismerjük, egyszerűsítést lehetővé válik

Két vagy több formula ugyanazzal a jelentéstartalommal rendelkezik, téhát a kiértékelésük megegyezik

(6.)

1. Ennek meghatározásához felírjuk a két formula igazságtábláját (külön vagy egy táblába

2. Csak az a lényeg, hogy az teljes formulák kiértékelése megegyezik (ugyanazokban a sorokban jön ki igaz meg hamis (pl mindkettőnek fentről lefele I, I, N, N jön ki))

Pl. fenti kettő formula ekvivalens

Mivel a számítógép nem rendelkezik implikáció és ekvivalencia jelekkel, ezeket ezért kikell küszöbölni

A P(1) +...+ P(k) alakú és minden P(i) részformulákban az ítéletváltozók vagy negáltjaik negáltjaik legfeljebb egyszer szerepelhetnek

Teljes DNF: Minden P(i)-ben mind az n darab ítéletváltozó szerepel

3. Az adott sorhoz tartozó részformulát úgy kapjuk, hogy felírjuk a változókat, negáljuk, ha hamis az értéke

Egy formula kiértékelésekor minden sorban igaz érték szerepel

- egzisztenciális kvantor (van olyan, létezik)

- univerzális kvantor (minden, tetszőleges, az összes)

x(1), x(2)...x(n) - indivídumváltozók, mint vizsgálandó objektumegyedek

Van egy állításunk, annak alanyait és tárgyait (objektumait) kisbetűs indivídumváltozókká (pl x, y), az állítmányokat nagybetűs predikátumjelekké (pl M(x), A(x, y)) alakítjuk

A kvantor az utána álló legrövidebb részformulára vonatkozik

Logikai ekvivalenciák:

Mindig része az üres halmaz, az adott halmaz tagjainak lehetséges párosításai, valamint a teljes halmaz

4 elemű:
N = {1, 2, 3, 4}
{\0, {1}, {2}, {3}, {4}, {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}, {1, 2, 3, 4}} - 12 elem

Véges és végtelen megszámlálható halmazok esetén két halmaz akkor egyenlő, ha mindegyiknek ugyanannyi eleme van

N (természetes számok) halmaza megszámlálhatóan végtelennek ((Nˇ0)),
R (valós számok) hazmazát kontinuum számosságnak nevezzük
(c)

16. Számossága az elemszámot jelenti, egyszerűen szorozzuk össze a két halmaz elemszámát

Elempárok (relációk) keletkeznek, sorrend fontos

• egy reláció inverze definiálható az a^-1 jelöléssel, aminek következtében az elempárok helyet cserélnek - (a, b) lesz (b, a)

17. Megfeleltetés: A x B Descartes-szorzat részhalmazait A-ból (indulási) B-be (érkezési) menő megfeleltetésnek nevezzük

18. Az A^2 Descartes-négyzet vagy A x B Descartes szorzat esetén A részhalmazait nevezzük relációknak - görög ábécé kis betűivel jelöljük

Azt kell megvizsgálnunk, lehetőleg ábrázolással, hogy elindulva a ρ-ból eltudunk-e jutni a középső elemen keresztül a σ-ba.

20. Reláció inverze: egyszerűen az elempárok elemei felcserélődnik: (a, b)-ból (b, a) lesz

Reflexív: kapcsolatba van önmagával - bármelyik a € A-ra teljesül

Szimmetrikus: Ha a reláció teljesül, akkor az inverze is

Dichotom: Valamelyik reláció teljesül - egy halmaz két részhalmazának nincs közös eleme

Egy A-beli elem pontosan egy C-beli halmaznak lehet eleme

Minden ekvivalenciareláció szétválasztja az A halmazt különálló osztályokra és minden osztály egy ekvivalenciareláció ekvivalenciagyűjtője

Megfeleltetés: Két külömböző halmaz elemeit kapcsolja

• egyikből a másikba megy
• fordítva nem ugyanaz

Leképzés: Aϕ ⊆ A × B megfeleltetést A-ból B-be menő leképezésnek nevezünk, ha
bármely a ∈ A-ra létezik pontosan egy b ∈ B, amelyre (a, b) ∈ ϕ

Injektív: Két külömböző bemenet nem eredményezhet egynél több azonos kimenetet
(nyíldiagramon minden A-beli elemből pontosan egy nyíl indul ki és minden B-beli elembe legfeljebb egy nyíl mutathat)
(24.)

Szürjektív: A leképzés értékkészlete megegyezik az érkezés halmazával
(nyíldiagramon minden A-beli elemből pontosan egy nyíl indul ki és minden B-beli elembe mutat nyíl)

Végtelen elemszámú halmazok esetén használjuk a számosság megnevezést

|A| = |B|, ha létezik olyan bijekció f: A→B, amely minden a € A elemhez van b € B és fordítva

https://www.math.u-szeged.hu/~katai/dimat1_2020/DM07-lekep_20.pdf

Irányítattlan: Az összekötő kapcsolat mindkét oldalon fennál, mert az élek nem rendelkeznek iránnyal

G = (V, E) irányított vagy irányítatlan gráf, ahol az e az u és v csúcs közötti kapcsolatot jelent:
Irányított: e = (u, v) vagy uv
Irányítatlan: e = {u, v} vagy u→v

27. Példák: kapcsolati háló, számítógépes hálózat, városok úthálózata

Ha nincs ismétlődés az élsorozatban, akkor vonal (lehet zárt)

Ha nincs ismétlődés az csúcssorozatban, akkor vonal, zártság esetén kör (itt lehet ismétlődés)

G = (V, E) esetén v(0), e(1), v(1), . . . , v(k)−1, e(k), v(k) egy séta, ha v(0), v(1), ..., v(k) sorozat V-beli csúcsok egy lehetséges sorozata, valamint az e(i) € E élek végpontjai v(i-1) és v(i) minden i € {1, ..., k} esetén

Irányított esetén a bemeneti és kimeneti fok(szám) összfokát, vagyis az összfokot

Egy (minimálisan) összefüggő gráf, azaz bármely éle elhagyása után nem lesz összefüggő

Egy maximálisan körmentes gráf, tehát nincs benne kör, de bárhova új élt hozzáadva lenne

32. Összefüggőség: Két csúcs között van legalább egy út (bármelyik pontból ellehet jutni bármelyikbe)

31. G = (V, E) gráf esetén a csúcsok fok(szám)ainak összege megegyezik az élek számának kétszeresével

SUM(d(v)) = 2 * |E|
v € V

Jelölés: P(H)

Szimmetrikus differencia (háromszög): Mindkettő elemei, de nem a közösek