A matematika nyelvér l bevezetés

A matematika nyelvér®l bevezetés Wettl Ferenc

2012-09-06

Wettl Ferenc ()

A matematika nyelvér®l bevezetés

2012-09-06

1 / 19

Tartalom

1

Matematika Matematikai kijelentések

2

Logikai m¶veletek Állítások tagadása És, vagy, ha. . . akkor, pontosan akkor, nem Implikáció megfordítása Szükséges és elegend®/elégséges Kontrapozíció de Morgan azonosságok

3

Kvantorok Minden. . . , van olyan. . .

4

Halmazm¶veletek és logikai m¶veletek Halmazok Halmazm¶veletek Végtelen halmazok

Wettl Ferenc ()


2012-09-06

2 / 19

Matematika

Matematikai kijelentések

Matematika: bizonyos szerkezet¶ kijelent® mondatok. Értelmetlen

Szintaktikailag (formailag) hibás Szemantikailag (tartalmilag) hibás Én most hazudok.

Értelmes

Igaz Hamis A matematikai kijelentések olyan mondatok, amelyekben matematikai objektumok (pl. szám, halmaz, függvény, osztható. . . ) logikai konnektívumok (és, vagy, ha. . . akkor, pontosan akkor. . . ), és kvantorok (minden, van olyan)

Wettl Ferenc ()


2012-09-06

3 / 19

Logikai m¶veletek

Állítások tagadása

Példa Mi az alábbi állítások tagadása?

E

Esik az es®.

¬E

Nem esik. Esik az es® és süt a nap. Nem esik vagy nem süt. Ma moziba megyünk vagy fagyizuk. Nem megyünk moziba és nem fagyizunk. Ha hétf®n nem futunk, (akkor) futunk kedden. Hétf®n nem futunk de/és kedden sem. Ha hétf®n futunk, futunk kedden is. Hétf®n futunk de kedden nem.

Wettl Ferenc ()


E ∧ F (E &F ) ¬E ∨ ¬F M ∨F ¬M ∧ ¬F H⇒K H ∧ ¬K H⇒K H ∧ ¬K 2012-09-06

4 / 19

Logikai m¶veletek

Deníció Jelöljön

P

és

Q

És, vagy, ha. . . akkor, pontosan akkor, nem

két állítást. Igazságtáblájukkal a következ® logikai

m¶veleteket deniáljuk (0

= hamis,

1

= igaz):

NOT), szorzás (∧, és/de, AND),

tagadás, negáció (¬, nem, és, konjunkció, logikai

(megenged®) vagy, diszjunkció, logikai összeadás (∨, vagy, kizáró vagy (⊗, vagy. . . , vagy,

OR),

XOR),

implikáció (⇒, ha. . . , akkor. . . ), ekvivalencia (⇔, pontosan akkor, akkor és csak akkor),

P

¬P

0

1

0

0

0

0

0

1

1

1

0

0

1

0

1

1

1

0

1

0

0

1

1

0

0

1

1

1

1

0

1

1

Wettl Ferenc ()

P Q P ∧Q P ∨Q P ⊗Q P ⇒Q P ⇔Q


2012-09-06

5 / 19

Logikai m¶veletek


Deníció Két logikai kifejezést azonosnak (azonosan egyenl®nek) tekintünk, ha logikai értékük a bennük szerepl® logikai változók bármely értékére azonos. Az azonosság jele

≡.

Ha nem futunk hétf®n, futunk kedden

≡

Hétf®n vagy kedden futunk.

Példa (Az implikáció ekvivalens alakja)

A ⇒ B ≡ ¬A ∨ B Megoldás

A

⇒

B

0

1

0

0

1

1

1

0

0

1

1

1

≡ ¬ X 1 X 1 X 0 X 0

Wettl Ferenc ()

A

∨

B

0

1

0

0

1

1

1

0

0

1

1

1


2012-09-06

6 / 19

Logikai m¶veletek


Nem igaz, hogy ha nem futunk hétf®n, futunk kedden

≡

Se hétf®n se kedden nem futunk.

n > N , akkor |an − a| < ε ≡ n > N , de |an − a| ≥ ε.

Nem igaz, hogy ha

Példa (Az implikáció tagadása)

¬(A ⇒ B ) ≡ A ∧ ¬B Megoldás

¬ (A ⇒ 0

0

1

B) 0

0

0

1

1

1

1

0

0

0

1

1

1

Wettl Ferenc ()

≡ X X X X

A

∧ ¬

B

0

0

0

1

0

0

0

1

1

1

1

0

1

0

0

1


2012-09-06

7 / 19

Logikai m¶veletek

Implikáció megfordítása

Deníció Az

A⇒B

implikáció megfordításán az

B ⇒ A implikációt értjük.

Példa Ha Béla orvoshoz megy, tiszta fehérnem¶t húz. Ha Béla tiszta fehérnem¶t húz, orvoshoz megy.

Példa

(A ⇒ B ) ∧ (B ⇒ A) ≡ A ⇔ B .

Wettl Ferenc ()


2012-09-06

8 / 19

Logikai m¶veletek

Ha ha

Szükséges és elegend®/elégséges

n osztható 4-gyel, akkor osztható 2-vel is. A, akkor B ≡

A igazsága elegend® (de nem szükséges) feltétele B igazságának ≡ B igazságának A igazsága elegend® (de nem szükséges) feltétele Csak akkor osztható n 4-gyel, ha 2-vel is. csak akkor A, ha B ≡ B igazsága A igazságának szükséges (de esetleg nem elegend®) feltétele

≡

A igazságának szükséges (de esetleg nem elegend®) feltétele B igazsága Matematikai szövegekben a fenti két mondatszerkezet ekvivalens:

A elegend® feltétele B -nek, és B

szükséges feltétele

A-nak.

Nem matematikai példa: csak akkor kapsz diplomát, ha bezeted a tandíjat!

A szükséges és elegend® feltétele B -nek, azaz A ⇔ B ≡ csak akkor B , ha A (mert szükséges, azaz B ⇒ A), és ha A, akkor B (mert elégséges, azaz A ⇒ B ). ≡ Akkor és csak akkor A, ha B Wettl Ferenc ()


2012-09-06

9 / 19

Logikai m¶veletek

Példa

Kontrapozíció

m és n olyan pozitív egészek, hogy m + n ≥ 49, m ≥ 25 vagy n ≥ 25.

Mutassuk meg, hogy ha akkor

Példa (Kontrapozíció)

A ⇒ B ≡ ¬B ⇒ ¬A Megoldás

A

⇒

B

0

1

0

0

1

1

1

0

0

1

1

1

≡ ¬ X 1 X 0 X 1 X 0

Wettl Ferenc ()

B

⇒ ¬

A

0

1

1

0

1

1

1

0

0

0

0

1

1

1

0

1


2012-09-06

10 / 19

Logikai m¶veletek

de Morgan azonosságok

Példa (de Morgan azonosságok)

¬(A ∧ B ) ≡ ¬A ∨ ¬B

¬(A ∨ B ) ≡ ¬A ∧ ¬B

Megoldás

¬ (A

∧

B)

1

0

0

0

1

0

0

1

1

1

0

0

0

1

1

1

¬ (A

∨

B)

1

0

0

0

0

0

1

1

0

1

1

0

0

1

1

1

Wettl Ferenc ()

≡ ¬ X 1 X 1 X 0 X 0 ≡ ¬ X 1 X 1 X 0 X 0

A

∨ ¬

B

0

1

1

0

0

1

0

1

1

1

1

0

1

0

0

1

A

∧ ¬

B

0

1

1

0

0

0

0

1

1

0

1

0

1

0

0

1


2012-09-06

11 / 19

Kvantorok

Jelölés A

∀xP (x )

és a

és van olyan

∃xP (x )

Minden. . . , van olyan. . .

jelölések jelentése: minden

x , hogy P (x ).

A

∀

ill. a

∃

x -re (igaz, hogy) P (x )

jel neve univerzális ill.

egzisztenciális kvantor.

∀: ∃:

minden, tetsz®leges, bármely, akármelyik, bármikor . . . All van, van olyan, létezik, található olyan, megesik . . . Exists

Példa Jelölje

y -nak.

P (x ), hogy x

prím,

S (x ), hogy x

páros és

O (x , y ), hogy x

osztója

Formalizáljuk az alábbi állításokat, és döntsük el, hogy igazak-e!

∃x [S (x ) ∧ P (x )]

Létezik páros prím.

i

∀x [P (x ) ⇒ ¬S (x )] z -nek, ∀x , y , z [O (x , z ) ∧ O (y , z ) ⇒ O (xy , z )]

Minden prím páratlan. Ha

x

akkor

és

xy

y

osztója

is.

Wettl Ferenc ()


2012-09-06

h h

12 / 19

Kvantorok

Minden. . . , van olyan. . .

Példa Mi az alábbi állítások tagadása?

∀x ∈ J [S (x )]

Mindenki szereti Júliát.

∃x ∈ J [¬S (x )]

Van aki nem szereti.

∃x ∈ E [I (x )]

Valaki járt itt.

∀x ∈ E [¬I (x )]

Senki sem járt itt.

∀a ∈ A ∃k ∈ K [R (a, k )]

Minden ajtón van kilincs. Van olyan ajtó, amin nincs kilincs.

Kvantoros állítások tagadása:

Wettl Ferenc ()

∀∀∃ . . .

∃a ∈ A ∀k ∈ K [¬R (a, k )]

A tagadása ∃∃∀ . . . ¬A.


2012-09-06

13 / 19

Halmazm¶veletek és logikai m¶veletek

Halmazok

Deníció Két halmazt akkor és csak akkor tekintünk egyenl®nek, ha elemeik ugyanazok. A halmazt, melynek nincs eleme, üres halmaznak nevezzük.

∅. Az x dolog eleme az X halmaznak jelölése: x ∈ X . A halmazt a B halmaz részhalmazának nevezzük (A ⊆ B ), ha az A minden eleme B -nek is eleme. A valódi része B -nek (A ⊂ B ), ha A ⊆ B , de A 6= B . Jele:

Az

Halmazokról mindig csak mint egy adott alaphalmaz részhalmazairól beszélünk, még ha ezt az alaphalmazt nem is nevezzük meg.

Jelölés

R:

valósok,

N:

természetes számok,

Z:

egészek,

Q:

+ pozitív egészek, R : pozitív valós számok. A

H

halmaz azon

x

elemeinek halmazát, melyek a

P

racionálisok,

N+ :

tulajdonsággal

rendelkeznek a következ®képp adjuk meg:

{ x ∈ H : P (x ) } . Wettl Ferenc ()


2012-09-06

14 / 19


Halmazm¶veletek

Deníció (Halmazm¶veletek) Legyen

A és B

egy

H

halmaz két részhalmaza. Az

A és B

halmaz

A∩B

metszetén (közös részén) azoknak az elemeknek a halmazát értjük, amelyek mindkét halmazban benne vannak:

A ∩ B = { x ∈ H : x ∈ A ∧ x ∈ B }. A∪B

egyesítettjén (unióján) azoknak az elemeknek a halmazát értjük,

amelyek a két halmaz közül legalább az egyikben benne vannak:

A ∪ B = { x ∈ H : x ∈ A ∨ x ∈ B }. A összes olyan elemének B -ben. Az A halmaz H -ra vonatkozó komplementerén a H − A halmazt értjük. Jele AH . Ha az alaphalmaz nincs megnevezve, a komplementert egyszer¶en A jelöli. Az

A és B

halmaz

A−B

különbségén az

halmazát értjük, amelyek nincsenek benne

AH = { x ∈ H : x ∈/ A }. Wettl Ferenc ()


2012-09-06

15 / 19


Végtelen halmazok

Deníció (Halmazok számossága) Két halmaz azonos számosságú, ha elemeik közt létezik kölcsönösen egyértelm¶ megfeleltetés.

A: A: B: A: A: B: A: A: B: C: D: E: F:

1 3 1 1 2 1 1 1 3 4 10 11 . . .

2 4 2 2 4 3 2 2 5 9 12 20

3 5 3 6 5 3 6 8 13 19 24

Wettl Ferenc ()

4 5 6 7

6 7 ... 8 9...

4 5 6 7 ... 8 10 12 ... 7 9 11 ... 4 5 6 7 ... 7 15 16 28 ... 14 17 27 ... 18 26 ... 25 ... ... A matematika nyelvér®l bevezetés

2012-09-06

16 / 19


Végtelen halmazok

Deníció (Megszámlálhatóan végtelen halmaz) Egy halmazt megszámlálhatóan végtelennek nevezünk, ha egyenl® számosságú az

N

halmazzal.

Tétel Az egész számok és a racionális számok halmaza is megszámlálhatóan végtelen.

Wettl Ferenc ()


2012-09-06

17 / 19


Végtelen halmazok

Tétel A valós számok (és az irracionális számok) halmaza nem megszámlálható.

Bizonyítás Indirekt bizonyítás:

1 2 3 4 5 6 7 8 9 .. .

0,3610513769310776034... 3,1159236543282345014... 0,1585026723823654328... 2,6748231345822345014... 7,5748700000000000000... -0,6548727650234576800... -5,2687623176577653234... 0,9870244807633333777... 0,1113554322346000214...

0,523315111 Wettl Ferenc ()


2012-09-06

18 / 19


Végtelen halmazok

Amit tudni kell!

1

logikai m¶veletek m¶veleti tábláinak ismerete,

2

egyszer¶ logikai összefüggések igazolása táblázattal,

3

kvantorok,

4

logikai m¶veleteket és kvantorokat tartalmazó állítások tagadása,

5

halmazm¶veletek deníciói,

6

a természetes számok, a racionális és a valós számok számossága.

Wettl Ferenc ()


2012-09-06

19 / 19

A matematika nyelvér l bevezetés

Recommend Documents