1. előadás

8:25-9:55

Követelmények

Végén vizsga, ha van gyakorlati jegy

írásbeli + szóbeli
+ Elővizsga (papíros + canvas hetente)

Gyakorlaton:

2 ZH
RöpZH-k (Canvas)

Anyagok

Alapozás (Logikai halmazok, reláció, fv)
Komplex számok
Kombinatorika (leszámlálások)
Gráfok

Logikai jelek

Állítások lehetnek:

Igaz
Hamis

A 2 egy páros prím: \(PÁROS(2) \land PRÍM(2)\)

Igazságtábla

Egy n-változós formula igazságtáblájával megadott {i,h}^n -> {i,h} n-változós logikai műveletet ír le.

Ebből következik a formula igazhalmaza és hamishalmaza.

És - Konjunkció

\(A \land B\)

A\B	I	H
I	I	H
H	H	H

\(\land\)
A	I	I	H	H
B	I	H	I	H
\(A\land B\)	I	H	H	H

Vagy - Diszjunkció

\(\lor\)
A	I	I	H	H
B	I	H	I	H
\(A\lor B\)	I	I	I	H

Tagadás - Negáció

A	I	H
\(\neg A\)	H	I

Ha, akkor - Implikáció

Ha A, akkor B

pl: Ha x prím, akkor x páratlan. (\(\forall x > 10\))

\(x\)	\(A\)	\(B\)	\(A \Rightarrow B\)
4	H	H	I
7	I	I	I
9	H	I	I
2	I	H	H

Lényegében csak akkor hamis, ha A igaz, de B hamis

Érdekes példák gyűjteménye

Ha \(2+2=5\), akkor én vagyok a római pápa.

def is_clean(directory: os.DirEntry) -> bool: # Van-e a mappában vírusos fájl?
    for file in directory:
        if has_virus(file):
            return False
    return True

\(A\Rightarrow B \space\sim\space \neg A \lor B \space\sim\space \neg B \Rightarrow \neg A\)

Ekvivalencia: \(\iff\)

\(A\)	\(B\)	\(A \iff B\)
I	H	H
I	I	I
H	I	H
H	H	I

Kizáró vagy: \(\oplus\)

\(A\)	\(B\)	\(A \oplus B\)
I	H	I
I	I	H
H	I	I
H	H	H

Kvantorok - Minden | Létezik

\(\forall\): mind
\(\exists\): létezik

\(\forall x (PRÍM(x) \Rightarrow PÁROS(X))\)

Akkor igaz, ha MINDEN \(x\): a zárójelen belüli kifejezés igaz

\(\exists x(Y)\)

Akkor igaz, ha van olyan \(x\), melyre \(Y\) igaz

Összesítve: \(\land, \lor, \Rightarrow, \neg, \oplus, \iff\)

De Morgan azonosságok

\(\neg (A \land B) \iff (\neg A) \lor (\neg B)\)

\(\neg (A \lor B) \iff (\neg A) \land (\neg B)\)

Példák:

\(\neg \forall x (A(x)) \iff \exists x (\neg A(x))\)

\(\neg \exists x (A(x)) \iff \forall x (\neg A(x))\)

Halmazok

"Dolgok gyűjteménye" (alapfogalom)

\(x \in H\): \(x\) eleme \(H\)-nak

Elemeknek nincs sorrendje
Mindegy, hogy hányszor van benne I/H

Egy halmazt egyértelműen meghatározza, hogy mik az elemei

\(H = K \iff \forall x (x \in H \iff x \in K)\)

Halmazok megadása

Kapcsoszárójelekbe felsorolva
- \(\{1, 2, 3\}\)
Elemek felsorolása tulajdonságukkal
- \(\{x \in \mathbb{Z} | x > 10\}\)
  - \(\mathbb{Z}\) azon elemei, amikre igaz: \(x > 10\)
Szövegesen
- \(\{Minden \space 10-nél \space nagyobb \space egész \space szám\}\)

Pl: \(\{n^2 + 1 | n \in \{1, 2, 3, 7\}\}\)

>>> [n * n + 1 for n in [1, 2, 3, 7]]
[2, 5, 10, 50]

"|" és ":" a felsorolásnál felcserélhető (egyenértékű)

Halmazműveletek

Üres halmaz

\(\varnothing := \{\}\): az üres halmaz

Megjegyzés: \(\varnothing \neq \{\varnothing\}\)

\(\{\varnothing\}\) egy üres halmazt tartalmazó halmaz

Részhalmaz

\(A \subseteq B\): \(A\) minden eleme eleme \(B\)-nek is

\(\forall x (x \in A \Rightarrow x \in B)\)

Metszet

\(A \cap B\): \(x \in A \cap B \iff x \in A \land x \in B\)

Unió

\(A \cup B\) \(A\) vagy \(B\) elemei

Diszjunkt

A és B diszjunkt, ha \(A \cap B = \varnothing\)

Nincsenek közös elemei

Egyéb ?

Minden A, B, C halmazra

Áll: \(\cap\) és \(\cup\) kommutatív

Kommutativitás - az elemek felcserélhetőek

\(A \cap B = B \cap A\)
\(A \cup B = B \cup A\)

Asszociativitás - a csoportosítás felbontható és áthelyezhető

\((A \cap B) \cap C = A \cap (B \cap C)\)
\((A \cup B) \cup C = A \cup (B \cup C)\)
\(A \cap A = A\)
\(A \cup A = A\)

a subset b <=> a és B = a