Matematikai logikai alapok

Tartalom, témakörök

11. Á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^⇒
12. 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)
    • Kijelentéslogika. Logikai azonosságok.^⇒
    • Összetett érvelések, levezetések.^⇒
    • Következtetési sémák.^⇒
      • Egy példa a modus ponens és a modus tollens alkalmazására.^⇒
    • Példák következtetési sémák használatára.^⇒
    • Gyakorló feladatok^⇒
13. A halmazműveletek és a logikai műveletek kapcsolata. Kvantifikáció.^⇒ (Kopasz 1996: 24-25; 26-29; Borsodi 1972: 314-320)
    • Gyakorló feladatok^⇒
14. ⇐ megelőző témakörök (1-10)

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

11.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:

• Paks a Duna mellett fekszik.
  • individuumnév: Paks
  • predikátum: (vmi) fekszik (vmi mellett)
  • individuumnév: Duna

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.

• Ha egy kijelentést egy betűvel helyettesítünk, kijelentésváltozót kapunk. A fentiek értelmében a kijelentésváltozók logikai értéke 1 vagy 0 lehet. (Például bevezethetjük a 'p' kijelentésváltozót a következőképpen: p ⇋ "Paks a Duna mellett fekszik." Mivel Paks tényleg a Duna mellett fekszik, azaz a kijelentés igaz, tehát |p|=1 teljesül.)
• Az individuumneveket szintén helyettesíthetjük betűkkel, ekkor individuumváltozókat vagy röviden változókat kapunk. (Például bevezethetjük az 'a' és 'b' individuumváltozókat a ⇋ "Paks" és b ⇋ "Duna" módon.)
  Jegyezzük meg, hogy általános iskolában a nyitott mondatok^⇒ tanításakor az individuumváltozók jelölésére betűk helyett más szimbólumokat is szokás használni (például üres négyzeteket, köröket, háromszögeket stb.).
• A predikátumot is helyettesíthetjük egy betűvel, azonban ekkor figyelembe kell vennünk (azaz valamilyen formában jelölnük kell) a predikátum és az individuumnevek kapcsolatát, az állítás vagy kijelentés belső szerkezetét, amelyet egy függvény segítségével írhatunk le. (Például bevezethetjük a 'P' szimbólumot P=P(a,b) ⇋ "(vmi) fekszik (vmi mellett)" módon. Vegyük észre, hogy a (vmi) az alanyt ('a'), a 'fekszik' az állítmányt ('P'), a (vmi mellett) a határozót ('b') jelöli.)

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:

• Paks a Duna mellett fekszik.
  • predikátum: P ⇋ "(vmi) fekszik (vmi mellett)"
  • individuumnév: a ⇋ "Paks"
  • individuumnév: b ⇋ "Duna"
  • kijelentésváltozó, formalizált kijelentés: p ⇋ P(a,b)
  • igazságérték: |p|=1 (p igaz, mert Paks tényleg a Duna mellett fekszik)
• Kata szomszédja Marinak.
  • predikátum: Q ⇋ "(vki) szomszédja (vkinek)"
  • individuumnév: u ⇋ "Kata"
  • individuumnév: v ⇋ "Mari"
  • kijelentésváltozó, formalizált kijelentés: q ⇋ Q(u,v)
  • igazságérték: ha Kata tényleg a szomszédja Marinak, akkor |q|=1 (q igaz), egyébként |q|=0 (q hamis)

11.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)∈π teljesül (az 'x' város az 'y' folyó mellett fekszik). A π relációt formálisan
π⇋{(x,y)|x∈V, y∈F, |P(x,y)|=1}
módon adhatjuk meg. Figyeljük meg, hogy a legalább két változót tartalmazó és igaz logikai értékű nyitott mondatok (pl. |P(a,b)|=1) és a relációk (pl. π) között szoros kapcsolat van.

Nagyon fontosak 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 logikai törvények (ld. alább) vagy logikai azonosságok^⇒ (tautológiák) esetében mindig teljesül. (Logikai azonosságok esetében az azonosságokban szereplő kijelentésváltozók helyére bármilyen formula vagy nyitott mondat helyettesíthető, feltéve, hogy az azonos kijelentésváltozók minden esetben pontosan ugyanannak a formulának felelnek meg.)

Különösen fontosak azok a nyitott mondatok, amelyekről tudjuk, hogy egy adott környezetben a bennük szereplő változók minden lehetséges értékére teljesülnek. Általánosan megfogalmazva ezt a számunkra nagyon fontos esetet:

Logikai törvényről beszélünk akkor, ha egy adott nyitott mondat vagy formula teljesül
– a benne szereplő individuumváltozók minden lehetséges értékére,
– a változók értéktartományát meghatározó alaphalmazok bármilyen választása mellett.

Másképpen megfogalmazva: a logikai törvények olyan nyitott mondatok vagy formulák, amelyek az értelmezésükre használt tárgyalási univerzum^⇒ összes lehetséges alaphalmaza esetén teljesülnek.

Például az alábbi nyitott mondat: "Ha az 'x' tanuló jeles minden tárgyból, akkor jeles matematikából." az iskola univerzumban logikai törvény (azaz minden 'x' tanulóra igaz, bármilyen osztályt is választunk a nyitott mondatban szereplő 'x' változó alaphalmazának). További példák: a klasszikus mechanikában jól ismert törvények Newton vagy Kepler törvényei; a természetes számok körében pedig ismertek a 2-vel, 3-mal, 4-gyel, 5-tel stb. való oszthatóság törvényei.

A nyitott mondatok és a relációk kapcsolatára egy további példaként tekintsük a
    σ = {(a,b) | a∈ℕ, b∈ℕ, ∃q∈ℕ (b=q*a)} ⊆ ℕΧℕ
oszthatósági relációt.^⇒ Egy lehetséges nyitott mondat:
q ⇋     osztója 15-nek.
Ebben az esetben az alaphalmaz a természetes számok halmaza, és a lehetséges megoldások az
I_q = {x∈ℕ | (x,15)∈σ}
halmaz elemei. Az I_q halmazt a 'q' nyitott mondat igazsághalmazának nevezzük. Egy nyitott mondat igazsághalmaza megadja, hogy a nyitott mondat a benne szereplő individuumváltozók milyen értékeire lesz igaz. Tehát egy nyitott mondat igazsághalmaza a nyitott mondat alaphalmazának azokat az elemeit tartalmazza, amelyeket a nyitott mondatba helyettesítve a nyitott mondat igaz lesz.

Az egy individuumváltozót tartalmazó nyitott mondatok igazsághalmaza az alaphalmazok egy meghatározott részhalmaza. Tehát az ilyen tulajdonsággal rendelkező nyitott mondatok felhasználhatók a hozzájuk rendelt alaphalmazok meghatározott részhalmazainak a megadására. Jegyezzük meg, hogy a legalább két individuumváltozót tartalmazó predikátumokból bármikor előállíthatunk ilyan (egy individuumváltozót tartalmazó) nyitott mondatokat a többi individuumváltozó helyébe konkrét individuumneveket helyettesítve.

Ha az individuumvá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.

Például a
    P(a,b) ⇋ "Az 'a' város a 'b' folyó mellett fekszik."
nyitott mondat az a="Paks", b="Duna" helyettesítések mellett igaz lesz, vagyis
    |P("Paks","Duna")|=1
teljesül. Ezzel szemben a P(a,b) nyitott mondat az a="Debrecen", b="Tisza" helyettesítések mellett hamis lesz, vagyis
    |P("Debrecen","Tisza")|=0
teljesül (mivel a Tisza nem Debrecen mellett folyik, vagyis Debrecen nem a Tisza mellett fekszik). Ha a π relációt ismerjük a városok és a folyók között, akkor úgy is fogalmazhatunk, hogy "Paks" és "Duna" π szerint relációban állnak egymással, "Debrecen" és "Tisza" pedig nem állnak relációban egymással.

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:

• Egy város a Duna mellett fekszik.
  • predikátum: P ⇋ "(vmi) fekszik (vmi mellett)"
  • változó: x ⇋ "város"
    • lehetséges alaphalmaz: x ∈ V, ahol
      V = {"Esztergom", "Visegrád", "Budapest", "Dunaújváros", "Paks", ..., "Miskolc", "Debrecen", "Szeged", "Pécs", ...} ('V' meghatározott magyarországi^⇒ városok halmaza)
  • individuumnév: b ⇋ "Duna"
  • nyitott mondat: p ⇋ P(x,b)
    • x ⟷ "Paks" helyettesítés esetén |p|=1
    • x ⟷ "Miskolc" helyettesítés esetén |p|=0
• Kata szomszédja egy (másik) tanulónak.
  • predikátum: Q ⇋ "(vki) szomszédja (vkinek)"
  • individuumnév: u ⇋ "Kata"
  • változó: y ⇋ "tanuló"
    • lehetséges alaphalmaz: y ∈ I, ahol
      I = {"Tercsi", "Fercsi", "Kata", "Klára", "Anett", "Peti", "Mari", "Pisti", "Zoli", "Zsuzsa"} ('I' egy osztály tanulóinak halmaza; ha az állításban szerepel a "másik" határozatlan névmás, akkor y≠"Kata" teljesül)
  • nyitott mondat: q ⇋ Q(u,y)
    • y ⟷ "Mari" helyettesítés esetén |q|=1 (ha Kata tényleg a szomszédja Marinak)
    • y ⟷ "Tercsi" helyettesítés esetén |q|=0 (ha a valóságban Kata és Tercsi nem szomszédok)

---

A predikátumok n változós, kétértékű (logikai) függvények:
P(x₁,x₂,...,x_n) : H₁Χ H₂Χ ...Χ H_n → {0,1}
ahol H_i az x_i 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(x,y) : V Χ {Duna} → {0,1}
• Q(x,y) : {Kata} Χ I → {0,1}

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=H₁, F=H₂). 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). Korábban ezt a relációt jelöltük π-vel. A π relációra a fentiek alapján π⊆VΧF teljesül.

---

Á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, a különböző típusú változóknak, és az alaphalmazok elemei között 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)

11.3. Logikai alapelvek

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

• az ellentmondásmentesség logikai elve: egy állítás nem lehet egyszerre igaz is és hamis is
  • egy állítás és a tagadása^⇒ nem lehet egyszerre^⇒ igaz^⇒
    • ha egy állítás igaz, akkor a tagadása hamis, nem lehet igaz
    • ha egy állítás tagadása igaz, akkor az állítás hamis, nem lehet igaz
• a harmadik kizárásának logikai elve: egy állítás vagy igaz, vagy hamis, nincs harmadik lehetőség
  • egy állítás és ennek a tagadása^⇒ közül az egyik^⇒ biztosan teljesül^⇒
    • ha egy állítás hamis, akkor a tagadása igaz kell, hogy legyen
    • ha egy állítás tagadása hamis, akkor az állítás igaz kell, hogy legyen

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:

• az az állítás, hogy "A fű zöld." és "A fű nem zöld." nem lehet egyszerre igaz;
  • az az állítás, hogy "A fű zöld." és "A fű fehér." nem lehet egyszerre igaz (mert ha a fű fehér, akkor^⇒ nem zöld, és ha zöld, akkor nem fehér);
• az az állítás, hogy "A zsír egészséges." és "A zsír egészségtelen." nem lehet egyszerre igaz;
  (Számos ilyen példát kaphatunk, ha túlságosan általános kijelentő mondatokat vizsgálunk. Ha egy ilyen típusú mondat logikai értéke nem dönthető egyértelműen el, akkor nem tekinthető állításnak (tehát vitatkozni sem érdemes róla), ezért valamilyen módon pontosítani kell. Például az, hogy "A zsír egészséges 'x' (ember) számára." már olyan nyitott mondat, amely egyes emberek (x∈E_a) esetén igaz, más emberek (x∈E_b) esetén pedig hamis lehet.)
• az az állítás, hogy "Paks a Duna mellett fekszik.", igaz; tehát az, hogy "Paks nem a Duna mellett fekszik.", hamis;
• Ha bebizonyítjuk, hogy a primszámok halmaza nem véges (például úgy, hogy ha feltesszük, hogy véges, ellentmondásra jutunk), akkor biztosak lehetünk benne, hogy a primszámok halmaza végtelen.
• az a mondat, hogy "Azt hiszem, ma esni fog." az esőt illetően nem állítás, mert nem dönthető el egyértelműen, hogy igaz vagy hamis.

11.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. (Jegyezzük meg, hogy az atomi formulák az adott tárgyalási univerzumban értelmezett individuumváltozókat tartalmazó predikátumok, amelyek részint a tárgyalási univerzum alaphalmazainak a tulajdonságait, részint pedig az alaphalmazok közötti relációkat adják meg.^⇒)

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ő.

---

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

• negáció^⇒ vagy tagadás (logikai "nem"): ⌝P
• konjunkció^⇒ vagy összekapcsolás (logikai "és"): P∧Q
• diszjunkció^⇒ (alternáció) vagy szétválasztás (logikai "vagy"; szokásos a "megengedő vagy" elnevezés is): P∨Q
  • kizáró vagy:^⇒ P⨁Q
• ekvivalencia^⇒ (bikondicionális) vagy kettős feltételes állítás: P≡Q
• implikáció^⇒ (kondicionális) vagy feltételes állítás: P⊃Q
  • implikáció tagadása ("és nem"):^⇒ P⊅Q ≡ P∧⌝Q

---

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^⇒ ezt az állítást
    P(x) = ( jegy(x,"matek")=4 ∨ jegy(x,"matek")=5 ) ∧ ( jegy(x,"tesi")=2 ∨ jegy(x,"tesi")=1 )
módon formalizálhatjuk. Figyeljük meg a "vagy" (∨) és "és" (∧) logikai műveletek használatát.

Azok az x∈I tanulók, akikre a P(x) "összetett", logikai műveleteket tartalmazó állítás igaz
    I_P = {x∈I | |P(x)|=1}
módon választhatók ki. Nevezzük az I_P⊆I halmazt, amelynek elemeire a P(x) állítás teljesül, a P(x) állítás igazsághalmazának.

Vezessük be az alábbi "elemi" állításokat és ezek igazsághalmazát:

• matekből négyest kapott tanulók
  • M4(x) = {x∈I | jegy(x,"matek")=4}
  • I_M4 = {x∈I | |M4(x)|=1}
• matekből ötöst kapott tanulók
  • M5(x) = {x∈I | jegy(x,"matek")=5}
  • I_M5 = {x∈I | |M5(x)|=1}
• testnevelésből kettest kapott tanulók
  • T2(x) = {x∈I | jegy(x,"tesi")=2}
  • I_T2 = {x∈I | |T2(x)|=1}
• testnevelésből egyest kapott tanulók
  • T1(x) = {x∈I | jegy(x,"tesi")=1}
  • I_T1 = {x∈I | |T1(x)|=1}

A fenti halmazokkal a P(x) összetett állítás igazsághalmaza
    I_P = ( I_M4∪I_M5) ∩ ( I_T2∪I_T1)
módon fejezhető ki. Jól látszik, hogy a logikai műveleteknek az igazsághalmazok közötti halmazműveletek felelnek meg.

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

Értékelési alapelv:

Az összetett, logikai műveleteket tartalmazó állítások logikai értékét a logikai műveletekkel összekapcsolt (elemi) á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 alapelv kifejezi, hogy az általunk használt műveletek függvények:

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

(2) A több logikai műveletből összetett logikai állításokat közvetett függvényekkel írhatjuk le.

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

• Mi csak egyváltozós vagy kétváltozós logikai műveletekkel foglalkozunk.
• Egyváltozós műveletek esetén az értéktáblázatok első oszlopa, kétváltozós műveletek esetén pedig a táblázatok első két oszlopa a műveletek mint logikai függvények független változóinak (argumentumainak) lehetséges logikai értékeit tartalmazza.
• A táblázatok utolsó oszlopa az értéktáblázattal megadott művelet logikai értékét tartalmazza a táblázat adott sorának megfelelő argumentumértékek mellett.

---

Az igazságtáblázatok alapján meghatározhatjuk, elvileg hány egyváltozós, ill. kétváltozós logikai művelet lehetséges.
   (1) Mivel az egyváltozós logikai függvények értelmezési tartománya a {0,1} halmaz és értékkészlete a {0,1} halmaz, egyváltozós logikai műveletekből elvileg V₂^2,i=2²=4, lehetséges.
   (2) Mivel a kétváltozós logikai függvények értelmezési tartománya a {0,1} halmaz és értékkészlete a {0,1}Χ{0,1} halmaz, kétváltozós logikai műveletekből elvileg V₂^4,i=2⁴=16 lehetséges.

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űveletek (max. 2²=4 lehetőség):
  f : {0,1} → {0,1}
• kétváltozós logikai műveletek (max. 2⁴=16 lehetőség):
  g : {0,1}Χ{0,1} → {0,1}

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).

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

11.4.1. A logikai műveletek értelmezése az iskola univerzumban

Legyen a tárgyalási univerzum az iskola univerzum, amelyben 'I' a tanulók halmaza. Ebben

• legyen M₅⊆I azoknak a tanulóknak a halmaza, akik ötöst kaptak matematikából, és E₅⊆I azoknak a tanulóknak a halmaza, akik ötöst kaptak énekből;
• ha x∈I egy tetszőleges tanuló, akkor vizsgáljuk az x∈M₅ és az x∈E₅ állításokat.

A logikai műveletek "intuitív" ismeretében és a tanulók 'I' halmazát, valamint az M₅⊆I és E₅⊆I halmazokat ábrázoló Venn-diagram segítségével megállapíthatjuk a következőket:

1. Negáció: azoknak a tanulóknak a halmaza, amelyekre ⌝(x∈M₅) vagy x∉M₅ teljesül (azaz x∈M₅ nem teljesül), M₅.
2. Konjunkció: azoknak a tanulóknak a halmaza, amelyekre (x∈M₅)∧(x∈E₅) teljesül, M₅∩E₅.
3. Diszjunkció ("megengedő" vagy): azoknak a tanulóknak a halmaza, amelyekre (x∈M₅)∨(x∈E₅) teljesül, M₅∪E₅.
   • Szavakban: azok a tanulók, akik ötöst kaptak matematikából vagy ötöst kaptak énekből (esetleg: azok a tanulók, akik akár matematikából, akár énekből, akár mindkettőből ötöst kaptak)
4. Kizáró vagy: azoknak a tanulóknak a halmaza, amelyekre (x∈M₅)⨁(x∈E₅) teljesül, M₅ΔE₅.
   • Szavakban: azok a tanulók, akik vagy ötöst kaptak matematikából, vagy ötöst kaptak énekből (de nem kaptak mindkét tárgyból ötöst)
5. Ekvivalencia: azoknak a tanulóknak a halmaza, amelyekre (x∈M₅)≡(x∈E₅) teljesül, (M₅∩E₅) ∪ (M₅∩E₅).
   • Szavakban: azok a tanulók, akik egyformán teljesítettek matematikából és énekből (ti. vagy mindkettőből kiválók, vagy egyikből sem)
6. Implikáció tagadása: azoknak a tanulóknak a halmaza, amelyekre (x∈M₅)⊃(x∈E₅) nem teljesül, M₅∖E₅= M₅∩E₅.
   • Szavakban: azok a tanulók, akikre nem teljesül, hogy ha ötöst kaptak matematikából akkor ötöst kaptak énekből; feltételezzük, hogy ők azok a tanulók, akik ötöst kaptak matematikából, és (vagy de) nem kaptak ötöst énekből vagyis
     ⌝[(x∈M₅)⊃(x∈E₅)] ⇋ (x∈M₅)⊅(x∈E₅) ≡. (x∈M₅)∧⌝(x∈E₅)

Azoknak a tanulóknak a halmaza, akikre nem teljesül, hogy "ha ötöst kaptak matematikából, akkor ötöst kaptak énekből" azok, akikre teljesül, hogy "ötöst kaptak matematikából és nem kaptak ötöst énekből". Ez az állítás igazsághalmazokkal M₅∖E₅ módon fejezhető ki.

Vegyük észre, hogy a fentiekben az egyes logikai műveletek igazsághalmazát határoztuk meg. A példákban
– az egyes logikai műveletek, és
– az elemi állítások igazsághalmazai között értelmezett halmazelméleti műveletek
között egyértelmű kapcsolatot figyelhettünk meg.

A logikai műveletek és ezek igazsághalmaza közötti kapcsolatot a "...-ból következik ..." vagy "ha ... akkor ..." módon megadható logikai művelet, az implikáció esetében a legnehezebb megérteni, mivel ha a köznapi beszédben ezt a szerkezetet használjuk, akkor rendszerint feltételezzük, hogy az minden tanulóra teljesül.

Mivel az implikáció tagadásának igazsághalmaza M₅∖E₅= M₅∩E₅, ezért az implikáció igazsághalmaza ennek komplementere kell, hogy legyen. Azaz azoknak a t∈I tanulóknak a halmaza, amelyekre (t∈M₅)⊃(t∈E₅) teljesül, a de Morgan szabály alkalmazásával (M₅∪E₅).

Tehát azok a tanulók, akikre teljesül, hogy "ha ötöst kaptak matematikából, akkor ötöst kaptak énekből" azok, akikre teljesül, hogy

• "ötöst kaptak matematikából és ötöst kaptak énekből";
• "nem kaptak ötöst matematikából és ötöst kaptak énekből";
• "nem kaptak ötöst matematikából és nem kaptak ötöst énekből".

Mindezekből nagyon fontos következtetéseket vonhatunk le az implikációra (⊃) vonatkozóan.

(1) Ha az M₅⊃E₅ implikáció mint következtetés minden hallgatóra teljesül, ez azt jelenti, hogy a logikai művelet igazsághalmaza a teljes 'I' halmaz. Ez ekvivalens azzal, hogy a logikai művelet tagadásának igazsághalmaza üres, vagyis M₅∖E₅=∅ teljesül. Ennek két nagyon fontos következménye van:
    – az M₅∖E₅=∅ állítás halmazelméletileg ekvivalens az M₅⊆E₅ relációval;
    – az 'I' igazsághalmaz azokat a tanulókat is tartalmazza, akik nem kaptak ötöst matematikából.

(2) A (t∈M₅)⊃(t∈E₅) implikáció mint logikai művelet formálisan mindig teljesül ("érvényes") azokra a t∈I tanulókra, akikre t∉M₅ (azaz akik nem kaptak ötöst matematikából). Az ő esetükben azonban semmit sem tudunk mondani arról, hogy jelest kaptak-e énekből, azaz nem tudunk az implikációból semmilyen használható ("értelmes") következtetést levonni (mivel mind t∈E₅, mind t∉E₅ lehetséges). Másképpen megfogalmazva:

Tegyük fel, hogy egy osztályban minden tanulóra érvényes, hogy aki jelest kapott matematikából, az jelest kapott énekből is. Azonban ez nem azt jelenti, hogy minden tanuló jeles volt matematikából. Azok a tanulók, akik az osztályban nem kaptak jelest matematikából, azok vagy jelest kaptak énekből, vagy nem (függetlenül a matematika jeles és az ének jeles jegyek közti összefüggéstől).

(3) Ha viszont egy w∈I tanulóra w∈M₅ (azaz jelest kapott matematikából), és a (w∈M₅)⊃(w∈E₅) implikáció teljesül a 'w' tanulóra, akkor ebből az következik (⊨ vagy ⇒), hogy w∈E₅ teljesül (azaz a 'w' tanuló jelest kapott énekből is). Formálisan:
    w∈M₅, (w∈M₅)⊃(w∈E₅) ⊨ w∈E₅
(ez az ún. modus ponens szabály).

Érdemes további példákon keresztül áttekinteni a logikai műveletek értelmezését az iskola univerzumban.^⇒

Foglaljuk össze tömören a fenti megállapításokat:

A (t∈M₅)⊃(t∈E₅) implikáció mint logikai művelet természetes nyelven azokat a t∈I tanulókat jelenti, akikre a következő állítás teljesül:

"ha ötöst kaptak matematikából, akkor ötöst kaptak énekből; ha pedig nem kaptak ötöst matematikából, akkor bármilyen jegyet kaphattak énekből"

11.5. Összetett formulák és értékelések

A logikai műveletek lehetővé teszik, hogy összetett logikai kifejezéseket hozzunk létre.

• A predikátumokból és (individuum)változókból álló nyitott mondatokat atomi formuláknak nevezzük (pl. a "Kata szomszédja Marinak." kijelentés a Q(x,y) atomi formulából kapható, ahol 'Q' predikátum, 'x' és 'y' pedig individuumváltozók, amelyek a tanulók I halmazából vehetnek fel értékeket^⇒).
  • Speciálisan a "nullváltozós" predikátumok is atomi formulák (Dragálin-Buzási 1986: 32,34), ezeket a kijelentésváltozókkal^⇒ azonosítjuk (vö. Kopasz 1996: 27, Sashalminé Kelemen 2003: 37).
• Az atomi formulákból logikai műveletek^⇒ (pl. 'nem', 'és', 'vagy' stb.) és zárójelek segítségével összetett logikai kifejezéseket, formulákat hozhatunk létre. (Bár a 'formula' és a 'logikai kifejezés' szinonimák, azonban 'formula' alatt rendszerint nyitott mondatokból álló logikai kifejezést értünk.)

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

• azokat a műveleteket kell először végrehajtani, amelyek a táblázatban jobbról előrébb állnak (magasabb "precedenciával" rendelkeznek);
• ha két művelet azonos precedenciával rendelkezik, akkor végrehajtásuk balról jobbra történik.

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

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

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

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

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)

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

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

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

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

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.

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.)

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!

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.)

Hibás válaszok száma: ?