Tartalom, témakörök
Bevezető fejezetek
- Halmazok, halmazműveletek. Matematikai és nem matematikai tartalmú halmazba rendezések.⇒ (Kopasz 1996: 21-24; Borsodi-Göndöcs 1970: 9-48)
- Gyakorló feladatok⇒
- Relációk fogalma, megadási módjai, tulajdonságai.⇒ (Vajda 1996: 30-42; Borsodi-Göndöcs 1970: 48-61)
- Gyakorló feladatok⇒
- Az ekvivalenciareláció és a rendezési relációk.⇒ (Vajda 1996: 40-41; Borsodi-Göndöcs 1970: 58-60)
- Gyakorló feladatok⇒
- Függvények fogalma, megadási módjai, tulajdonságai.⇒ (Vajda 1996: 42-50; Borsodi-Göndöcs 1970: 61-71)
- Gyakorló feladatok⇒
- Sorozatok. A számosság fogalma. A természetes számfogalom kialakítása.⇒ (Vajda 1996: 50-54; Brindza 1996: 55-60; Borsodi-Göndöcs 1970: 235-239; 72-80)
- Gyakorló feladatok⇒
- további témakörök (6-13) ⇒
Egyéb információk
1.1. Halmazok, halmazok megadása
A különböző objektumok (dolgok, tárgyak, fogalmak stb.) bizonyos összességét halmaznak nevezzük. A halmaz és a halmazelem fogalmát alapfogalomnak tekintjük és nem definiáljuk (vö. Kopasz 1996: 21).
A halmazokat rendszerint nagybetűkkel jelöljük, a halmazok elemeit pedig rendszerint kisbetűkkel. Azt, hogy a 'p' dolog (tárgy, fogalom stb.) az 'I' halmaz eleme, p∈ I módon jelöljük. Ezt formálisan
p∈ I ⇋ "p eleme az I halmaznak"
módon írhatjuk le.
Azt, hogy egy 'q' dolog nem eleme az I halmaznak, q∉ I módon jelöljük. Ezt formálisan
q∉ I ⇋ "q nem eleme az I halmaznak"
módon írhatjuk le.
Egy probléma tárgyalása során mindig megadunk egy alaphalmazt (Kopasz 1996: 21). Egy halmazt akkor tekintünk adottnak (vagy meghatározottnak), ha bármely objektumról eldönthető, hogy eleme-e a halmaznak vagy sem (Bonifert-Kovácsné Győri 1987: 5). Egy adott halmaz esetében mindig feltételezzük, hogy a halmazelemek azonosságát ("egyenlőségét"), ill. különbözőségét tetszőlegesen kiválasztott két elem esetén bármikor el tudjuk dönteni.
Egy halmaz elemei mindig különbözők.A halmazok megadása többféleképpen lehetséges:
- az elemek felsorolásával: a halmaz elemeit kapcsos zárójelek között adjuk meg, vesszővel elválasztva (jegyezzük meg, hogy a felsorolt elemek sorrendje nem számít);
- az elemek jellemzésével: ilyenkor a halmaz elemeit egy alaphalmazból választjuk ki az elemek egy vagy több közös tulajdonságának a megadásával (az így megadott halmaz az alaphalmaz részhalmaza⇒ lesz).
Példák halmazok megadására az elemek felsorolásával:
- egy osztály tanulóinak halmaza:
I = {"Tercsi", "Fercsi", "Kata", "Klára", "Anett", "Peti", "Mari", "Pisti", "Zoli", "Zsuzsa"}
- az I véges halmaz elemeinek száma: |I|=10
- a decimális számjegyek halmaza:
D = {0,1,2,3,4,5,6,7,8,9}
- a D véges halmaz elemeinek száma: |D|=10
- a bináris számjegyek halmaza:
B = {0,1}
- a B véges halmaz elemeinek száma: |B|=2
- a hexadecimális számjegyek halmaza:
X = {0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F}
- az X véges halmaz elemeinek száma: |X|=16
Ha egy halmaz végtelen sok elemből áll, az összes elem felsorolása nem lehetséges. Ilyen esetekben például úgy járhatunk el, hogy a halmaz első néhány elemét felsoroljuk, és feltételezzük, hogy a halmaz többi elemét valamilyen (ismert) szabály alapján képezni tudjuk. Példák ilyen módon megadott végtelen halmazokra:
- a természetes számok halmaza:
ℕ = {0,1,2,3,4,...,∞}
- A további elemek előállítása úgy történhet, hogy a felsorolt utolsó elemhez egyet hozzáadunk.
- a pozitív természetes számok halmaza:
ℕ+ = {1,2,3,4,...,∞}- a primszámok halmaza:
ℙ = {2,3,5,7,11,13,...,∞}
- A további elemek előállítása úgy történhet, hogy a felsorolt utolsó elemhez addig adunk hozzá egyet, amíg az így kapott szám csak eggyel és önmagával lesz osztható.
Ha egy halmazt az elemek jellemzésével adunk meg, akkor szükségünk van egy alaphalmazra (vagy "univerzumra"), amelyből megadott tulajdonságok segítségével ki tudjuk választani a halmaz elemeit.
A halmaz elemeit közösen jellemző tulajdonságokat a | jel után (ritkábban a : után) soroljuk fel, vesszővel elválasztva. Ebben az értelemben a vessző a logikai 'és' műveletnek felel meg. (Az elemek jellemzése során számos további logikai műveletet is használhatunk.)
Jegyezzük meg, hogy
– sok esetben az alaphalmazba tartozást még a | elválasztójel előtt megadjuk;
– az elválasztó jel után az elemek tulajdonságait megadhatjuk szövegesen (ún. leíró megadási mód révén), formálisan (matematikai szimbólumokat használva), vagy a kettő kombinálásával.Példák halmazok megadására a halmazelemek jellemző tulajdonságának (vagy tulajdonságainak) a megadásával:
- egy 'I' osztályban tanuló fiúk és lányok halmaza:
Q = {q∈I | "q fiú"}
R = {r∈I | "r lány"}
(például a Q halmaz fenti megadását "azok a 'q' tanulók az 'I' osztályból, akik fiúk" módon olvashatjuk)- egy 'b' természetes szám (b∈ℕ) osztóinak halmaza:
Db = {a∈ℕ | van olyan q∈ℕ természetes szám, amelyre b=q*a teljesül}
- tömören ezt így írhatjuk le:
Legyen az alaphalmaz a természetes számok halmaza (ℕ) és ennek megfelelően jelöljenek az 'a', 'b', 'c', ..., 'q' szimbólumok ("változók") természetes számokat (a, ..., q∈ℕ). Ekkor a 'b' természetes szám osztóinak halmaza
Db = {a∈ℕ | ∃q (b=q*a)}
- az ∃ ún. egzisztenciális kvantor jelentése: "van olyan", ill. "létezik olyan"
- az oszthatóság⇒ fogalmát felhasználva a 'b' természetes szám osztóinak halmaza
Db = {a∈ℕ | a|b}
módon is leírható.- a kétjegyű páros számok halmaza:
P = {n∈ℕ | 10≤n<100, 2|n}
ahol
▸ 2|n ⇋ "2 osztója n-nek";
▸ a P halmaz fenti megadását "azok az 'n' természetes számok, amelyek a [10,100) balról zárt, jobbról nyílt intervallumba esnek és párosak" módon olvashatjuk;
▸ az [10,100) intervallum a ℕ halmaz részhalmaza, azaz [10,100)⊆ℕ teljesül;
▸ a [10,100) balról zárt, jobbról nyílt intervallumot [10,100[ formában is jelölhetjük.- a primszámok halmaza:
ℙ = {n∈ℕ | n>1, és nem létezik olyan k∈ℕ természetes szám, amelyre 1<k<n és k|n teljesül}
- formálisan ezt így írhatjuk le:
legyen az alaphalmaz a természetes számok halmaza (ℕ) és ennek megfelelően jelöljenek az 'a', ..., 'k', ..., 'n' változók természetes számokat (a, ..., n∈ℕ). Ekkor a primszámok halmaza
ℙ = {n∈ℕ | n>1 ∧ ⌝∃k (1<k<n ∧ k|n)}- a fenti formális leírás logikailag ekvivalens (≡) a következővel:
ℙ = {n∈ℕ | n>1 ∧ ∀k (1<k<n ⊃ k∤n)}
a fenti leírás második feltétele például a következőképpen olvasható: "bármely 'k' természetes számra teljesül, hogy ha a (1<k<n) feltétel igaz, abból következik az, hogy 'k' nem osztója 'n'-nek"
- az ∧ szimbólum a logikai "és" műveletet jelöli
- a ⌝ szimbólum a logikai "nem" műveletet jelöli
- az ∀ ún. univerzális kvantor jelentése: "bármely olyan", ill. "minden olyan"
- az ⊃ szimbólum az implikáció logikai műveletét jelöli. Jelentése: "ha ... akkor ...", ill. "...-ből következik, hogy ..."
- érdemes megjegyezni, hogy a második feltételben használt kifejezések a logikai műveletek felhasználásával a következőképpen írhatóak le:
(1<k<n) ⇋ (1<k ∧ k<n)
k∤n ⇋ ⌝(k|n)A természetes számok ℕ halmazán egy 'n' szám akkor és csak akkor osztható a 'k' számmal, ha van olyan 'q' szám, amelyre n=q*k teljesül.
Azt, hogy a 'k' természetes szám osztója az 'n' természetes számnak, k|n módon jelöljük.
Az oszthatóság fenti meghatározásának az egyik következménye, hogy 0|0 teljesül, azaz a zérus önmagának osztója.
A halmazok ábrázolása ún. Venn-diagrammal történhet (Bonifert-Kovácsné Győri 1987: 6), amely a halmazok elemeit és az ezeket tartalmazó részhalmazokat szemléltető (rendszerint színes) ábra. A Venn-diagram konstruálásakor
- megadunk egy alaphalmazt (rendszerint téglalappal);
- megadjuk az alaphalmaz egy vagy több részhalmazát⇒ az alaphalmazt ábrázoló alakzaton belül (például körökkel, ellipszisekkel vagy tetszőleges zárt görbével);
- megadjuk az alaphalmaz elemeit a Venn-diagramon ábrázolt zárt alakzatok belső pontjaiként (ha egy pont egy adott alakzat belső pontja, akkor a pontnak megfeleltetett elem az alakzatnak megfeleltetett részhalmaznak az eleme).
Ha a Venn-diagramon például az 'I' alaphalmaz A⊆I, B⊆I, C⊆I és D⊆I részhalmazainak az elemeit akarjuk ábrázolni, akkor olyan alakzatokat kell használnunk, ahol négy lehetséges szín összes lehetséges kombinációja megjelenik az ábrázolt alakzatok közös, egymást kölcsönösen átfedő részeiként (beleértve azt is, amikor nincs szín, amely az E=I∖(A∪B∪C∪D) részhalmaz elemeinek felel meg). Tehát ha 'a', 'b', 'c' és 'd' színű alakzatokkal dolgozunk, akkor az
{a}, {b}, {c}, {d}, {a,b}, {a,c}, ..., {c,d}, {a,b,c}, ..., {b,c,d}, {a,b,c,d}
színeknek, ill. színkombinációknak kell megjelennie (egy "üres" téglalapban, amelynek "nincs színe"). Vegyük észre, hogy a fenti felsorolással a színek négy elemű halmazának a hatványhalmazát adtuk meg, amelynek elemszámára 24=16 teljesül.A Venn-diagram használatára tekintsük az alábbi példát.⇒
Legyen az ábrázolandó halmaz
H = {1,2,3,4,5,6,7}
és tételezzük fel, hogy a 'H ' halmaz elemei meghatározott tulajdonságokkal rendelkeznek. Csoportosítsuk a közös tulajdonsággal rendelkező elemeket az A, B és C halmazokba:
A = {1, 2, 5}
B = {1, 6}
C = {4, 7}
A H, valamint az A, B és C halmazokat a következőképpen ábrázolhatjuk Venn-diagramon:Kérdés: hová kerül a H halmaz '3' eleme a Venn-diagramon?
Feladat: keressünk olyan tulajdonságokat, amelyek alapján az A, B és C halmazok megadhatóak! (tipp: legyen a H alaphalmaz a törpék halmaza, és tegyük fel azt a kérdést, hogy milyen gyümölcsöket szeret a hét törpe?⇒ például legyen
A = {"azok a törpék, akik szeretik az epret"}
B = {"azok a törpék, akik szeretik a barackot"}
C = {"azok a törpék, akik szeretik a dinnyét"}
A kérdések megválaszolásához természetesen tudnunk kell azt is, hogy mit szeretnek az egyes törpék; pl. "Tudor, az első törpe ('1') szereti az epret" stb.)
1.2. Halmaz, részhalmaz, hatványhalmaz
Azt a halmazt, amelynek egyetlen eleme sincs, üres halmaznak nevezzük, és ∅ vagy {} módon jelöljük.
Az 'A' halmaz részhalmaza a 'B' halmaznak, ha az 'A' halmaz minden eleme eleme a 'B' halmaznak is:
A⊆B ⇋ "minden a∈A esetén a∈B teljesül"A két halmaz közötti részhalmaz viszony (vagy reláció) bizonyításának során az alábbi következtetések megértése és memorizálása nagyon fontos:
I. Az 'A' halmaz részhalmaza a 'B' halmaznak. A⊆B Az 'A' halmaz minden eleme eleme a 'B' halmaznak is. (tetszőleges 'x' elemre) x∈A ⇒ x∈B
II. Az 'A' halmaz minden eleme eleme a 'B' halmaznak is. (tetszőleges 'x' elemre) x∈A ⇒ x∈B Az 'A' halmaz részhalmaza a 'B' halmaznak. A⊆B A fenti következtetések esetében az "aláhúzás" az ok-okozati viszonyt fejezi ki a vonal felett álló logikai feltétel (premissza) és a vonal alatt álló következtetés között. Például az I. következtetési szabály így olvasandó:
– "Ha az 'A' halmaz részhalmaza a 'B' halmaznak, akkor az 'A' halmaz minden eleme eleme a 'B' halmaznak is."
– "Ha A⊆B teljesül, akkor tetszőleges (bármely, minden stb.) 'x' elemre x∈A teljesüléséből x∈B következik."Két halmaz egyenlő, ha az elemeik megegyeznek:
A=B ⇋ "minden a∈A esetén a∈B, és minden b∈B esetén b∈A teljesül", azaz
A=B ⇋ A⊆B és B⊆AEmeljük ki, hogy ha az 'A' és 'B' halmazokra A⊆B és B⊆A egyszerre teljesül, akkor abból a fenti definíció szerint A=B következik. Az ilyen típusú relációkat antiszimmetrikus relációknak⇒ nevezzük.
Ennek megfelelően az A és B halmazok különbözőek (nem egyenlők, A≠B), ha van olyan 'x' elem, amelyik csak az egyik halmaznak az eleme, a másiknak nem (azaz vagy x∈A és x∉B, vagy x∈B és x∉A teljesül).
Az 'A' halmaz részhalmazai:
- ∅⊆A (az üres halmaz minden halmaznak részhalmaza)
- A⊆A (minden halmaz részhalmaza önmagának)
- valódi részhalmaz (R⊂A): az 'A' halmaznak az az 'R' nem üres részhalmaza, amely nem tartalmazza A összes elemét (azaz van az A halmaznak olyan eleme, amely nem eleme az R részhalmaznak). Formálisan
R⊂A ⇋ R⊆A, R≠∅ és R≠A
Emeljük ki, hogy R≠∅, azaz az üres halmaz egyetlen halmaznak sem valódi részhalmaza.Az 'A' halmaz hatványhalmaza⇒ az 'A' halmaz összes részhalmazának halmaza (azaz a hatványhalmaz elemei az üreshalmaz, az 'A' halmaz valódi részhalmazai, és maga az 'A' halmaz):
2A ⇋ {X | X⊆A}Az 'A' halmaz hatványhalmazát P(A) módon is szokás jelölni.
Ha az 'A' halmaz véges és elemeinek száma |A|=n (n≥0), akkor a 2A halványhalmaz is véges és elemeinek száma |2A|=2n.Ha |A|=n, akkor rendezzük egy n elemű sorozatba az 'A' halmaz elemeit (azaz lássuk el őket sorszámokkal), és feleltessük meg a {0,1} jelekből álló
B=(b1, b2, ..., bn) (bi∈{0,1}, 1<=i<=n)bináris jelsorozatot az 'A' halmaz egyes részhalmazainak a következőképpen:egy tetszőleges R⊆A részhalmaznak az 'A' halmaz i-dik eleme pontosan akkor legyen az eleme, ha bi=1 teljesül (bi∈{0,1}, 1<=i<=n).Világos, hogy a csupa 0-ból álló jelsorozat az üreshalmaznak (∅), a csupa 1-ből álló jelsorozat pedig magának az 'A' halmaznak felel meg. Mivel pedig minden különböző jelsorozatnak különböző R⊆A részhalmaz felel meg, az 'A' halmaz összes részhalmazának száma megegyezik az összes különböző B jelsorozat számával. Ennek értéke két különböző elem n-ed rendű ismétléses variációja, azaz 2n.
1.3. Műveletek halmazokkal
Legyen 'I' egy halmaz, amelynek az elemeit a továbbiakban vizsgálni akarjuk (például egy osztály tanulóinak a halmaza, a természetes számok halmaza stb.). Az előzőek alapján⇒ nevezzük az 'I' halmazt alaphalmaznak.
Az 'I' alaphalmaz elemeiből álló tetszőleges 'A' halmaz esetén A⊆I teljesül.Legyen A⊆I és B⊆I két tetszőleges halmaz. Az 'A' és 'B' halmazok között a következő műveleteket értelmezzük:
(1) unió (egyesítés)
A∪B = {x∈I | x∈A vagy⇒ x∈B}
(Az A és B halmazok uniója pontosan azokat az elemeket tartalmazza, amelyek az A és B halmazok közül legalább az egyik halmaznak az elemei.)(2) metszet (közös rész)
A∩B = {x∈I | x∈A és⇒ x∈B}
(Az A és B halmazok metszete pontosan azokat az elemeket tartalmazza, amelyek az A és B halmazok közül mindkét halmaznak az elemei.)
- az A és B halmazokat diszjunktaknak nevezzük, ha nincs közös elemük (azaz A∩B=∅ teljesül)
(3) komplementer vagy kiegészítő halmaz (másként ún. abszolút komplementer halmaz)
A = {x∈I | x∉A}
(Az A halmaz (I-re vonatkozó) komplementere az I alaphalmaz összes olyan eleme, amely az A halmaznak nem eleme. Ez a logikai nem (negáció)⇒ műveletével A={x∈I | ⌝(x∈A)} módon fejezhető ki.)(4) különbség vagy differencia
A∖B = {x∈I | x∈A és x∉B} = A∩B
(Az A és B halmazok különbsége A-nak az összes olyan elemét tartalmazza, amely a B halmaznak nem az eleme.)
A∖B = A∩B
![]()
A B Megjegyzések:
- Az A és B halmazok A∖B különbsége vagy differenciája a logikai és és nem műveleteivel (az implikáció tagadásával⇒) az alábbi módon fejezhető ki:
- {x∈I | (x∈A) ∧ ⌝(x∈B)}
- a 'B' halmaz komplementer halmazának a kifejezése a differencia műveletével:
- B = I∖B = I∩B
- az I∖B = I∩B különbséget a 'B' halmaznak az 'I' halmazra vonatkozó abszolút komplementer halmazának, az A∖B különbséget pedig a 'B' halmaznak az 'A' halmazra (ill. az A∪B halmazra) vonatkozó relatív komplementer halmazának is nevezzük: (A∪B)∖B ≡ A∖B = A∩B
(5) szimmetrikus differencia
AΔB = {x∈I | x∈A∖B vagy⇒ x∈B∖A}
(Az A és B halmazok szimmetrikus különbsége az A halmaznak a B elemeitől különböző elemeiből vagy a B halmaznak az A elemeitől különböző elemeiből áll.Másképpen megfogalmazva: az A és B halmazok szimmetrikus különbsége pontosan azokat az elemeket tartalmazza, melyek vagy csak az A halmaznak, vagy csak a B halmaznak az elemei. Ez a logikai kizáró vagy⇒ műveletével {x∈I | (x∈A) ⨁ (x∈B)} módon fejezhető ki.)
a szimmetrikus differencia két lehetséges kifejezése az eddig tanult műveletekkel:
- AΔB = (A∖B)∪(B∖A)
- AΔB = (A∪B)∖(A∩B)
Mindegyik fenti halmazművelet eredménye egy I-beli halmaz, vagyis
A∪B⊆I, A∩B⊆I, A⊆I, A∖B⊆I és AΔB⊆I
teljesül.
A fenti műveletekkel kifejezhető az is, hogy az 'A' halmaz a 'B' halmaz részhalmaza.⇒ A definíció alapján belátható, hogy A⊆B (azaz A minden eleme egyúttal eleme B-nek is) pontosan akkor teljesül, ha a következő összefüggések teljesülnek:
- A = A∩B
- A∪B = I (az előző összefüggésből I=A∪A=A∪(A∩B) következik, innen egyszerű átalakításokkal már adódik az A∪B=I összefüggés)
- A∪B = B
- A∖B = A∩B = ∅
Az első összefüggés bizonyítása:
(1) Tegyük fel, hogy A⊆B teljesül. Ekkor egyrészt A⊆A miatt A⊆A∩B teljesül, másrészt a metszetképzés definíciója miatt A∩B⊆A mindig teljesül. Ebből viszont⇒ A=A∩B következik (szükséges feltétel).
(2) Tegyük fel, hogy A=A∩B teljesül. Ekkor az egyenlőség definíciója⇒ miatt minden x∈A elem esetén x∈A∩B teljesül, ebből viszont a metszetképzés definíciója⇒ miatt x∈B teljesül. De ez a részhalmaz definíciója⇒ miatt éppen A⊆B teljesülését jelenti (elégséges feltétel).Az A⊆B ⇔ A=A∩B összefüggés bizonyításának lépései formálisan leírva (∧ ⇋ "és", ∨ ⇋ "vagy"):
- tegyük fel, hogy A⊆B
- x∈A ⇒ x∈B
- x∈A ∧ x∈B ⇒ x∈(A∩B)
- tehát A⊆(A∩B)
- x∈(A∩B) ⇒ x∈A ∧ x∈B
- x∈A ∧ x∈B ⇒ x∈A
- tehát (A∩B)⊆A
- A⊆(A∩B) ∧ (A∩B)⊆A ⇒ A=A∩B (antiszimmetria!)
- tegyük fel, hogy (A∩B)=A
- x∈A ⇒ x∈(A∩B)
- x∈(A∩B) ⇒ x∈A ∧ x∈B
- x∈A ∧ x∈B ⇒ x∈B
- tehát A⊆B
- (A⊆B ⇒ (A∩B)=A) ∧ ((A∩B)=A ⇒ A⊆B) ⇒ (A⊆B ⇔ (A∩B)=A) (q.e.d. = ezt akartuk bizonyítani)
1.4. A halmazműveletek főbb tulajdonságai
Legyen az 'I' halmaz alaphalmaz (ún. teljes halmaz), az A, B, C⊆I halmazok pedig az alaphalmaz tetszőleges részhalmazai. Ekkor teljesülnek az alábbi azonosságok:
- kettős komplementálás:
- A = A
- a metszetképzés idempotenciája:
- A∩A=A
- a metszetképzés kommutativitása:
- A∩B=B∩A
- a metszetképzés asszociativitása:
- (A∩B)∩C=A∩(B∩C)
(Megjegyzés: a metszetképzés asszociativitása miatt egyszerűen A∩B∩C is írható. A kifejezés kiértékelése történhet pl. balról jobbra.)- metszetképzés a teljes halmazzal és az üreshalmazzal:
- A∩I=A
- A∩∅=∅
- az unióképzés idempotenciája:
- A∪A=A
- az unióképzés kommutativitása:
- A∪B=B∪A
- az unióképzés asszociativitása:
- (A∪B)∪C=A∪(B∪C)
(Megjegyzés: az unióképzés asszociativitása miatt egyszerűen A∪B∪C is írható. A kifejezés kiértékelése történhet pl. balról jobbra.)- unióképzés a teljes halmazzal és az üreshalmazzal:
- A∪I=I
- A∪∅=A
- disztributivitás:
- A∩(B∪C) = (A∩B)∪(A∩C)
- A∪(B∩C) = (A∪B)∩(A∪C)
- abszorpció (elnyelés; elimináció):
- A∩(A∪B) = A
- A∪(A∩B) = A
- de Morgan-féle azonosságok:
- (A∩B) = A∪B
- (A∪B) = A∩B
- műveletek a halmaz és komplementere között:
- A∩A=∅
- A∪A=I
- a teljes halmaz és az üreshalmaz komplementer halmaza:
- I=∅
- ∅=I
Egy kifejezés duálisán azt a kifejezést értjük, amely az eredeti kifejezésből úgy keletkezik, hogy bizonyos műveleti jeleket és egyéb szimbólumokat kicserélünk az alábbiak szerint:
- ∪ helyett ∩
- ∩ helyett ∪
- ∅ helyett I
- I helyett ∅
A fenti azonosságok mindegyikére érvényes a dualitás törvénye: ha egy azonosság mindkét oldalát "dualizáljuk" (azaz mindkét oldalon az ott szereplő kifejezés helyére a kifejezés duálisát írjuk), szintén azonossághoz jutunk.
A fenti azonosságokat átalakíthatjuk úgy, hogy eredményül ismét érvényes azonosságokat kapunk (vö. Ruzsa 1968a: 458-459).
(1) Egy azonosságban szereplő bármelyik (A, B, ...) változó minden előfordulását helyettesíthetjük egy másik kifejezéssel (ez az ún. helyettesítés elve).
Például hajtsuk végre az alábbi helyettesítéseket az A∖B = A∩B azonosságban:
A∖B = A∩B helyettesítéssel kapott kifejezés helyettesítés C∖B = C∩B A↔C A∖D = A∩D B↔D C∖D = C∩D A↔C, B↔D B∖A = B∩A A↔B, B↔A A∖B = A∩B B↔B A∖(A∩B) = A∩(A∩B) B↔A∩B (A∪B)∖B = (A∪B)∩B A↔A∪B (2) Egy azonosságban szereplő bármelyik kifejezést kicserélhetjük ("pótolhatjuk") egy vele azonosan egyenlő kifejezéssel (ez az ún. pótlás elve)
- Például, ha az unióképzés kommutativitását kifejező A∪B=B∪A azonosság bal oldalán szereplő A változót kicseréljük ("pótoljuk") az abszorpciót kifejező A∪(A∩B)=A azonosságnak megfelelően az A↔(A∪(A∩B)) ekvivalens kifejezéssel, akkor a szintén bármilyen A és B esetén érvényes (A∪(A∩B))∪B=B∪A azonossághoz jutunk. Az unióképzés kommutativitása és asszociativitása miatt ez A∪B=A∪(A∩B)∪B módon is felírható. (Tipp: hasonlítsuk össze a kapott azonosságot az unióképzés szemléltetésére használt Venn-diagrammal!)
- Második példaként az A∖B = A∩B azonosságban hajtsuk végre először a B↔B helyettesítést 'B' minden előfordulására (ld. a fenti táblázat megfelelő sorában), majd végezzük el a kettős komplementálás azonosságának megfelelően a B=B cserét ("pótlást") a helyettesítés után kapott kifejezés jobb oldalán. Eredményül az A∖B = A∩B azonossághoz jutunk.
A fenti átalakításokat használjuk olyankor, amikor két kifejezés azonosságát akarjuk levezetni. A levezetés során kiindulunk az egyik (rendszerint összetettebb) kifejezésből, és olyan átalakításokat keresünk, amelyek révén végül a másik kifejezést kapjuk.
Balassa Zsófia (szerk.) 1996. Matematika feladatgyűjtemény az általános képzéshez a tanítóképző főiskolák számára. Budapest: Nemzeti Tankönyvk.
Birkhoff, Garrett – Bartee, Thomas C. 1974. A modern algebra a számítógép-tudományban. Budapest: Műszaki K.
Bogya Norbert 2018. Elméleti összefoglaló a Diszkrét matematika I. gyakorlathoz. Szeged: SZTE.
http://eta.bibl.u-szeged.hu/1531/1/diszkret_mat.pdf, 2020-09-20.
Bonifert Domokos – Kovácsné Győri Ida 1987. Matematika a tanítók intenzív továbbképzéséhez. Budapest: [k.n.].
Borsodi István 1972. A matematikai logika elemei. In: Borsodi István – Göndöcs László (szerk.) 1972. 255-320.
Borsodi István – Göndöcs László (szerk.) 1970. Matematika a tanítóképző intézetek első évfolyama számára. Budapest: Tankönyvk.
Borsodi István – Göndöcs László (szerk.) 1972. Matematika a tanítóképző intézetek harmadik évfolyama számára. Budapest: Tankönyvk.
Brindza Attila 1996. A természetes számok halmaza. In: Pappné Ádám Györgyi (szerk.) 1996. 55-72.
Csizmadia László 2009. Bevezetés az analízisbe. [előadás vázlat]
http://www.math.u-szeged.hu/~csizmadia/Bevanalea1.pdf, 2020-10-26.
Dragálin Albert – Buzási Szvetlana 1986. Bevezetés a matematikai logikába. Debrecen: KLTE TTK.
Dringo L. – Kátai I. 1986. Bevezetés a matematikába. Budapest: Tankönyvk.
Farkas Miklós (szerk.) 2001. Matematika. I. kötet. A matematika alapjai. Budapest: Műegyetemi K.
Farkas Miklós – Fritz Józsefné – Kiss Ernőné 2000. Matematika. II. kötet. Egyváltozós valós függvények. (szerk. Farkas Miklós.) Budapest: Műegyetemi K.
Bognár László – Forrai Gábor (szerk.) 2004. Esszéírás és Informális logika. Budapest: Budapest – Miskolc: Bölcsész Konzorcium.
https://www.uni-miskolc.hu/~bolantro/informalis/index.html, 2020-11-07.
http://gepeskonyv.btk.elte.hu/adatok/Altalanos%20bolcseszet/6Forrai/essz%E9%EDr%E1s%20%E9s%20inform%E1lis%20logika/index.html, 2020-11-07.
Fried Ervin 1968. Algebra. In: Lukács Ernőné – Tarján Rezsőné (szerk.) 1968. 5-132.
Fried Katalin – Korándi József – Török Judit 2013. A modern algebra alapjai. Budapest: ELTE Természettudományi Kar.
https://regi.tankonyvtar.hu/hu/tartalom/tamop412A/2011-0073_bevezetes_modern_algebraba/index.html, 2020-10-26.
Gémes Margit – Szentmiklóssy Zoltán 2015. Bevezetés a matematikába. Jegyzet és példatár kémia BsC-s hallgatók számára. Budapest: ELTE TTK Matematikai Intézet.
http://web.cs.elte.hu/~szzoltan/bmk/bmk.html#content, 2020-10-25.
Herendiné Kónya Eszter 2013. A természetes számfogalom alakítása. In: Herendiné Kónya Eszter (szerk.) 2013. 12-27.
Herendiné Kónya Eszter (szerk.) 2013. A matematika tanítása az alsó tagozaton. Budapest: Nemzedékek Tudása Tankönyvk.
Kiss Andrea 1996. Logika, halmazok. In: Balassa Zsófia (szerk.) 1996. 11-25.
Kiss Emil 2007. Bevezetés az algebrába. Budapest: Typotex K.
Kopasz Éva 1996. Logika, halmazok. In: Pappné Ádám Györgyi (szerk.) 1996. 11-29.
Kozma László 2004. Matematikai alapok. [Egyetemi jegyzet.] Debrecen: Debreceni Egyetem.
Lavrov, I. A. – Maximova, L. L. 1987. Halmazelméleti, matematikai logikai és algoritmuselméleti feladatok. Budapest: Műszaki K.
Lukács Ernőné – Tarján Rezsőné (szerk.) 1968. Matematikai kisenciklopédia. Budapest: Gondolat K.
Margitay Tihamér 2014. Az érvelés mestersége. Budapest: Typotex K.
https://regi.tankonyvtar.hu/hu/tartalom/tamop425/2011-0001-526_margitay_az_erveles/adatok.html, 2020-08-26.
[MaYoR 2020] oktatas:matematika:halmazok:relacio [MaYoR elektronikus napló].
https://wiki.mayor.hu/doku.php?id=oktatas:matematika:halmazok:relacio, 2020-09-13.
Miklovicz András 2018. Alapozó feladatok. Halmazok és logika 3. osztályosoknak. Budapest: Babilon K.
Monostory Iván (szerk.) 2006. Matematika példatár I-II. A matematika alapjai. Egyváltozós valós függvények. Budapest: Műegyetemi K.
Nagy Gábor 2017. Diszkrét matematika 1. Középszint.
http://compalg.inf.elte.hu/~nagy/dm1_ea_17osz.html, 2020-09-20.
Obádovics J. Gyula 1972. Matematika. Középiskolai, technikumi tanulók, egyetemi hallgatók és technikusok számára, gyakorlati alkalmazásokkal. Budapest: Műszaki K.
Pappné Ádám Györgyi 1996. A számfogalom bővítése. In: Pappné Ádám Györgyi (szerk.) 1996. 73-102.
Pappné Ádám Györgyi (szerk.) 1996. Matematika az általános képzéshez a tanítóképző főiskolák számára. Budapest: Nemzeti Tankönyvk.
Pintér Klára 2013. Matematika módszertan.
http://www.jgypk.hu/mentorhalo/tananyag/Matematika_mdszertan/index.html, 2020-09-18.
Pintér Klára 2013. Matematika I. (tantárgypedagógia) óvóképzős hallgatók számára.
http://www.jgypk.hu/mentorhalo/tananyag/Matematika_I._tantrgypedaggia/index.html, 2020-09-18.
Ruzsa Imre 1968a. Halmazelmélet. In: Lukács Ernőné – Tarján Rezsőné (szerk.) 1968. 448-485.
Ruzsa Imre 1968b. Matematikai logika. In: Lukács Ernőné, Tarján Rezsőné (szerk.) 1968. Matemaikai kisenciklopédia. Budapest: Gondolat K. 530-564.
Sashalminé Kelemen Éva 2003. A matematikai logika és a halmazelmélet elemei. Eger: EKF Líceum K.
Szászné Virányi Katalin – Brindza Attila 1996. A természetes számok halmaza. In: Balassa Zsófia (szerk.) 1996. 37-45.
Szendrei János 1975. Algebra és számelmélet. Budapest: Tankönyvk.
Szendrei János – Tóth Balázs 1978. Logika a matematika szakos hallgatók részére. Budapest: Tankönyvk. (Tanárképző főiskolai jegyzet.)
Tallér József 1996. A logika alapjai. Szeged: Mozaik Oktatási Stúdió.
Vajda János 1996. Megfeleltetések, relációk, leképezések (függvények), sorozatok. In: Pappné Ádám Györgyi (szerk.) 1996. 30-54.
Vajda János 1996. A számfogalom bővítése. In: Balassa Zsófia (szerk.) 1996. 46-51.
Veress Róbertné 1996. Megfeleltetések, relációk, leképezések (függvények), sorozatok. In: Balassa Zsófia (szerk.) 1996. 26-36.
A matematikai logika alapjai.
(Informatika 6. évfolyam | Sulinet Tudásbázis)
https://tudasbazis.sulinet.hu/HU/informatika/informatika/informatika-6-evfolyam/logikai-muveletek-es-kapuk/a-matematikai-logika-alapjai, 2018-12-08.
Mikulás mese gyűjteménye. Grimm legszebb meséi. Hófehérke.
http://www.mikulasbirodalom.hu/mese/grim/hofeherke.htm, 2020-07-30.
Egész számok. Wikipédia.
https://hu.wikipedia.org/wiki/Eg%C3%A9sz_sz%C3%A1mok, 2020-10-14.
Fa (adatszerkezet). Wikipédia.
https://hu.wikipedia.org/wiki/Fa_(adatszerkezet), 2020-09-20.
Fibonacci-számok. Wikipédia.
https://hu.wikipedia.org/wiki/Fibonacci-sz%C3%A1mok, 2020-10-13.
Görög ábécé. Wikipédia.
https://hu.wikipedia.org/wiki/G%C3%B6r%C3%B6g_%C3%A1b%C3%A9c%C3%A9, 2020-09-16.
Halmaz. Wikipédia.
https://hu.wikipedia.org/wiki/Halmaz, 2020-07-27.
Hasse-diagram. Wikipédia.
https://hu.wikipedia.org/wiki/Hasse-diagram, 2020-08-20.
Háló (matematika). Wikipédia.
https://hu.wikipedia.org/wiki/H%C3%A1l%C3%B3_(matematika), 2020-09-20.
Hatványhalmaz. Wikipédia.
https://hu.wikipedia.org/wiki/Hatv%C3%A1nyhalmaz, 2020-07-30.
Cantor-tétel. Wikipédia.
https://hu.wikipedia.org/wiki/Cantor-t%C3%A9tel, 2020-10-20.
Hatvány. Wikipédia.
https://hu.wikipedia.org/wiki/Hatv%C3%A1ny, 2020-10-03.
Logikai függvények. Wikipédia.
https://hu.wikipedia.org/wiki/Logikai_f%C3%BCggv%C3%A9nyek, 2020-11-08.
Osztályfelbontás. Wikipédia.
https://hu.wikipedia.org/wiki/Oszt%C3%A1lyfelbont%C3%A1s, 2020-09-26.
Páros és páratlan számok. Wikipédia.
https://hu.wikipedia.org/wiki/P%C3%A1ros_%C3%A9s_p%C3%A1ratlan_sz%C3%A1mok, 2020-10-22.
A nulla paritása. Wikipédia.
https://hu.wikipedia.org/wiki/A_nulla_parit%C3%A1sa, 2020-10-22.
Giuseppe Peano. Wikipédia.
https://hu.wikipedia.org/wiki/Giuseppe_Peano, 2020-10-02.
Permanenciaelv. Wikipédia.
https://hu.wikipedia.org/wiki/Permanenciaelv, 2020-10-03.
Pitagorasz-tétel. Wikipédia.
https://hu.wikipedia.org/wiki/Pitagorasz-t%C3%A9tel, 2020-10-24.
Polinom. Wikipédia.
https://hu.wikipedia.org/wiki/Polinom, 2020-10-26.
Rendezett halmaz. Wikipédia.
https://hu.wikipedia.org/wiki/Rendezett_halmaz, 2020-07-30.
Set Operations and Venn Diagrams.
https://www.math24.net/set-operations-venn-diagrams/, 2020-07-30.
Siklófélék. Wikipédia.
https://hu.wikipedia.org/wiki/Sikl%C3%B3f%C3%A9l%C3%A9k, 2020-10-12.
Symmetric difference. Wikipedia.
https://en.wikipedia.org/wiki/Symmetric_difference, 2020-07-30.
Számosság. Wikipédia.
https://hu.wikipedia.org/wiki/Sz%C3%A1moss%C3%A1g, 2020-07-30.
Kardinális szám. Wikipédia.
https://hu.wikipedia.org/wiki/Kardin%C3%A1lis_sz%C3%A1m, 2020-07-30.
Teljes indukció. Wikipédia.
https://hu.wikipedia.org/wiki/Teljes_indukci%C3%B3, 2020-10-02.
Természetes számok. Wikipédia.
https://hu.wikipedia.org/wiki/Term%C3%A9szetes_sz%C3%A1mok, 2020-07-30.
Tizedestört. Wikipédia.
https://hu.wikipedia.org/wiki/Tizedest%C3%B6rt, 2020-11-22.
Tree (set theory). Wikipedia.
https://en.wikipedia.org/wiki/Tree_(set_theory), 2020-09-26.
Valós számok. Wikipédia.
https://hu.wikipedia.org/wiki/Val%C3%B3s_sz%C3%A1mok, 2020-10-25.
Venn diagram. Wikipedia.
https://en.wikipedia.org/wiki/Venn_diagram, 2020-07-26.
Venn-diagram. Wikipédia.
https://hu.wikipedia.org/wiki/Venn-diagram, 2020-08-13.