Matematika 1 (folytatás)

Tartalom, témakörök

  1. ⇐ megelőző témakörök (1-5)
  2. Állítások, logikai műveletek.⇒ (Kopasz 1996: 11-15; Borsodi 1972: 255-294)
    • A fontosabb logikai műveletek értéktáblázatai⇒
    • Az értéktáblázatok elkészítésének lépései⇒
    • Az értéktáblázatok gyakorlása⇒
    • Gyakorló feladatok⇒
  3. (a) Logikai azonosságok, logikai következtetések. Köznyelvi és matematikai tartalmú szövegek formalizálása.⇒ (Kopasz 1996: 15-20; Borsodi 1972: 294-314)
  4. (b) Következtetési sémák. Példák következtetési sémák használatára.⇒
    • Gyakorló feladatok⇒
  5. A halmazműveletek és a logikai műveletek kapcsolata. Kvantifikáció.⇒ (Kopasz 1996: 24-25; 26-29; Borsodi 1972: 314-320)
    • Gyakorló feladatok⇒
  6. A természetes számfogalom. Peano-axiómák, a teljes indukció. A számfogalom kialakításának lépései.⇒ (Brindza 1996: 61-65; Borsodi-Göndöcs 1970: 81-92)
    • Gyakorló feladatok⇒
  7. A négy alapművelet elméleti megalapozása.⇒ (Brindza 1996: 65-72; Borsodi-Göndöcs 1970: 92-134)
  8. Az egész számok halmaza.⇒ (Pappné Ádám 1996: 73-82; Borsodi-Göndöcs 1970: 183-199)
  9. A racionális számok halmaza.⇒ (Pappné Ádám 1996: 82-95; Borsodi-Göndöcs 1970: 199-220)
  10. A valós számok halmaza.⇒ (Pappné Ádám 1996: 102; Borsodi-Göndöcs 1970: 221-235)

Matematikai logika (alapfogalmak, tételek, feladatok)

  1. kijelentés vagy állítás
  2. természetes nyelven adott (tő)mondatok formalizálása (kijelentésváltozó, predikátum, individuumnevek, individuumváltozók)
  3. nyitott mondat vagy (atomi) formula; alaphalmaz(ok); helyettesítés, értékelés
  4. tárgyalási univerzum
  5. logikai alapelvek
  6. logikai műveletek, logikai kifejezések vagy formulák; értékelési alapelv
  7. értéktáblázatok vagy igazságtáblázatok
  8. fontosabb logikai műveletek és értéktáblázatuk
  9. összetett kifejezések értéktáblázatának elkészítése⇒⇒
  10. a logikai műveletek végrehajtásának sorrendje (műveletek "precedenciája"); a pont (.) operátor
  11. kijelentéslogika, kijelentésváltozók
  12. szabványkijelentések; a logikai alapelvek leírása szabványkijelentések segítségével
  13. logikai kifejezések ekvivalenciája; logikai azonosságok
  14. a felsorolt logikai azonosságok felhasználása további azonosságok bizonyítására (levezetésére)⇒
  15. a helyettesítés elve és az egyenértékű pótlás (vagy kicserélés) elve
  16. logikai következmény; premissza és konklúzió
  17. logikai törvény; tautológia
  18. a felsorolt logikai azonosságok felhasználása logikai törvények bizonyítására (levezetésére)⇒
  19. a logikai következmény leírása implikációt tartalmazó logikai törvény formájában
  20. logikai következtetések érvényessége és értelmessége
  21. következtetési sémák; szillogizmusok
  22. általános következtetési sémák
  23. gyakran haszált következtetési sémák
  24. fontosabb szillogizmusok
  25. példák következtetési sémák alkalmazására

6.1. Kijelentések, állítások

Kijelentésen vagy állításon olyan kijelentő mondatot értünk, amely valamely személyről, tárgyról, dologról stb. megállapít valamit. Egy kijelentés logikai értéke (vagy igazságértéke) igaz (1) vagy hamis (0) lehet. (vö. Kopasz 1996: 11)

Egy kijelentésről mindig egyértelműen eldönthető, hogy az igazságértéke igaz vagy hamis.

Egy kijelentés egy predikátumból ("állítmányból") és egy vagy több individuumnévből áll. Például tekintsük az alábbi kijelentést:

Egy kijelentést formalizálhatunk úgy, hogy a kijelentés egyes összetevőit, és magát a kijelentést is betűkkel helyettesítjük.

A predikátumok kétértékű (logikai) függvények, esetükben az egyes individuumneveket tartalmazó halmazok direkt szorzata a függvények értelmezési tartománya.⇒

Példák:

6.2. Nyitott mondatok

Ha egy kijelentésben egy vagy több individuumnevet individuumváltozókkal helyettesítünk, nyitott mondathoz jutunk. (A nyitott mondattal lényegében egyező értelemben használhatjuk az (elemi vagy atomi) formula terminust is. A továbbiakban, ha nem okoz félreértést, individuumváltozók helyett egyszerűen változókról fogunk beszélni.)

Egy nyitott mondat esetében minden individuumváltozó egy meghatározott alaphalmazból vehet fel értéket. Az alaphalmaz ebben az értelemben meghatározza az illető változó típusát.

Például formalizáljuk a p ⇋ "Paks a Duna mellett fekszik." kijelentést p ⇋ P(a,b) módon. Ekkor

  • az 'a' változó lehetséges értékei városnevek lehetnek (a∈V, ahol V={"Paks", "Tokaj", ...});
  • a 'b' változó lehetséges értékei pedig folyónevek lehetnek (b∈F, ahol F={"Duna", "Tisza", ...}).

Figyeljük meg, hogy P("Paks","Duna") igaz kijelentés, de például P("Győr","Tisza") hamis.

A P(a,b) nyitott mondat logikai értékét általános esetben csak akkor tudjuk meghatározni, ha ismerjük az 'a' és 'b' változók konkrét értékét, valamint a 'P' predikátum által meghatározott π⊆VΧF relációt a városok (V) és a folyók (F) között, azaz azokat az 'x' városokat és 'y' folyókat, amelyekre (x,y)∈π, ahol
π⇋{(x,y)|x∈V, y∈F, |P(x,y)|=1}
teljesül.

Kivételt képeznek azok az esetek, amikor egy P(a,b) nyitott mondat a változók minden lehetséges értékére azonos (pl. igaz) logikai értéket ad, ami például logikai törvények vagy logikai azonosságok esetében teljesül.

Ha a változók helyére különböző értékeket helyettesítünk, a nyitott mondat értéke különböző lehet (egyszer igaz, másszor hamis). Ilyen esetekben a nyitott mondat (vagy formula) értékeléséről beszélünk.

Egy nyitott mondat logikai értéke a benne szereplő változók értékétől függ.

Vannak olyan nyitott mondatok, amelyek a változók minden lehetséges értékére⇒ igaz logikai értéket adnak; például az I osztály minden 'u' és 'v' tanulójára igaz, hogy "Ha az 'u' tanuló szomszédja a 'v' tanulónak, akkor a 'v' tanuló is szomszédja az 'u' tanulónak." A példa a tanulók közötti szomszédsági reláció egy ismert tulajdonságát (a reláció szimmetriáját) fejezi ki, ami az iskola univerzumban⇒ általános, logikai törvény.⇒

Példák:

A predikátumok n változós, kétértékű (logikai) függvények:
P(x1,x2,...,xn) : H1Χ H2Χ ...Χ Hn → {0,1}
ahol Hi az xi változó lehetséges értékeit (a lehetséges individuumneveket) tartalmazó alaphalmaz (i=1,2,...,n).
Ha például V a magyarországi városok halmaza,⇒ I pedig egy meghatározott osztály tanulóinak halmaza⇒, akkor a P(x,"Duna") ⇋ "az 'x' város a Duna mellett fekszik", ill. a Q("Kata",y) ⇋ "Kata szomszédja az 'y' tanulónak" nyitott mondatok az alábbi kétértékű függvényeknek felelnek meg:

Például a P(x,y) kétértékű (logikai) függvényt, ha y="Duna", az alábbi táblázattal adhatjuk meg:

x y P(x,y)
Budapest Duna 1
Debrecen Duna 0
Dunaújváros Duna 1
Esztergom Duna 1
Miskolc Duna 0
Paks Duna 1
Pécs Duna 0
Szeged Duna 0
Visegrád Duna 1
... Duna ...

A fenti példában a 'V', halmaznak azok az elemei (azok az 'x' városok), amelyekhez a P(x,"Duna")=Q(x) predikátum 'igaz' (1) értéket rendel, egy adott tulajdonsággal rendelkeznek (ti. Q(x) ⇋ "az 'x' város a Duna mellett fekszik"). A Q(x) tulajdonsággal rendelkező városok a 'V' halmaz részhalmazai, tehát a Q(x) predikátum a 'V' halmaz egy részhalmazát adja meg.

Ha a P(x,y) predikátum második argumentumában különböző folyóneveket is megengedünk, és F-vel jelöljük a lehetséges folyók halmazát, akkor a P(x,y) predikátum igaz értékei a VΧF direkt szorzat egy részhalmazát adják meg (a fenti általános jelöléssel V=H1, F=H2). Ezáltal a P(x,y) predikátum egy meghatározott relációt ad meg az adott városok és folyók között (ti. azok a városok (x) és folyók (y) állnak egymással relációban, amelyekre P(x,y) igaz).

Általános esetben egy állításban különböző típusú változók fordulnak elő, amelyek különböző alaphalmazokból vehetnek fel értékeket (például városok, folyók, hidak stb., ill. tanulók, tanárok, tárgyak, osztályzatok stb.). Az alaphalmazoknak, az individuumváltozóknak, és a köztük fennálló relációknak azt körét, amelyben a logikai vizsgálatok során a különböző nyitott mondatokat értelmezzük, tárgyalási univerzumnak nevezzük. (vö. Bognár-Forrai 2004; Margitay 2014: 183-184)

Általánosan megfogalmazva a tárgyalási univerzum azoknak a dolgoknak az összessége, amelyek valamely logikai vizsgálódás tárgyát képezik. (vö. Tallér 1996: 277)

6.3. Logikai alapelvek

Arisztotelésztől származik két fontos logikai alapelv:

Megjegyzés:
– Az ellentmondásmentesség elve elvileg megengedi, hogy mind az állítás, mind a tagadása hamis legyen (ha viszont az egyik igaz, akkor a másik biztosan hamis lesz).
– A harmadik kizárásának elve elvileg megengedi, hogy mind az állítás, mind a tagadása igaz legyen (ha viszont az egyik hamis, akkor a másik biztosan igaz lesz).

A fenti alapelvek kifejezik, hogy a klasszikus (arisztotelészi) logikában
(1) az állítások egyértelmű logikai értékkel rendelkeznek, és
(2) csak két logikai érték van (igaz és hamis).

Néhány példa:

6.4. Logikai műveletek

Eddig olyan elemi állításokkal (nyitott mondatokkal, elemi vagy atomi formulákkal) foglalkoztunk, amelyek egy predikátumot és egy vagy több individuumnevet tartalmaztak.

Elvileg lehetséges az is, hogy egy elemi állítás nem tartalmaz egy individuumnevet sem, ilyen lehet pl. az "Esik." kijelentés. Azonban a természetes nyelv mindig erősen tömörít, tehát ha kiegészítjük ezt az állítást, pl. "Most Debrecenben esik." módon, akkor például a mondatban szereplő helyhatározó ("Debrecenben"), és az időhatározó ("most") egyaránt individuumnévnek tekinthető.

Az állítások között meghatározott logikai műveleteket értelmezünk, amelyek segítségével összetett állításokat (logikai kifejezéseket vagy formulákat) fogalmazhatunk meg.

A "logikai kifejezés" rendszerint arra utal, hogy egy összetett állítás formalizálásakor logikai műveleteket használunk; a "formula" pedig rendszerint arra, hogy egy állításban rendszerint egy vagy több individuumváltozó szerepel. Emellett egy formulán többnyire összetett kifejezést ("összetett formulát") értünk, amely elemi vagy atomi formulákból logikai műveletek segítségével épül fel.

A logikai műveletek legfontosabb funkciója az, hogy segítségükkel összetett logikai kifejezéseket tudunk létrehozni.

Később látni fogjuk azt is, hogy néhány logikai alapművelet segítségével minden logikai függvény kifejezhető.

Például az iskola univerzumban feltehetjük azt a kérdést, hogy kik azok a tanulók, akik legalább jó eredményt értek el matematikából, de testnevelésből közepesnél gyengébb a teljesítményük. A
    jegy : IΧT→{1, 2, 3, 4, 5}
"osztályozó" függvény" felhasználásával⇒ ez az állítás
    {x∈I | ( jegy(x,"matek")=4 ∨ jegy(x,"matek")=5 ) ∧ ( jegy(x,"tesi")=2 ∨ jegy(x,"tesi")=1 )}
módon fogalmazható meg. Figyeljük meg a "vagy" (∨) és "és" (∧) logikai műveletek használatát.

Csak olyan logikai műveletekkel foglalkozunk, amelyekre érvényes az alábbi, ún. értékelési alapelv:

Értékelési alapelv:

Az összetett állítások logikai értékét a logikai műveletekkel összekapcsolt állítások logikai értékei egyértelműen meghatározzák.

Másképpen megfogalmazva: tetszőleges állításokon értelmezve egy logikai műveletet, a logikai művelet az általa összekapcsolt állításokhoz az állítások logikai értékétől függően egy egyértelműen meghatározott logikai értéket rendel.

Az értékelési alapelvből következnek az alábbiak:

(1) Az általunk használt logikai műveletek logikai (vagy Boole) függvényekkel írhatók le.

(2) A logikai műveletek értéktáblázatok (igazságtáblázatok) segítségével adhatók meg.

Az általunk használt egy- és kétváltozós logikai műveletek az alábbi logikai (vagy Boole) függvényekkel írhatók le:

Egyváltozós logikai műveletre példa a negáció (tagadás, logikai "nem"). Ha 'p' egy állítás, akkor a negációt az alábbi függvény írja le:

f(p) = {  1  ha 'p' hamis, vagyis |p|=0
 0  ha 'p' igaz, vagyis |p|=1

A fenti logikai függvényt az alábbi értéktáblázattal (vagy igazságtáblázattal) adhatjuk meg:

p f(p)
0 1
1 0

Kétváltozós logikai műveletre példa a konjunkció (logikai "és"). Ha 'p' egy állítás, akkor a konjunkciót az alábbi függvény írja le:

f(p,q) = {  1  ha 'p' és 'q' igaz, vagyis |p|=1 és |q|=1
 0  ha 'p' vagy 'q' bármelyike hamis, vagyis |p|=0 vagy |q|=0

A fenti logikai függvényt szintén megadhatjuk egy értéktáblázattal (vagy igazságtáblázattal):

p q f(p,q)
0 0 0
0 1 0
1 0 0
1 1 1

Egy másik példa kétváltozós logikai műveletre a diszjunkció (logikai "vagy"). Ha 'p' egy állítás, akkor a diszjunkciót az alábbi függvény írja le:

f(p,q) = {  0  ha 'p' és 'q' hamis, vagyis |p|=0 és |q|=0
 1  ha 'p' vagy 'q' bármelyike igaz, vagyis |p|=1 vagy |q|=1

A fenti logikai függvényt szintén megadhatjuk egy értéktáblázattal (vagy igazságtáblázattal):

p q f(p,q)
0 0 0
0 1 1
1 0 1
1 1 1

Az értéktáblázatból látszik, hogy a diszjunkció ún. "megengedő" vagy műveletet jelöl, azaz ha |p|=1 és |q|=1 egyszerre igaz, akkor a diszjunkció igaz. Ezt úgy is kifejezhetjük, hogy |p|=1 és/vagy |q|=1 igaz (de jegyezzük meg, hogy ezt a formát csak kivételes esetekben használjuk).

A legfontosabb logikai műveletek és jelölésük, ha 'P' és 'Q' tetszőleges állítások (vö. Kopasz 1996: 12-15):

A felsorolt logikai műveletek egy-, ill. kétváltozós logikai függvények, ezért megadásukra értéktáblázatokat használunk.

6.4.1. Példák logikai műveletekre (kiegészítő anyag)

A következőkben vizsgáljuk meg példákon keresztül az egyes logikai műveletek jelentését egy általunk választott tárgyalási univerzumban.

(I.) Legyen a tárgyalási univerzum az iskola univerzum, amelyben 'I' a tanulók halmaza. Legyen A⊆I azoknak a tanulóknak a halmaza, akik kiválók matematikából, és B⊆I azoknak a tanulóknak a halmaza, akik közepesek testnevelésből.

Ha x∈I egy tetszőleges elem (tanuló), tekintsük az alábbi két nyitott mondatot:
P(x,A) ⇋ "'x' eleme az 'A' halmaznak (azaz x∈A)"
Q(x,B) ⇋ "'x' eleme a 'B' halmaznak (azaz x∈B)"

A fenti nyitott mondatok P(x,A) ⇋ "az 'x' tanuló kiváló matematikából" és Q(x,B) ⇋ "az 'x' tanuló közepes testnevelésből" módon is leírhatók.

Az iskola univerzumban először vizsgáljuk meg a három logikai alapműveletet.

Az alapkérdés, amit az iskola univerzumban felteszünk: milyen tanulókra igaz egy logikai kifejezés, ha igaz, ill. hamis logikai értékkel rendelkezik?

(1) ⌝P(x,A) ⇋ "'x' nem eleme az 'A' halmaznak" (ennek szokásos jelölése x∉A; emlékezzünk rá, hogy ez definíció szerint az x∈A állításnak felel meg⇒)

A fentiekből következik, hogy a ⌝P(x,A) negáció akkor és csak akkor igaz, ha az 'x' tanuló nem kiváló matematikából (|P(x,A)|=0). Jelöljük azoknak a tanulóknak a halmazát, akikre a ⌝P(x,A) állítás igaz, I¬P=A módon. Ekkor a |⌝P(x,A)|=1 és az x∈I¬P állítások ekvivalensek.

Bevezetve a p ⇋ P(x,A) kijelentésváltozót, a negációt az
⌝p : {0,1}→{0,1}
egyváltozós logikai függvénnyel írhatjuk le (a továbbiakban, ha az nem okoz félreértést, az egyszerűség kedvéért elhagyjuk a |...| jeleket). A fenti megállapítások alapján a ⌝p függvényt az alábbi, korábban már megismert értéktáblázat adja meg:

p ⌝p
1 0
0 1

(2) P(x,A)∧Q(x,B) ⇋ "'x' eleme az 'A' halmaznak és 'x' eleme a 'B' halmaznak" (ennek szokásos jelölése x∈A ∧ x∈B; emlékezzünk rá, hogy ez definíció szerint az x∈A∩B állításnak felel meg⇒)

A fentiekből következik, hogy a P(x,A)∧Q(x,B) konjunkció akkor és csak akkor igaz, ha az 'x' tanuló matematikából kiváló és tesiből közepes. Jelöljük azoknak a tanulóknak a halmazát, akikre a P(x,A)∧Q(x,B) állítás igaz, IP∧Q=A∩B módon. Ekkor a |P(x,A)∧Q(x,B)|=1 és az x∈IP∧Q állítások ekvivalensek.

Bevezetve a p ⇋ P(x,A) és q ⇋ Q(x,B) kijelentésváltozókat, a konjunkciót a
p∧q : {0,1}Χ{0,1}→{0,1}
kétváltozós logikai függvénnyel írhatjuk le (most is elhagyjuk a |...| jeleket). A fenti megállapítások alapján a p∧q függvényt az alábbi értéktáblázat adja meg:

p q p∧q
1 1 1
1 0 0
0 1 0
0 0 0

(3) P(x,A)∨Q(x,B) ⇋ "'x' eleme az 'A' halmaznak vagy 'x' eleme a 'B' halmaznak" (ennek szokásos jelölése x∈A ∨ x∈B; emlékezzünk rá, hogy ez definíció szerint az x∈A∪B állításnak felel meg⇒)

A fentiekből következik, hogy a P(x,A)∨Q(x,B) diszjunkció akkor és csak akkor igaz, ha az 'x' tanuló matematikából kiváló vagy tesiből közepes. Jelöljük azoknak a tanulóknak a halmazát, akikre a P(x,A)∨Q(x,B) állítás igaz, IP∨Q=A∪B módon. Ekkor a |P(x,A)∨Q(x,B)|=1 és az x∈IP∨Q állítások ekvivalensek.

Bevezetve most is a p ⇋ P(x,A) és q ⇋ Q(x,B) kijelentésváltozókat, a diszjunkciót a
p∨q : {0,1}Χ{0,1}→{0,1}
kétváltozós logikai függvénnyel írhatjuk le (most is elhagyjuk a |...| jeleket). A fenti megállapítások alapján a p∨q függvényt az alábbi értéktáblázat adja meg:

p q p∨q
1 1 1
1 0 1
0 1 1
0 0 0

A példákból jól látszik, hogy

(II.) Legyen most is a tárgyalási univerzum egy iskola, ezen belül 'I' egy osztály, és x∈I egy tetszőleges tanuló. Legyen most C⊆I azoknak a tanulóknak a halmaza, akik jók matematikából, és D⊆I azoknak a tanulóknak a halmaza, akik kiválók énekből. Tekintsük az alábbi két nyitott mondatot:
P(x,C) ⇋ "az 'x' tanuló jó matematikából"
Q(x,D) ⇋ "az 'x' tanuló kiváló énekből"

A fenti nyitott mondatok az előzőekhez hasonlóan P(x,C) ⇋ "'x' eleme a 'C' halmaznak" és Q(x,D) ⇋ "'x' eleme a 'D' halmaznak" módon is leírhatók.

Az iskola univerzumban vizsgáljuk meg az implikáció és az ekvivalencia jelentését.

Az alapkérdés, amit az iskola univerzumban most felteszünk: ha a vizsgált implikáció, ill. ekvivalencia minden tanulóra igaz, akkor ez milyen kapcsolatot jelent a tanulók között?

(4) P(x,C)⊃Q(x,D) ⇋ "ha az 'x' tanuló jó matematikából, akkor kiváló énekből is"
– a P(x,C) állítást az implikáció előtagjának nevezzük
– a Q(x,D) állítást az implikáció utótagjának nevezzük

A fentiekből következik, hogy a P(x,C)⊃Q(x,D) implikáció akkor és csak akkor igaz minden tanulóra, ha a matematikából jó tanulók (|P(x,C)|=1) egyszersmind kiválók énekből is (|Q(x,D)|=1).

   (1) Ha |P(x,C)⊃Q(x,D)|=1, akkor ha az 'x' tanuló jó matematikából (|P(x,C)|=1), akkor kiváló énekből (|Q(x,D)|=1), ugyanis az implikáció igazságtáblázatában |P(x,C)⊃Q(x,D)|=1 és |P(x,C)|=1 csak egyetlen sorban szerepel, és ott |Q(x,D)|=1 teljesül. (!! Az implikáció igazságtáblázatának harmadik sorában |P(x,C)|=1 és |Q(x,D)|=0 mellett |P(x,C)⊃Q(x,D)|≠1 áll. !!)

   (2) Ha az 'x' tanuló jó matematikából (|P(x,C)|=1) és kiváló énekből (|Q(x,D)|=1), akkor |P(x,C)⊃Q(x,D)|=1 teljesül, ugyanis az implikáció igazságtáblázatában a |P(x,C)|=1 és |Q(x,D)|=1 sorban |P(x,C)⊃Q(x,D)|=1 áll.

Jegyezzük meg, hogy |P(x,C)⊃Q(x,D)|=1 esetén nem állítunk semmit sem azokról a tanulókról, akik nem jók matematikából (|P(x,C)|=0), ugyanis rájuk mind |Q(x,D)|=0, mind |Q(x,D)|=1 teljesülhet. Az implikációnak ezt a tulajdonságát sokszor az anyagi implikáció elnevezéssel emeljük ki, mert a bizonyítások, levezetések során számos előnnyel jár.

Érdemes továbbá megjegyezni a következőket:
– Ha az implikáció igazságtáblázatában a |P(x,C)|=0 és |Q(x,D)|=0 sorban |P(x,C)⊃Q(x,D)|=0 szerepelne, az kizárná, hogy egy matekból rossz tanuló rossz énekes lenne, azaz
    C∩D=∅ vagy C∪D=I ⇒ D=I
teljesülne (azaz ekkor az osztályban minden tanuló kiváló énekes lenne, akik jó és rossz matekesek lehetnének, vagyis ebben az esetben D∖C≠∅ teljesülhet).
– Ha az implikáció igazságtáblázatában a |P(x,C)|=0 és |Q(x,D)|=1 sorban |P(x,C)⊃Q(x,D)|=0 szerepelne, az kizárná, hogy egy matekból rossz tanuló jó énekes lenne, azaz
    C∩D=∅ vagy D∖C=∅ ⇒ C=D
teljesülne (ebben az esetben a "jó matekes" és a "kiváló énekes" tulajdonságok ekvivalensek lennének, de a rossz matekesek lehetnének rossz énekesek (és megfordítva), azaz ebben az esetben C∩D≠∅ teljesülhet).
– Végül ha az implikáció igazságtáblázatában mind a |P(x,C)|=0 és |Q(x,D)|=0 sorban, mind a |P(x,C)|=0 és |Q(x,D)|=1 sorban |P(x,C)⊃Q(x,D)|=0 szerepelne, az kizárná, hogy egy matekból rossz tanuló kiváló énekes vagy rossz énekes lenne, azaz
    C=∅ vagy C=I ⇒ C=D, D=I
teljesülne (azaz ekkor az osztályban csak jó matekesek lennének, akik egyszersmind kiváló énekesek is; ennek egy érdekes következménye, hogy az osztályban csak kiváló énekesek lennének).

Jelöljük azoknak a tanulóknak a halmazát, akikre a P(x,C) állítás igaz, C=IP módon, és azoknak a tanulóknak a halmazát, akikre a Q(x,D) állítás igaz, D=IQ módon. Ekkor |P(x,C)⊃Q(x,D)|=1 akkor és csak akkor igaz minden tanulóra, ha IP⊆IQ (azaz C⊆D) teljesül.

Vegyük észre, hogy az az állítás, hogy "A matematikából jó tanulók (|P(x,C)|=1) egyszersmind kiválók énekből is (|Q(x,D)|=1)." átfogalmazható a következőképpen: "A matematikából jó tanulók halmazának (C=IP) minden eleme egyszersmind eleme a kiváló tanulók halmazának (D=IQ)." Ez pedig éppen a IP⊆IQ részhalmaz reláció korábban tanult⇒ meghatározása.

Megfordítva: ha két halmaz közötti részhalmaz viszonyt szeretnénk kifejezni, ezt az implikáció segítségével is megtehetjük. Például ha egy osztályban teljesül, hogy "A matematikából jó tanulók egyszersmind kiválók énekből is.", vagyis C⊆D teljesül, azt kifejezhetjük a minden osztálybeli tanulóra igaz P(x,C)⊃Q(x,D) implikáció segítségével is, aminek a jelentése: "Ha az 'x' tanuló jó matematikából, akkor kiváló énekből is." Ebben az esetben értelmet nyer az is, hogy ha az implikáció előtagja hamis, akkor az implikációt igaznak tekintjük. Ugyanis azoknak a tanulóknak a halmaza, amelyekre a P(x,C)⊃Q(x,D) implikáció igaz, magában foglalja azokat a tanulókat is, akik nem jók matematikából. Ezt úgy is megfogalmazhatjuk, hogy az IP⊃Q={x | |P(x,C)⊃Q(x,D)|=1} halmaz megadja az osztály összes tanulóját. Általánosan fogalmazva: a C⊆D reláció ekvivalens azzal, hogy az IP⊃Q halmaz az osztály összes tanulóját megadja.

Emeljük ki, hogy
(1) Az implikáció akkor és csak akkor hamis, ha az előtagja igaz és az utótagja hamis.
(2) Ha az implikáció előtagja hamis, akkor az implikációt mindig igaznak tekintjük.

Bevezetve a p ⇋ P(x,C) és q ⇋ Q(x,D) kijelentésváltozókat, az implikációt a
p⊃q : {0,1}Χ{0,1}→{0,1}
kétváltozós logikai függvénnyel írhatjuk le (most is elhagyjuk a |...| jeleket). A fenti megállapítások alapján a p⊃q függvényt az alábbi értéktáblázat adja meg:

p q p⊃q
0 0 1
0 1 1
1 0 0
1 1 1

Egy tetszőleges 'I' osztályban egy adott x∈I tanulóra a P(x,C)⊃Q(x,D) állítás lehet igaz is és hamis is. Azonban ha a P(x,C)⊃Q(x,D) állítás az 'I' osztály minden tanulójára igaz, akkor minden x∈I tanuló, aki négyes matematikából, az ötös énekből is.

(5) P(x,C)≡Q(x,D) ⇋ az 'x' tanuló pontosan akkor ("akkor és csak akkor") jó matematikából, ha kiváló énekből is"

A fentiekből következik, hogy a P(x,C)≡Q(x,D) ekvivalencia akkor és csak akkor igaz minden tanulóra, ha a matematikából jó tanulók (|P(x,C)|=1) ugyanazok a tanulók, akik kiválók énekből is (|Q(x,D)|=1). Jelöljük most is azoknak a tanulóknak a halmazát, akikre a P(x,C) állítás igaz, C=IP módon, és azoknak a tanulóknak a halmazát, akikre a Q(x,D) állítás igaz, D=IQ módon. Ekkor |P(x,C)≡Q(x,D)|=1 akkor és csak akkor igaz minden tanulóra, ha IP=IQ (azaz C=D) teljesül.

Az ekvivalencia mint logikai művelet akkor és csak akkor igaz, ha a művelettel összekapcsolt állítások azonos logikai értékűek (azaz vagy mindkettő igaz, vagy mindkettő hamis).

Bevezetve a p ⇋ P(x,C) és q ⇋ Q(x,D) kijelentésváltozókat, az ekvivalenciát a
p≡q : {0,1}Χ{0,1}→{0,1}
kétváltozós logikai függvénnyel írhatjuk le (most is elhagyjuk az |...| jeleket). A fenti megállapítások alapján a p≡q függvényt az alábbi értéktáblázat adja meg:

p q p≡q
1 1 1
1 0 0
0 1 0
0 0 1

Egy tetszőleges 'I' osztályban egy adott x∈I tanulóra a P(x,C)≡Q(x,D) állítás lehet igaz is és hamis is. Ha azonban a P(x,C)≡Q(x,D) állítás minden tanulóra igaz, akkor a tanulók vagy egyszerre jók matematikából és kiválók énekből, vagy nem jók matematikából és ugyanakkor nem kiválók énekből sem.

A fontosabb logikai műveletek értéktáblázatai

negáció, tagadás ("nem A", "NOT A"): ( ⌝A )

negáció
A ( ⌝A )
0 1
1 0

konjunkció ("A és B", "A AND B"): ( A ∧ B )

konjunkció
A B ( A ∧ B )
0 0 0
0 1 0
1 0 0
1 1 1

diszjunkció ("A vagy B", "A OR B"): ( A ∨ B ) (a diszjunkció az ún. megengedő vagy-nak felel meg; formális szövegekben szokásos erre az "és/vagy" kötőszó használata is)

diszjunkció
A B ( A ∨ B )
0 0 0
0 1 1
1 0 1
1 1 1

kizáró vagy ("A XOR B"): ( A ⨁ B )

kizáró vagy
A B ( A ⨁ B )
0 0 0
0 1 1
1 0 1
1 1 0

implikáció ("A-ból következik B"; A-t előtagnak, B-t utótagnak is szokás nevezni): ( A ⊃ B )

implikáció
A B ( A ⊃ B )
0 0 1
0 1 1
1 0 0
1 1 1

implikáció tagadása ("A de/és nem B", "A AND NOT B"): ( (⌝(A ⊃ B) ~ (A ∧ ⌝B))

implikáció
A B ⌝(A ⊃ B)
0 0 0
0 1 0
1 0 1
1 1 0

ekvivalencia ("A ekvivalens B-vel"): ( A ≡ B )

ekvivalencia
A B ( A ≡ B )
0 0 1
0 1 0
1 0 0
1 1 1

Az értéktáblázatok elkészítésének lépései

Legyenek 'p' és 'q' tetszőleges kijelentésváltozók (azaz olyan állítások, amelyek logikai értéke vagy 0, vagy 1). Vizsgáljuk meg az
F ⇋ (p⊃q)≡.(p∧q)
formula igazságértékét a 'p' és 'q' kijelentésváltozók különböző logikai értéke esetén.

Például ha |p|=1 és |q|=1, akkor az 'F' formula értékét az alábbi lépésekkel könnyen kiszámíthatjuk:

  1. az implikáció értéktáblázata⇒ alapján |p⊃q|=1 teljesül;
  2. a konjunkció értéktáblázata⇒ alapján |p∧q|=1 teljesül;
  3. az ekvivalencia értéktáblázata⇒ alapján pedig F=|(p⊃q)≡.(p∧q)|=|1≡1|=1 teljesül.

Ha az 'F' formula értékét a 'p' és 'q' kijelentésváltozók minden lehetséges értékére ki akarjuk számítani, a könnyebb áttekintés érdekében érdemes a számítás részeredményeit egy értéktáblázatban összefoglalni.

p q p⊃q p∧q (p⊃q)≡.(p∧q)
0 0 1 0 0
0 1 1 0 0
1 0 0 0 1
1 1 1 1 1

Vegyük észre, hogy a fenti értéktáblázat utolsó sora azokat a részeredményeket tartalmazza, amelyeket a 'p' és 'q' kijelentésváltozók |p|=1 és |q|=1 értéke mellett az 'F' formula kiszámításakor korábban már kiszámoltunk.

Egy másik példaként vizsgáljuk meg a
G ⇋ (p⊃q)∧⌝q⊃.⌝p
formula igazságértékét a 'p' és 'q' kijelentésváltozók különböző logikai értéke esetén. Vegyük észre, hogy az értéktáblázat most a 'p' és 'q' kijelentésváltozók negáltját⇒ is tartalmazza. (A könnyebb áttekintés érdekében az összetett formulák logikai értékeit tartalmazó oszlopokban kiemeltük az elvégzendő műveletet.)

p q p⊃q ⌝q (p⊃q)∧⌝q ⌝p (p⊃q)∧⌝q⊃.⌝p
0 0 1 1 1 1 1
0 1 1 0 0 1 1
1 0 0 1 0 0 1
1 1 1 0 0 0 1

Jegyezzük meg, hogy a 'G' formula kiszámításakor az utolsó lépés a pont (.) operátorral jelölt implikáció (⊃.) kiszámítása volt.

Az értéktáblázatból látszik, hogy a 'G' formula a 'p' és 'q' kijelentésváltozók minden lehetséges értékére igaz, vagyis logikai törvény.⇒ Később látni fogjuk, hogy ezzel a modus tollens⇒ következtetési szabályt igazoltuk.

Az értéktáblázatok gyakorlása

1. feladat: Töltse ki az értéktáblázat harmadik oszlopát az oszlop fejrészében megadott formulának megfelelően!

p q p⊃q
0 0
0 1
1 0
1 1

Hibás válaszok száma: ?

2. feladat: Töltse ki az értéktáblázat utolsó oszlopát az oszlop fejrészében megadott formulának megfelelően! (A táblázat ötödik és hatodik oszlopa segédoszlop, amit a program az utolsó oszlop ellenőrzése során nem vesz figyelembe. Ezek kitöltése nem kötelező, de ajánlott, mivel az oszlopok kitöltése segíti a végső formula meghatározását.)

p q ⌝p ⌝q ? ? ?
0 0 1 1
0 1 1 0
1 0 0 1
1 1 0 0

Hibás válaszok száma: ?

6.5. Formulák és értékelések (kiegészítő anyag)

Ennek a gondolatkörnek a zárásaként vezessünk be, ill. pontosítsunk néhány fontos fogalmat.

Azokat a formulákat, amelyek nem tartalmaznak szabad (azaz konkrét értékekkel helyettesíthető) változókat, zárt formuláknak nevezzük. Nyitott mondatokból a "minden" és a "létezik" (ill. "van olyan") kvantorokkal⇒ zárt formulákat képezhetünk. Egy zárt formuláról egy adott tárgyalási univerzumban mindig egyértelműen eldönthető, hogy az igazságértéke igaz vagy hamis. Például "Minden város a Duna mellett fekszik." hamis és "Van olyan város, amely a Duna mellett fekszik." igaz, ha a magyarországi városokat vesszük figyelembe a 'város' individuumváltozó alaphalmazaként.⇒ Vegyük észre, hogy egyik fenti állításban sincsenek szabad változók, ugyanis a "minden", ill. "van olyan" kvantorok után nem helyettesíthetünk be egyetlen konkrét városnevet sem.)

Amikor egy nyitott mondat változóinak értéket adunk (azaz a változók helyére a típusuknak megfelelő alaphalmazokból vett elemeket helyettesítünk), a formula konkretizálásáról vagy értékeléséről beszélünk. Az értékelt formulák egyértelmű (igaz vagy hamis) logikai értékkel rendelkező állítások. (Például "Paks a Duna mellett fekszik." egy értékelt formula.)

Mind a zárt formulák, mind az értékelt formulák egyértelmű logikai értékkel rendelkező állítások.

Összetett logikai kifejezések kiértékelésekor fontos a logikai műveletek sorrendje:

. ≡ ⊃ ∨
∧ 		⌝ ∀
∃ 		( ... )

Egy összetett logikai kifejezés kiértékelésekor

A pont (.) operátor nem önálló logikai művelet, a pontot mindig egy másik művelet után adjuk meg. A pont operátor azt jelzi, hogy a ponttal jelölt műveletet mindig utoljára kell végrehajtani.

Például értékeljük ki az A ∧ (A ∨ B) ≡. A összetett logikai kifejezést, ha |A|=1 és |B|=0.

  1. |A ∨ B| = |1 ∨ 0| = 1
  2. |A ∧ (A ∨ B)| = |A ∧ (A ∨ B)| = |A ∧ 1| = 1
  3. |A ∧ (A ∨ B) ≡. A| = |A ∧ (A ∨ B) ≡. A| = |1 ≡ A| = |1 ≡ 1| = 1

Figyeljük meg, hogy minden lépésben egy logikai műveletet értékeltünk ki (a művelet értéktáblázatának⇒ megfelelően), és a kapott részeredményeket felhasználtuk a kiértékelés további lépései során.

Készítsük el ezután az A ∧ (A ∨ B) ≡. A összetett logikai kifejezés értéktáblázatát az egyes műveletek kiértékelésének sorrendjében, és emeljük ki azt a sort, amelyben |A|=1 és |B|=0.

A B A∨B A∧(A∨B) A∧(A∨B)≡.A
1 1 1 1 1
1 0 1 1 1
0 1 1 0 1
0 0 0 0 1

Egy másik példaként készítsük el az A∧B⊃.A∨B logikai kifejezés értéktáblázatát.

A B A∧B A∨B A∧B⊃.A∨B
1 1 1 1 1
1 0 0 1 1
0 1 0 1 1
0 0 0 0 1

Végül pedig készítsük el az A⊃B≡.⌝B⊃⌝A logikai kifejezés értéktáblázatát.

A B A⊃B ⌝B ⌝A ⌝B⊃⌝A A⊃B≡.⌝B⊃⌝A
1 1 1 0 0 1 1
1 0 0 1 0 0 1
0 1 1 0 1 1 1
0 0 1 1 1 1 1

Gyakorló feladatok

(→ következő témakörök)

Boda István, 2021-24.