Probleme date la examenul de logic˘a matematic˘a ¸si computat¸ional˘a. Partea a IX-a Claudia MURES¸AN Universitatea din Bucure¸sti Facultatea de Matematic˘ a ¸si Informatic˘ a Str. Academiei Nr. 14, Sector 1, Cod po¸stal 010014, Bucure¸sti, Romˆ ania Adrese de email:
[email protected],
[email protected]
Abstract Textul de fat¸˘ a cont¸ine probleme date de autoare la examenul aferent cursului de logic˘a matematic˘a ¸si computat¸ional˘ a din anul I de studiu al Facult˘a¸tii de Matematic˘a ¸si Informatic˘a a Universit˘a¸tii din Bucure¸sti.
Vom folosi notat¸ia “ddac˘a“ drept prescurtare pentru sintagma “dac˘a ¸si numai dac˘a“. Amintim abrevierea “i. e.“ (“id est“), semnificˆand “adic˘a“. Pentru not¸iunile ¸si rezultatele teoretice pe care le vom folosi ˆın exercit¸iile urm˘atoare, recomand˘ am consultarea bibliografiei de la sfˆar¸situl acestui text. Oferim ˆın cele ce urmeaz˘a un mic mnemonic de denumiri, notat¸ii ¸si rezultate care ne vor fi necesare pentru rezolvarea acestor exercit¸ii. Amintim denumirile alternative: • poset (de la englezescul partially ordered set) ≡ mult¸ime part¸ial ordonat˘ a; • lant¸ ≡ mult¸ime liniar ordonat˘ a ≡ mult¸ime total ordonat˘ a; • funct¸ie izoton˘ a ≡ funct¸ie care p˘ astreaz˘ a ordinea ≡ funct¸ie cresc˘ atoare; • algebr˘ a Boole ≡ algebr˘ a boolean˘ a. Peste tot ˆın acest referat, vom nota: • pentru orice mult¸ime A, cu card(A) sau card A cardinalul mult¸imii A; • pentru orice mult¸ime A, cu A2 = A × A = {(a, b) | a, b ∈ A} (produsul cartezian, produsul direct de mult¸imi; aici, produsul direct al unei mult¸imi cu ea ˆıns˘a¸si; ˆın general, not˘am cu A1 = A ¸si cu An+1 = An × A = {(a, b) | a ∈ An , b ∈ A}, pentru orice n natural nenul; a se vedea, ˆın materialele din bibliografie, ¸si produsele directe de structuri algebrice); • cu Ln lant¸ul cu n elemente, pentru orice n natural nenul; • laticile sub forma (L, ∨, ∧, ≤), laticile m˘arginite sub forma (L, ∨, ∧, ≤, 0, 1), iar algebrele Boole sub forma (B, ∨, ∧, ≤, ·, 0, 1), cu semnificat¸ia uzual˘a pentru fiecare simbol din aceste notat¸ii; • cu V mult¸imea variabilelor calculului propozit¸ional clasic; • cu E mult¸imea enunt¸urilor calculului propozit¸ional clasic; • cu (E/∼ , ∨, ∧, ≤, ·, 0, 1) algebra Lindenbaum–Tarski a logicii propozit¸ionale clasice, despre care ¸stim c˘a este o algebr˘a Boole; 1
2 • cu ϕˆ ∈ E/∼ clasa unui enunt¸ ϕ ˆın algebra Lindenbaum–Tarski E/∼ ; ˜ : E → L2 unica extindere la E care transform˘a conectorii logici ˆın operat¸ii booleene a unei • cu h interpret˘ari h : V → L2 ; • cu ` ϕ faptul c˘a un enunt¸ ϕ este o teorem˘a formal˘a (adev˘ar sintactic) ˆın logica propozit¸ional˘ a clasic˘a; • cu ϕ faptul c˘a un enunt¸ ϕ este universal adev˘arat (tautologie, adev˘ar semantic) ˆın logica propozit¸ional˘a clasic˘a; • cu Σ ` ϕ faptul c˘a un enunt¸ ϕ ∈ E este deductibil sintactic din ipotezele Σ ⊆ E ˆın logica propozit¸ional˘a clasic˘a; • cu Σ ϕ faptul c˘a un enunt¸ ϕ ∈ E este deductibil semantic din ipotezele Σ ⊆ E ˆın logica propozit¸ional˘a clasic˘a; • cu h ϕ, respectiv h Σ, faptul c˘a o interpretare h : V → L2 satisface un enunt¸ ϕ ∈ E, ˜ ˜ respectiv o mult¸ime de enunt¸uri Σ ⊆ E, i. e. h(ϕ) = 1, respectiv h(σ) = 1 pentru orice σ ∈ Σ. Amintim c˘a: • pentru orice relat¸ie binar˘a R pe o mult¸ime A (adic˘a orice submult¸ime R ⊆ A2 ), se define¸ste inversa lui R ca fiind relat¸ia binar˘a pe A notat˘a cu R−1 ¸si dat˘a de: R−1 = {(b, a) | a, b ∈ A, (a, b) ∈ R} ⊆ A2 = A × A; inversa unei relat¸ii de ordine notate ≤ se noteaz˘a, uzual, cu ≥; • leg˘atura dintre operat¸iile ∨ ¸si ∧ ¸si relat¸ia de ordine ≤ ˆın orice latice (L, ∨, ∧, ≤) este: pentru orice elemente x, y ∈ L, au loc echivalent¸ele: x ≤ y ddac˘a x ∨ y = y ddac˘a x ∧ y = x; • orice lant¸ este o latice distributiv˘a, cu operat¸iile binare ∨ = max ¸si ∧ = min; • ˆın orice algebr˘a Boole (B, ∨, ∧, ≤, ·, 0, 1), pentru orice elemente x, y ∈ B, au loc urm˘atoarele: (i) x = x (idempotent¸a operat¸iei de complementare); (ii) x ∨ y = x ∧ y ¸si x ∧ y = x ∨ y (legile lui de Morgan); (iii) x → y = x ∨ y (definit¸ia implicat¸iei ˆıntr–o algebr˘ a Boole); (iv) x ≤ y ddac˘a x → y = 1; • pentru orice ϕ, ψ ∈ E ¸si orice Σ ⊆ E, are loc echivalent¸a: Σ ` ϕ → ψ ddac˘a Σ ∪ {ϕ} ` ψ (Teorema deduct¸iei pentru calculul propozit¸ional clasic); • pentru orice ϕ ∈ E, are loc echivalent¸a: ` ϕ ddac˘a ϕˆ = 1 (lem˘ a din calculul propozit¸ional clasic); • pentru orice ϕ ∈ E, are loc echivalent¸a: ` ϕ ddac˘a ϕ (Teorema de completitudine a calculului propozit¸ional clasic); • pentru orice ϕ ∈ E ¸si orice Σ ⊆ E, are loc echivalent¸a: Σ ` ϕ ddac˘a Σ ϕ (Teorema de completitudine tare a calculului propozit¸ional clasic).
3
1
Lista 1 de subiecte
Exercit¸iul 1.1. Fie L = (L, ∨, ∧, ≤) o latice nevid˘ a (i. e. cu mult¸imea suport L 6= ∅). Pentru orice a, b ∈ L, definim relat¸iile binare Ra,b ¸si Sa,b pe L, astfel: def.
• Ra,b = {(x, y) | x, y ∈ L, x ∨ a = y ∨ b} ⊆ L2 ; def.
• Sa,b = {(x, y) | x, y ∈ L, x ∧ a = y ∧ b} ⊆ L2 . −1 −1 (i) Demonstrat¸i c˘ a, pentru orice a, b ∈ L, au loc egalit˘ a¸tile: Ra,b = Rb,a ¸si Sa,b = Sb,a .
(ii) Fie a, b ∈ L. S˘ a se demonstreze c˘ a urm˘ atoarele patru afirmat¸ii sunt echivalente: • (1) Ra,b ¸si Sa,b sunt reflexive; • (2) (a, a) ∈ Ra,b ∩ Sa,b ; • (3) (b, b) ∈ Ra,b ∩ Sa,b ; • (4) a = b. ˆ cazul particular ˆın care L este diamantul, cu L = {0, α, β, γ, 1} ¸si diagrama Hasse de mai jos, (iii) In s˘ a se determine Rα,β ¸si Sα,β . 1r αr
@ rβ @rγ
@ @r
0
Rezolvare: (i) Fie a, b ∈ L, arbitrare. Pentru orice x, y ∈ L, au loc echivalent¸ele: (x, y) ∈ Ra,b ddac˘ a −1 −1 x ∨ a = y ∨ b ddac˘a y ∨ b = x ∨ a ddac˘a (y, x) ∈ Rb,a ddac˘a (x, y) ∈ Rb,a . Prin urmare, Ra,b = Rb,a . −1 Analog rezult˘a c˘a Sa,b = Sb,a . (ii) ( Fie a, b ∈ L, arbitrare. Vom demonstra echivalent¸a celor patru condit¸ii ˆın aceast˘a ordine: (1) ⇒ (2) ⇒ (4) ⇒ (1) ¸si (3) ⇒ (4) ⇒ (1). (1) ⇒ (2): Trivial. (1) ⇒ (3): Trivial. (2) ⇒ (4): Ipoteza acestei implicat¸ii este c˘a (a, a) ∈ Ra,b ∩ Sa,b , i. e. (a, a) ∈ Ra,b ¸si (a, a) ∈ Sa,b . (a, a) ∈ Ra,b ˆınseamn˘a c˘a a ∨ a = a ∨ b, adic˘a a = a ∨ b, i. e. b ≤ a. (a, a) ∈ Sa,b ˆınseamn˘ a c˘ a a ∧ a = a ∧ b, adic˘a a = a ∧ b, i. e. a ≤ b. Deci b ≤ a ¸si a ≤ b, a¸sadar a = b. (3) ⇒ (4): Analog cu implicat¸ia anterioar˘a. (4) ⇒ (1): Dac˘a a = b, atunci Ra,b = Ra,a ¸si Sa,b = Sa,a . Orice x ∈ L satisface x ∨ a = x ∨ a, deci (x, x) ∈ Ra,a = Ra,b . Prin urmare, Ra,b este reflexiv˘a. Analog se arat˘a c˘a Sa,b este reflexiv˘a. (iii) Rα,β = {(x, y) | x, y ∈ L, x ∨ α = y ∨ β}. Prin urmare, avem: • ˆıntrucˆat 0 ∨ α = α ∨ α = α, rezult˘a c˘a {y ∈ L | (0, y) ∈ Rα,β } = {y ∈ L | (α, y) ∈ Rα,β } = {y ∈ L | α = y ∨ β} = ∅, pentru c˘a, dac˘a ar exista un element y ∈ L cu α = y ∨ β ≥ β, atunci ar rezulta c˘a β ≤ α, ceea ce nu este adev˘arat;
4 • ˆıntrucˆat β ∨ α = γ ∨ α = 1 ∨ α = 1, rezult˘a c˘a {y ∈ L | (β, y) ∈ Rα,β } = {y ∈ L | (γ, y) ∈ Rα,β } = {y ∈ L | (1, y) ∈ Rα,β } = {y ∈ L | 1 = y ∨ β} = {α, γ, 1}. A¸sadar, Rα,β = {(β, α), (β, γ), (β, 1), (γ, α), (γ, γ), (γ, 1), (1, α), (1, γ), (1, 1)}. Sα,β = {(x, y) | x, y ∈ L, x ∧ α = y ∧ β}. Prin urmare, avem: • ˆıntrucˆat 0 ∧ α = β ∧ α = γ ∧ α = 0, rezult˘a c˘a {y ∈ L | (0, y) ∈ Sα,β } = {y ∈ L | (β, y) ∈ Sα,β } = {y ∈ L | (γ, y) ∈ Sα,β } = {y ∈ L | 0 = y ∧ β} = {0, α, γ}; • ˆıntrucˆat α ∧ α = 1 ∧ α = α, rezult˘a c˘a {y ∈ L | (α, y) ∈ Sα,β } = {y ∈ L | (1, y) ∈ Sα,β } = {y ∈ L | α = y ∧ β} = ∅, pentru c˘a, dac˘a ar exista un element y ∈ L cu α = y ∧ β ≤ β, atunci ar rezulta c˘a α ≤ β, ceea ce nu este adev˘arat. A¸sadar, Sα,β = {(0, 0), (0, α), (0, γ), (β, 0), (β, α), (β, γ), (γ, 0), (γ, α), (γ, γ)}. Exercit¸iul 1.2. Consider˘ am urm˘ atoarele latici m˘ arginite: • cubul, notat cu L32 , cu mult¸imea suport L32 = {0, a, b, c, x, y, z, 1}, • pentagonul, pe care ˆıl vom nota cu P, cu mult¸imea suport P = {0, m, p, s, 1}, • diamantul, pe care ˆıl vom nota cu D, cu mult¸imea suport D = {0, t, u, v, 1}, • lant¸ul cu trei elemente, notat cu L3 , cu mult¸imea suport L3 = {0, α, 1}, cu urm˘ atoarele diagrame Hasse: 1r @ ry @rz @ @ r @r @ r a@ b c @r
1r
xr
mr
@rs
rp @ @r
0
0
L32
P
tr
1r
1r
@ ru @rv
rα
@
@r
r
0
0
D
L3
S˘ a se demonstreze c˘ a nu exist˘ a niciun morfism surjectiv de latici: (i) de la L32 la P; (ii) de la L32 la D; (iii) de la L32 la L3 . Rezolvare: Dup˘a cum ¸stim, cele patru latici enumerate ˆın enunt¸ au urm˘atoarele caracteristici: • cubul este o algebr˘a Boole, adic˘a o latice distributiv˘a m˘arginit˘a complementat˘a; • pentagonul este o latice m˘arginit˘a nedistributiv˘a; • diamantul este o latice m˘arginit˘a nedistributiv˘a; • lant¸ul cu trei elemente este o latice distributiv˘a m˘arginit˘a.
5 Vom folosi aceste caracteristici ale celor patru latici pentru a rezolva exercit¸iul. Pentru ˆınceput, s˘a demonstr˘am o serie de fapte generale. Fie L = (L, ∨, ∧, ≤) ¸si M = (M, ∨, ∧, ≤) dou˘a latici nevide arbitrare. S˘a ar˘at˘am c˘a: • dac˘a laticea L este distributiv˘a ¸si exist˘a un morfism surjectiv de latici h : L → M, atunci ¸si laticea M este distributiv˘a; • dac˘a laticile L ¸si M sunt m˘arginite ¸si exist˘a un morfism surjectiv de latici h : L → M, atunci h este morfism de latici m˘arginite ¸si h duce orice element complementat al lui L ˆıntr–un element complementat al lui M, a¸sadar, dac˘a L este complementat˘a, atunci ¸si M este complementat˘ a. A¸sadar, s˘a presupunem c˘a laticea L este distributiv˘a ¸si exist˘a un morfism surjectiv de latici h : L → M. Fie δ, ε, ϕ ∈ M , arbitrare. h este surjectiv, a¸sadar exist˘a d, e, f ∈ L cu h(d) = δ, h(e) = ε ¸si h(f ) = ϕ. L este o latice distributiv˘a, deci d ∨ (e ∧ f ) = (d ∨ e) ∧ (d ∨ f ). Obt¸inem: δ ∨ (ε ∧ ϕ) = h(d)∨(h(e)∧h(f )) = h(d∨(e∧f )) = h((d∨e)∧(d∨f )) = (h(d)∨h(e))∧(h(d)∨h(f )) = (δ ∨ε)∧(δ ∨ϕ). Echivalent¸a celor dou˘a legi de distributivitate ˆıntr–o latice ne asigur˘a de faptul c˘a M satisface ¸si cealalt˘a lege de distributivitate. A¸sadar, M este o latice distributiv˘a. Acum s˘a presupunem c˘a laticile L ¸si M sunt m˘arginite ¸si exist˘a un morfism surjectiv de latici h : L → M. Folosim notat¸iile obi¸snuite 0 ¸si 1 pentru primul ¸si ultimul element, respectiv, ˆın fiecare dintre laticile L ¸si M. Fie δ ∈ M , arbitrar. Surjectivitatea lui h ne asigur˘a de faptul c˘a exist˘ ad∈L cu h(d) = δ. ˆIn L are loc dubla inegalitate: 0 ≤ d ≤ 1. h : L → M este un morfism de latici ¸si, prin urmare, o funct¸ie izoton˘a ˆıntre poseturile (L, ≤) ¸si (M, ≤), a¸sadar h(0) ≤ h(d) = δ ≤ h(1). Am obt¸inut c˘a, oricare ar fi δ ∈ M , h(0) ≤ δ ≤ h(1). Definit¸ia ¸si unicitatea minimului ¸si maximului ˆıntr–un poset arat˘a c˘a h(0) = 0 ¸si h(1) = 1, deci h este morfism de latici m˘arginite. Acum, fie d ∈ L un elementcomplementat al lui L ¸si e ∈ L un complement al lui d, adic˘a un element al lui L care d ∨ e = 1 satisface: ¸si Atunci, ˆın M avem: d ∧ e = 0. h(d) ∨ h(e) = h(d ∨ e) = h(1) = 1 ¸si h(d) ∧ h(e) = h(d ∧ e) = h(0) = 0, a¸sadar h(e) este un complement al lui h(d), deci h(d) este element complementat al lui M. Dac˘ a laticea m˘arginit˘a L este complementat˘a, adic˘a are toate elementele complementate, iar δ ∈ M , arbitrar, atunci, cum h este surjectiv, rezult˘a c˘a exist˘a d ∈ L cu h(d) = δ, iar d este un element complementat, ca toate elementele lui L, prin urmare δ = h(d) este element complementat al lui M, deci M are toate elementele complementate, adic˘a laticea m˘arginit˘a M este complementat˘a. Dup˘a aceste preparative, s˘a trecem la rezolvarea celor trei puncte ale exercit¸iului. (i) L32 este o latice distributiv˘a, a¸sadar, dac˘a ar exista un morfism surjectiv de latici h : L32 → P, atunci, conform celor de mai sus, ar rezulta c˘a laticea P este distributiv˘a, ceea ce este fals. Prin urmare, nu exist˘a niciun morfism surjectiv de latici h : L32 → P. (ii) Analog cu (i). (iii) L32 este o latice m˘arginit˘a complementat˘a, a¸sadar, dac˘a ar exista un morfism surjectiv de latici h : L32 → L3 , atunci, conform celor de mai sus, ar rezulta c˘a laticea L3 este complementat˘ a, deci elementul α ar fi complementat ˆın L3 . Dar, ˆın L3 , α ∨ 0 = α ∨ α = α 6= 1, deci nici 0, nici α nu sunt complemente ale lui α, iar α ∧ 1 = α 6= 0, deci 1 nu este complement al lui α, prin urmare α nu are complement ˆın L3 , a¸sadar am obt¸inut o contradict¸ie. Deci nu exist˘a niciun morfism surjectiv de latici h : L32 → L3 .
6 O alt˘a variant˘a de rezolvare a punctului (iii) este folosirea observat¸iei c˘a, dac˘a L este o algebr˘ a Boole, i. e. o latice distributiv˘a m˘arginit˘a complementat˘a, iar M este o latice m˘arginit˘a, astfel ˆıncˆ at exist˘a un morfism surjectiv de latici h : L → M, atunci, conform preparativelor de mai sus, rezult˘ a c˘a M este o latice distributiv˘a m˘arginit˘a complementat˘a, i. e. o algebr˘a Boole. A¸sadar, dac˘ a ar exista un morfism surjectiv de latici h : L32 → L3 , atunci ar rezulta c˘a L3 este o algebr˘a Boole, ceea ce este fals, ˆıntrucˆat L3 are exact 3 elemente, deci este o latice finit˘a care nu are cardinalul putere a lui 2 (a se vedea Teorema de structur˘ a a algebrelor Boole finite, caz particular al Teoremei de reprezentare a lui Stone). Exercit¸iul 1.3. Fie α, β, γ, δ ∈ E, astfel ˆıncˆ at: ` (α ∨ β) → (γ ∧ δ) S˘ a se demonstreze c˘ a: ` (α → γ) ∧ (β → δ)
Rezolvarea 1 (sintactic): Folosim faptele cunoscute (a se vedea, de exemplu, [6]) c˘a, pentru orice ϕ, ψ, χ ∈ E: (i) ` ϕ → (ϕ ∨ ψ) (ii) ` ϕ → (ψ ∨ ϕ) (iii) ` (ϕ ∧ ψ) → ϕ (iv) ` (ψ ∧ ϕ) → ϕ ` ϕ (v) ` ϕ ∧ ψ ddac˘a ¸si `ψ (vi) este valabil˘a regula de deduct¸ie:
` ϕ → ψ, ` ψ → χ `ϕ→χ
Din (i), relat¸ia din ipotez˘a ¸si (iii), avem: ` α → (α ∨ β), ` (α ∨ β) → (γ ∧ δ), ` (γ ∧ δ) → γ, de unde, prin dou˘a aplic˘ari ale regulii de deduct¸ie de la (vi), obt¸inem: `α→γ
(a)
Din (ii), relat¸ia din ipotez˘a ¸si (iv), avem: ` β → (α ∨ β), ` (α ∨ β) → (γ ∧ δ), ` (γ ∧ δ) → δ, de unde, prin dou˘a aplic˘ari ale regulii de deduct¸ie de la (vi), obt¸inem:
7 `β→δ
(b)
Din (a), (b) ¸si implicat¸ia reciproc˘a din (v), rezult˘a: ` (α → γ) ∧ (β → δ) ˆ c = γˆ , d = δˆ ∈ E/∼ . Conform ipotezei, Rezolvarea 2 (algebric): Not˘am cu a = α ˆ , b = β, \ ˆ → (ˆ ˆ = 1, i. ` (α ∨ β) → (γ ∧ δ), ceea ce este echivalent cu (α ∨ β) → (γ ∧ δ) = 1, adic˘a (ˆ α ∨ β) γ ∧ δ) e. (a ∨ b) → (c ∧ d) = 1, ceea ce este echivalent cu a ∨ b ≤ c ∧ d. Dar a ≤ a ∨ b, b ≤ a ∨ b, c ∧ d ≤ c ¸si c ∧ d ≤ d. A¸sadar, a, b ≤ a ∨ b ≤ c ∧ d ≤ c, d, de unde, prin tranzitivitate, rezult˘a c˘a a ≤ c ¸si b ≤ d, ceea ˆ = 1, ce este echivalent cu a → c = 1 ¸si b → d = 1, deci (a → c) ∧ (b → d) = 1, adic˘a (ˆ α → γˆ ) ∧ (βˆ → δ) \ i. e. (α → γ) ∧ (β → δ) = 1, ceea ce este echivalent cu ` (α → γ) ∧ (β → δ).
2
Lista 2 de subiecte
Exercit¸iul 2.1. Fie P = (P, ≤) un poset nevid (i. e. cu mult¸imea elementelor P 6= ∅). Definim urm˘ atoarea relat¸ie binar˘ a pe mult¸imea P : R = {(a, b) | a, b ∈ P, card{x ∈ P | a ≤ x sau x ≤ a} = card{x ∈ P | b ≤ x sau x ≤ b}} ⊆ P 2 . Cu alte cuvinte, R este format˘ a din perechile (a, b) de elemente din P cu proprietatea c˘ a mult¸imea elementelor comparabile cu a ˆın posetul P are acela¸si cardinal cu mult¸imea elementelor comparabile cu b ˆın posetul P. S˘ a se demonstreze c˘ a: (i) R este o relat¸ie de echivalent¸˘ a pe mult¸imea P ; (ii) dac˘ a posetul P este m˘ arginit, atunci (min P, max P) ∈ R; (iii) dac˘ a posetul P este lant¸, atunci R = P 2 ; (iv) dac˘ a posetul P este finit ¸si are minim sau maxim, atunci are loc echivalent¸a: R = P 2 ddac˘ aP este lant¸; (v) dac˘ a posetul P este infinit sau nu are nici minim, nici maxim, atunci nu are neap˘ arat loc 2 echivalent¸a de la punctul (iv), adic˘ a: egalitatea R = P nu este neap˘ arat echivalent˘ a cu condit¸ia ca posetul P s˘ a fie lant¸. Rezolvare: Introducem urm˘atoarea notat¸ie, care va fi util˘a pentru redactarea solut¸iei acestui exercit¸iu: pentru orice a ∈ P , fie hai mult¸imea elementelor lui P care sunt comparabile cu a ˆın posetul P, i. e. hai = {x ∈ P | a ≤ x sau x ≤ a} ⊆ P . Cu aceast˘a notat¸ie, putem scrie definit¸ia lui R ˆın felul urm˘ator: R = {(a, b) | a, b ∈ P, cardhai = cardhbi}. Altfel spus, pentru orice a, b ∈ P , are loc echivalent¸a: (a, b) ∈ R ddac˘a cardhai = cardhbi. Este trivial faptul c˘a, dac˘a dou˘a elemente a, b ∈ P au proprietatea c˘a hai = hbi, atunci (a, b) ∈ R (nu ¸si reciproc). (i) Pentru orice a ∈ P , hai = hai, a¸sadar (a, a) ∈ R, deci R este reflexiv˘a. Pentru orice a, b ∈ P , au loc echivalent¸ele: (a, b) ∈ R ddac˘a cardhai = cardhbi ddac˘a cardhbi = cardhai ddac˘a (b, a) ∈ R. Prin urmare, relat¸ia R este simetric˘a. Pentru orice a, b, c ∈ P , dac˘a (a, b) ∈ R ¸si (b, c) ∈ R, atunci cardhai = cardhbi ¸si cardhbi = cardhci, a¸sadar cardhai = cardhci, adic˘a (a, c) ∈ R. Deci R este tranzitiv˘a. Prin urmare, R este o relat¸ie de echivalent¸˘a pe mult¸imea P . (ii) Presupunem c˘a posetul P este m˘arginit, i. e. are minim ¸si maxim. Minimul ¸si maximul unui poset (m˘arginit) sunt comparabile cu toate elementele posetului, deci hmin Pi = P = hmax Pi, prin urmare (min P, max P) ∈ R.
8 (iii) Dac˘a P este lant¸, atunci elementele sale sunt dou˘a cˆate dou˘a comparabile, prin urmare, oricare ar fi x, y ∈ P , hxi = P = hyi, a¸sadar (x, y) ∈ R, deci R = P 2 . (iv) Consider˘am posetul P ca fiind finit (i. e. cu mult¸imea suport P finit˘a) ¸si avˆand minim. Fie n = card(P ) ∈ N∗ (ˆıntrucˆat P este finit˘a ¸si nevid˘a). Cum hmin Pi = P , rezult˘a c˘a are loc: cardhmin Pi = card(P ) = n. “⇒:“ Dac˘a R = P 2 , atunci, ˆın particular, oricare ar fi x ∈ P , are loc (min P, x) ∈ R, i. e. cardhxi = cardhmin Pi = card(P ) = n. Deci, pentru orice x ∈ P , mult¸imile finite hxi ¸si P au propriet˘ a¸tile: hxi ⊆ P ¸si cardhxi = card(P ) = n. Rezult˘a c˘a hxi = P , pentru orice x ∈ P , adic˘a orice element x ∈ P este comparabil cu orice element al lui P , cu alte cuvinte toate elementele lui P sunt dou˘a cˆ ate dou˘ a comparabile, adic˘a P este lant¸. “⇐:“ Aceast˘a implicat¸ie rezult˘a din punctul (iii). Demonstrat¸ia decurge analog ˆın cazul ˆın care posetul P este finit ¸si are maxim. (v) Implicat¸ia reciproc˘a de la punctul (iv) este valabil˘a ˆıntotdeauna, conform punctului (iii). Prin urmare, avem de demonstrat c˘a, ˆın absent¸a oric˘areia dintre condit¸iile de la (iv), implicat¸ia direct˘ a nu are loc. Altfel spus, avem de demonstrat c˘a exist˘a poseturi P = (P, ≤) care nu sunt lant¸uri, dar ˆın care relat¸ia R definit˘a ca ˆın enunt¸ satisface R = P 2 . Vom demonstra acest lucru prin exemple, pe care le vom c˘auta printre poseturile infinite, precum ¸si printre acelea care nu au nici minim, nici maxim, ˆıntrucˆat punctul (iv) ne asigur˘a de faptul c˘a putem elimina celelalte cazuri. Pentru ˆınceput, vom da un exemplu de poset infinit P = (P, ≤) care nu este lant¸, dar ˆın care R = P 2 . Mai mult, acest poset este infinit ¸si m˘arginit. S˘a consider˘am posetul N = (N, | ): mult¸imea numerelor naturale, ˆınzestrat˘a cu divizibilitatea, mai precis relat¸ia de ordine part¸ial˘a “divide pe“. Acest poset este m˘arginit: min N = 1 ¸si max N = 0, pentru c˘a, oricare ar fi x ∈ N, 1 | x | 0. S ¸ i, desigur, acest poset este infinit: card(N) = ℵ0 (cardinalul mult¸imilor num˘arabile). 1 ¸si 0 sunt minimul ¸si, respectiv, maximul lui N , deci, ˆın N , h1i = h0i = N, a¸sadar cardh1i = cardh0i = card(N) = ℵ0 . Pentru orice x ∈ N\{0, 1} ¸si orice n ∈ N∗ = N\{0}, x | xn , iar xn 6= xk , oricare ar fi k ∈ N\{n}, a¸sadar {xn | n ∈ N∗ } ⊆ hxi ⊆ N, iar card{xn | n ∈ N∗ } = card{n | n ∈ N∗ } = card(N∗ ) = card(N) = ℵ0 , deci ℵ0 ≤ cardhxi ≤ ℵ0 , a¸sadar cardhxi = ℵ0 = cardh1i = cardh0i. Prin urmare, oricare ar fi x, y ∈ N, cardhxi = ℵ0 = cardhyi, deci (x, y) ∈ R, a¸sadar R = N2 . Desigur, N nu este lant¸, pentru c˘ a, de exemplu, 2 nu divide pe 5 ¸si 5 nu divide pe 2. Acum vom da mai multe exemple de poseturi P = (P, ≤) care nu au nici minim, nici maxim, ¸si nu sunt lant¸uri, dar ˆın care relat¸ia binar˘a corespunz˘atoare R = P 2 , adic˘a, pentru orice x, y ∈ P , cardhxi = cardhyi. Mai mult, aceste poseturi sunt finite ¸si nu au nici minim, nici maxim. Le vom da prin reprezentarea diagramelor lor Hasse:
r r r r r
P1 = (P1 , ≤)
r
r
r
r
P2 = (P2 , ≤)
r r A@ A@r A Ar
P3 = (P3 , ≤)
r @ @r
r
r
r @ @r
P4 = (P4 , ≤)
Posetul P1 este un antilant¸, adic˘a oricare dou˘a elemente diferite ale sale sunt incomparabile, a¸sadar, pentru orice x ∈ P1 , cardhxi = 1 (fiecare element al acestui poset este comparabil numai cu el ˆınsu¸si). ˆIn posetul P2 , orice x ∈ P2 are cardhxi = 2 (fiecare element al acestui poset este comparabil doar cu el ˆınsu¸si ¸si cu ˆınc˘a un element). ˆIn P3 , orice x ∈ P3 are cardhxi = 3. ˆIn P4 , orice x ∈ P4 are cardhxi = 3. Exercit¸iul 2.2. Consider˘ am urm˘ atoarele latici m˘ arginite:
9 • cubul, notat cu L32 , cu mult¸imea suport L32 = {0, a, b, c, x, y, z, 1}, • pentagonul, pe care ˆıl vom nota cu P, cu mult¸imea suport P = {0, m, p, s, 1}, cu diagramele Hasse de mai jos, ¸si fie f : L32 → P un morfism de latici m˘ arginite. 1r @ ry @rz @ @ r @r @r a@ b c @r
xr
1r f -
mr
@rs
rp @ @r
0
0
L32
P
S˘ a se demonstreze c˘ a: (i) dac˘ a p ∈ Im(f ), atunci s ∈ / Im(f ); (ii) dac˘ a s ∈ Im(f ), atunci p ∈ / Im(f ). Rezolvare: Vom ˆıncepe prin a demonstra unele fapte teoretice. Cu toate c˘a acestea sunt, ˆın general, cunoscute, ¸si c˘a rat¸ionamentele necesare pentru a le demonstra sunt similare celor pe care le–am aplicat ˆın rezolvarea Exercit¸iului 1.2, vom expune aici aceste rat¸ionamente, pentru completitudine. Primul rezultat teoretic pe care ˆıl vom folosi ˆın cele ce urmeaz˘a este faptul c˘a imaginea oric˘ arui morfism de latici m˘arginite este o sublatice m˘arginit˘a a codomeniului acelui morfism. S˘a demonstr˘ am, 3 a¸sadar, c˘a imaginea lui f (Im(f ) = f (L2 )) este o sublatice m˘arginit˘a a codomeniului lui f (P). Im(f ) ⊆ P . Cum L32 6= ∅, rezult˘a c˘a Im(f ) = f (L32 ) 6= ∅. Fie δ, ε ∈ Im(f ). Atunci exist˘a d, e ∈ L32 , astfel ˆıncˆat f (d) = δ ¸si f (e) = ε. Rezult˘a c˘a δ ∨ ε = f (d) ∨ f (e) = f (d ∨ e) ∈ Im(f ) ¸si δ ∧ ε = f (d) ∧ f (e) = f (d ∧ e) ∈ Im(f ), a¸sadar Im(f ) este ˆınchis˘ a la operat¸iile de latice (∨ ¸si ∧), deci Im(f ) este o sublatice a lui P. 1 = f (1) ∈ Im(f ) ¸si 0 = f (0) ∈ Im(f ). Prin urmare, Im(f ) este ˆınchis˘a la operat¸iile de latice m˘arginit˘a (∨, ∧, 0 ¸si 1), deci Im(f ) este o sublatice m˘arginit˘a a lui P. Al doilea rezultat de care vom avea nevoie este faptul c˘a imaginea unei latici distributive printr–un morfism de latici este o latice distributiv˘a. S˘a demonstr˘am, a¸sadar, c˘a Im(f ) este o latice distributiv˘ a. 3 Fie δ, ε, τ ∈ Im(f ), a¸sadar exist˘a d, e, t ∈ L2 astfel ˆıncˆat f (d) = δ, f (e) = ε ¸si f (t) = τ . Folosind faptul c˘a L32 este o latice distributiv˘a, obt¸inem: (δ ∨ ε) ∧ τ = (f (d) ∨ f (e)) ∧ f (t) = f (d ∨ e) ∧ f (t) = f ((d ∨ e) ∧ t) = f ((d ∧ t) ∨ (e ∧ t)) = f (d ∧ t) ∨ f (e ∧ t) = (f (d) ∧ f (t)) ∨ (f (e) ∧ f (t)) = (δ ∧ τ ) ∨ (ε ∧ τ ). Prin urmare, laticea Im(f ) satisface una dintre legile de distributivitate, ¸si, deci, pe amˆandou˘a, a¸sadar Im(f ) este o latice distributiv˘a. Am obt¸inut c˘a Im(f ) este o latice distributiv˘a m˘arginit˘a (ca fapt general, imaginea unei latici distributive m˘arginite printr–un morfism de latici m˘arginite este o latice distributiv˘a m˘arginit˘ a). Un alt rezultat necesar pentru a rezolva acest exercit¸iu spune c˘a imaginea printr–un morfism de latici m˘arginite a complementului unui element al domeniului morfismului este un complement al imaginii acelui element ˆın codomeniul morfismului, precum ¸si ˆın imaginea morfismului. Fie, a¸sadar, d, e ∈ L32 astfel ˆıncˆat e este complement al lui d ˆın L32 ; s˘a demonstr˘am c˘a f (e) este complement al lui f (d) ˆın P ¸si ˆın Im(f ). Conform definit¸iei unui complement, avem: d ∨ e = 1 ¸si d ∧ e = 0. Rezult˘a c˘a f (d) ∨ f (e) = f (d ∨ e) = f (1) = 1 ¸si f (d) ∧ f (e) = f (d ∧ e) = f (0) = 0, deci f (e)
10 este complement al lui f (d) ˆın P, dar ¸si ˆın Im(f ), pentru c˘a tot¸i termenii din P care apar ˆın aceste relat¸ii apart¸in sublaticii m˘arginite Im(f ) a lui P. S¸i acum s˘a demonstr˘am c˘a nu putem avea p, s ∈ Im(f ). Presupunem prin absurd c˘a p, s ∈ Im(f ), adic˘a exist˘a u, v ∈ L32 astfel ˆıncˆat f (u) = p ¸si f (v) = s. u ¸si v sunt elemente ale laticii m˘arginite complementate L32 , deci au complemente ˆın L32 . Fie u, v ∈ L32 , astfel ˆıncˆat u este complement al lui u ˆın L32 ¸si v este complement al lui v ˆın L32 . Atunci f (u) este complement al lui f (u) = p ˆın P ¸si ˆın Im(f ) ¸si f (v) este complement al lui f (v) = s ˆın P ¸si ˆın Im(f ). Dar singurul complement al lui p ˆın P este m, ¸si tot m este singurul complement al lui s ˆın P. Rezult˘ a c˘a m = f (u) = f (v) ∈ Im(f ). Prin urmare, m ∈ Im(f ) are doi complement¸i distinct¸i, anume p ¸si s, ˆın P ¸si ˆın Im(f ). Dar Im(f ) este o latice distributiv˘a m˘arginit˘a, deci satisface proprietatea de unicitate a complementului, conform unui rezultat teoretic binecunoscut: orice element al lui Im(f ) are cel mult un complement ˆın laticea distributiv˘a m˘arginit˘a Im(f ). Am obt¸inut o contradict¸ie; a¸sadar nu putem avea simultan p ∈ Im(f ) ¸si s ∈ Im(f ). (i) Conform celor de mai sus, dac˘a p ∈ Im(f ), atunci s ∈ / Im(f ). (ii) Similar, dac˘a s ∈ Im(f ), atunci p ∈ / Im(f ). Ca o observat¸ie suplimentar˘a, ˆıntrucˆat L32 este o algebr˘a Boole, adic˘a o latice distributiv˘a m˘ arginit˘ a complementat˘a, iar f este un morfism de latici m˘arginite, rezult˘a c˘a ¸si Im(f ) este o latice distributiv˘ a m˘arginit˘a complementat˘a, adic˘a o algebr˘a Boole (a se revedea rat¸ionamentul anterior, precum ¸si rezolvarea Exercit¸iului 1.2). ˆIn plus, elementele lui P 0, 1 ∈ Im(f ). Dac˘a am avea p, s ∈ Im(f ), atunci ¸si complementul acestor elemente din P, anume m, ar satisface m ∈ Im(f ) (ca mai sus). Deci am avea ˆıntregul P ⊆ Im(f ) ⊆ P , adic˘a P = Im(f ). Iar aici am putea argumenta c˘a, atunci, card(Im(f )) = card(P ) = 5, iar 5 nu este o putere natural˘a a lui 2, deci am obt¸ine o contradict¸ie cu faptul c˘a Im(f ) este o algebr˘a Boole (a se vedea Teorema de structur˘ a a algebrelor Boole finite). Sau am putea observa c˘a Im(f ), ca latice m˘arginit˘a, ar fi exact P (ca mai sus), iar P nu este o algebr˘a Boole, deci, iar˘a¸si, am avea o contradict¸ie. Acestea sunt alte dou˘a moduri ˆın care am putea ˆıncheia rezolvarea exercit¸iului. Exercit¸iul 2.3. Fie α, β, γ ∈ E, arbitrare. S˘ a se demonstreze c˘ a: ` α → (β → ¬ γ)
ddac˘ a
{γ} ` ¬ (α ∧ β).
Rezolvarea 1 (part¸ial sintactic, part¸ial algebric): Conform Teoremei deduct¸iei, {γ} ` ¬ (α ∧ β) ddac˘a ` γ → ¬ (α ∧ β). ˆ c = γˆ ∈ E/∼ . Au loc echivalent¸ele: ` γ → ¬ (α ∧ β) ddac˘a γ → \ Fie a = α ˆ , b = β, ¬ (α ∧ β) = 1 ˆ = 1 ddac˘a c → (a ∧ b) = 1 ddac˘a c∨(a ∧ b) = 1 ddac˘a c∨a∨b = 1 ddac˘a a∨b∨c = 1 ddac˘a γˆ → (ˆ α ∧ β) ddac˘a a → (b ∨ c) = 1 ddac˘a a → (b → c) = 1 ddac˘a α ˆ → (βˆ → γˆ ) = 1 ddac˘a α ˆ → (βˆ → ¬cγ) = 1 ddac˘a α → \ (β → ¬ γ) = 1 ddac˘a ` α → (β → ¬ γ). Am folosit definit¸ia implicat¸iei ˆıntr–o algebr˘ a Boole, legile lui de Morgan ¸si comutativitatea operat¸iei ∨ ˆıntr–o latice. Am obt¸inut echivalent¸a din enunt¸. Rezolvarea 2 (semantic): Conform Teoremei de completitudine tare a calculului propozit¸ional clasic, au loc urm˘atoarele echivalent¸e: ` α → (β → ¬ γ) ddac˘a α → (β → ¬ γ) ¸si {γ} ` ¬ (α ∧ β) ddac˘a {γ} ¬ (α ∧ β). Vom demonstra, prin dubl˘a implicat¸ie, echivalent¸a: α → (β → ¬ γ)
ddac˘a
{γ} ¬ (α ∧ β).
11 S¸i aici vom folosi definit¸ia implicat¸iei ˆıntr–o algebr˘a Boole, legile lui de Morgan ¸si comutativitatea operat¸iei ∨ ˆıntr–o latice, dar ¸si idempotent¸a complement˘arii. De data aceasta, algebra Boole ˆın care vom lucra va fi L2 (algebra Boole standard, cu mult¸imea suport {0, 1}). “⇒:“ Presupunem c˘a α → (β → ¬ γ). ˜ ˜ Fie h : V → L2 astfel ˆıncˆat h γ, i. e. h(γ) = 1. Cum α → (β → ¬ γ), are loc: h(α → ˜ ˜ ˜ ˜ ˜ (β → ¬ γ)) = 1, i. e. h(α) → (h(β) → h(γ)) = 1, prin urmare h(α) → (h(β) → 1) = 1, deci ˜ ˜ ˜ ˜ ˜ ˜ ˜ ˜ ∨ 0) = 1, i. e. h(α) → h(β) = 1, deci h(α) ∨ h(β) = 1, h(α) → (h(β) → 0) = 1, adic˘a h(α) → (h(β) ˜ ˜ ˜ (α ∧ β)) = 1, a¸sadar h ¬ (α ∧ β). a¸sadar h(α) ∧ h(β) = 1, i. e. h(¬ Prin urmare, {γ} ¬ (α ∧ β). “⇐:“ Presupunem c˘a {γ} ¬ (α ∧ β). Fie h : V → L2 o interpretare arbitrar˘a. ˜ ˜ γ) = h(γ) ˜ ˜ → ¬ γ) = h(β) ˜ ˜ γ) = h(β) ˜ Dac˘a h(γ) = 0, atunci h(¬ = 0 = 1, prin urmare h(β → h(¬ → ˜ ˜ ˜ ˜ 1 = 1, a¸sadar h(α → (β → ¬ γ)) = h(α) → h(β → ¬ γ)) = h(α) → 1 = 1. ˜ ˜ (α ∧ β)) = 1, Dac˘a h(γ) = 1, atunci h γ, a¸sadar, ˆıntrucˆat {γ} ¬ (α ∧ β), rezult˘a c˘a h(¬ ˜ ∧ β) = 1, deci h(α ˜ ∧ β) = h(α ˜ ∧ β) = 1 = 0, prin urmare h(α) ˜ ˜ adic˘a h(α ∧ h(β) = 0, a¸sadar ˜ ˜ ˜ ˜ ˜ h(α) = 0 sau h(β) = 0, deoarece h(α) ¸si h(β) sunt elemente ale lui L2 . Dac˘a h(α) = 0, atunci ˜ ˜ ˜ ˜ ˜ h(α → (β → ¬ γ)) = h(α) → h(β → ¬ γ) = 0 → h(β → ¬ γ) = 1. Dac˘a h(β) = 0, atunci ˜ → ¬ γ) = h(β) ˜ ˜ γ) = 0 → h(¬ ˜ γ) = 1, prin urmare h(α ˜ → (β → ¬ γ)) = h(α) ˜ ˜ → h(β → h(¬ → h(β ˜ ¬ γ) = h(α) → 1 = 1. ˜ → (β → ¬ γ)) = 1. A¸sadar, α → (β → ¬ γ). ˆIn fiecare caz posibil obt¸inem h(α Am obt¸inut echivalent¸a din enunt¸.
Bibliografie [1] S. Burris, H. P. Sankappanavar, A Course in Universal Algebra, The Millenium Edition, disponibil˘a online. [2] D. Bu¸sneag, D. Piciu, Lect¸ii de algebr˘ a, Editura Universitaria Craiova, 2002. [3] D. Bu¸sneag, D. Piciu, Probleme de logic˘ a ¸si teoria mult¸imilor, Craiova, 2003. [4] V. E. C˘az˘anescu, Curs de bazele informaticii, Tipografia Universit˘a¸tii din Bucure¸sti, 1974, 1975, 1976. [5] G. Georgescu, Elemente de logic˘ a matematic˘ a, Academia Militar˘a, Bucure¸sti, 1978. [6] G. Georgescu, A. Iorgulescu, Logic˘ a matematic˘ a, Editura ASE, Bucure¸sti, 2010. [7] K. Kuratowski, Introducere ˆın teoria mult¸imilor ¸si ˆın topologie, traducere din limba polonez˘ a, Editura Tehnic˘a, Bucure¸sti, 1969. [8] S. Rudeanu, Curs de bazele informaticii, Tipografia Universit˘a¸tii din Bucure¸sti, 1982. [9] A. Scorpan, Introducere ˆın teoria axiomatic˘ a a mult¸imilor, Editura Universit˘a¸tii din Bucure¸sti, 1996. [10] Articolele cu probleme date la examenul de logic˘a matematic˘a ¸si computat¸ional˘a, precum ¸si celelalte articole din Revista de logic˘ a, publicat¸ie online, ˆın care se afl˘a ¸si articolul de fat¸˘ a. [11] Cursurile de logic˘a matematic˘a ¸si computat¸ional˘a de pe site–ul Facult˘a¸tii de Matematic˘ a ¸si Informatic˘a a Universit˘a¸tii din Bucure¸sti (pe serverul de cursuri: moodle).
