Matematika | Felsőoktatás » Bevezetés a Matematikába tételek, 2006

BEVEZETÉS A MATEMATIKÁBA TÉTELEK Bevezetés a Matematikába tételek - 2006 01. Halmazok Halmazműveletek Metszet, unio, komplementer, különbség, szimmetrikus különbség definíciója, tulajdonságai. Rendezett számpár, két halmaz Descartes szorzata. A halmaz és a halmaz eleme fogalmakat a matematikában nem definiáljuk, mindkettő úgynevezett alapfogalom. A halmazokat alkotó dolgokat hívjuk a halmaz elemeinek. Bármely dolog vagy benne van az adott halmazban, vagy nem. a ∈ A jelöli azt, hogy a eleme az A halmaznak. Két halmazról akkor mondjuk, hogy egyenlőek, ha ugyanazok az elemeik. Azt a halmazt, amelynek nincsen eleme, üres halmaznak hívjuk, jele: Ø. Tetszőleges A halmaz eseténm A összes részhalmazának halmazát az A halmaz hatványhalmazának nevezzük, és P(A)- val jelöljük. Halmazműveletek: Legyen A és B két tetszőleges halmaz. Az A és B halmazok egyesítése azon elemek halmaza, amelyek A,B közül legalább az egyikben benne vannak,

Jele: A ∪ B Az A és B halmazok metszete azon elemek halmaza, emelyek A,B mindegyikében benne vannak, Jele: A ∩ B Ha A ∩ B=Ø, akkor azt mondjuk, hogy az A és B halmazok diszjunktak. Univerzum: Az összes halmaz halmaza. Legyen a rögzített univerzum: U, A⊆U pedig tetszőleges halmaz. Az UA különbséghalmazt A komplementerének nevezzük. Jelölése: /A (A felülvonás) Legyen A és B tetszőleges halmazok. Az A és B halmazok különbsége azon A beli elemek halmaza, melyek B ben nincsenek benne Jele: AB Az A és B halmazok szimmetrikus különbsége azon elemek halmaza, melyek A és B közül pontosan az egyikben vannak benne. Jele: A∆B A∆B=(AB) ∪ (BA) Legyenek A és B tetszőleges halmazok. Azt mondjuk, hogy B részhalmaza A-nak, ha b minden eleme A nak is eleme. Jele: B⊆A Valódi részhalmazról beszélünk, ha B⊆A , de B≠A 1 BEVEZETÉS A MATEMATIKÁBA TÉTELEK Tulajdonságok: Tetszőleges A,B,C halmazokra: A⊆A és Ø⊆A: Ha A⊆B és B⊆C, akkor

A⊆C : A=B akkor és csak akkor, ha A⊆B és B⊆A: reflexivitás tranzitivitás antiszimmetria A∩A=A A∩B=B∩A (A∪B)∩A=A idempotencia kommutativitás abszorptivitás A∪A =A A∪B=B∪A (A∩B)∪A=A ((A∩B)∩C)= (A∩(B∩C)) és ((A∪B)∪C)= (A∪(B∪C)) asszociativitás ((A∪B)∩C)=(A∩C)∪(B∩C) és ((A∩B) ∪C)=(A∪C)∩(B∪C) disztributivitás Tetszőleges A,B∈U halmazokra: /(A∩B)=/A∩/B /(A∪B)=/A∪/B //A=A A∩/A= Ø A∩U=A A∪/A=U A∪U=U De Morgan azonosság A∩Ø= Ø A∪Ø=A Ha U tetszőleges, nem üres indexhalmaz és minden i ∈I re adott egy A i halmaz, akkor: ∪ i∈I ={x: x∈A i valamely i ∈I -re} ∩ i∈I ={x: x∈A i valamely i ∈I -re} Rendezett számpár: (a,b) ahol a∈A és b∈B , lényeges a kettő elem sorrendje a: első komponens vagy koordináta b: második komponens vagy koordináta (a,b)=(c,d) ha a=c és b=d (a,b)={{a,b},{a}}; {a}: ez adja meg hogy mnelyik az első koordináta Descartes szorzat: A×B=

{(a,b): a∈A és b∈B} 2 BEVEZETÉS A MATEMATIKÁBA TÉTELEK 02. Megfeleltetések, relációk Megfeleltetés, reláció, parciális leképezés, leképezés fogalma (indulási halmaz, érkezési halmaz, értelmezési tartomány, értékkészlet, kép, ős) Megfeleltetések szorzata, inverze, tulajdonságaik. Identikus megfeleltetés Megfeleltetések ábrázolása nyíldiagrammon. Szürjektív, injektív, bijektív leképezések, tulajdonságaik. Kiválasztási függvények, tetszőleges sok halmaz Descartes szorzata. Megfeleltetés: legyen A és B tetszőleges halmazok. Az A×B halmaz részhalmazait A-ból B-be történő megfeleltetéseknek nevezzük. A-t indulási, B-t érkezési halmaznak nevezzük. A S⊆A×B A-ból B-be történő megfeleltetés értelmezési tartománya mindazon a∈A elemek halmaza, melyekhez van olyan b∈B, hogy aδb (b az a megfeleltetése) Értékkészlete pedig mindazon b∈B elemek halmaza, melyekhez van olyan a∈A, hogy aδb. Reláció: Az A×A

halmaz részhalmazait A-n értelmezett relációknak nevezzük. Parciális leképezés: a ϕ⊆A×B megfeleltetés parciális leképezés, ha bármely a∈A hoz legfeljebb egy olyan b∈B van, amelyre (a,b)∈ϕ. Jelölése: ϕ: A->B Ha ϕ parciális leképezés, és(a,b)∈ϕ, akkor b az a elem képe, a pedig a b elem őse. Leképezés: A ϕ⊆A×B megfeleltetés leképezés, ha bármely a∈A hoz pontosan egy olyan b∈B van, amelyre: (a,b)∈ϕ. Jelölése: ϕ: A->B Megfeleltetések szorzata: Legyen δ⊆A×B és σ⊆B×C megfeleltetések. δσ={(a,c)∈A×C: van olyan b∈B, hogy (a,b) ∈ δ és (b,c)∈σ} Megfeleltetés inverze: δ-1={(b,a) ∈B×A: (a,b) ∈δ} Tulajdonságok: Legyenek δ⊆A×B és σ⊆B×C és τ⊆C×D megfeleltetések (δ σ)τ=δ (σ τ) ω A δ=δ δωB =δ -1 -1 -1 -1 -1 (δ ) =δ (δσ) =σ *δ 3 BEVEZETÉS A MATEMATIKÁBA TÉTELEK Identikus megfeleltetés: Tetszőleges A halmazra , A önmagába való identikus megfeleltetése: az ωA

={(a,a): a∈A}⊆A×A megfeleltetés Megfeleltetések ábrázolása nyíldiagrammon: Indulási halmaz Érkezési halmaz Szürjektív leképezés: Legyen ϕ: A->B tetszőleges leképezés. ϕ:A->B leképezés ráképezés /szürjektív/, ha minden b∈B elemnek van őse Injektív leképezés: ϕ:A->B leképezés kölcsönösen egyértelmű (injekció), ha a különböző elemek képe különböző Bijektív leképezés: ϕ:A->B leképezés bijekció, ha kölcsönösen egyértelmű és ráképezés. Tulajdonságok: Legyen ϕ:A->B és ψ:B->C tetszőleges leképezés a, Ha ϕ és ψ szürjektív, akkor ϕψ is az. b, Ha ϕ és ψ injektív, akkor ϕψ is az. c, Ha ϕ és ψ bijektív, akkor ϕψ is az. d, Ha ϕψ szürjektív, akkorψ szürjektív. e, Ha ϕψ injektív, akkorϕ injektív. f, Ha ϕψ bijektív, akkor ϕ injektív és ψ szürjektív Legyen ϕ: A->B tetszőleges leképezés. A ϕ-1 megfeleltetés akkor és csak akkor leképezés, ha ϕ bijekció.

Bármely ϕ:A->B bijektív leképezésre a, ϕ-1 is bijektív leképezés b, ϕϕ-1= id A =ωA és ϕ-1ϕ=id B =ωB Tetszőleges ϕ: A->B és ψ:B->C bijektív leképezésre (ϕ-1) -1= ϕ és (ϕψ)-1=ψ-1*ϕ-1 4 BEVEZETÉS A MATEMATIKÁBA TÉTELEK Kiválasztási függvények: Legyen I egy indexhalmaz, A i (i∈I) tetszőleges halmazok Kiválasztási függvénynek nevezzük azokat a K: I->∪ i∈I A i leképezéseket, amelyekre iK∈A i minden i∈I re. Tetszőleges sok halmaz Descartes szorzata: Az A i (i∈I) halmazok descartes szorzata az összes ilyen kiválasztási függvények halmaza. Jelölése: ∏ i∈I A i 5 BEVEZETÉS A MATEMATIKÁBA TÉTELEK 03. Permutációk Az {1,.,n} halmaz összes permutációját S n -el jelöljük (önmagába való bijektív leképezés) Tétel: tetszőleges σ,τ∈ S n permutációkra στ,σ∈ S n . A permutációk szorzása asszociatív, és teljesülnek az alábbi egyenlőségek: id σ = σ id = σ σσ-1 = id= σ-1σ

(σ-1)-1=σ (στ)-1=τ-1 σ-1 1 2 3 4 5 6 7 8 9 * nyíldiagramm : γ= 4 7 1 2 5 6 3 8 9 * Legyen σ∈S n tetszőleges permutáció. Azt mondjuk, hogy σ mozgatja az i∈{1,.,n} elemet, ha iσ ≠ i A σ által mozgatott elemek halmazát M σ -val jelöljük. * Legyen σ∈S n tetszőleges permutáció, s legyen |M σ |=k>1 A σ permutációt ciklikusnak hívjuk, ha vannak olyan (a 1 ,,a k )∈{1,.,n} elemek, hogy Mσ=(a 1 ,,a k ) és a 1 σ=a 2 , a k σ=a 1 Ebben az esetben σ-t így jelöljük (a 1 , a 2 , , a k ), a k szám pedig a ciklus hossza. * Ha a γ,δ∈ S n ciklusokra az M γ , M δ halmazok diszjunktak, akkor azt mondjuk, hogy a γ és δ ciklusok idegenek * Akkor mondjuk hogy a σ , τ ∈S n permutációk felcserélhetőek, ha στ=τσ Tétel: az idegen ciklusok felcserélhetőek. Következmény: Legyenek γ 1 ,, γ r ∈S n páronként idegen ciklusok. Akkor : (a) tetszőleges a∈{1,,n} elemre: a(γ 1 γ r )=  a γ i : ha a∈M γi (1≤i≤r)

 a : különben (b) M γ1 γr = ∪ i=1.r M γi 6 BEVEZETÉS A MATEMATIKÁBA TÉTELEK Tétel: minden S n -beli permutáció előáll páronként idegen ciklusok szorzataként, s ez az előállítás a tényezők sorrendjétől eltekintve egyértelműen meghatározott. A 2 hosszúságú ciklust transzpozíciónak hívjuk. Tétel: Minden S n beli permutáció transzpozíciók szorzatára bontható. Megfeleltetések megadása leképezéssel: δ= δ⊆A×B A={a1,,a5} (a 1 ,b 1 ),(a 2 ,b 1 ),(a 2 ,b 3 )  (a 1 ,b 2 ),(a 3 ,b 2 ),(a 4 ,b 1 ) a δ* ={b∈B : (a,b)∈δ} a 1 δ*={b 1 ,b 2 } a 2 δ*={b 1 ,b 3 } a 3 δ*={b 2 } a 4 δ*={b 1 } a 5 δ*={Ø} Minden a-hoz rendel elemet! δ*=AP(B) 7 BEVEZETÉS A MATEMATIKÁBA TÉTELEK 04. Relációk és irányított gráfok Tetszőleges A halmazra az A×A részhalmazait A-n értelmezett relációknak nevezzük. Irányított gráfon egy (A;δ) alakú párt értünk, ahol A tetszőleges nem üres halmaz, δ pedig

tetszőleges A-n értelmezett reláció. Az A halmaz elemeit a gráf pontjainak, a δ-beli párokat pedig a gráf éleinek nevezzük. Ha (a,b) a gráf egy éle, akkor a-t az él kezdőpontjának , b-t pedig az él végpontjának hívjuk. Az (a,a) alakú él neve hurokél. Zárt séta, nyílt séte, irányított út, irányított kör: Legyen G=(A, δ) tetszőleges irányított gráf. Az (a 1 ,a 2 ) (a 2 ,a 3 )(a n-1 ,a n ) ∈δ élek sorozatát zárt sétának nevezzük ,ha a 1 =a n . Az (a 1 ,a 2 ) (a 2 ,a 3 )(a n-1 ,a n ) ∈δ élek sorozatát nyitott sétának nevezzük a 1 -ből a n –be. Ha az (a 1 ,a 2 ) (a 2 ,a 3 )(a n-1 ,a n ) ∈δ élek sorozata páronként különbözőek, akkor irányított útról beszélünk. Ha az (a 1 ,a 2 ) (a 2 ,a 3 )(a n-1 ,a n ) ∈δ élek sorozata páronként különbözőek és a 1 =a n akkor irányított körről beszélünk. Az n számot a séta/út/kör hosszának neezzük Tuljadonságok: Legyen δ tetszőleges reláció az A halmazon. A δ

reláció: a, reflexív, ha minden a∈A esetén: (a,a)∈ δ vagyis G minden pontján van hurokél. b, szimmetrikus, ha minden (a,b)∈ δ esetén (b,a)∈ δ vagyis G minden élével együtt a fordított él is G ben van. c, antiszimmetrikus, ha minden a,b∈A esetén (a,b)∈δ és (b,a)∈δ akkor és csak akkor, ha a=b vagyis G bármely két különböző pontja max 1 irányban van összekötve d, dichotom, ha bármely a,b∈A esetén (a,b)∈δ vagy (b,a)∈ δ vagyis G bármely két pontja között min 1 irányban fut él. e, tranzitív, ha bármely (a,b)∈δ , (b,c)∈δ esetén (a,c)∈ δ vagyis ha űg bármely két pontja között létzik 2 hosszúságú irányított séta, akkor létezik a két pont között ugyanilyen irányú él is. 8 BEVEZETÉS A MATEMATIKÁBA TÉTELEK Tranzitív relációk jellenzése: Tetszőleges G=(A;δ) irányított gráfra a δ reláció akkor és csak akkor tranzitív, ha valahányszor G két pontja között létezik irányított séta,

mindannyiszor létezik ugyanilyen irányú él is. Egy reláció tranzitív bejártja: Legyen δ A-n értelmezett tetszőleges reláció, G=(A; δ) a megfelelő irányított gráf, ĝ =g∪g2∪gn=∪ n=1.∞ gn Tetszőleges a,b ∈A elemekre aĝb akkor és csak akkor, ha G-ben van irányított (a,b) séta. ĝ tranzitív reláció Az A halmazon értelmezett és g-t tartalmazó bármely τ tranzitív relációra ĝ⊆τ A ĝ relációt g tranzitív bezártjának nevezzük. 9 BEVEZETÉS A MATEMATIKÁBA TÉTELEK 05. Részbenrendezések A reflexív, antiszimmetrikus és tranzitív relációkat részbenrendezéseknek nevezzük. Az (A; δ) részbenrendezett halmaz, ha A tetszőleges nem üres halmaz, δ pedig részbenrendezés Részbenrendezett halmaz Hasse diagramja: A részbenrendezéseket az irányított gráfok helyett ún. Hasse-diagrammjukkal szemléltetik Ebben az alaphalmaz elemeunek a pontok úgy vannak megfeleltetve, hogy a kisebb elem pontja lejebb van és két pont akkor

van összekötve, ha a nekik megfelelő elemek közül legfeljebb lévő fedi a lejebb lévőt. Azt mondjuk, hogy az (A; ≤) részbenrendezett halmaz a∈A eleme fedi a b∈B elemet, ha b<a és nincs olyan c∈A , hogy b<c<a. Jelölése: b<a Min/ max elem, legkisebb legnagyobb elem: Az (A; ≤) részbenrendezett halmaz egy a∈A eleme minimális elem, ha A-ban nincs nála kisebb elem, aza nincs olyan c∈A, hogy c<a. Egy a∈A maximális elem, ha A ban nincs nála nagyobb elem, azaz nincs olyan c∈A,hogy c>a Az (A; ≤) részbenrendezett halmaz egy a∈A eleme legkisebb elem, ha minden b∈A esetén b≥a Egy a∈A elem legnagyobb elem, ha minden b∈A esetén b≤a. Kapcsolódó állítások: Minden részbenrendezett halmazban legfeljebb egy legkisebb elem és legfeljebb egy legnagyobb elem van. Minden véges részbenrendezett halmazban van minimális ill. maximális elem Részbenrendezett halmazok direkt szorzata: Legyen n∈N Az (A 1 ; ≤ 1 ),.,(A n ;≤ n )

részbenrendezett halmazok direkt szorzatán az (A 1 ××A n ; ≤) részbenrendezett halmazt értjük, ahol a ≤ úgy van definiálva : 10 BEVEZETÉS A MATEMATIKÁBA TÉTELEK (a 1 ,,a n ) ≤(b 1 ,,b n )<=> a 1 ≤ 1 b 1 ,,a n ≤ n b n Lexikografikus rendezés: Legyen n∈N és (A 1 ; ≤ 1 ),.,(A n ;≤ n ) tetszőleges rendezett halmazok Az A 1 ××A n halmaz lexikografikus rendezése az alábbi ≤ reláció: (a 1 ,,a n ) ≤(b 1 ,,b n ) <=> (a 1 ,,a n )=(b 1 ,,b n ) vagy van olyan i (1≤i≤n), hogy a 1 =b 1 ,,a i-1 =b i-1 és a i ≤ i b i Rendezés: Az (A; ≤) részbenrendezett halmaz a,b elemei összehasonlíthatók, ha a≤b vagy b≤a A Lichotom részbenrendezést rendezésnek nevezzük. 11 BEVEZETÉS A MATEMATIKÁBA TÉTELEK 06. Ekvivalenciarelációk A reflexív, szimmetrikus és tranzitív relációkat ekvivalenciarelációknak nevezzük, Ekvivalenciaosztályok: Bármely δ A-n értelmezett ekvivalenciarelációra az aδ* (a∈A) halmazokat

ekvivalenciaosztályoknak nevezzük. Osztályozás: Legyen A tetszőleges halmaz. P(A) egy C részhalmazát A osztályozásának nevezzük, ha a, a C-beli halmazok nem üresek b, a C beli halmazok egyesítése A c, bármely két különböző C-beli halmaz diszjunkt egymástól Ha C osztályozás, akkor a C-beli halmazokat osztályoknak nevezzük. Faktorhalmaz: Tetszőleges δ A-n értelmezett ekvivalenciarelációra a δ osztályainak halmazát A δ szerinti faktorhalmazának nevezzük. Jelölése: A/δ Alapvető állítások: Legyen δ tetszőleges reláció A-n, δ*: A->P(A) pedig a hozzá tartozó leképezés. A δ reláció akkor és csak akkor ekvivalenciareláció, ha δ*-ra teljesülnek az: a, a∈aδ* minden a∈A-ra b, bármely a,a’ ∈A –ra, aδ*=a’δ vagy aδ∩a’δ =Ø Tetszőleges A halmazon értelmezett bármely δ ekvivalenciarelációra a ν:A->A/δ, a->aδ* hozzárendelés olyan szürjektív leképezés melynek magja éppen δ. ν-t természetes

leképezésnek nevezzük. Leképezés magja: Tetszőleges ψ: A->B leképezésre ker(ψ)={(a,a’)∈A2: aψ=a’ψ} a ψ leképezés magja. ker(ψ) mindig ekvivalenciareláció 12 BEVEZETÉS A MATEMATIKÁBA TÉTELEK 07. Véges halmazok jellemzése Az A és B véges halmazok akkor és csak akkor azonos elemszámúak, ha létezik A->B bijekció. Az A és B halamz ekvivalens egymással, ha létezik A->B bijekció. Tetszőleges A halmazra ekvivalensek az alácci feltételek: a, A véges b, Nem létezik A->S (S⊂A) bijekció c, Nem létezik N 0 ->A injekció Véges halmaz minden részhalmaza véges. Végtelen halmazok jellemzése: Tetszőleges A halmazra ekvivalensek az alábbi feltételek: a, A végtelen b, létezik A->S (S⊂A) bijekció c, létezik N 0 ->A injekció Minden halmaz, melynek van végtelen részhalmaza, maga is végtelen. Megszámlálhatóan végtelen halmazok és tulajdonságaik: Az A halmaz megszámlálhatóan végtelen, ha |A|=|N 0 | Minden

végtelen halmaznak van megszámlálhatóan végtelen részhalmaza. Legyen A tetszőleges halmaz. a, Ha léteki N 0 ->A szürjekció, akkor A véges vagy megszámlálhatóan végtelen. b, Ha valamely M megszámlálhatóan végtelen halmazra létezik M->A szürjekció, akor A véges vagy megszámlálhatóan végtelen. c, Megszámlálhatóan végtelen halmaz minden részhalmaza és minden faktorhalmaza véges vagy megszámlálhatóan végtelen. d, Véges sok megszámlálhatóan végtelen halmaz Descartes szorzata is megsz. végtelen e, Véges sok nemüres véges vagy megsz. végtelen halmaz Descartes- szorzata véges vagy megsz. végtelen Ha legalább egy tényező végtelen, akkor a szorzat is az f, ((Véges sok) vagy (megsz. végtelen sok)) (véges vagy megsz végtelen) halmaz egyesítése is véges vagy megsz. végtelen Ha legalább egy tag végtelen akkor az egyesítés is az. g, Megszámlálhatóan végtelen halmaz véges részhalmazainak halmaza megsz. végtelen 13

BEVEZETÉS A MATEMATIKÁBA TÉTELEK 08. Számosságok összehasonlítása: Tetszőleges A halmaz esetén A számosságát |A| jelöli. Legyen µ és ν két tetszőlege számosság, A és B pedig olyan halmazok, amelyekre |A|=µ és |B|=ν. µ≤ν, ha létezik AB injekció |A|≤|B| akkor és csak akkor, ha létezik AB injekció. Cantor –Schröder-Bernstein-tétel: Tetszőleges A és B halmazok esetén, ha létezik ϕ:AB bijektív leképezés is, tehát az A és a B halmaz ekvivalens egymással. Egy halmazon értelmezett összes karakterisztikus függvény halmazának vonatkozó állítás: BA={ϕ:AB} az összes AB leképezés. Ha A={a 1 ,,a n } és B={b 1 ,,b m }, akkor az összes AB leképezés: mn db. {0,1}A={ϕ:A{0,1}} az összes A{0,1} leképezés. Halmaz karakterisztikus függvénye: Legyen A⊆X. 1, ha x∈A χA=  1, ha x∉A χ A : X{0,1} Tetszőleges A halmazra |A|<|{0,1}A| Minden számosságnál van nagyobb számosság. Kontinuum számosság: A {0,1}N0 h

almaz számosságát kontinuum számosságnak nevezzük. Jele: c (kis gót c) |{0,1}N0|=|P(N 0 )|=|R|=|[0,1]| 14 számosságára BEVEZETÉS A MATEMATIKÁBA TÉTELEK 09. Logikai ítéletek és műveletek Az ítélet olyan állítás, amely igaz vagy hamis, de a kettő egyidejűleg nem teljesül. Logika: ítéletkalkulusz. Tetszőleges A,B ítéletekre: a, A negációja: „nem A” jele: ¬A b, A,B konjukciója: „A és B” jele: A∧B A h h i i c, B h i h i B h i h i jele: A∨B A+B h i i i A,B implikációja: „Ha A akkor B” A h h i i e, A*B h h h i A,B diszjunkciója: „A vagy B” A h h i i d, B h i h i jele: aB A->B i i h i A,B ekvivalenciája: „Akkor és csak akkor A, ha B” A h h i i B h i h i Jele: A↔B A<->B i h h i Formulák: Ítéletváltozók: olyan változól, amelyekaz ítéletek helyett állnak a forulákban. Legyen A 1 ,,A n (n≥1) ítéletváltozók a, Az ítéletváltozók mindegyike formula b, Ha F és G formula, akkor

(¬ F),(F∧G),(F∨G),(FG),(F↔G) is az. Minden az A 1 ,,A n változókból képzett formula megkapható (a,) és (b,) véges számú alkalmazásával. A műveletek erősségi sorrendje: legerősebbleggyengébb fele: (¬) (∧) (∨) () (↔) 15 BEVEZETÉS A MATEMATIKÁBA TÉTELEK Részformulák: Legyenek F és G tetszőleges formulák. G részformulája F nek , ha G fellép F nem a fenti rekurzív definicióban leírt előállítása során. Logikai változók: Ítéletváltozók. Formulák logikai ekvivalenciája: Az F és G logikai formulák logikailag ekvivalensek ha értékük a bennük szereplő változók bármilyen logikai értékei esetén megegyezik. Jelölése: F≡G Azonosságok és állítások: a, , ↔ kifejezése a többi művelettel: A↔B≡(AB)∧(BA) AB≡ (¬ A)∨B b, A∨B≡B∨A A∧B≡B∧A kommutativitás A∧A≡A A∨A≡A idempotencia (A∧B)∧C≡A∧(B∧C) (A∨B)∨C≡A∨(B∨C) asszociativitás (A∨B)∧C≡(A∧C)∨(B∧C)

(A∧B)∨C≡ (A∨C)∧(B∨C) disztributivitás (A∨B)∧A≡A (A∧B)∨A ≡A abszorptivitás c, ¬ (A∧B)≡(¬A)∨(¬B) ¬ (A∨B) ≡ (¬A)∧(¬B) De morgan azonosság ¬ (¬A)≡A A∧(¬A)≡B∧(¬B) A∨(¬A)≡B∨(¬B) A∧(B∨(¬B))≡A A∨( B∨(¬B))≡B∨(¬B) A∧( B∧(¬B)) ≡ B∧(¬B) A∨( B∧(¬B))≡A d, ()-t és (↔)-t tartalmazó logiaki ekvivalenciák: A↔B≡B↔A kommutativitás (A↔B)↔C≡A↔(B↔C) asszociativitás AB≡ (¬B)(¬A) (AC)∧(BC)≡(A∨B)C (AB)∧(AC)≡A(B∧C) A(BC)≡(A∧B)C A(B∧(¬B))≡¬ A Ha két formula logikailag ekvivalens, akkor a bennük szereplő változókat tetszőleges formulákkal helyettesítve újra logikailag ekvivalens formulákat kapunk. Ha egy formula valamely részformulája helyébe egy vele logikailag ekvivalens formulát írunk. akkor az ereteivel logikailag ekvivalens formulát kapunk. 16 BEVEZETÉS A MATEMATIKÁBA TÉTELEK Legyen F= F(A 1 ,,A n ) az A 1 ,,A n változókból felépített

tetszőleges formula, amely -t és ↔ -t nem tartalmaz. F*= F(A 1 ,,A n ) az a formula, amely F ből úgy áll elő: a, minden ∧-t ∨-ra és minden ∨-t ∨-re szerélünk b, minden A i -t ¬A i –re és miden ¬ A i –t A i re cserélünk Bármely () -t és (↔)-t nem tartalmazó F formulára ¬ F ≡F* Logikai formulák teljes diszjunktív normálformája: Egy formulát diszjunktív normálformának nevezünk, ha K 1 ∨∨K m alakú, ahol K 1 ∨∨K m mindegyike változóknak, illetve változók negáltjának konjugáltja. Az A 1 ,A n változókból felépített K 1 ∨∨K m diszjunktív normálformát teljes diszjunktív normálformának nevezzük, ha a K 1 ∨∨K m páronként különböző n- tagú konjukciók, melyekben az A 1 ,An változók mindegyike szerepel negálva vagy negálatlanul. Bérmely F formula logikailag ekvivalens egy teljes diszjunktív normálformával. 17 BEVEZETÉS A MATEMATIKÁBA TÉTELEK 10. Tautológia Egy F formula tautológia, ha F

logikai értéke az F-ben fellépő változók logiaki értékei esetén igaz. Jelölése: ╞F Azonosságok és állítások: Tetszőlege F és G formulákra ekvivalensek az alábbiak: a, F≡G b, ╞F↔G c, ╞FG és ╞GF Az alábbi formulák mindegyike tautológia: AA (≡ A∨(¬A)) (A∧ (AB))B ((¬B)∧(AB))(¬A) ((¬A)∧(A∨B))B A(B(A∧B)) (A∧B)A A(A∨B) ((AB)∧(BC))(AC) (AB)((BC)(AC)) (AB)((A∧C)(B∧C)) (AB)((A∨C)(B∨C)) ((A↔B)∧(B↔C))(A↔C) Továbbá ahol * az ∧ ∨ ↔ bármelyike lehet: (A↔B)((A*C)↔(BC)) (A↔B)((C*A)↔(CB)) Logikai következmény, prmeissza, konklúzió: Legyenek F 1 ,,F n (n ≥0) és G tetszőleges logikai formulák. G logikai következménye F1,,Fn –nek ha az F1,,Fn és G formulában lévő változóknak az összes lehetséges módon logiakai értéket adva, minden olyan esetben , amikor F1,,Fn mindegyike igaz, akkor G is igaz. Jelölése: (F1,,Fn )╞G Az (F1,,Fn ) formulákat premisszáknak, G-t pedig konklúziónak

nevezzük. Tetszőleges F és G formulákra ekvivalensek az alábbiak: a, F╞G b, ╞FG Tetszőleges (F 1 ,,F n ) (n≥1) és G formulákra ekvivalensek az alábbiak: a, (F 1 ,,F n ) ╞G 18 BEVEZETÉS A MATEMATIKÁBA TÉTELEK b, (F 1 ∧∧F n )╞G c, ╞(F 1 ∧∧F n )G Tetszőleges A és B formulákra: a, AB╞B b, (¬A¬B╞BA) ¬B¬A╞AB c, BC ╞ AC d, ¬A¬B╞ A Egy {F 1 ,,F n } formulahalmazt kielégíthetőnek nevezük, ha adható a formulákban lévő változóknak logikai értékek úgy, hogy F 1 ,,F n mindegyike igaz. Tetszőleges F 1 ,,F n és G formulákra , valamint H hamis formulákra ekvivalensek az alábbiak: a, F 1 ,,F n ╞G b, {F 1 ,,F n , ¬G } nem kielégíthető c, F 1 ,,F n , ¬G╞ H 19 BEVEZETÉS A MATEMATIKÁBA TÉTELEK 11. n-változós művelet Tetszőleges A nemüres halmazra és n∈N0 esetén az A-n értelmezett n-változós műveleten egy AnA leképezést értünk. n a művelet változószáma Algebra: Az (A;F) párt, ahol A nemüres

halmaz, F pedig az A-n értelmezett műveletek egy halmaza, algebrai struktúrának nevezzük. (A;F)=(A;◦;*) ha F={◦,} Asszociatív, kommutatív művelet, egységelem, zéruselem, elem inverze: Legyen az (A;◦) olyan algebrai struktúra, ahol a ◦ kétváltozós. Ekkor bármely a,b,c∈A elemekre az (A; ◦): asszociatív: ha (a◦b)◦c=a◦(b◦c) kommutítív: ha a◦b=b◦a Az u∈A elem az (A; ◦) algebrai struktúra egységeleme, ha bármely a∈A esetén u◦a=a◦u=a. Az u∈A elem az (A; ◦) algebrai struktúra zéruseleme, ha bármely a∈A esetén u◦a=a◦u=u. Az asszociatív algebrai struktúrát félcsoportnak nevezzük. Ha az (A; ◦) tetszőleges egységelemes algebrai struktúra, akkor a b∈A az a∈A elem inverze, ha a◦b=b◦a=1 jelölése: a-1 Egy (A, ◦) algebrai struktúra a,b elemei felcserélhetőek ha a◦b=b◦a Ha az (A; ◦) algebrai struktúrában van egységelem, akkor az egyértelmű. Általános asszociativitás tétele: Tetszőleges (A; ◦)

félcsoportban bármely a 1 ,,a k (k∈N) elemére az a 1 ◦◦a k szorzat eredménye nem függ a zárójelezéstől. Általános kommutativitás tétele: Kommutatív félcsoportban a többtényezős szorzatok nem függnek a tényezők sorrendjétől. Hatványozás: Legyen (A; ◦) tetszőleges félcsoport, n∈N és a∈A. an jelöli az n -tényezős a◦a◦◦a szorzatot. Az (A; ◦) csoport, ha félcsoport és minden elemnek van inverze. Ha az a∈A elemnek van inverze, akkor az an (n∈N) elemnek is van inverze és (an)-1=(a-1)n Legyen (A; ◦) tetszőleges csoport, a∈A és n∈N Ekkor: a0=1 és a-n=(an)-1 20 BEVEZETÉS A MATEMATIKÁBA TÉTELEK Azonosságok: Legyen (A; ◦) tetszőleges félcsoport, a,b∈A és m,n∈N. Ekkor: (am)n= am*n a, am◦an=am+n b, ha a,b felcserélhető, akkor (a◦b)n= an◦bn Legyen (A; ◦) tetszőleges félcsoport, a,b∈A és m,n∈Z. Ekkor: (am)n= am*n a, am◦an=am+n b, ha a,b felcserélhető, akkor (a◦b)n= an◦bn c, Ha a

invertálható, akkor (a-1)-1=a d, Ha a,b invertálható, akkor (a◦b)-1=b-1◦a-1 e, Ha a invertálható, akkor a-1 egyértelmű Gyűrű: Test: Az (A;+, ◦) algebrai struktúrát gyűrűnek nevezzük, ha: az (A;+) kommutatív csoport az (A; ◦) félcsoport a ◦ disztributív az + -ra nézve. Az (A;+; ◦) kommutatív gyűrű, ha gyűrű és a ◦ kommutatív Testnek nevezzük az olyan kommutatív gyűrűt, ahol az (A{0};◦) csoport. 21 BEVEZETÉS A MATEMATIKÁBA TÉTELEK 12. Komplex számok bevezetése: Olyan testet szeretnénk konstruálni, amely tartalmazza a valós számtestet, és amelyben a negatív számokból is lehet négyzetgyököt vonni. Legyen T=(R×R;+; ◦) olyan test, ahol a + és a ◦ műveletek a következők: tetszőleges (a,b),(c,d) ∈R×R esetén: (a,b)+(c,d)=(a+c,b+d) (a,b)◦(c,d)=(a◦c-b◦d,a◦d+b◦c) zéruselem: (0,0) egységelem: (1,0) (0,1)2=(0,1)(0,1)=(-1,0) (a,b)=(a,0)+(b,0)(0,1) i=(0,1) i2=-1 (a,b)=a+bi (a,b)-1=(a/(a2+b2),-b/(a2+b2)) A

T-ből a fent leírt azonosítás után keletkező testet komplex számtestnek, elemeit komplex számoknak nevezzük. Jele: C (0,1)=i i2=-1 Minden szám előáll a+bi alakban, ahol a,b ∈R A komplex számoknak az a+bi alakját kanoniskus alaknak, a-t valós résznek , b-t képzetes résznek, i-t képzetes egységnek nevezzük. Z=a+bi esetén: Re z =a Imz =b A Z=a+bi komplex szám konjugáltján a /Z=a-bi komplex számot értjük. (/Z=Z felülvonás) A Z komplex szám abszolút értékén a √ (Z*/Z)= √ (a2+b2) valós számot értjük. Jele: |Z| A Z=r*(cosα+isinα) alakot a Z=a+bi komplex stám trigonometrikus alakjának nevezzük. r=√(a2+b)=|Z| α a Z argumentuma a=r*cosα b=r*sinα A Z= a+bi=r(cosα+i*sinα) komplex szám exponenciális alakjának nevezzük az eiα= cosα+i*sinα számot. 22 BEVEZETÉS A MATEMATIKÁBA TÉTELEK Azonosságok: Tetszőleges u,v∈C számokra: a, /(u+v)=/u+/v , /(u*v)=/u/v //u=u , /(-u)=-/u ((egy osztva u) konjugáltja=egy osztva (u

konjugáltja)) /(1/u)=1/(/u) b, u=/u akkor és csak akkor, ha u∈R. c, u+/u=2*Re u u- /u=2*iImu |(1/u)|=1/|u| |/u|=|u| d, |u|2=u*/u e, 1/u=/u/(|u|2) f, |u*v|=|u||v| g, |u+v|≤|u|+|v| háromszög egyenlőtlenség Ha a Z=r(cosϕ+i*sinϕ)= s(cosψ+isinψ), ahol r,s, ψ,ϕ∈R, akkor r=s és ϕ-ψ=2kπ, k∈Z Tetszőleges Z=r(cosϕ+i*sinϕ) és W=s(cosψ+isinψ) komplex számokra: a, /Z=r*(cos(-ϕ)+isin(-ϕ))=r(cosϕ-isinϕ) b, Z*W=rs(cos(ϕ +ψ)isin(ϕ +ψ)) c, 1/Z=1/r*(cos(-ϕ)+isin(-ϕ)) d, Z/W=r/s*(cos(ϕ-ψ)+isin(ϕ-ψ)) n∈ Z esetén: e, Zn=rn(cos(n*ϕ)+isin(nϕ)) Gyökvonás komplex számokból: Minden 0-tól különböző komplex számnak pontosan n különböző n-edik gyöke van a komplex számok között. Ha Z=a+b*i=r(cosϕ+isinϕ), akkor Z n-edik gyökei: n √Z= n√r*( cos((ϕ+2kπ)/n)+isin((ϕ+2kπ)/n), k=0,1,n-1 Komplex egységgyökök: Az 1 komplex szám n-edik gyökeit n-edik egységgyököknej hívjuk. jele: ε k n √1=1 , i=cos0+i*sin0 ε k

=cos((2kπ)/n)+i*sin((2kπ)/n) Ha u egy nedik egységgyöke z-nek, akkor z gyökei: u, u*ε 1 , uε 1 2,, uε 1 n-1 23