Logikai azonosságok, logikai következtetések. Köznyelvi és matematikai tartalmú szövegek formalizálása.
Gyakorló feladatok (vö. Kiss 1996: 14-16):
Készítse el az alábbi logikai azonosságok⇒ értéktáblázatát és ellenőrizze, hogy az azonosságok bal- és jobboldalán szereplő logikai kifejezések értéke megegyezik!⇒
Az értéktáblázatok utolsó oszlopában szerepeljenek az azonosságok bal- és jobboldalán szereplő logikai kifejezések az ekvivalencia műveletével összekapcsolva. (Ha az azonosság teljesül, akkor ebben az oszlopban csupa '1' értéknek kell szerepelnie.)
(a1) A∧(B∨C) = (A∧B)∨(A∧C) (a konjunkció disztributivitása a diszjunkcióra)
(a2) A∨(B∧C) = (A∨B)∧(A∨C) (a diszjunkció disztributivitása a konjunkcióra)
(b) A∨(A∧B) = A (abszorpció vagy elnyelés)
(c1) ⌝(A∧B) = ⌝A∨⌝B (de Morgan-féle azonosság)
(c2) ⌝(A∨B) = ⌝A∧⌝B (de Morgan-féle azonosság)
(d) A⊃B = ⌝A∨B (az implikáció kifejezése)
(e) A≡B = (A⊃B)∧(B⊃A) (az ekvivalencia kifejezése)
Igazolja értéktáblázattal és azonos átalakítások segítségével az alábbi logikai azonosságokat!
(a) p∧(p⊃q) = p∧q
Induljunk ki a bizonyítandó azonosság bal oldalából. Célunk az, hogy a korábbi logikai azonosságokat⇒ felhasználva olyan azonos átalakításokat végezzünk, amelynek végén eljutunk a bizonyítandó azonosság jobb oldalán szereplő logikai kifejezéshez:
p∧(p⊃q) =
p∧(⌝p∨q) =
(p∧⌝p)∨(p∧q) =
⊥∨(p∧q) =
p∧q (q.e.d)
(b) ⌝p∨(p∧q) = p⊃q
(c) q⊃(p∧q) = q⊃p
(d) p∧(⌝p⊃q) = p
(e) p∨⌝(p⊃q) = p
(f) (p⊃q)⊃p = p
(g) (p⊃q)⊃r = (p∨r)∧(q⊃r)
Igazolja értéktáblázattal és azonos átalakítások segítségével az alábbi logikai törvényeket!
Emlékeztető: ha egy 'p' formula "azonosan igaz", vagyis logikai törvény, ezt
⊨ p
módon jelöljük. Az alább igazolandó logikai törvények azonosságok (tautológiák), vagyis a bennük szereplő kijelentésváltozók bármilyen értékére igazak, tehát a levezetés végén a
⊤
szimbólumot kell megkapnunk.
(a) ⊨ p⊃p (az azonosság törvénye⇒)
(b) ⊨ p⊃⊤ (az igaz következmény törvénye⇒)
(c) ⊨ ⊥⊃p (a hamis előfeltétel törvénye⇒)
(d) ⊨ ⌝p⊃(p⊃q) (ennek a logikai törvénynek a jelentése az, hogy "az ellentmondásból bármi következik", vö. Dragálin-Buzási 1986: 88)
Induljunk ki a bizonyítandó logikai törvényből. Célunk az, hogy a korábbi logikai azonosságokat⇒ felhasználva olyan azonos átalakításokat végezzünk, amelynek végén eljutunk a "szabvány-igaz" (⊤)⇒ kijelentéshez:
⌝p⊃(p⊃q) = (→ implikáció kifejezése)
⌝p⊃(⌝p∨q) = (→ implikáció kifejezése)
p∨(⌝p∨q) = (→ asszociativitás)
(p∨⌝p)∨q = (→ kizárt harmadik törvénye⇒)
⊤∨q = (→ diszjunkció szabvány-igaz kijelentéssel)
⊤ (q.e.d.)
(e) ⊨(p∧q)⊃p (a szűkítés szabálya⇒)
(f.1) ⊨ p⊃(p∨q) (a bővítés szabálya⇒)
(f.2) ⊨ (r∧p)⊃.r∧(p∨q) (a bővítés szabálya konjunktív előtag esetén)
(g) ⊨ (p⊃r)∧(q⊃r)⊃.(p∨q)⊃r (esetelemzés⇒)
(h.1) ⊨ ⌝p⊃(p⊃q)
(h.2) ⊨ p⊃(q⊃p)
(i) ⊨ p⊃(q⊃.p∧q)
(j) ⊨ (p⊃r)⊃.(p∧q)⊃r (premisszák bővíthetősége⇒)
(k) ⊨ p∧(p⊃q)⊃.q (modus ponens⇒)
(l) ⊨ (p⊃q)∧⌝q⊃.⌝p (indirekt bizonyítás⇒)
(m) ⊨ (q⊃p)∧(q⊃⌝p)⊃.⌝q (indirekt bizonyítás, ill. reductio ad absurdum)
(n) ⊨ (p⊃q)∧⌝q⊃.⌝p (modus tollens⇒)
(o) ⊨ (p∨q)∧⌝p ⊃.q (modus tollendo ponens⇒)
(p) ⊨ (⌝p⊃q)∧(⌝p⊃⌝q)⊃p (reductio ad absurdum⇒)
(q) ⊨ (⌝p⊃q)∧(q⊃p)⊃.p (reductio ad absurdum, 2. variáció)
(r) ⊨ (p⊃q)∧(q⊃r)⊃.(p⊃r) (láncszabály⇒)
Kiegészítő anyag
[kieg.] Legyenek A, B, C és D tetszőleges halmazok. Bizonyítsa be levezetéssel⇒ az alábbi halmazelméleti összefüggéseket, ill. azonosságokat!
Néhány halmazelméleti összefüggést, ill. azonosságot⇒ korábban már megismertünk, ezért érdemes ezeket is átismételni.
(a) ha A⊆B és B⊆C teljesül, akkor A⊆C is teljesül
premisszák:
P1 ⇋ A⊆B;
P2 ⇋ B⊆C
a levezetés sémája:
x∈A ... ⇒ ...
...
... ⇒ x∈C
Tehát ... (q.e.d)
premisszák:
P1 ⇋ A⊆B;
P2 ⇋ B⊆C
x∈A ∧ A⊆B ⇒ x∈B
(
P, P1 ⊨ R
)
x∈B ∧ B⊆C ⇒ x∈C
(
R, P2 ⊨ Q
)
Tehát A⊆C teljesül az adott feltétel mellett (q.e.d.). ( P, P1, P2 ⊨ Q )
(b1) ha A⊆B, akkor A⊆A∩B teljesül
premissza:
P ⇋ A⊆B
a levezetés sémája:
x∈A ... ⇒ ...
...
... ⇒ x∈A∩B
Tehát ... (q.e.d)
premissza: P1 ⇋ A⊆B
x∈A ∧ A⊆B ⇒ x∈B
(
P, P1 ⊨ R
)
x∈A ∧ x∈B ⇒ x∈A∩B
(
P, R ⊨ Q
)
Tehát A⊆A∩B teljesül az adott feltétel mellett (q.e.d.). ( P, P1 ⊨ Q )
(b2) ha A⊆B, akkor A∪B⊆B teljesül
premissza:
P ⇋ A⊆B
a levezetés sémája:
x∈A∪B ... ⇒ ...
...
... ⇒ x∈B
Tehát ... (q.e.d)
A bizonyítás során fel fogjuk használni az esetelemzés⇒ szabályát.
premissza: P1 ⇋ A⊆B
x∈A∪B ⇒ x∈A ∨ x∈B
(
P ⊨ R
)
(x∈A ∨ x∈B) ∧ A⊆B ⇒
(x∈A ∧ A⊆B) ∨ (x∈B ∧ A⊆B)
(
R, P1 ⊨ V; ld. disztributivitás⇒
)
x∈A ∧ A⊆B ⇒ x∈B
(
V1 ⊨ W
)
x∈B ∧ A⊆B ⇒ x∈B
(
V2 ⊨ W; ld. a szűkítés szabályát⇒
)
(x∈A ∧ A⊆B) ∨ (x∈B ∧ A⊆B) ⇒ x∈B
(
V ⊨ W; ld. az esetelemzés szabályát⇒
)
(x∈A ∨ x∈B) ∧ A⊆B ⇒ x∈B
(
R, P1 ⊨ Q; ld. disztributivitás⇒
)
Tehát A∪B⊆B teljesül az adott feltétel mellett (q.e.d.). ( P, P1 ⊨ Q )
(c1) ha A⊆B és C⊆D, akkor A∩C⊆B∪D teljesül
premisszák:
P1 ⇋ A⊆B;
P2 ⇋ C⊆D
a levezetés sémája:
x∈A∩C ⇒ ...
...
... ⇒ x∈B∪D
Tehát ... (q.e.d)
premisszák:
P1 ⇋ A⊆B;
P2 ⇋ C⊆D
x∈A∩C ⇒ x∈A ∧ x∈C
(
P ⊨ R
)
x∈A ∧ x∈C ⇒ x∈A
(
R ⊨ R1; ld. a szűkítés szabályát⇒
)
x∈A ∧ A⊆B ⇒ x∈B
(
R1, P1 ⊨ R2
)
x∈B ⇒ x∈B ∨ x∈D
(
R2 ⊨ S; ld. a bővítés szabályát⇒
)
x∈A ∧ x∈C = x∈C ∧ x∈A ⇒ x∈C
(
R ⊨ R3; ld. a konjunkció kommutativitását⇒ és a szűkítés szabályát⇒
)
x∈C ∧ C⊆D ⇒ x∈D
(
R3, P2 ⊨ R4
)
x∈D ⇒ x∈D ∨ x∈B = x∈B ∨ x∈D
(
R4 ⊨ S; ld. a diszjunkció kommutativitását⇒ és a bővítés szabályát⇒
)
x∈B ∨ x∈D ⇒ x∈B∪D
(
S ⊨ Q
)
Tehát A∩C⊆B∪D teljesül az adott feltétel mellett (q.e.d.). ( P, P1, P2 ⊨ Q )
(c2) ha A⊆B és C⊆D, akkor A∩C⊆B∩D teljesül
premisszák:
P1 ⇋ A⊆B;
P2 ⇋ C⊆D
a levezetés sémája:
x∈A∩B ⇒ ...
...
... ⇒ x∈B∩D
Tehát ... (q.e.d)
premisszák:
P1 ⇋ A⊆B;
P2 ⇋ C⊆D
x∈A∩C ⇒ x∈A ∧ x∈C
(
P ⊨ R
)
x∈A ∧ x∈C ⇒ x∈A
(
R ⊨ R1; ld. a szűkítés szabályát⇒
)
x∈A ∧ A⊆B ⇒ x∈B
(
R1, P1 ⊨ R2
)
x∈A ∧ x∈C = x∈C ∧ x∈A ⇒ x∈C
(
R ⊨ R3; ld. a konjunkció kommutativitását⇒ és a szűkítés szabályát⇒
)
x∈C ∧ C⊆D ⇒ x∈D
(
R3, P2 ⊨ R4
)
x∈B ∧ x∈D ⇒ x∈B∩D
(
R2, R4 ⊨ Q
)
Tehát A∩C⊆B∩D teljesül az adott feltétel mellett (q.e.d.). ( P, P1, P2 ⊨ Q )
(d1) A∩(B∪C) = (A∩B)∪(A∩C)
a levezetés sémája:
(1) x∈A∩(B∪C) ⇒ ...
...
... ⇒ x∈(A∩B)∪(A∩C)
Tehát ...
(2) x∈(A∩B)∪(A∩C) ⇒ ...
...
... ⇒ x∈A∩(B∪C)
Tehát ...
(3) A∩(B∪C)⊆(A∩B)∪(A∩C) ∧
(A∩B)∪(A∩C)⊆A∩(B∪C) ⇒ ...
Tehát ... (q.e.d)
A bizonyítás három lépésből áll.
(1)
x∈A∩(B∪C) ⇒ x∈A ∧ (x∈B ∨ x∈C)
(
P1 ⊨ U1
)
x∈A ∧ (x∈B ∨ x∈C) ⇒ (x∈A ∧ x∈B) ∨ (x∈A ∧ x∈C)
(
U1 ⊨ V1; ld. disztributivitás⇒
)
(x∈A ∧ x∈B) ∨ (x∈A ∧ x∈C) ⇒ x∈A∩B ∨ x∈A∩C
(
V1 ⊨ W1
)
x∈A∩B ∨ x∈A∩C ⇒ x∈(A∩B)∪(A∩C)
(
W1 ⊨ Q1
)
Tehát A∩(B∪C)⊆(A∩B)∪(A∩C) teljesül.
(2)
x∈(A∩B)∪(A∩C) ⇒ (x∈A ∧ x∈B) ∨ (x∈A ∧ x∈C)
(
P2 ⊨ U2
)
(x∈A ∧ x∈B) ∨ (x∈A ∧ x∈C) ⇒ x∈A ∧ (x∈B ∨ x∈C)
(
U2 ⊨ V2; ld. disztributivitás⇒
)
x∈A ∧ (x∈B ∨ x∈C) ⇒ x∈A ∧ x∈B∪C
(
V2 ⊨ W2
)
x∈A ∧ x∈B∪C ⇒ x∈A∩(B∪C)
(
W2 ⊨ Q2
)
Tehát (A∩B)∪(A∩C)⊆A∩(B∪C) teljesül.
(3)
A∩(B∪C)⊆(A∩B)∪(A∩C) ∧
(A∩B)∪(A∩C)⊆A∩(B∪C) ⇒
A∩(B∪C)=(A∩B)∪(A∩C)
(
Q1, Q2 ⊨ Q;
ld. a részhalmaz reláció antiszimmetriáját⇒
)
Tehát bebizonyítottuk, hogy A∩(B∪C)=(A∩B)∪(A∩C) teljesül (q.e.d.).
(d2) A∪(B∩C) = (A∪B)∩(A∪C)
a levezetés sémája:
(1) x∈A∪(B∩C) ⇒ ...
...
... ⇒ x∈(A∪B)∩(A∪C)
Tehát ...
(2) x∈(A∪B)∩(A∪C) ⇒ ...
...
... ⇒ x∈A∪(B∩C)
Tehát ...
(3) A∪(B∩C)⊆(A∪B)∩(A∪C) ∧
(A∪B)∩(A∪C)⊆A∪(B∩C) ⇒ ...
Tehát ... (q.e.d)
(e1) A∩(A∪B) = A
a levezetés sémája:
(1) x∈A∩(A∪B) ⇒ ...
...
... ⇒ x∈A
Tehát ...
(2) x∈A ... ⇒ ...
...
... ⇒ x∈A∩(A∪B)
Tehát ...
(3) A∩(A∪B)⊆A ∧ A⊆A∩(A∪B) ⇒ ...
Tehát ... (q.e.d)
A bizonyítás három lépésből áll.
(1)
x∈A∩(A∪B) ⇒ x∈A ∧ (x∈A ∨ x∈B)
(
P1 ⊨ V1
)
x∈A ∧ (x∈A ∨ x∈B) ⇒ x∈A
(
V1 ⊨ Q1; ld. a szűkítés szabályát⇒
)
Tehát A∩(A∪B)⊆A teljesül.
(2)
x∈A ⇒ x∈A ∨ x∈B
(
P2 ⊨ V2; ld. a bővítés szabályát⇒
)
x∈A ∧ (x∈A ∨ x∈B) ⇒ x∈A∩(A∪B)
(
P2, V2 ⊨ Q2
)
Tehát A⊆A∩(A∪B) teljesül.
(3)
A∩(A∪B)⊆A ∧
A⊆A∩(A∪B) ⇒ A∩(A∪B)=A
(
Q1, Q2 ⊨ Q;
ld. a részhalmaz reláció antiszimmetriáját⇒
)
Tehát bebizonyítottuk, hogy A∩(A∪B)=A teljesül (q.e.d.).
(e2) A∪(A∩B) = A
a levezetés sémája:
(1) x∈A∪(A∩B) ⇒ ...
...
... ⇒ x∈A
Tehát ...
(2) x∈A ... ⇒ ...
...
... ⇒ x∈A∪(A∩B)
Tehát ...
(3) A∪(A∩B)⊆A ∧ A⊆A∪(A∩B) ⇒ ...
Tehát ... (q.e.d)