8.1. Predikátumlogika. A logikai műveletek és a halmazműveletek kapcsolata.

A predikátumlogika esetében formulákkal foglalkozunk, és figyelembe vesszük a kijelentések "belső szerkezetét", amely "a predikátumok felhasználása révén tárul fel" (Szendrei-Tóth 1978: 63).

A logikai műveletek^⇒ és a halmazműveletek^⇒ között szoros kapcsolat van. Ennek leírására szükségünk van az igazsághalmaz fogalmára.

Legyen I egy alaphalmaz és F(x):I→{0,1} egy egyváltozós formula. Tekintsük az I alaphalmaznak azt a legbővebb részhalmazát, amelyben az F(x) formula minden értékelése^⇒ igaz logikai értéket ad. Ezt a részhalmazt az F(x) formula igazsághalmazának nevezzük és I_F(x) módon jelöljük.

Az F(x) formula I_F(x)⊆I igazsághalmaza az I alaphalmaz azon elemeinek halmaza, amelyekre az F(x) formula igaz. Formálisan:
    I_F(x) ⇋ {x∈I | |F(x)|=1}

Megjegyzések:

• Az F(x) formula értékelése alatt a formula logikai értékének a meghatározását értjük az I alaphalmaz egy adott t∈I eleme esetén. Ez azt jelenti, hogy x=t helyettesítés után meghatározzuk az F(t) állítás igazságértékét (ami vagy igaz, vagy hamis).
• Az igazsághalmaz fogalma a fentihez hasonlóan definiálható olyan formulák esetén, amelyek tetszőleges számú változót (és ezeknek megfelelő alaphalmazokat) tartalmaznak.

---

Példaként legyenek P(x) és Q(x) a tanulók I alaphalmazán^⇒ értelmezett (atomi) formulák^⇒, amelyekben egyváltozós predikátumok fordulnak elő:

P(x) ⇋ "az 'x' tanuló kiváló matematikából";
Q(x) ⇋ "az 'x' tanuló kiváló énekből".

Tekintsük az I alaphalmaznak azokat a legbővebb részhalmazait, amelyekben a P(x), ill. Q(x) formulák minden értékelése igaz logikai értéket ad. Ekkor a P(x), ill. Q(x) formulák igazsághalmazait kapjuk:

I_P = {x∈I | |P(x)|=1}⊆I (a matematikából kiváló tanulók halmaza)
I_Q = {x∈I | |Q(x)|=1}⊆I (az énekből kiváló tanulók halmaza)

Határozzuk meg ezek után az I alaphalmaznak azokat a legbővebb részhalmazait, amelyekben a P(x), ill. Q(x) formulákból a fontosabb logikai műveletek segítségével képzett összetett formulák minden értékelése igaz logikai értéket ad. Ennek megfelelően értelmezzük a következő igazsághalmazokat:

• a ⌝P(x) negáció igazsághalmaza:
  I_⌝P = {x∈I | |P(x)|=0} = I∖I_P = I_P
• a P(x)∧Q(x) konjunkció igazsághalmaza:
  I_P∧Q = {x∈I | |P(x)|=1 és |Q(x)|=1} = I_P∩I_Q
• a P(x)∨Q(x) diszjunkció igazsághalmaza:
  I_P∨Q = {x∈I | |P(x)|=1 vagy |Q(x)|=1} = I_P∪I_Q
• a ⊤=P(x)∨⌝P(x) igaz állítás igazsághalmaza:^⇒
  I_⊤ = {x∈I | |⊤|=1} = I_P ∪ I_P = I
• a ⊥=P(x)∧⌝P(x) hamis állítás igazsághalmaza:^⇒
  I_⊥ = {x∈I | |⊥|=1} = I_P ∩ I_P = ∅
• a P(x)⊃Q(x) implikáció igazsághalmaza:^⇒
  I_P⊃Q = {x∈I | ha |P(x)|=1 akkor |Q(x)|=1 teljesül} = I_P∧Q∪I_⌝P
  (I_P⊃Q a matematikából és énekből kiváló tanulók, valamint a matematikából nem kiváló tanulók halmaza, ugyanis az implikáció hamis előtag esetén mindig teljesül; jegyezzük meg, hogy I_P∧Q∪I_⌝P = I_P∩I_Q∪I_⌝P = I_⌝P∪I_P∩I_Q = (I_⌝P∪I_P)∩(I_⌝P∪I_Q) = (I_P∪I_P)∩(I_⌝P∪I_Q) = I∩(I_⌝P∪I_Q) = I_⌝P∪I_Q teljesül)
  • ha a P⊃Q implikáció minden x∈I esetén igaz (röviden megfogalmazva "mindig igaz"), akkor igazsághalmaza I_P⊃Q = I
    • ha a P⊃Q implikáció mindig igaz, akkor I_P⊆I_Q teljesül
    • ha az I_P és I_Q igazsághalmazokra I_P⊆I_Q teljesül, akkor a P⊃Q implikáció mindig igaz
• a P(x)≡Q(x) ekvivalencia igazsághalmaza:^⇒
  I_P≡Q = {x∈I | |P(x)|=1 akkor és csak akkor teljesül, ha |Q(x)|=1 teljesül} = I_P∧Q∪I_⌝P∧⌝Q = I_P⊃Q∩I_Q⊃P
  (I_P≡Q a matematikából és énekből kiváló tanulók, valamint a sem matematikából sem énekből nem kiváló tanulók halmaza; ők azok, akik a matematika és az ének területén egyforma ("ekvivalens") teljesítményt nyújtanak)

Az összetett állítások és az igazsághalmazok kapcsolata úgy fejezhető ki, hogy egy F(x) összetett formula az 'x' individuumváltozó egy adott t∈I értékére akkor és csak akkor igaz (|F(t)|=1), ha t∈I_F teljesül.

---

Második példaként tekintsük az I (véges) alaphalmazt, és legyen A⊆I, B⊆I ennek két tetszőleges részhalmaza. Értelmezzük a P(x) és Q(x) (atomi) formulákat a következőképpen:
P(x) ⇋ "x∈A"
Q(x) ⇋ "x∈B"

Ekkor a P(x), ill. Q(x) formulák igazsághalmazai:

I_P = {x∈I | |P(x)|=1} = {x∈I | x∈A} = A⊆I
I_Q = {x∈I | |Q(x)|=1} = {x∈I | x∈B} = B⊆I

A fontosabb logikai műveletek igazsághalmazai a halmazműveletek definíciói alapján könnyen meghatározhatók:

logikai kifejezés	igazsághalmaz
⌝P(x) (negáció)	A
P(x)∧Q(x) (konjunkció)	A∩B
P(x)∨Q(x) (diszjunkció)	A∪B
P(x)⊃Q(x) (implikáció)	(A∩B)∪A A∪B
P(x)≡Q(x) (ekvivalencia)	(A∩B)∪(A∩B) (A∪B)∩(B∪A)

Emeljük ki, hogy ha a P(x)⊃Q(x) implikáció minden x∈I elem esetén teljesül, az a részhalmaz reláció meghatározása^⇒ alapján pontosan azt fejezi ki, hogy A⊆B teljesül (azaz az A⊆I halmaz részhalmaza a B⊆I halmaznak).

8.2. Kvantifikáció

Legyen A(x) tetszőleges formula a H alaphalmazon. Vezessük be a következő két logikai szimbólumot, ún. kvantort:

• univerzális kvantor:
  ∀x A(x) ⇋ "minden x∈H elem esetén |A(x)|=1 teljesül"
  (A ∀x A(x) formula logikai értéke akkor és csak akkor igaz, ha az A(x) formula értékelése a H alaphalmaz minden eleme esetén igaz értéket ad.)
• egzisztenciális kvantor:
  ∃x A(x) ⇋ "van olyan x∈H elem, amelyre |A(x)|=1 teljesül"
  (A ∃x A(x) formula logikai értéke akkor és csak akkor hamis, ha az A(x) formula értékelése a H alaphalmaz minden eleme esetén hamis értéket ad.)
  • sok esetben nagyon hasznos a ∃! szimbólum használata:
    ∃!x A(x) ⇋ "pontosan egy olyan x∈H elem létezik, amelyre |A(x)|=1 teljesül" (∃! ⇋ "pontosan egy létezik")

Az univerzális kvantor szoros kapcsolatban áll a konjunkcióval. Ha a 'H' alaphalmaz véges, akkor úgy tekinthetjük, mint az alábbi konjunkciók sorozatát:
   ∀x A(x) = A(x₁)∧A(x₂)∧...∧A(x_n)
ahol az x₁, x₂, ..., x_n elemek az x∈H változó összes lehetséges értékét jelentik.

Emiatt "az univerzális kvantifikáció a konjunkció általánosításaként is felfogható" (Szendrei-Tóth 1978: 70), vagyis ∀x A(x) ≃ A(x₁)∧A(x₂)∧...∧A(x_n)∧...

Az egzisztenciális kvantor szoros kapcsolatban áll a diszjunkcióval. Ha a 'H' alaphalmaz véges, akkor úgy tekinthetjük, mint az alábbi diszjunkciók sorozatát:
   ∃x A(x) = A(x₁)∨A(x₂)∨...∨A(x_n)
ahol az x₁, x₂, ..., x_n elemek az x∈H változó összes lehetséges értékét jelentik.

Emiatt "az egzisztenciális kvantifikáció a diszjunkció általánosításának is tekinthető" (Szendrei-Tóth 1978: 72), vagyis ∃x A(x) ≃ A(x₁)∨A(x₂)∨...∨A(x_n)∨...

---

Példaként legyenek ismét^⇒ P(x) és Q(x) a tanulók I alaphalmazán^⇒ értelmezett alábbi formulák:

P(x) ⇋ "az 'x' tanuló kiváló matematikából";
Q(x) ⇋ "az 'x' tanuló kiváló énekből".

Ekkor az univerzális és egzisztenciális kvantorok segítségével zárt formulákat^⇒ képezhetünk:

• |∀x P(x)|=1 ⇋ "az 'I' osztályban mindenki kiváló matematikából";
• |∃x Q(x)|=1 ⇋ "az 'I' osztályban van olyan ("létezik olyan") tanuló, aki kiváló énekből".

Nézzünk néhány példát összetett logikai kifejezések kvantifikációjára is:

• |∀x (P(x)∧Q(x))|=1 ⇋ "az 'I' osztályban mindenki kiváló matematikából és énekből";
• |∀x (P(x)∨Q(x))|=1 ⇋ "az 'I' osztályban mindenki kiváló matematikából vagy énekből" ("megengedő vagy" értelemben: lehet olyan tanuló is, aki mind matematikából, mind énekből is kiváló);
• |∃x (⌝P(x)∧Q(x))|=1 ⇋ "az 'I' osztályban van olyan tanuló, aki nem kiváló matematikából, de kiváló énekből";
• |∀x (P(x)⊃Q(x))|=1 ⇋ "az 'I' osztályban minden olyan tanuló, aki kiváló matematikából, az kiváló énekből is" (jegyezzük meg, hogy ez semmit sem állít azokról a tanulókról, akik nem kiválóak matematikából);
• |⌝∃x (P(x)∧⌝Q(x))|=1 ⇋ "az 'I' osztályban nincs olyan tanuló, aki kiváló matematikából és nem kiváló énekből" (ez megfelel annak, hogy az 'I' osztályban minden olyan tanuló, aki kiváló matematikából, az kiváló énekből is).
• ...

---

A kvantorok segítségével ún. kategorikus állítások fogalmazhatóak meg. A kategorikus állításokat tartalmazó, két premisszával rendelkező következtetési szabályok az ún. kategorikus szillogizmusok. Például a modus ponens^⇒ szabály megfelelője a következő:

A(x₀) , ∀x (A(x)⊃B(x)) ⊨ B(x₀)

Ezt a következtetési sémát "ha az A(x)⊃B(x) implikáció minden x∈H elem esetén teljesül és egy adott x₀∈H elemre A(x₀) igaz, akkor erre az x₀∈H elemre B(x₀) is igaz lesz" módon olvashatjuk.

Például ha egy adott 'I' osztályban teljesül a |∀x (P(x)⊃Q(x))|=1 törvény, és ha az osztályban |P("Pisti")|=1 is teljesül, akkor a

    P("Pisti") , ∀x (P(x)⊃Q(x)) ⊨ Q("Pisti")

következtetés premisszái teljesülnek. Tehát mivel Pisti kiváló matematikából, ebben az 'I' osztályban biztosan teljesül, hogy kiváló énekből is. (Jegyezzük meg, hogy |∀x (P(x)⊃Q(x))|=1 nem logikai törvény,^⇒ mivel biztosan létezik olyan osztály, amelyben van olyan tanuló (x₀∈I), aki kiváló matematikából ((P(x₀)|=1), de énekből már nem kiváló ((Q(x₀))|=0).

8.3. Alkalmazások

Az alábbi táblázat egy naplórészlet, amely a tanulók jegyeit tartalmazza matematikából, énekből és testnevelésből.

sorszám	dátum	név	tárgy	jegy

Értelmezzük a 'datum', 'nev', 'targy' és 'jegy' függvényeket a következőképpen:

datum(i) ⇋ "az 'i'-dik sorban szereplő dátum"
nev(i) ⇋ "az 'i'-dik sorban levő tanuló neve"
targy(i) ⇋ "az 'i'-dik sorban levő tárgy neve"
jegy(i) ⇋ "az 'i'-dik sorban szereplő jegy"

(1) A tanult logikai műveletekkel és a fent definiált függvényekkel olyan logikai kifejezéseket ("nyitott mondatokat") hozhatunk létre, amelyek alapján különböző szempontok szerint információkat kereshetünk a naplóban.

Például az az 'I' igazsághalmaz, amely Kata jegyeit tartalmazza az összes tárgyból, az alábbi logikai kifejezéshez tartozik:
A(j) ⇋ ∃i (nev(i)="Kata" ∧ jegy(i)=j))
I_A(j) ⇋ {j∈{1,2,3,4,5} | |A(j)|=1}

Az I_A(j) igazsághalmaz elemeit alkotó jegyek és a naplónak azok a sorai, amelyekben a keresett jegyek szerepelnek, az alábbi lekérdezéssel kiírathatók:

sorszám	dátum	név	tárgy	jegy

A lekérdezés ... sort eredményezett.

(2) A tanult logikai műveletekkel és a fent definiált függvényekkel olyan összefüggéseket kereshetünk, amelyek alapján adott feltételek (premisszák) fennállásából meghatározott információkra következtethetünk a naplóban.

Például tegyük fel, hogy ha egy tanuló matematikából csak jelest vagy jót kap, akkor mind énekből, mind tesiből csak jelesnél rosszabb jegyet kap (azaz nem jelest).

Ezt az összefüggést a következőképpen fejezhetjük ki:

(a) Először keressük meg azokat a tanulókat, akik matematikából csak jelest vagy jót kaptak:
    A(x) ⇋ ∀i (nev(i)=x ∧ targy(i)="matematika" ⊃. jegy(i)=5 ∨ jegy(i)=4)
A fenti formula igazságértéke egy adott tanuló (x₀∈I) és egy adott sor (i₀) esetén:

előtag nev(i0)=x0 ∧ targy(i0)="matematika"	utótag jegy(i0)=5 ∨ jegy(i0)=4	⊃.	A(x0)
0 (az adott sorban vagy nem az adott tanuló szerepel, vagy nem matematika jegy)	0 vagy 1 (bármilyen lehet)	1	lehet 1
1 (az adott sorban a tanuló matematika jegye szerepel)	0 (a tanuló matematika jegye 4-nél rosszabb)	0	0
	1 (a tanuló matematika jegye vagy 4, vagy 5)	1	lehet 1

Az A(x) formula igazsághalmaza a "jó matekes" tanulókat adja meg (ti. akik csak jeles vagy jó osztályzatot kaptak matematikából).

Jegyezzük meg, hogy így azokat a tanulókat is megkapjuk, akik matematikából még nem kaptak semmilyen jegyet (és azokat is, akik egy tárgyból sem kaptak még semmilyen jegyet). Ha őket ki akarjuk zárni, akkor a fenti formulát tovább kell szűkítenünk:
A'(x) ⇋ A(x) ∧ ∃i (nev(i)=x ∧ targy(i)="matematika")
Ezzel megköveteljük, hogy legalább egy sorban (∃i) az adott tanulónak (x) szerepeljen valamilyen jegye matematikából.

(b) Ezután keressük meg azokat a tanulókat, akik sem énekből, sem testnevelésből nem kaptak jelest:
        B(x) ⇋ ∀i (nev(i)=x ∧ (targy(i)="ének" ∨ targy(i)="testnevelés") ⊃. ⌝jegy(i)=5)
A fenti formula igazságértéke egy adott tanuló (x₀∈I) és egy adott sor (i₀) esetén:

előtag nev(i0)=x0 ∧ (targy(i0)="ének" ∨ targy(i0)="testnevelés")	utótag ⌝jegy(i0)=5	⊃.	B(x0)
0 (az adott sorban vagy nem az adott tanuló szerepel, vagy sem ének, sem testnevelés jegy)	0 vagy 1 (bármilyen lehet)	1	lehet 1
1 (az adott sorban a tanuló ének vagy testnevelés jegye szerepel)	0 (a tanuló ének vagy testnevelés jegye jeles)	0	0
	1 (a tanuló ének vagy testnevelés jegye rosszabb, mint jeles)	1	lehet 1

A B(x) formula igazsághalmaza a "nem kiváló énekes és tesis" tanulókat adja meg (ti. akik nem kaptak jeles osztályzatot sem énekből, sem testnevelésből).

Jegyezzük meg, hogy így megkapjuk azokat a tanulókat is, akik sem énekből, sem testnevelésből (vagy semmilyen tárgyból) nem kaptak még jegyet. Ha őket ki akarjuk zárni, akkor a fenti formulát tovább kell szűkítenünk:
B'(x) ⇋ B(x) ∧ ∃i (nev(i)=x ∧ (targy(i)="ének" ∨ targy(i)="testnevelés"))
Ezzel megköveteljük, hogy legalább egy sorban (∃i) az adott tanulónak (x) szerepeljen valamilyen jegye vagy énekből, vagy testnevelésből.

(c) Ezután az adott naplórészlet alapján határozzuk meg azokat a tanulókat, akikre A(x), A'(x), ill. B(x), B'(x) teljesül:
I_A(x) ⇋ {x∈{Tercsi, Fercsi, ...} | |A(x)|=1}
I_A'(x) ⇋ {x∈{Tercsi, Fercsi, ...} | |A'(x)|=1}
I_A'(x)⊆I_A(x)

I_B(x) ⇋ {x∈{Tercsi, Fercsi, ...} | |B(x)|=1}
I_B'(x) ⇋ {x∈{Tercsi, Fercsi, ...} | |B'(x)|=1}
I_B'(x)⊆I_B(x)

sorszám	dátum	név	tárgy	jegy

A lekérdezés ... sort eredményezett.

A lekérdezések eredményeinek összesítése:

Matematikából még nem kaptak jegyet (|A(x)|=1, |A'(x)|=0): {...}⊆I_A(x)
Matematikából csak jelest vagy jót kaptak (|A(x)|=1, |A'(x)|=1): {...}⊆I_A(x)∩I_A'(x)
Matematikából nem csak jelest vagy jót kaptak (|A(x)|=0, |A'(x)|=0): {...}

Sem énekből, sem testnevelésből még nem kaptak jegyet (|B(x)|=1, |B'(x)|=0): {...}⊆I_B(x)
Énekből és testnevelésből csak jelesnél rosszabbat kaptak (|B(x)|=1, |B'(x)|=1): {...}⊆I_B(x)∩I_B'(x)
Énekből vagy testnevelésből kaptak jelest (|B(x)|=0, |B'(x)|=0): {...}

(d) Ha a feladatban vizsgált összefüggés igaz, akkor az alábbi következtetések közül legalább az egyik teljesül:
    |∀x (A'(x) ⊃ B'(x))|=1 ⇔ I_A'(x)⊆I_B'(x)
    |∀x (A'(x) ⊃ B(x))|=1 ⇔ I_A'(x)⊆I_B(x)
    |∀x (A(x) ⊃ B'(x))|=1 ⇔ I_A(x)⊆I_B'(x)
    |∀x (A(x) ⊃ B(x))|=1 ⇔ I_A(x)⊆I_B(x)
A lekérdezések eredménye alapján a fenti következtetések egyértelműen eldönthetők: a megadott naplórészletben ... következtetés teljesül.
(Megjegyzés: érdemes többször frissíteni az oldalt (CTRL R vagy F5), utána újra lefuttatni a lekérdezéseket, és ellenőrizni a kapott következtetéseket!)

A legáltalánosabb eset az, amikor |∀x (A(x) ⊃ B'(x))|=1 teljesül. Ekkor fennállnak az alábbi összefüggések:
I_A'(x)⊆ I_A(x)⊆ I_B'(x)⊆ I_B(x)
Vegyük észre, hogy ebben az esetben mind a négy lehetséges következtetés igaz.
Ezzel szemben a legspeciálisabb eset az, amikor kizárólag a |∀x (A'(x) ⊃ B(x))|=1 következtetés teljesül (és a többi összefüggés nem áll fenn).

Fogalmazzuk meg végül természetes nyelven is a fentieket. Ha a feladatban vizsgált összefüggés igaz, akkor minden olyan 'x' tanulóra,
– akire A'(x) teljesül (azaz csak jelest vagy jót kapott matematikából) és/vagy akire A(x) teljesül (azaz csak jelest vagy jót kapott matematikából, vagy matematikából még nem kapott osztályzatot),
– egyszersmind B'(x) is teljesül (azaz csak jelesnél rosszabb jegyet kapott mind énekből, mind testnevelésből), és/vagy B(x) is teljesül (azaz csak jelesnél rosszabb jegyet kapott mind énekből, mind testnevelésből, vagy énekből, ill. testnevelésből még nem kapott jegyet).
Leegyszerűsítve: Ha a vizsgált összefüggés igaz, akkor az adott osztályban a "jó matekes" (vagy matekből még nem értékelt) tanulók nem kiválók sem énekből, sem testnevelésből (vagy esetleg még nem értékelték őket egyikből vagy másikból).