Please enable JavaScript.
Coggle requires JavaScript to display documents.
Első blokk - Coggle Diagram
Első blokk
Ítéletkalkulus 1-8
Műveletek
(->)
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)
Formulák lehetnek
Ítéletváltozók
Ítéletváltozók műveletekkel (Pl. /F, F*G, F+G)
Felső kettő véges szokszori alkalmazása
Igazságtáblázat
Így egyszerűbben meglehet vizsgálni a teljes formula igazságát, valamint azt, hogy
(8.)
tautológia-e (minden végkimenet igaz)
Leírjuk az ABC igaz-hamis kimenetkombinációit
Haladjunk a(z első, ha több van) legbelső zárójeltől kifelé, és vizsgáljuk meg, hogy mi a kimenet
/B
(/B) + C
B + ((/B) + C)
Végül jöhet az egészé
Az
igazságtáblázat
részformulákból és azoknak igazságvizsgálatával készül el
De Morgan-azonosságok
Augustus De Morgan
Ha egy logikai kifejezésben ezeket felismerjük, egyszerűsítést lehetővé válik
5-6. Formulaekvivalencia
Két vagy több formula ugyanazzal a jelentéstartalommal rendelkezik, téhát a kiértékelésük megegyezik
(6.)
Ennek meghatározásához felírjuk a két formula igazságtábláját (külön vagy egy táblába
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
DNF
Mivel a számítógép nem rendelkezik
implikáció
és
ekvivalencia
jelekkel, ezeket ezért kikell küszöbölni
Írjuk fel az igazságtábláját
Nézzük meg, hol igazak az implikációk és az ekvivalenciák
Az adott sorhoz tartozó részformulát úgy kapjuk, hogy felírjuk a változókat, negáljuk, ha hamis az értéke
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
(/A
*
B
*
/C) + (A
*
B
*
/C) - ez teljes
A + (A
*
/A)
Tautológia
Egy formula kiértékelésekor minden sorban igaz érték szerepel
Nem feltétlen függ össze a hosszával
Igazságtáblával könnyen ellenőrizhető
15-22. Relációk
15-17. Descartes-szorzat
Minden elemet összepárosítunk mindegyikkel
Legyen A = {1, 2, 3}
B = {x, y}
A x B = {(1x), (1y), (2x), (2y), (3x), (3y)}
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)
Megfeleltetés
: A x B Descartes-szorzat részhalmazait A-ból (indulási) B-be (érkezési) menő megfeleltetésnek nevezzük
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
Relációszorzat
Legyen ρ és σ relációnk
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.
Reláció inverze: egyszerűen az elempárok elemei felcserélődnik: (a, b)-ból (b, a) lesz
Tulajdonságok
https://www.math.u-szeged.hu/~katai/dimat1_2018/00DiMat1.pdf
14. oldal
Reflexív
: kapcsolatba van önmagával - bármelyik a € A-ra teljesül
Szimmetrikus
: Ha a reláció teljesül, akkor az inverze is
Tranzitív
: Ha (a, b), (b, c) teljesül, akkor (a, c) is
Antiszimmetrikus
: A reláció az inverzével nem teljesül
Dichotom
: Valamelyik reláció teljesül - egy halmaz két részhalmazának nincs közös eleme
Ha nem reflexív, nem lehet dichotom
Ekvivalencia
: RSzT
Részben rendezés
: RAT
Teljes rendezés
: RATD
Osztályozás
Legyen egy A halmaz, ekkor létrejön egy
C
halmaz, ha...
Nem üres
Részhalmazokból áll
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
23-25. Leképzések
Reláció
: Egy adott halmaz elemei közötti kapcsolat
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, szürjektív, bijektív
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)
Bijektív
: injektív és szürjektív
Számosság
Végtelen elemszámú halmazok esetén használjuk a számosság megnevezést
Ha létezik A→B bijektív leképzés
|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
26-32. Gráfok
Irányítottság
Irányítattlan
: Az összekötő kapcsolat mindkét oldalon fennál, mert az élek nem rendelkeznek iránnyal
Irányított
: Az élek 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
Példák: kapcsolati háló, számítógépes hálózat, városok úthálózata
Séta
"Végigmegyünk" a gráf csúcsain megadott sorozatban
Zárt séta
, ha az indulási pont megegyezik az érkezési ponttal, külömben
nyílt séta
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
Szomszédság
X ⊆ V csúcshalmaz szomszédságát N(X)-el jelöljük
Valamelyik X halmazbeli csúccsal összevannak kötve éllel
Közvetlen összekötöttséget jelent
Fok(szám)
Irányítatlan
esetén a csatlakozó élek száma
Irányított
esetén a
bemeneti
és
kimeneti
fok(szám) összfokát, vagyis az összfokot
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
Fák
Egy (minimálisan) összefüggő gráf, azaz bármely éle elhagyása után nem lesz összefüggő
V = E - 1
Egy maximálisan körmentes gráf, tehát nincs benne kör, de bárhova új élt hozzáadva lenne
Egy körmentes gráfot
erdő
nek nevezünk.
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)
Halmazok 11-13
Hatványhalmaz
Egy adott halmaz összes részhalmazát tartalmazza
Mindig része az üres halmaz, az adott halmaz tagjainak lehetséges párosításai, valamint a teljes halmaz
H = {1, 2, 3} hatványhalmaza:
{ \0, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}
Tehát 8 eleme van 3 elemű halmaz hatványhalmazának
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
Jelölés:
P
(H)
De Morgan azonosságok
Számosság
Véges és végtelen megszámlálható halmazok esetén két halmaz akkor egyenlő, ha mindegyiknek ugyanannyi eleme van
Bijekció: halmaz elemeinek párba állítása
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)
14.
Z (egész számok halmaza) = N
Z != R
Műveletek
Unió
: Mindkettőnek eleme (közössek is)
Metszet
: Valamelyiknek eleme
Külömbség
: Nem eleme a \ bal oldalán lévőnek
Szimmetrikus differencia (háromszög)
: Mindkettő elemei, de nem a közösek
Komplementer
: Minden másnak eleme - U-nak
9-10. Predikátumkalkulus
Formulák
Szimbólumok
Ítéletkalkulusbeliek és ","
- 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
Formalizálás
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
Tagadás
Logikai ekvivalenciák:
Tehát "Minden"-nél "Van olyan, amelyik nem",
"Van olyan"-ból "Semelyik", vagyik "Nincs olyan"
Többféleképpen is lehet negálni
Az egész formulát
Az egyik részformulát és a megfelelő "vagy"-ot
"és"-é cseréljük és fordítva
A kvantort is, ekkor felcserélődik
