A matematikai logika alkalmazásszemléletű tárgyalása

Főoldal > TAMOP 4.2.5 Pályázat könyvei > Könyvek > Természettudományok > Matematika

A matematikai logika alkalmazásszemléletű tárgyalása

Pásztorné Varga Katalin, Várterész Magda, Sági Gábor

Panem Kft.

Beágyazás

Szemantikus következményfogalom

5.4.1. DEFINÍCIÓ. Legyen $Γ$ az $ℒ [V_{ν}]$ nyelv formuláinak tetszőleges halmaza és $B$ tetszőleges formulája. Azt mondjuk, hogy a $B$ formula logikai következménye a $Γ$ formulahalmaznak (vagy a $Γ$ -beli formuláknak), ha minden olyan $ℒ [V_{ν}]$ -beli interpretáció és változókiértékelés, amely kielégít minden $Γ$ -beli formulát, az kielégíti a $B$ formulát is. Jelölése: $Γ ⊨ B$ .

Próbáljuk meg először a fenti definíció alapján eldönteni, hogy egy adott formula valamely véges formulahalmaznak logikai következménye-e.

5.4.2. PÉLDA.

Az $ℒ^{p_{1}}$ nyelvben a ${P (c), \forall x (P (x) \supset \exists \tilde{x} Q (x, \tilde{x}))}$ formulahalmaznak logikai következménye a $\exists \tilde{x} Q (c, \tilde{x})$ formula. Ugyanis ha $ℐ$ olyan interpretáció, amelyben $| P (c) |^{ℐ} = i$ és $| \forall x (P (x) \supset \exists \tilde{x} Q (x, \tilde{x})) |^{ℐ} = i$ , akkor bármely $x$ -variáns $κ$ változókiértékelés mellett $| P (x) \supset \exists \tilde{x} Q (x, \tilde{x}) |^{ℐ, κ} = i$ . Legyen $κ (x) = | c |^{ℐ}$ . Az 5.2.15. tétel szerint $| P (x) |^{ℐ, κ} = | P (c) |^{ℐ}$ és $| \exists \tilde{x} Q (x, \tilde{x}) |^{ℐ, κ} = | \exists \tilde{x} Q (c, \tilde{x}) |^{ℐ}$ , így világos, hogy $| P (x) |^{ℐ, κ} = i$ miatt $| \exists \tilde{x} Q (x, \tilde{x}) |^{ℐ, κ} = i$ , tehát $| \exists \tilde{x} Q (c, \tilde{x}) |^{ℐ} = i$ . Azaz tetszőleges, a ${P (c), \forall x (P (x) \supset \exists \tilde{x} Q (x, \tilde{x}))}$ formulahalmazt kielégítő interpretáció kielégíti a $\exists \tilde{x} Q (c, \tilde{x})$ formulát is.
Ugyanakkor a $\exists x \forall \tilde{x} R (f (x, \tilde{x}), \tilde{x})$ formulának nem logikai következménye a $\forall \tilde{x} R (\tilde{x}, \tilde{x})$ formula, hisz az $ℐ^{p_{1}}$ interpretációban a $\exists x \forall \tilde{x} R (f (x, \tilde{x}), \tilde{x})$ formula $i$ , de a $\forall \tilde{x} R (\tilde{x}, \tilde{x})$ formula $h$ igazságértékű.

Az elsőrendű logika következményfogalmát is hasznos lenne alkalmas formulák szemantikai jellemzésével leírni. Ehhez nyújtanak lehetőséget az ítéletlogikában megismerthez nagyon hasonló tételek.

5.4.3. TÉTEL. Legyen $Γ$ az $ℒ [V_{ν}]$ nyelv formuláinak tetszőleges halmaza és $B$ tetszőleges formulája. $Γ ⊨ B$ pontosan akkor, ha a $Γ \cup {\neg B}$ formulahalmaz kielégíthetetlen.

BIZONYÍTÁS.

Legyen $Γ ⊨ B$ . Ekkor az 5.4.1. definíció szerint minden olyan interpretáció és változókiértékelés, amely kielégíti $Γ$ -t, kielégíti $B$ -t is. Ezekben az interpretációkban és változókiértékelések mellett tehát $\neg B$ hamis, továbbá ezek az interpretációk és változókiértékelések nem elégítik ki $Γ \cup {\neg B}$ -t. Azok az interpretációk, melyek már nem elégítik ki $Γ$ -t sem, nyilván nem elégíthetik ki a bővebb $Γ \cup {\neg B}$ formulahalmazt sem.
Legyen most a $Γ \cup {\neg B}$ formulahalmaz kielégíthetetlen. Ekkor vagy már $Γ$ is kielégíthetetlen, ekkor nyilván $Γ ⊨ B$ . Ha viszont $Γ$ kielégíthető, akkor rögzítsük egy tetszőleges $ℐ$ interpretációt és $κ$ változókiértékelést, melyre $| A |^{ℐ, κ} = i$ minden $A \in Γ$ -ra. De $Γ \cup {\neg B}$ kielégíthetetlen, tehát $| \neg B |^{ℐ, κ} = h$ , azaz $| B |^{ℐ, κ} = i$ , így most is $Γ ⊨ B$ .

Ezzel a tételt bebizonyítottuk. $⋄$

Ennek a tételnek a felhasználásával könnyen bizonyítható a következő két állítás.

5.4.4. TÉTEL. Legyenek $A_{1}, A_{2}, \dots, A_{n}, B$ (n $\geq 1)$ az $ℒ [V_{ν}]$ nyelv tetszőleges formulái. ${A_{1}, A_{2}, \dots, A_{n}} ⊨ B$ pontosan akkor, ha

az $A_{1} \land A_{2} \land \dots \land A_{n} \land \neg B$ formula kielégíthetetlen,
az $A_{1} \land A_{2} \land \dots \land A_{n} \supset B$ formula logikai törvény.

Az elsőrendű logikában is érvényes a dedukciós tétel és a dedukciós tételen alapuló eldöntésprobléma-tétel. Bizonyításukat az olvasóra hagyjuk, mert az ítéletlogikai esethez nagyon hasonlók.

5.4.5. TÉTEL. (DEDUKCIÓS TÉTEL.)

Legyenek $A_{1}, A_{2}, \dots, A_{n}, B$ $(n \geq 1)$ az $ℒ [V_{ν}]$ nyelv tetszőleges formulái. ${A_{1}, A_{2}, \dots, A_{n - 1}, A_{n}} ⊨ B$ pontosan akkor, ha

${A_{1}, A_{2}, \dots, A_{n - 1}} ⊨ A_{n} \supset B .$

5.4.6. TÉTEL. (AZ ELDÖNTÉSPROBLÉMA TÉTEL.)

Legyenek $A_{1}, A_{2}, \dots, A_{n}, B$ $(n \geq 1)$ az $ℒ [V_{ν}]$ nyelv tetszőleges formulái. ${A_{1}, A_{2}, \dots, A_{n - 1}, A_{n}} ⊨ B$ pontosan akkor, ha

$⊨ A_{1} \supset A_{2} \supset \dots \supset A_{n - 1} \supset A_{n} \supset B .$

A tétel természetesen kimondható úgy is, hogy ${A_{1}, A_{2}, \dots, A_{n - 1}, A_{n}} ⊨ B$ akkor és csak akkor, ha $⊨ A_{i_{1}} \supset A_{i_{2}} \supset \dots \supset A_{i_{n}} \supset B$ , ahol $i_{1}, i_{2}, \dots i_{n}$ az $1,2, \dots, n$ számok tetszőleges permutációja.

5.4.7. TÉTEL. Legyen $Γ$ az $ℒ [V_{ν}]$ nyelv formuláinak tetszőleges halmaza, $B$ tetszőleges formula és $x$ olyan változó, hogy $x \notin Par (A)$ , ha $A \in Γ$ . Ha $Γ ⊨ B$ , akkor $Γ ⊨ \forall x B$ .

BIZONYÍTÁS. Ha $Γ ⊨ B$ , akkor minden olyan $ℒ [V_{ν}]$ -beli interpretáció és változókiértékelés, amely kielégít minden $Γ$ -beli formulát, az kielégíti a $B$ formulát is. Legyen tehát $ℐ$ és $κ$ tetszőlegesen rögzített olyan interpretáció és változókiértékelés, melyre $| A |^{ℐ, κ} = i$ minden $A \in Γ$ -ra. Ekkor mivel $x \notin Par (A)$ , ha $A \in Γ$ , $κ$ minden $κ^{'}$ $x$ -variánsa esetén is $| A |^{ℐ, κ^{'}} = i$ minden $A \in Γ$ -ra. Mivel $Γ ⊨ B$ , így $κ$ minden $κ^{'}$ $x$ -variánsára $| B |^{ℐ, κ^{'}} = i$ is, tehát az 5.2.9. definíció miatt $| \forall x B |^{ℐ, κ} = i$ . Ez pedig azt jelenti, hogy $Γ ⊨ \forall x B$ . $⋄$

Az előző fejezetben Quine-táblázat segítségével is jellemeztük az elsőrendű formulákat, tehát az elsőrendű következményfogalmat is megvizsgálhatjuk ezzel az eszközzel.

5.4.8. DEFINÍCIÓ. Legyen $Γ$ az $ℒ [V_{ν}]$ nyelv formuláinak véges halmaza és $B$ tetszőleges formulája. Azt mondjuk, hogy $B$ tautologikus következménye $Γ$ -nak, ha a $Γ$ formulahalmaz és $B$ közös Quine-táblázatában azon sorokban, ahol minden $Γ$ -beli formula alatt $i$ igazságérték található, $B$ oszlopában is csupa $i$ igazságérték van. Jelölése: a $Γ ⊨_{0} B$ .

5.4.9. PÉLDA.

A ${\forall x \exists \tilde{x} Q (x, \tilde{x}) \supset \forall x P (x), \neg \forall x P (x)}$ formulahalmaznak tautologikus következménye a $\neg \forall x \exists \tilde{x} Q (x, \tilde{x})$ formula:

$\forall x \exists \tilde{x} Q (x, \tilde{x})$	$\forall x P (x)$	$\forall x \exists \tilde{x} Q (x, \tilde{x}) \supset \forall x P (x)$	$\neg \forall x P (x)$	$\neg \forall x \exists \tilde{x} Q (x, \tilde{x})$
$i$	$i$	$i$	$h$	$h$
$i$	$h$	$h$	$i$	$h$
$h$	$i$	$i$	$h$	$i$
$h$	$h$	$i$	$i$	$i$

Az 5.4.2. (a) példájában pedig a következményformula nem tautologikus következménye a feltételformulák halmazának, hisz ezen formuláknak a prímkomponensei éppen saját maguk, így ha elkészítjük a közös Quine-táblázatot, abban nyilván lesz olyan sor, ahova mindkét feltételformula alá $i$ -t, a következményformula alá pedig $h$ -t írunk. Persze az 5.4.2. (a) példa gondolatmenete alapján világos, hogy ilyen interpretáció valójában nincs.

5.4.10. LEMMA. Legyenek $A_{1}, A_{2}, \dots, A_{n}, B$ $(n \geq 1)$ az $ℒ [V_{ν}]$ nyelv tetszőleges formulái. Ha ${A_{1}, A_{2}, \dots, A_{n}} ⊨_{0} B$ , akkor ${A_{1}, A_{2}, \dots, A_{n}} ⊨ B$ .

BIZONYÍTÁS. Az olvasóra bízzuk annak belátását, hogy ${A_{1}, A_{2}, \dots, A_{n}} ⊨_{0} B$ , pontosan akkor, ha az $A_{1} \land A_{2} \land \dots \land A_{n} \supset B$ formula tautologikusan igaz. Ekkor az 5.3.19. lemma szerint a formula logikailag is igaz, ahonnan az 5.4.4. tétellel adódik az állítás. $⋄$

Megjegyezzük, hogy az 5.4.10. lemma megfordítása nem igaz.

5.4.11. LEMMA. Legyenek $A_{1}, A_{2}, \dots, A_{n}, B$ $(n \geq 1)$ az $ℒ [V_{ν}]$ nyelv tetszőleges formulái. Jelölje az ${A_{1}, A_{2}, \dots, A_{n}}$ formulahalmazt $Γ$ . Legyenek továbbá a $B \in ℒ [V_{ν}]$ formula prímkomponensei a $B_{1}, B_{2}, \dots, B_{n}$ prímformulák, és legyenek $C_{1}, C_{2}, \dots, C_{n}$ tetszőleges $ℒ [V_{ν}]$ -beli formulák. Ha $Γ ⊨_{0} B$ , akkor

$Γ (B_{1}, B_{2}, \dots, B_{n} ∥ C_{1}, C_{2}, \dots, C_{n}) ⊨_{0} B (B_{1}, B_{2}, \dots, B_{n} ∥ C_{1}, C_{2}, \dots, C_{n}) .$

BIZONYÍTÁS. Ha $Γ ⊨_{0} B$ , könnyű belátni, hogy az $A_{1} \land A_{2} \land \dots \land A_{n} \supset B$ formula tautologikusan igaz. Az 5.3.21. lemma szerint ekkor az

$(A_{1} \land A_{2} \land \dots \land A_{n} \supset B) (B_{1}, B_{2}, \dots, B_{n} ∥ C_{1}, C_{2}, \dots, C_{n}),$

azaz az

$\begin{array}{l} A_{1} (B_{1}, B_{2}, \dots, B_{n} ∥ C_{1}, C_{2}, \dots, C_{n}) \land \\ \land A_{2} (B_{1}, B_{2}, \dots, B_{n} ∥ C_{1}, C_{2}, \dots, C_{n}) \land \\ ⋮ \\ \land A_{n} (B_{1}, B_{2}, \dots, B_{n} ∥ C_{1}, C_{2}, \dots, C_{n}) \supset \\ \supset B (B_{1}, B_{2}, \dots, B_{n} ∥ C_{1}, C_{2}, \dots, C_{n}) . \end{array}$

formula is tautologikusan igaz. Ekkor viszont $Γ (B_{1}, B_{2}, \dots, B_{n} ∥ C_{1}, C_{2}, \dots, C_{n}) ⊨_{0} B (B_{1}, B_{2}, \dots, B_{n} ∥ C_{1}, C_{2}, \dots, C_{n}) .$

Ezzel a lemmát bebizonyítottuk. $⋄$

Ha a feltételformuláknak egy formula logikai következménye volt, a formulahelyettesítés során nyert feltételformuláknak is logikai következménye lesz a kapott formula. Tehát ha egyszer kiderült, hogy helyesen következtettünk, olyan formában más formulákkal is helyesen lehet következtetni.

5.4.12. DEFINÍCIÓ. Legyenek $A_{1}, A_{2}, \dots, A_{n}, B$ $(n \geq 1)$ az $ℒ [V_{ν}]$ nyelv tetszőleges formulái. Az $({A_{1}, A_{2}, \dots, A_{n}}, B)$ párt elsőrendű következtetésformának nevezzük. Az $({A_{1}, A_{2}, \dots, A_{n}}, B)$ pár helyes következtetésforma, ha ${A_{1}, A_{2}, \dots, A_{n}}$ kielégíthető és ${A_{1}, A_{2}, \dots, A_{n}} ⊨ B$ .

5.4.13. TÉTEL. Legyenek $A, B$ és $C$ tetszőleges elsőrendű logikai formulák az $ℒ [V_{ν}]$ nyelvben. Az alábbiakban felsorolt elsőrendű következtetésformák helyesek:

a leválasztási szabály vagy modus ponens	$({A \supset B, A}, B)$
a kontrapozíció vagy modus tollens	$({A \supset B, \neg B}, \neg A)$
reductio ad absurdum	$({A \supset B, A \supset \neg B}, \neg A)$
az indirekt bizonyítás	$({\neg A \supset B, \neg A \supset \neg B}, A)$
feltételes szillogizmus	$({A \supset B, B \supset C}, A \supset C)$
következtetés esetszétválasztással	$({A \lor B, A \supset C, B \supset C}, C)$
modus tollendo ponens	$({A \lor B, \neg A}, B)$
modus ponendo tollens	$({A \oplus B, A}, \neg B)$
a $\lor$ -ra vonatkozó következtetésformák	$({A}, A \lor B) é s$ ({B}, A $\lor B)$
az $\land$ -re vonatkozó következtetésformák	$({A, B}, A \land B)$
	$({A \land B}, A) é s$ ({A $\land B}, B)$
az $\supset$ -ra vonatkozó következtetésforma	$({B}, A \supset B)$
a $\neg \neg$ -re vonatkozó következtetésformák	$({\neg \neg A}, A) é s$ ({A}, $\neg \neg A)$

BIZONYÍTÁS. Többet fogunk belátni: a felsorolt elsőrendű következtetésformákban a formulahalmaznak minden esetben tautologikus következménye a formula; az 5.4.10. lemma alapján ekkor azt mondhatjuk, hogy a formulák helyes elsőrendű következtetésformák. Ha az $A, B, C$ formulák rendre egy elsőrendű logikai nyelv atomi formulái, Quine-táblával könnyű igazolni, hogy a felsorolt következtetésformákban a formulahalmaznak tautologikus következménye a formula. Majd az atomi formulák helyére rendre tetszőleges elsőrendű formulákat helyettesítve az 5.4.11. lemmából adódik, hogy ezen következtetésformákban is a formulahalmaznak tautologikus következménye a formula. $⋄$

Természetesen vannak olyan elsőrendű következtetésformák is, amely következtetésformákban a formulahalmaznak logikai (de nem tautologikus) következménye a formula. Néhány ilyen jellegzetes helyes következtetésformát a teljesség igénye és bizonyítás nélkül felsorolunk:

az univerzális kvantor elhagyása	$({\forall x A}, [A (x ∥ t)])$
az egzisztenciális kvantor bevezetése	$({[A (x ∥ t)]}, \exists x A)$
szillogizmusok	$({\forall x (A \supset B), \forall x (B \supset C}, \forall x (A \supset C))$
	$({\exists x (A \land B), \forall x (B \supset C)}, \exists x (A \land C))$

Feladatok

5.4.1. FELADAT. Logikai, esetleg tautologikus következménye-e a $\forall x Q (x, x)$ formula az alábbi formulahalmazoknak:

${\forall x \forall y Q (x, y)}$
${\forall x \forall y (Q (x, y) \supset Q (y, x)), \forall x \forall y Q (x, y), \forall x \forall y \forall z (Q (x, y) \land Q (y, z) \supset Q (x, z))}$
${\forall x \forall y (Q (x, y) \supset Q (y, x)) \land \forall x Q (x, x)}$