Matematika 1 - Gyakorló feladatok


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, ill. törvényeket! (Ha egy 'p' formula "azonosan igaz", vagyis logikai törvény, ezt ⊨ p módon jelöljük.)

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

(h)  p⊃(q⊃p)

(i)  p⊃(q⊃.p∧q)

(j)  p∧(p⊃q)⊃.q

(k)  (p⊃q)∧⌝q⊃.⌝p

[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⊆Bx∈B    ( V1 ⊨ W )
    x∈B ∧ A⊆Bx∈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)


Boda István, 2021.