Logica Computationala Curs Partea I

8/20/2019 Logica Computationala Curs Partea I

1/40

1 Sintaxa limbajului

Vocabularul limbajului este V ∪ L ∪ S, unde

2 Sintaxa limbajului

Vocabularul limbajului este V ∪ L ∪ S, unde

V este mulţimea propoziţiilor elementare; V = ∅. Convenim să notămsimbolurile din mulţimea V prin literele alfabetului latin;

L = {∧, ∨, →, ↔,} este mulţimea conectivelor logice: conjuncţie,disjuncţie,implicaţie, echivalenţă şi negaţie;

S = {(, )} este mulţimea simbolurilor de punctuaţie.

Presupunem ı̂ndeplinite condiţiile V ∩ L = ∅, V ∩ S = ∅.Convenim să numim asamblaje elementele mulţimii A = (V ∪ L ∪ S )∗.

Pentru α ∈ A şi x ∈ V ∪ L ∪ S indicăm prin α x faptul că simbolul xapare cel puţin o dată printre simbolurile asamblajului α respectiv prin α xsituaţia contrară.

Structurile simbolice de interes ı̂n calculul cu propoziţii sunt formulele

logice; mulţimea formulelor notată FORM ; FORM ⊂ A este definită degramatica independentă de context G = (N , T , ), unde:

N = {formula , propozitie , conectiva} este mulţimea neterminalelor,T = V ∪ L ∪ S este mulţimea terminalelor şi este mulţimea regulilor derescriere:

=

formula → propozitie | ( formula) |(formula conectiva formula) ,

propozitie → a | b | ...,conectiva → ∧ | ∨ |→|↔

Mulţimea formulelor este limbajul generat de gramatica G pentru simbolulde start formula ; FORM = L (formula) . Convenim să reprezentămformulele prin litere din alfabetul grec.

Exemplul 1.1.1. Fie asamblajul α = (( ((a) ∨ b)) ↔ (a ∧ (b))). Con-siderăm următoarea schemă de derivare ; simbolul neterminal căruia este

1


2/40

aplicată regula de rescriere este subliniat:

formula ⇒

formula conectiva formula

⇒formula ↔ formula

⇒

( formula) ↔ formula

⇒( formula) ↔


⇒

( formula) ↔

aconectiva formula

⇒( formula) ↔

a ∧ formula

⇒

( formula) ↔

a ∧

formula

⇒

formula

↔ (a ∧ (b))

⇒


↔ (a ∧ (b))

⇒

formula ∨ formula

↔ (a ∧ (b))

⇒

formula ∨ b

↔ (a ∧ (b))

⇒

formula

∨ b

↔ (a ∧ (b))

⇒

(( ((a) ∨ b)) ↔ (a ∧ (b))) = α

deci α ∈ F ORM.O modalitate similar̆a pentru descrierea regulilor de bună formare pentru

structurile simbolice din sortul FORM este bazată pe noţiunea de SGF (S ecvenţă Generativă F ormule).

Definit ̧ia 1.1.1. Secvenţa de asamblaje α1, α2,...,αn este SGF , dacă pen-tru orice i, 1 ≤ i ≤ n, este ı̂ndeplinită una dintre condiţiile:

ι) αi ∈ V ,

ιι) există j, 1 ≤ j < i, astfel ı̂ncât, αi = (α j) ,

ιιι) există j, k, 1 ≤ j, k < i şi există ρ ∈ L \ {} , astfel ı̂ncât

αi = (α jραk) .

Observat ̧ie Fie α asamblaj. Atunci, există n ≥ 1 şiα1, α2,...,αn - SGF, astfel ı̂ncât, αn = α dacă şi numai dacă α ∈ FORM.Exemplul 1.1.2. Pentru formula α = (( ((a) ∨ b)) ↔ (a ∧ (b))), putem

construi următorul SGF :

a,b, (a) , (b) , (a ∧ (b)) , ((a) ∨ b) , ( ((a) ∨ b)) ,(( ((a) ∨ b)) ↔ (a ∧ (b))) = α.

Observat ̧ii

2


3/40

1. Dacă α ∈ V , atunci secvenţa α este SGF , deci V ⊂ F ORM.

2. Dacă α1, α2,...,αn este SGF , atunci pentru orice i, 1 ≤ i ≤ n, α1, α2,...,αieste SGF . Cu alte cuvinte, toate componentele unui SGF sunt for-mule.

3. Dacă α1,...,αn şi β 1, ....,β m sunt SGF, atunci α1,...,αn, β 1, ...., β m estede asemenea SGF

4. Parantezarea rezultată pentru structurile simbolice dinFORM \ V permite identificarea conectivei principale corespunzătoarefiecărei formule care nu este propoziţie elementară. Într-adevăr, orice

α ∈ FORM \ V este de unul şi numai de unul din tipurile: α = (β )sau α = (βργ ) cu ρ ∈ L \ {} . Dacă α = (β ) , atunci conectiva prin-cipală a formulei α este “” şi respectiv dacă α = (βργ ) , atunci α areconectiva principală “ρ”.

Reprezentarea neparantezată a structurilor simbolice din sortulFORM poate fi obţinută pe baza arborilor de structură.

Definit ̧ia 1.1.2. Arborele T , binar, direcţionat, cu rădăcină având vârfurileetichetate cu simboluri din mulţimea V ∪ L este arbore de structură dacăetichetele vârfurilor sunt astfel ı̂ncât pentru orice vârf n ∈ V (T ) ,

ι) dacă od (n) = 0, atunci ϕ (n) ∈ V

ιι) dacă od (n) = 1,atunci ϕ (n) =

ιιι) dacă od (n) = 2, atunci ϕ (n) ∈ L \ {}

unde ϕ (n) este eticheta vârfului n.Spunem că T este arbore de structură pentru ϕ (r) unde r este vârful

rădăcină.Fiecare formulă α poate fi reprezentată printr-un arbore de structură

T (α). Construcţia arborelui T (α) poate fi realizată recursiv utilizând observaţia4 astfel:

ι) dacă α ∈ V , atunci T (α) : r si ϕ (r) = α;

ιι) dacă α = (β ) , atunci

T (α) :r

↓T (β )

unde ϕ (r) = şi T (β ) este arborele de structură al formulei β ;

3


4/40

ιιι) dacă α = (βργ ) cu ρ ∈ L \ {} , atunci

T (α) :r

T (β ) T (γ )

,

unde ϕ (r) = ρ şi T (β ) , T (γ ) sunt arborii de structură corespunzătoriformulelor β respectiv γ.

Exemplul 1.1.3. Fie α = (( ((a) ∨ b)) ↔ (a ∧ (b))) .Deoarece α = (βργ ) cu ρ =↔, β = ( ((a) ∨ b)) şi γ = (a ∧ (b))

obţinem

T (α) :r

T (β ) T (γ )

unde ϕ (r) = ↔Deoarece β = (β 1) , unde β 1 = ((a) ∨ b) ,obţinem

T (β ) :n1↓

T (β 1), ϕ (n1) = .

Repetând aceleaşi argumente, obţinem,

T (β 1) :n2

T (β 2) T (β 3)

, ϕ (n2) = ∨, β 2 = (a) , β 3 = b

T (β 2) :n3↓

T (β 4), ϕ (n3) = , T (β 4) : n4, ϕ (n4) = a,

T (β 3) : n5, ϕ (n5) = b,

T (γ ) :n6

T (γ 1) T (γ 2)

, ϕ (n6) = ∧, γ 1 = a, γ 2 = (b)

T (γ 1) : n7, ϕ (n7) = a,

T (γ 2) :n8↓

T (γ 3), ϕ (n8) = , T (γ 3) : n9, ϕ (n9) = b

4


5/40

Obţinem ı̂n final

T (α) :

r (↔)

n1 () n6 (∧)↓

n2 (∨) n7 (a) n8 () ↓

n3 () n5 (b) n9 (b)↓

n4 (a)

Pentru o structură simbolică α din sortul FORM, reprezentarea prin ar-borele de structură T (α) este unic determinată şi permite obţinerea unorreprezentări neambigui şi neparantezate pentru formulele limbajului calcul-ului cu propoziţii şi anume reprezentarea polonez ̆a prefixată şi reprezentarea

polonez ̆a prefixată introduse de către logicianul de origine poloneză J.Lukasiewicz.Reprezentarea conform regulilor de bună formare definite prin intermediulSGF este numită reprezentare infixată.

Definit ̧ia 1.1.3. Fie gramatica independentă de contextG pref ix = (N , T , ), undeN = {formula , propozitie , conectiva}

este mulţimea neterminalelor, T = V ∪ L este mulţimea terminalelor şi este mulţimea regulilor de rescriere:

=

formula → propozitie | formula |conectiva formula formula ,


Mulţimea reprezentărilor ı̂n scrierea polonez ̆a prefixată a formulelor estelimbajul generat de gramatica G pref ix pentru simbolul de start formula ;FORM pref ix = L (formula) .

Exemplul 1.1.4. Fie ı̂n G prefix următoarea schemă de derivare, simbolulneterminal căruia este aplicată regula de rescriere fiind subliniat:

formula ⇒ conectiva formula formula ⇒

5


6/40

⇒ ↔ formula formula ⇒↔ formula formula

⇒ ↔ formula conectiva formula formula

⇒ ↔ formula conectivaa formula

⇒ ↔ formula ∧ aformula

⇒ ↔ formula ∧ aformula ⇒↔ formula ∧ ab

⇒ ↔ conectiva formula formula ∧ ab

⇒ ↔ ∨ formula formula ∧ ab

⇒ ↔ ∨ formulab ∧ ab ⇒↔ ∨ formulab ∧ ab

⇒ ↔ ∨ ab ∧ ab = α pref ix ,

deci α pref ix ∈ FORM pref ix.Structura simbolică α pref ix reprezentarea polonez ̆a prefixată a formulei

α = (( ((a) ∨ b)) ↔ (a ∧ (b))) .Definit ̧ia 1.1.4 Fie gramatica independentă de contextG postfix = (N , T , ), undeN = {formula , propozitie , conectiva}este mulţimea neterminalelor, T = V ∪ L este mulţimea terminalelor şi

este mulţimea regulilor de rescriere:

=

formula → propozitie | formula |formula formula conectiva ,


Mulţimea reprezentărilor ı̂n scrierea polonez ̆a postfixată a formulelor este

limbajul generat de gramatica G postfix pentru simbolul de start formula ;FORM postfix = L (formula) .

Exemplul 1.1.5. Fie ı̂n G postfix următoarea schemă de derivare, simbolulneterminal căruia este aplicată regula de rescriere fiind subliniat:

formula ⇒ formula formula conectiva

⇒ formula formula ↔⇒ formula formula ↔⇒ formulaformula formula conectiva ↔

⇒ formulaa formula conectiva ↔

⇒ formulaaformula∧ ↔

⇒ formulaaformula∧ ↔⇒ formulaab∧ ↔

⇒ formula formula conectivaab∧ ↔

⇒ formula formula ∨ ab∧ ↔⇒ formulab ∨ ab∧ ↔

⇒ formulab ∨ ab∧ ↔⇒ ab ∨ ab∧ ↔= α postfix,

6


7/40

deci α postfix ∈ FORM postfix.

Structura simbolică α postfix reprezentarea polonez ̆a postfixată a formuleiα = (( ((a) ∨ b)) ↔ (a ∧ (b))) .

Reprezentarea polonez ̆a prefixată a unei formule α ∈ FORM este secvenţade etichete corespunzătoare vârfurilor rezultate prin traversarea r-s-d (rădăcină-subarbore stâng- subarbore drept), respectivreprezentarea polonez ̆a postfixata rezultă prin traversarea s-d-r (subarborestâng- subarbore drept- rădăcină) a arborelui de structură T (α) .

Exemplul 1.1.6. Prin traversarea r-s-d a arborelui de structură al formuleiα = (( ((a) ∨ b)) ↔ (a ∧ (b))) . rezultă secvenţa de vârfuri : r, n1, n2, n3, n4, n5, n6, n7, n8, n9,secvenţa etichetelor corespunzătoare lor fiind ↔ ∨ab∧abα deci reprezentarea

α prefix. Prin traversarea s-d-r a arborelui de structură rezultă secvenţa devârfuri n4, n3, n5, n2, n1, n7, n9, n8, n6, r, secvenţa etichetelor corespunzătoarelor fiind ab ∨ ab∧ ↔, deci reprezentarea α postfix.

Complexitatea structurală a formulelor este exprimată prin intermediulvalorilor funcţiei adâncime.

Definit ̧ia 1.1.4. Funcţia adâncime : FORM−→ N este definită prin:

α ∈ FORM,

(α) =

0, dacă α ∈ V 1 + (β ) , dacă α = (β )

1 + max {

(β ) ,

(γ )} , dacă α = (βργ ) , ρ ∈ L \ {

}Exemplul 1.1.7. Conform Definit ̧iei 1.1.4., pentru

α = (( ((a) ∨ b)) ↔ (a ∧ (b))) , obţinem

(α) = 1 + max { (β ) , (γ )} ,

unde β = ( ((a) ∨ b)) , γ = (a ∧ (b)) ,

(β ) = 1 + (((a) ∨ b)) = 2 + max { ((a)) , (b)}

= 2 + max {1 + (a) , 0} = 2 + max {1, 0} = 3

(γ ) = 1 + max { (a) , ((b))} = 1 + max {0, 1 + (b)} = 2.

Rezultă (α) = 4.Observat ̧ie Pentru orice α ∈ FORM,valoarea (α) exprimă numărul

conectivelor logice (simbolurile din mulţimea L) care apar ı̂n structurasimbolică α.De asemenea, (α) este ı̂nălţimea arborelui de structură core-spunzător formulei α.

7


8/40

3 Abordarea axiomatică ı̂n formalizarea raţi-onamentelor

Modelarea raţionamentelor ı̂n contextul limbajului calculului cu propoziţiipresupune alegerea unui sistem de axiome şi definirea unui sistem de demonstraţieı̂n termenii unei mulţimi de reguli de inferenţă.

Fie a, b, c propoziţii elementare. Mulţimea axiomelor teoriei, notată AXIOM,este

AXIOM = {α1, α2,...,α9} ,

unde

α1 = (a → (b → a))

α2 = ((a → (a → b)) → (a → b))

α3 = ((a → b) → ((b → c) → (a → c)))

α4 = ((a ↔ b) → (a → b))

α5 = ((a ↔ b) → (b → a))

α6 = ((a → b) → ((b → a) → (a ↔ b)))

α7 = (((a) → (b)) → (b → a))

α8 = ((a ∨ b) ↔ ((a) → b))

α9 = ((a ∧ b) ↔ ( ((a) ∨ (b))))

Evident, AXIOM ⊂ FORM.Definit ̧ia 1.2.1. Se numeşte substituţie o mulţime finită de perechiσ = {γ 1 | a1,...,γ n | an} , unde γ 1,...,γ n ∈ FORM , a1,...,an ∈ V ast-

fel ı̂ncât pentru orice i = j, ai = a j şi γ j = a j. Formulele γ 1,...,γ n senumesc formule substituente, respectiv a1,...,an se numesc propoziţii sub-stituite. Notăm cu ε substituţia vidă, ε = ∅. Notăm cu SUBST mulţimeasubstituţiilor.

Definit ̧ia 1.2.2. Fie α ∈ FORM , σ ∈ SUBST . Se numȩste rezultat alaplicării substituţiei σ formulei α, structura simbolică ασ calculată astfel:

ασ =if σ = ε then α

else if σ = {γ 1 | a1,...,γ n | an} thenif α ∈ V \ {a1,...,an} then α

else if α = ai then γ ielse if α = (β ) then (βσ)

else if α = (βρδ ) pentru anume ρ ∈ L \ {}then (βσρδσ) .

8


9/40

Observat ̧ie Pentru orice α ∈ FORM , σ ∈ SUBST , ασ ∈ FORM.

Dacă α ∈ AXIOM, atunci ασ se numeşte exemplu de axiomă(instanţiere a axiomei α ).

Exemplul 1.2.1. Fie

α = ((a ∧ b) → c) şi

σ = {((a) ∨ p) | a, c | b, (a ∨ x) | p, b | q } .

Rezultă

ασ = ((a ∧ b) σ → cσ) = ((aσ ∧ bσ) → cσ)= ((((a) ∨ p) ∧ c) → c) ,

deoarece aσ = ((a) ∨ p), bσ = c, cσ = c.Definit ̧ia 1.2.3. Numim regulă de inferenţă orice relaţie ⊂ FORM p × FORM q,unde p, q sunt numere naturale; perechea ( p, q ) defineşte tipul relaţiei.Dacă ({α1,...,α p} , {β 1,...,β q}) ∈ , spunem că {β 1,...,β q} se deduce

din {α1,...,α p} pe baza regulei de inferenţă . Pentru simplificarea notaţiei,convenim să reprezentăm

({α1,...,α p} , {β 1,...,β q}) ∈ prin α1,...,αp

β 1

,...,β q

.

Mulţimile de formule {α1,...,α p} şi {β 1,...,β q} sunt referite ca premisăşi respectiv concluzie ale regulei .

Modelarea proceselor de raţionament ı̂n contextul limbajului calculului cupropoziţii este realizată pe baza a două reguli de inferenţă şi anume, regulasubstituţiei SU B de tip (1, 1) şi regula modus ponens M P de tip (2, 1) ,definite prin

SU B = {(α, β ) | α ∈ F ORM, ∃σ ∈ SUBST, β = ασ}

M P = {({α, (α → β )} , β ) | α, β ∈ FORM }

Dacă α ∈ AXIOM şi σ ∈ SUBST, convenim să numim ασ exemplu deaxiomă α sau instanţiere a axiomei α.

Definit ̧ia 1.2.4. Secvenţa de formule α1,...,αn este o demonstraţie formalădacă pentru orice i, 1 ≤ i ≤ n este ı̂ndeplinită una din condiţiile:

ι) αi este instanţiere a unei axiome;

ιι) ∃ j, ∃k, 1 ≤ j,k < i, astfel ı̂ncât ({α j , αk} , αi) ∈ M P.

9


10/40

Definit ̧ia 1.2.5. Spunem că α ∈ FORM este formulă demonstrabilă (teo-

remă) şi notăm α, dacă există n ≥ 1 si α1,...,αn demonstraţie formalăastfel ı̂ncât αn = α. Notăm cu T h mulţimea teoremelor;

T h = {α | α ∈ FORM, α} .

Observat ̧ie Dacă α1,...,αn şi β 1,...,β m sunt demonstraţii formale, atunciα1,...,αn, β 1,...,β m este o demonstraţie formală. În consecinţă, putem in-clude direct teoreme ca etape ı̂ntr-o demonstraţie formală.

Exemple

1.2.2. Pentru orice α ∈ FORM , (α → α) .Intr-adevăr, următoarea secvenţă de formule este o demonstraţie formală

pentru (α → α) ,

β 1 = (α → (α → α)) = α1 {α | a, α | b}

β 2 = ((α → (α → α)) → (α → α)) = α2 {α | a, α | b}

β 3 = (α → α) , β 1, β 2

β 3M P

1.2.3. Pentru orice α ∈ FORM , (α ∨ (α)) .Considerăm demonstraţia formală

β 1 = ((α ∨ (

α)) ↔ ((

α) → (

α))) = α8 {α | a, (

α) | b}β 2 =

((α ∨ (α)) ↔ ((α) → (α))) →

(((α) → (α)) → (α ∨ (α)))

= α5 {(α ∨ (α)) | a, ((α) → (α)) | b}

β 3 = (((α) → (α)) → (α ∨ (α))) , β 1, β 2

β 3M P

β 4 = ((α) → (α)) , β 4

β 5 = (α ∨ (α)) , β 4, β 3

β 5M P

Observat ̧ie Mulţimea teoremelor este nevidă.Definit ̧ia 1.2.6. Formula α este logic falsă dacă (α) ∈ T h.

4 Deductibilitatea sub o familie de ipoteze

Frecvent, ı̂n cazul raţionamentelor, sunt implicate cunoştinţe suplimentarereprezentate prin formule care nu sunt ı̂n mod necesar demonstrabile. For-mulele reprezentând cunoştinţe suplimentare sunt referite ca ipoteze, mode-larea raţionamentelor ı̂n care ipotezele sunt acceptate ca etape ale procesului

10


11/40

deductiv se realizează pe baza conceptelor de deductibilitate simplă şi re-

spectiv globală sub o familie de ipoteze.Definit ̧ia 1.3.1. Fie H ⊂ FORM. Secvenţa de formule α1,...,αn este o

H -secvenţă deductivă dacă pentru orice i, 1 ≤ i ≤ n este indeplinită una dincondiţiile:

ι) αi ∈ H ∪ T h

ιι) ∃ j, ∃k, 1 ≤ j, k < i astfel ı̂ncât αj ,αkαi

M P.

Spunem că formula α este deductibilă sub ipotezele H , notat H α, dacăexistă n ≥ 1 şi există o H -secvenţă deductivă α1,...,αn, astfel ı̂ncât αn = α.

Definit ̧ia 1.3.2. Mulţimea T (H ) = {α | α ∈ F ORM,H α} este mulţimeade deductibilitate corespunzătoare mulţimii de ipoteze H .

Definit ̧ia 1.3.3. Mulţimea de formule H este compatibilă dacăT (H ) = F ORM. Dacă T (H ) = FORM, atunci H este incompatibilă.

Observat ̧ii

1. Pentru orice H ⊂ FORM, H ∪ T h ⊂ T (H )

2. Dacă H 1, H 2 ⊂ FORM si H 1 ⊂ H 2, atunci T (H 1) ⊂ T (H 2)

3. T (∅) = T (T h) = T h

4. Pentru orice H ⊂ FORM, T (T (H )) = T (H )

5. Dacă α1,...,αn şi β 1,...,β m sunt H −secvenţe deductive, atunci α1,...,αn,

β 1,...,β m este de asemenea o H −secvenţă deductivă. În consecinţă,pentru simplificare putem conveni să includem direct formule din T (H )ca etape ı̂ntr-o H −secvenţă deductivă.

Din observaţiile precedente, notând cu ℘ (FORM ) mulţimea părţilormulţimii FORM, rezultă că : ℘ (FORM ) → ℘ (FORM ) este un oper-

ator de ı̂nchidere şi cum pentru orice H ⊂ F ORM, evidentT h ⊂ T (H ) , rezultă că T h este cel mai mic punct fix al operatorului (̂ın raport cu relaţ ia de incluziune).

Lema 1.3.1. Fie H ⊂ FORM. Pentru orice α ∈ FORM, α ∈ T (H )dacă şi numai dacă există H 0 (α) ⊂ H, H 0 (α) mulţime finită, astfel ı̂ncâtα ∈ T (H 0 (α)) .

Demonstrat ̧ie Evident, dacă H 0 (α) ⊂ H, H 0 (α) mulţime finită, astfelı̂ncât α ∈ T (H 0 (α)) , cum T (H 0 (α)) ⊂ T (H ), obţinemα ∈ T (H ) .

11


12/40

Dacă α ∈ T (H ) , atunci există o H −secvenţă deductivă pentru α,fie

aceasta α1,...,αn = α. Evident α1 ∈ T h ∪ H, deci{α1,...,αn} ∩ (T h ∪ H ) = ∅.Notând H 0 (α) = H ∩ {α1,...,αn} , rezultă imediat că α1,...,αn este o

H 0 (α) −secvenţă deductivă deci α ∈ T (H 0 (α)) .Observat ̧ie Concluzia stabilită de lema 1.3.1 evidenţiază caracterul finit

al proprietăţii de a fi deductibilă sub o familie de ipoteze.Lema 1.3.2. Fie H = {α} . Atunci

T (H ) = {β | β ∈ F ORM, (α → β )} .

Demonstrat ̧ie Pentru β ∈ FORM, notăm γ = (α → β ) . Evident, dacăβ = α, atunci secvenţa γ, α, β este o H −secvenţă deductivă, deci β ∈T (H ).

Demonstrăm prin inducţie asupra lungimii H -secvenţei deductive că dacăβ ∈ T (H ), atunci γ. Notăm cu l (β ) lungimea minimă a unei H -secvenţedeductive pentru β .

Dacă l (β ) = 1, atunci β este H -secvenţă deductivă, deci β = α sau β .Dacă β = α, rezultă evident (α → β ) (exemplul 1).Dacă β , atunci secvenţa

β, (β → (α → β )) = α1 {β | a, α | b} , (α → β )

este demonstraţie formală, deci (α → β ).Presupunem că pentru orice β ∈ FORM, astfel ı̂ncât l (β ) ≤ n, rezultă

(α → β ). Fie β ∈ FORM astfel ı̂ncât, l (β ) ≤ n+1 şi fie β 1,...,β n, β n+1 = β o H -secvenţă deductivă.

Deoarece pentru orice p ≤ n, β 1,...,β p este H -secvenţă deductivă, rezultă (α → β p) , 1 ≤ p ≤ n.Dacă β n+1 ∈ T h ∪ H , evident rezultă (α → β n+1) , adică

(α → β ) .Rămâne de analizat cazul ı̂n care β n+1 rezultă prin regula modus ponens

aplicată unei perechi de formule de ranguri mai mici sau cel mult egale cun. Fie i,j, astfel ı̂ncât 1 ≤ i, j ≤ n şi β j= (β i → β n+1) . Aplicând ipotezainductivă, rezultă (α → β i) şi (α → (β i → β n+1)) .

12


13/40

Rezultă următoarea demonstraţie formală:

γ 1 = (α → β i)

γ 2 = (α → (β i → β n+1))

γ 3 = ((α → β i) → ((β i → β n+1) → (α → β n+1)))

= α3 {α | a, β i | b, β n+1 | c}

γ 4 = ((β i → β n+1) → (α → β n+1)) , γ 1, γ 3

γ 4M P

γ 5 =

(α → (β i → β n+1)) →(((β i → β n+1) → (α → β n+1)) → (α → (α → β n+1)))

= α3 {α | a, (β i → β n+1) | b, (α → β n+1) | c}

γ 6 = (((β i → β n+1) → (α → β n+1)) → (α → (α → β n+1))) ,γ 2, γ 5

γ 6M P

γ 7 = (α → (α → β n+1)) , γ 4, γ 6

γ 7M P

γ 8 = ((α → (α → β n+1)) → (α → β n+1)) = α2 {α | a, β n+1 | b}

γ 9 = (α → β n+1) , γ 7, γ 8

γ 9M P,

deci (α → β n+1) .Unul dintre cele mai importante rezultate ı̂n deductibilitatea sub o familie

de ipoteze este teorema deduct ̧iei (Herbrand).Teorema 1.3.1. (Teorema deduct ̧iei )Fie H ⊂ F ORM , α, β ∈ F ORM .Atunci, H ∪ {α} β , dacă şi numai dacă H (α → β ) .Demonstrat ̧ie Presupunem că H (α → β ) deci H ∪ {α} (α → β ) .

Evident α, (α → β ) , β este o H ∪ {α} − secvenţă deductivă, deciH ∪ {α} β .Demonstrăm prin inducţie asupra lungimii H ∪{α} − secvenţei deductive

că, dacă β admite o H ∪ {α} − secvenţă deductivă, atunci H (α → β ) .Dacă β admite o H ∪ {α} − secvenţă deductivă de lungime l (β ) = 1,

atunci β ∈ T h ∪ H ∪ {α} .

1. Dacă β = α , cum (α → α) , rezultă H (α → α) .

2. Dacă β ∈ T h, atunci β, (β → (α → β )) , (α → β ) este o demonstraţieformală, deci (α → β ) ceea ce implică ı̂n particular

H (α → β ) .

13


14/40

3. Dacă β ∈ H, atunci β, (β → (α → β )) , (α → β ) este o H -secvenţă

deductivă, deci H (α → β ) .

Presupunem că proprietatea este adevărată pentru toate formulele ce ad-mit H ∪ {α} − secvenţe deductive de lungimi cel mult egale cu n.

Fie β 1,...,β n, β n+1 = β o H ∪{α} − secvenţă deductivă. Evident, pe bazaipotezei inductive rezultă H (α → β i), 1 ≤ i ≤ n .

Dacă β n+1 ∈ T h∪H ∪{α} , atunci pe baza argumentului precedent rezultăH (α → β n+1) .

Dacă β n+1 rezultă prin aplicarea regulei modus ponens formulelor β i, β j,cu 1 ≤ i, j ≤ n, atunci β j = (β i → β n+1) . In acest caz, se observă cu uşurinţă

că secvenţa γ 1 − γ 9 din demonstraţia lemei precedente este o H − secvenţădeductivă, deci H (α → β n+1) .În cazul particular al mulţimilor finite de ipoteze, poate fi stabilit următorul

corolar al teoremei deducţiei.Corolar 1.3.1. Fie H = {α1,...,αn} o mulţime finită de ipoteze. Pentru

orice β ∈ FORM, H β , dacă şi numai dacă

(α1 → (α2 → (... → (αn → β )))) .

Demonstrat ̧ie Fie γ n = (αn → β ) , γ k = (αk → γ k+1) pentruk = n − 1, ..., 1, deci γ 1 = (α1 → (α2 → (... → (αn → β )))) .

Presupunem că H β , deci {α1,...,αn−1} ∪ {αn} β .Utilizând teorema deducţiei, obţinem

{α1,...,αn−1} (αn → β ) = γ n.

Iterând acelaşi argument, obţinem{α1,...,αk} (αk+1 → γ k+2) = γ k+1; k = n − 1, ..., 1.Pentru k = 1 rezultă {α1} (α2 → γ 3) = γ 2, deci pe baza concluziei

stabilite de Lema 1.3.2 obţinem (α1 → γ 2) = γ 1.Reciproc, dacă γ 1 = (α1 → γ 2) , atunci din Lema 1.3.2. rezultă{α1} γ 2 = (α2 → γ 3) .Din teorema deducţiei rezultă {α1, α2} γ 3 = (α3 → γ 4) .Iterând acelaşi argument, obţinem ı̂n continuare{α1,...,αk} γ k+1 = (αk+1 → γ k+2) , k = 1,...,n − 1.Pentru k = n − 1 rezultă {α1,...,αn−1} γ n = (αn → β ) , din care pe

baza teoremei deducţiei obţinem ı̂n final {α1,...,αn} β .Corolarul teoremei deducţiei oferă o modalitate de a stabili că

anumite formule sunt demonstrabile, şi anume permite reducerea problemeideterminării unei demonstraţii formale la determinarea unei secvenţe deduc-tive. In particular, deoarece o regulă de inferentă de tipul ( p, 1), p ≥ 1

14


15/40

exprimă ı̂n fapt ideea că formula din partea de concluzie a regulei este “di-

rect” deductibilă sub mulţimea de ipoteze reprezentată de mulţimea premisă,rezultă că ((α1,...,α p) , β ) ∈ poate fi reprezentată {α1,...,α p} β , sauechivalent, pe baza corolarului teoremei deducţiei, (α1 → (α2 → (... → (αn → β )))) .

În particular, deoarece pentru orice α, β ∈ FORM, avem({α, (α → β )} , β ) ∈ M P, rezultă {α, (α → β )} β deci, pe baza corolaruluiteoremei deducţiei obţinem următoarele concluzii:

(α → ((α → β ) → β )) , ((α → β ) → (α → β )) ,{α} ((α → β ) → β ) ,

{(α → β )} (α → β ) .

In continuare vor fi stabilite câteva reguli (scheme) de inferenţă auxiliare acăror utilizare facilitează construirea demonstraţiilor formale şi a secvenţelordeductive.

Corolar 1.3.2. Dacă α, β ∈ FORM, atunci {α} β , dacă şi numai dacă(α → β ) ∈ T h.

Demonstrat ̧ie Evident T h = T (∅) , deci pentru H = ∅, din teoremadeducţiei obţinem, ∅ ∪ {α} β dacă şi numai dacă ∅ (α → β ) , adică{α} β dacă şi numai dacă (α → β ) ∈ T h.

5 Aplicaţii

5.1 1.4.1. Schema silogismului (RS).

Pentru oriceα , β , γ ∈ F ORM, {(α → β ) , (β → γ )} (α → γ ) .Deoarece

α3 {α | a, β | b, γ | c} = ((α → β ) → ((β → γ ) → (β → γ )))

utilizând corolarul teoremei deducţiei, obţinem

{(α → β ) , (β → γ )} (α → γ ) .

Schema (regula) silogismului este reprezentată convenţional

(α → β ) , (β → γ )

(α → γ ) RS.

15


16/40

5.2 1.4.2. Schema ”trecerii” de la implicaţie la echiva-

lenţă (IE ).

Pentru orice α, β , γ ∈ F ORM,{(α → β ) , (β → α)} (α ↔ β ) .Deoarece α6 {α | a, β | b} = ((α → β ) → ((β → α) → (α ↔ β ))) uti-

lizând corolarul teoremei deducţiei, obţinem

{(α → β ) , (β → α)} (α ↔ β ) .

Schema trecerii de la implicaţie la echivalenţă este reprezentată

(α → β ) , (β → α)

(α ↔ β )

IE.

5.3 1.4.3. Schema permutării premiselor (P P ) .

Pentru orice α, β , γ ∈ F ORM, ((α → (β → γ )) → (β → (α → γ ))) .Fie H = {α,β, (α → (β → γ ))} . Evident, secvenţa

α, (α → (β → γ )) , (β → γ ) , β , γ

este o H − secvenţă deductivă, deci {α,β, (α → (β → γ ))} γ .Aplicând teorema deducţiei, rezultă

{β, (α → (β → γ ))} (α → γ ) ,

{(α → (β → γ ))} (β → (α → γ )) , ((α → (β → γ )) → (β → (α → γ ))) .

Schema permutării premiselor este reprezentată

(α → (β → γ ))

(β → (α → γ ))P P.

5.4 1.4.4. Schemele ”trecerii” de la echivalenţă la implicaţie(EI ) .

Deoarece pentru orice α, β ∈ FORM,

α4 {α | a, β | b} = ((α ↔ β ) → (α → β ))

şiα5 {α | a, β | b} = ((α ↔ β ) → (β → α))

rezultă {(α ↔ β )} (α → β ) şi {(α ↔ β )} (β → α) .Schemele ”trecerii” de la echivalenţă la implicaţie (EI ) sunt reprezentate

prin(α ↔ β )

(α → β )EI respectiv

(α ↔ β )

(β → α)EI .

16


17/40

5.5 1.4.5. Pentru orice

α, β ∈ FORM, ((α) → (α → β )) .Secvenţa

γ 1 = (((β ) → (α)) → (α → β )) = α7 {β | a, α | b}

γ 2 = ((α) → ((β ) → (α))) = α1 {(α) | a, (β ) | b}

γ 3 = ((α) → (α → β )) , γ 2, γ 1

γ 3RS

este o demonstraţie formală, deci ((α) → (α → β )) .În particular rezultă {(α) , α} β pentru orice β ∈ FORM, deci pentru

orice α ∈ FORM, T ({(α) , α}) = F ORM.

5.6 1.4.6. Schema dublei negaţii (DN ) .

Pentru oriceα ∈ FORM, (α ↔ ( (α))) .Pentru H = {( (α))} şi β ∈ T h (de exemplu β = (α → α) ) fieH − secvenţa deductivă,

γ 1 = (( (α)) → ((α) → (β ))) ∈ T h (aplicaţia 1.4.5)

γ 2 = ( (α)) ∈ H

γ 3 = ((α) → (β )) , γ 2, γ 1γ 3

M P

γ 4 = (((α) → (β )) → (β → α)) = α7 {α | a, β | b}

γ 5 = (β → α) , γ 3, γ 4

γ 5 M P

γ 6 = β ∈ T h

γ 7 = α, γ 6, γ 5

γ 7M P.

Rezultă {( (α))} α, deci (( (α)) → α) pentru orice formulă α,ceea ce ı̂n particular implică

(( ( (α))) → (α))

Considerăm demonstraţia formală

δ 1 = (( ( (α))) → (α)) ∈ T hδ 2 = ((( ( (α))) → (α)) → (α → ( (α)))) =

= α7 {( (α)) | a, α | b}

δ 3 = (α → ( (α))) , δ 1, δ 2

δ 3M P.

17


18/40

deci (α → ( (α))) , adică {α} ( (α)) .

Fie demonstraţia formală

η1 = (( (α)) → α) ∈ T h

η2 = (α → ( (α))) ∈ T h

η3 = (α ↔ ( (α))) , η1, η2

η3IE.

Din rezultatele stabilite obţinem schemele de inferenţă (DN ) reprezentate

prin α((α))

DN şi respectiv ((α))α

DN.

Observat ̧ie Mulţimea formulelor false este nevidă. Într-adevăr,

deoarece T h = ∅, fie α ∈ T h. Evident, rezultă ( (α)) ∈ T h, deci (α)este formulă falsă. Convenim să notăm prin o formulă demonstrabilă,respectiv prin ⊥ o formulă falsă oarecare.

5.7 1.4.7. Schema negaţiei (N N ) .

Pentru oriceα, β ∈ FORM, ((α → β ) ↔ ((β ) → (α))) .Fie demonstraţia formală

δ 1 = α7 {β | a, α | b} = (((β ) → (α)) ↔ (α → β ))

δ 2 = (((β ) → (α)) → (α → β )) , δ 1

δ 2EI

deci {((β ) → (α))} (α → β ) .

Obţinem astfel prima schemă de negaţie ((β )→(α))(α→β )

N N.

Considerăm mulţimea de ipoteze H = {(α → β )} şi H − secvenţa deduc-tivă

η1 = (α → β ) ∈ H

η2 = (( (α)) → α) ∈ T h

η3 = (( (α)) → β ) ,

η2, η1

η3 RS

η4 = (β → ( (β ))) ∈ T h

η5 = (( (α)) → ( (β ))) , η3, η4

η5RS

η6 = ((β ) → (α)) , η5

η6N N.

Rezultă {(α → β )} ((β ) → (α)) , deci

((α → β ) → ((β ) → (α))) ,

18


19/40

din care obţinem cea de a doua schemă de negaţie (α→β )(β )→(α)

N N.

Aplicând corolarul teoremei deducţiei, rezultă

((α → β ) → ((β ) → (α))) .

În final, putem considera demonstraţia formală

ζ 1 = (((β ) → (α)) → (α → β ))

ζ 2 = ((α → β ) → ((β ) → (α)))

ζ 3 = (((β ) → (α)) ↔ (α → β )) , ζ 1, ζ 2

ζ 3IE.

5.8 1.4.8.

Pentru orice α, β ∈ FORM,

((α → (β )) ↔ (β → (α))) .

Fie H = {(α → (β ))} . Considerăm H − secvenţa deductivă

ζ 1 = (α → (β )) ∈ H

ζ 2 = (( (α)) → α) ∈ T h

ζ 3 = (( (α)) → (β )) , ζ 2, ζ 1ζ 3

RS

ζ 4 = ((( (α)) → (β )) → (β → (α))) ∈ T h

ζ 5 = (β → (α)) , ζ 3, ζ 4

ζ 5M P

deci {(α → (β ))} (β → (α)) , adică

((α → (β )) → (β → (α))) .

Deoarece proprietatea a fost stabilită pentru orice formule α, β, rezultă

((β → (α)) → (α → (β ))) ,

deci utilizând schema trecerii de la implicaţie la echivalenţă rezultă

((β → (α)) ↔ (α → (β ))) .

19


20/40

5.9 1.4.9. Schema rezoluţiei (REZ ).

Pentru oriceα , β , γ ∈ F ORM, ((α → β ) → (((α) → γ ) → (β ∨ γ ))) .Fie H = {(α → β ) , ((α) → γ )} şi H − secvenţa deductivă

δ 1 = ((β ∨ γ ) ↔ ((β ) → γ )) = α8 {β | a, γ | b}

δ 2 = (((β ) → γ ) → (β ∨ γ )) , δ 1

δ 2EI

δ 3 = (α → β ) ∈ H

δ 4 = ((α → β ) → ((β ) → (α))) ∈ T h

δ 5 = ((β ) → (α)) , δ 3, δ 4

δ 5RS

δ 6 = ((α) → γ ) ∈ H

δ 7 = ((β ) → γ ) , δ 5, δ 6

δ 7RS

δ 8 = (β ∨ γ ) , δ 7, δ 2

δ 8RS.

Obţinem astfel {(α → β ) , ((α) → γ )} (β ∨ γ ) , deci aplicând corolarul

teoremei deducţiei, rezultă

((α → β ) → (((α) → γ ) → (β ∨ γ )))

şi (((α) → γ ) → ((α → β ) → (β ∨ γ ))) .

Schema rezoluţiei este reprezentată prin (α→β ),((α)→γ )(β ∨γ )

REZ.

5.10 1.4.10.


(α → (α ∨ β )) , (β → (α ∨ β )) .

20


21/40

Pentru H = {α} , considerăm secvenţa deductivă

δ 1 = ((α ∨ β ) ↔ ((α) → β )) = α8 {α | a, β | b}

δ 2 = (((α) → β ) → (α ∨ β )) , δ 1

δ 2EI

δ 3 = ((α) → (α → β )) ∈ T h, (aplicacţia 1.4.5)

δ 4 = (α → ((α) → β )) , δ 3

δ 4P P

δ 5 = α ∈ H

δ 6 = ((α) → β ) , δ 5, δ 4

δ 6M P

δ 7 = ((α ∨ β ) ↔ ((α) → β )) = α8 {α | a, β | b}

δ 8 = (((α) → β ) → (α ∨ β )) , δ 7

δ 8EI

δ 9 = (α ∨ β ) , δ 6, δ 8

δ 9M P,

deci {α} (α ∨ β ), din care rezultă (α → (α ∨ β )) .Fie demonstraţia formală

η1 = ((α ∨ β ) ↔ ((α) → β )) = α8 {α | a, β | b}

η2 = (((α) → β ) → (α ∨ β )) , η1

η2

EI

η3 = (β → ((α) → β )) = α1 {β | a, (α) | b}

η4 = (β → (α ∨ β )) , η3, η2

η4RS

deci (β → (α ∨ β )) .

5.11 1.4.11.

Pentru orice α, β ∈ FORM, ((α ∨ β ) ↔ (β ∨ α)) .Fie H = {(β ∨ α)} . Considerăm H − secvenţa deductivă

δ 1 = ((α ∨ β ) ↔ ((α) → β )) = α8 {α | a, β | b}

δ 2 = (((α) → β ) → (α ∨ β )) , δ 1

δ 2EI

δ 3 = ((β ∨ α) ↔ ((β ) → α)) = α8 {β | a, α | b}

δ 4 = ((β ∨ α) → ((β ) → α)) , δ 3

δ 4EI

δ 5 = (β ∨ α) ∈ H

δ 6 = ((β ) → α) , δ 5, δ 4

δ 6M P

21


22/40

δ 7 = (α → ( (α))) ∈ T h

δ 8 = ((β ) → ( (α))) , δ 6, δ 7

δ 8RS

δ 9 = (((β ) → ( (α))) → ((α) → β )) = α7 {β | a, (α) | b}

δ 10 = ((α) → β ) , δ 8, δ 9

δ 10M P

δ 11 = (α ∨ β ) , δ 10, δ 2

δ 11M P.

Rezultă {(β ∨ α)} (α ∨ β ) , deci pentru orice α, β ∈ FORM,

((β ∨ α) → (α ∨ β )) .

Deoarece ((β ∨ α) → (α ∨ β )) şi ((α ∨ β ) → (β ∨ α)) , utilizând schema(IE ) , obţinem ((β ∨ α) ↔ (α ∨ β )) .

5.12 1.4.12.


((α ∧ β ) → α) , ((α ∧ β ) → β ) , ((α ∧ β ) ↔ (β ∧ α)) .


δ 1 = ((α ∧ β ) ↔ ( ((α) ∨ (β )))) = α9 {α | a, β | b}

δ 2 = ((α ∧ β ) → ( ((α) ∨ (β )))) , δ 1

δ 2EI

δ 3 = ((α) → ((α) ∨ (β ))) ∈ T h

δ 4 =

((α) → ((α) ∨ (β ))) →→ (( ((α) ∨ (β )) → ( (α))))

∈ T h, (aplicaţia 1.4.7)

δ 5 = (( ((α) ∨ (β )) → ( (α)))) , δ 3, δ 4

δ 5M P

δ 6 = (( (α)) → α) ∈ T h

δ 7 = ( ((α) ∨ (β )) → α) , δ 5, δ 6

δ 7RS

δ 8 = ((α ∧ β ) → α) , δ 2, δ 7

δ 8RS,

deci ((α ∧ β ) → α) .

22


23/40

Analog, putem construi demonstraţia formală

γ 1 = ((α ∧ β ) ↔ ( ((α) ∨ (β )))) = α9 {α | a, β | b}

γ 2 = ((α ∧ β ) → ( ((α) ∨ (β )))) , γ 1

γ 2EI

γ 3 = ((β ) → ((α) ∨ (β ))) ∈ T h

γ 4 =

((β ) → ((α) ∨ (β ))) →→ (( ((α) ∨ (β )) → ( (β ))))

∈ T h, (aplicaţia 1.4.7)

γ 5 = (( ((α) ∨ (β )) → ( (β )))) , γ 3, γ 4

γ 5M P

γ 6 = (( (β )) → β ) ∈ T h

γ 7 = ( ((α) ∨ (β )) → β ) , γ 5, γ 6δγ

RS

γ 8 = ((α ∧ β ) → β ) , γ 2, γ 7

γ 8RS,

deci ((α ∧ β ) → β ) .Considerăm demonstraţia formală

η1 = ((α ∧ β ) ↔ ( ((α) ∨ (β )))) = α9 {α | a, β | b}

η2 = ((α ∧ β ) → ( ((α) ∨ (β )))) , η1

η2EI

η3 = (((β ) ∨ (α)) → ((α) ∨ (β ))) ∈ T h

η4 =

(((β ) ∨ (α)) → ((α) ∨ (β ))) →→ (( ((α) ∨ (β )) → ( ((β ) ∨ (α)))))

∈ T h

η5 = (( ((α) ∨ (β )) → ( ((β ) ∨ (α))))) , η3, η4

η5M P

η6 = ((α ∧ β ) → ( ((β ) ∨ (α)))) , η2, η5

η6RS

η7 = ((β ∧ α) ↔ ( ((β ) ∨ (α)))) = α9 {β | a, α | b}

η8 = (( ((β ) ∨ (α))) → (β ∧ α)) , η7

η8EI

η9 = ((α ∧ β ) → (β ∧ α)) , η6, η8η9

RS.

Rezultă că pentru orice α, β ∈ FORM , ((α ∧ β ) → (β ∧ α)) , deci şi ((β ∧ α) → (α ∧ β )), şi ı̂n final, utilizând schema (IE ) , obţinem

((α ∧ β ) ↔ (β ∧ α)) .

5.13 1.4.13.

Pentru orice α, β ∈ FORM, (α → (β → (α ∧ β ))) .

23


24/40

Fie H 1 = {α,β, (β → (α))} şi ⊥ o formulă falsă. Demonstrăm că H 1

⊥.Considerăm H 1− secvenţa deductivă

γ 1 = β ∈ H 1

γ 2 = (β → (α)) ∈ H 1

γ 3 = (α) , γ 1, γ 2

γ 3M P

γ 4 = ((α) → (α → ⊥)) ∈ T h, (aplicaţia 1.4.5)

γ 5 = (α → ⊥) , γ 3, γ 4

γ 5M P

γ 6 = α ∈ H 1γ 7 = ⊥,

γ 6, γ 5

γ 7M P,

deci H 1 ⊥.Aplicând teorema deducţiei, rezultă {α, β } ((β → (α)) → ⊥) .Notăm H = {α, β } şi construim H − secvenţa deductivă

η1 = ((β → (α)) → ⊥) ∈ T (H )

η2 = ((⊥) → ( (β → (α)))) , η1

η2N N

η3 = (

⊥) ∈ T hη4 = ( (β → (α))) ,

η3, η2

η4M P

η5 = ((α ∧ β ) ↔ ( ((α) ∨ (β )))) = α9 {α | a, β | b}

η6 = (( ((α) ∨ (β ))) → (α ∧ β )) , η5

η6EI

η7 = (((α) ∨ (β )) ↔ (( (α)) → (β ))) =

= α8 {(α) | a, (β ) | b}

η8 = (((α) ∨ (β )) → (( (α)) → (β ))) , η7

η8EI

η9 = (((

(

α)) → (

β )) → (β → (

α))) ∈ T hη10 = (((α) ∨ (β )) → (β → (α))) ,

η8, η9

η10RS

η11 = (( (β → (α))) → ( ((α) ∨ (β )))) , η10

η11N N

η12 = ( ((α) ∨ (β ))) , η4, η11

η12M P

η13 = (α ∧ β ) , η12, η6

η13M P.

24


25/40

Obţinem astfel {α, β } (α ∧ β ) , deci, aplicând teorema deducţiei rezultă

(α → (β → (α ∧ β ))) .

5.14 1.4.14.

Fie H ⊂ FORM. Atunci H este compatibilă dacă şi numai dacă pentruorice α ∈ FORM cel puţin una dintre mulţimile H ∪ {α} , H ∪ {(α)} estecompatibilă.

Deoarece H ⊂ H ∪ {α} , H ⊂ H ∪ {(α)} , obţinemT (H ) ⊂ T (H ∪ {α}) şi T (H ) ⊂ T (H ∪ {(α)}) .Rezultă evident că, dacă cel puţ in una dintre mulţimile H ∪ {α} ,

H ∪ {(α)} este compatibilă, atunci H este compatibilă.Demonstrăm că H este incompatibilă dacă şi numai dacă ⊥∈ T (H ) . Într-

adevăr, dacă T (H ) = FORM, cum ⊥∈ FORM, rezultă evident ⊥∈ T (H ) .Presupunem ⊥∈ T (H ) . Pentru β ∈ FORM arbitrară, rezultăH − secvenţa deductivă

γ 1 = (⊥→ ((β ) →⊥)) = α1 {⊥| a, (β ) | b}

γ 2 = ⊥, ⊥∈ T (H )

γ 3 = ((β ) →⊥) , γ 2, γ 1

γ 3M P

γ 4 = (((

β ) →⊥) → ((

⊥) → β )) ∈ T h, (aplicaţia 1.4.8)γ 5 = (( ⊥) → β ) ,

γ 3, γ 4

γ 5M P

γ 6 = ( ⊥) , ( ⊥) ∈ T h

γ 7 = β, γ 6, γ 5

γ 7M P

deci, β ∈ T (H ) , ceea ce evident implică T (H ) = F ORM.Fie H ⊂ FORM astfel ı̂ncât pentru orice α ∈ FORM cel puţin una

dintre mulţimile H ∪ {α} , H ∪ {(α)} este compatibilă. Deoarece T (H ) ⊂T (H ∪ {α}) ∩ T (H ∪ {(α)}) , rezultă T (H ) = FORM, deci H este com-

patibilă.Presupunem că H este compatibilă şi fie α ∈ FORM arbitrară. Dacă

ambele mulţimi H ∪ {α} , H ∪ {(α)} sunt incompatibile, atunci aplicândteorema deducţiei rezultă H (α →⊥), H ((α) →⊥) . Obţinem astfel

25


26/40

H − secvenţa deductivă

δ 1 = ((α) →⊥) ∈ T (H )

δ 2 = (((α) →⊥) → (( ⊥) → α)) ∈ T h, (aplicaţia 1.4.8)

δ 3 = (( ⊥) → α) , δ 1, δ 2

δ 3M P

δ 4 = ( ⊥) ∈ T h

δ 5 = α, δ 4, δ 3

δ 5M P,

deci α ∈ T (H ) ,adică H este incompatibilă, ceea ce este o contradicţie. În

concluzie, cel puţin una dintre mulţimile H ∪ {α} , H ∪ {(α)} este ı̂n modnecesar compatibilă.

5.15 1.4.15.

Fie α, β ∈ F ORM. Dacă {(α → β ) , (β → α)} ⊂ T h, atunciT (H ∪ {α}) = T (H ∪ {β }) pentru orice mulţime de formule H .Demonstrăm T (H ∪ {α}) ⊂ T (H ∪ {β }) prin inducţie asupra

lungimii H ∪ {α} − secvenţei deductive.Fie γ astfel ı̂ncât admite o H ∪ {α} − secvenţă deductivă de

lungime 1. Rezultă γ ∈ T h ∪ H ∪ {α} .Evident, dacă γ ∈ T h ∪ H, atunciγ ∈ T (H ∪ {β }).Dacă γ = α, atunci secvenţa β, (β → α) , α este o H ∪ {β } − secvenţă

deductivă, deci α ∈ T (H ∪ {β }) .Presupunem că pentru orice formulă γ ce admite o H ∪ {α} − secvenţă

deductivă de lungime cel mult egală cu n, rezultăγ ∈ T (H ∪ {β }) .Fie γ 1,...,γ n, γ n+1 = γ o H ∪ {α} − secvenţă deductivă.Evident, pentru orice 1 ≤ k ≤ n, γ 1,...,γ k este de asemeneaH ∪ {α} − secvenţă deductivă, deci conform ipotezei inductive rezultăγ k ∈ T (H ∪ {β }) , 1 ≤ k ≤ n.Dacă γ n+1 ∈ T h∪H ∪{α} , atunci pe baza argumentului precedent obţinem

γ n+1 ∈ T (H ∪ {β }) .Dacă există 1 ≤ i, j ≤ n astfel ca γ j = (γ i → γ n+1) , atunci secvenţa

γ i, γ j, γ n+1 este H ∪ {β } − secvenţă deductivă, deciγ ∈ T (H ∪ {β }) .Incluziunea T (H ∪ {β }) ⊂ T (H ∪ {α}) poate fi stabilită pe baza unui

argument similar.

26


27/40

În particular, dacă {(α → β ) , (β → α)} ⊂ T h atunci

T (H ∪ {(α)}) = T (H ∪ {(β )}) pentru orice mulţime de formule H .Într-adevăr, utilizând rezultatul stabilit de aplicaţia 1.4.7., dacă{(α → β ) , (β → α)} ⊂ T h, atunci{((α) → (β )) , ((β ) → (α))} ⊂ T h, deciT (H ∪ {(α)}) = T (H ∪ {(β )}) .

5.16 1.4.16.


{((α → β ) → ((α) ∨ β )) , (((α) ∨ β ) → (α → β ))} ⊂ T h.

Pentru H 1 = {(α → β )} considerăm următoarea H 1− secvenţă deductivă

γ 1 = (α → β ) ∈ H 1γ 2 = (( (α)) → α) ∈ T h

γ 3 = (( (α)) → β ) , γ 2, γ 1

γ 3RS

γ 4 = (((α) ∨ β ) ↔ (( (α)) → β )) = α8 {(α) | a, β | b}

γ 5 = ((( (α)) → β ) → ((α) ∨ β )) , γ 4

γ 5EI

γ 6 = ((α) ∨ β ) , γ

2, γ

5γ 6

M P.

Aplicând teorema deducţiei, rezultă ((α → β ) → ((α) ∨ β )) ∈ T h.Pentru H 2 = {((α) ∨ β )}, fie H 2− secvenţa deductivă

η1 = ((α) ∨ β ) ∈ H 2

η2 = (((α) ∨ β ) ↔ (( (α)) → β )) = α8 {(α) | a, β | b}

η3 = (((α) ∨ β ) → (( (α)) → β )) , η2

η3EI

η4 = (( (α)) → β ) , η1, η3

η4M P

η5 = (α → ( (α))) ∈ T h

η6 = (α → β ) , η5, η4

η6RS

Aplicând teorema deducţiei, rezultă (((α) ∨ β ) → (α → β )) ∈ T h.Rezultă {((α → β ) → ((α) ∨ β )) , (((α) ∨ β ) → (α → β ))} ⊂ T h, deci

pe baza concluziei stabilite de aplicaţia 1.4.15. obţinem

T (H ∪ {(α → β )}) = T (H ∪ {((α) ∨ β )})

pentru orice mulţime de formule H .

27


28/40

6 Deductibilitate globală

Definit ̧ia 1.5.1. Fie H, Γ ⊂ FORM. Spunem că mulţimea de formule Γ esteglobal deductibilă pe baza mulţimii de ipoteze H, notat H Γ, dacă H ∪Γ ⊥ unde Γ = {(γ ) | γ ∈ Γ} . Mulţimea Γ convenim să fie referită printermenul de “mulţime concluzie”.

Lema 1.5.1. Pentru orice H, Γ ⊂ FORM şi orice α ∈ F ORM,

ι) H {α} dacă şi numai dacă H α

ιι) H ∪ {α} Γ dacă şi numai dacă H {(α)} ∪ Γ

ιιι) H Γ ∪ {α} dacă şi numai dacă H ∪ {(α)} Γ

Demonstrat ̧ie

ι) Presupunem H {α}; utilizând teorema deducţiei, obţinemH ((α) →⊥) . Considerăm următoarea H − secvenţă deductivă,

δ 1 = ((α) →⊥) ∈ T (H )

δ 2 = (((α) →⊥) → (( ⊥) → α)) ∈ T h, (aplicaţia 1.4.8.)

δ 3 = (( ⊥) → α) , δ 1, δ 2

δ 3M P

δ 4 = ( ⊥) ∈ T h

δ 5 = α , δ 4, δ 3

δ 5M P,

deci H α.Presupunem H α; deci H 1 α unde H 1 = H ∪ {(α)}.

Considerăm H 1− secventa deductivă

γ 1 = (α) ∈ H 1γ 2 = α ∈ T (H 1)

γ 3 = ((

α) → (α →⊥)) ∈ T h (aplicaţia 1.4.5)γ 4 = (α →⊥) ,

γ 1, γ 3

γ 4M P

γ 5 = ⊥, γ 2, γ 4

γ 5M P,

deci H {α} .

28


29/40

ιι) Presupunem H ∪ {α} Γ, deci H ∪ Γ ∪ {α} ⊥ . Aplicând teorema

deducţiei, obţinem, H ∪ Γ (α →⊥) . Fie H ∪ Γ− secvenţa deductivă

δ 1 = (α →⊥) ∈ T (H ∪ Γ)

δ 2 = ((α →⊥) → (( ⊥) → (α))) ∈ T h, (aplicaţia 1.4.7)

δ 3 = (( ⊥) → (α)) , δ 1, δ 2

δ 3M P

δ 4 = ( ⊥) ∈ T h

δ 5 = (α) , δ 4, δ 3

δ 5M P

Rezultă H ∪ Γ (α) , deci utilizând (ι) , obţinem

H ∪ Γ {(α)} .

Obţinem astfel H ∪ Γ ∪ {( (α))} ⊥, adică H ∪ (Γ ∪ (α)) ⊥, decirezultă ı̂n final H Γ ∪ (α) .

ιιι) Evident H Γ ∪{α} implică H ∪Γ∪{(α)} ⊥ adică H ∪{(α)} Γ. De asemenea, dacă H ∪ {(α)} Γ, atunci

H ∪ Γ ∪ {(α)} ⊥, ceea ce poate fi scris H ∪ (Γ ∪ {α}) ⊥, deciH Γ ∪ {α} . În concluzie, H Γ ∪ {α} dacă şi numai dacă H ∪ {(α)} Γ.

Corolarul 1.5.1. Pentru orice H, Γ ⊂ FORM, şi orice α ∈ FORM,

ι) H ∪ {(α)} Γ, dacă şi numai dacă H {α} ∪ Γ.

ιι) H Γ ∪ {(α)} , dacă şi numai dacă H ∪ {α} Γ.

Demonstrat ̧ie

ι) H ∪{(α)} Γ dacă şi numai dacă H ∪{(α)}∪Γ ⊥, dacă şi numaidacă H ∪ (Γ ∪ {α}) ⊥, deci, dacă şi numai dacă H {α} ∪ Γ.

ιι) H Γ ∪ {(α)} , dacă şi numai dacă H ∪ Γ ∪ {( (α))} ⊥, dacăşi numai dacă T (H ∪ Γ ∪ {( (α))}) = FORM.

Deoarece pentru orice formulă α,

{(α → ( (α))) , (( (α)) → α)} ⊂ T h,

utilizând rezultatul stabilit ı̂n aplicaţia 1.4.15, obţinem

T (H ∪ Γ ∪ {α}) = T (H ∪ Γ ∪ {( (α))}) .

Rezultă H ∪ Γ ∪ {α} ⊥ deci H ∪ {α} Γ.Observat ̧ie Pe baza rezultatelor stabilite de Lema 1.5.1. şi corolarul ei,

putem formula următoarea concluzie relativ la “transferul unei formule α

29


30/40

ı̂ntre mulţimea ipotezelor şi mulţimea concluzie” şi anume transferul poate fi

realizat fie prin includerea formulei (α) fie prin includerea formulei β dacăα = (β ) .

Teorema 1.5.1 Fie H ⊂ F ORM.

ι) H ∅, dacă şi numai dacă H este mulţime incompatibilă.

ιι) H {α, β } , dacă şi numai dacă H (α ∨ β ) .

ιιι) Pentru orice n ≥ 1 şi β 1,...,β n ∈ FORM , H {β 1,...,β n} , dacă şinumai dacă H {γ n}, unde γ 1 = β 1, γ k = (γ k−1 ∨ β k) ,2 ≤ k ≤ n.

Demonstrat ̧ie

ι) Evident, H ∅, dacă şi numai dacă H ⊥ deci, dacă şi numai dacă H este mulţime incompatibilă.

ιι) Presupunem H {α, β } deci H ∪ {(α) , (β )} ⊥. Utilizând (ι) ,obţinem H ∪ {(α)} β deci, aplicând teorema deducţiei, rezultă H ((α) → β ) .

Considerăm H − secvenţa deductivă

δ 1 = ((α ∨ β ) ↔ ((α) → β )) = α8 {α | a, β | b}

δ 2 = (((α) → β ) → (α ∨ β )) , δ 1δ 2

EI

δ 3 = ((α) → β ) ∈ T (H )

δ 4 = (α ∨ β ) , β 3, δ 2

δ 4M P,

deci H {(α ∨ β )} .Presupunem H (α ∨ β ). Notând H 1 = H ∪ {(α) , (β )} , obţinem

H 1− secvenţa deductivă

η1 = ((α ∨ β ) ↔ ((α) → β )) = α8 {α | a, β | b}

η2 = ((α ∨ β ) → ((α) → β )) , η1

η2EI

η3 = (α ∨ β ) ∈ T (H ) ⊂ T (H 1)

η4 = ((α) → β ) , η2, η3

η4M P

30


31/40

η5 = (α) ∈ H 1

η6 = β, η5, η4

η6M P

η7 = ((β ) → (β →⊥)) ∈ T h, (aplicaţia 1.1.5)

η8 = (β ) ∈ H 1

η9 = (β →⊥) , η8, η7

η9M P

η10 = ⊥, η6, η9

η10M P,

deci H {α, β } .

ιιι) Demonstrăm prin inducţie după n că pentru orice n ≥ 2 şi pentruorice β 1,...,β n ∈ FORM , H {β 1,...,β n} , dacă şi numai dacă H γ n, undeγ 1 = β 1, γ k = (γ k−1 ∨ β k) , 2 ≤ k ≤ n.

Pentru n = 2, γ 2 = (γ 1 ∨ β 2) = (β 1 ∨ β 2) şi conform (ιι) proprietatea esteverificată.

Presupunem că pentru orice k, 2 ≤ k ≤ n, orice H ⊂ FORM, {β 1,...,β k} ⊂FORM, H {β 1,...,β k} , dacă şi numai dacă H γ k unde γ 1 = β 1, γ j =(γ j−1 ∨ β j) , 2 ≤ j ≤ k.

Presupunem H {β 1, ...β n, β n+1} . RezultăH ∪ {(β n+1)} {β 1, ...β n} deci, aplicând ipoteza inductivă,obţinem H ∪ {(β n+1)} γ n .În continuare, utilizând Lema 1.5.1. (ι) , rezultăH ∪ {(β n+1)} {γ n} şi conform corolarului aceleiaşi leme obţinemH {β n+1, γ n} , deci H (γ n ∨ β n+1), adică H γ n+1.Dacă H γ n+1, atunci H (γ n ∨ β n+1) , ceea ce implicăH {β n+1, γ n} . Obţinem ı̂n continuare H ∪ {(β n+1)} {γ n} deci

aplicând ipoteza inductivă H ∪ {(β n+1)} {β 1, ...β n} din care pe bazacorolarului lemei 1.5.1 rezultă H {β 1, ...β n, β n+1} .

Observat ̧ie Convenim să notăm γ n = β j.Teorema 1.5.2. Fie Γ ⊂ F ORM.

ι) ∅ Γ dacă şi numai dacă Γ este mulţime incompatibilă.

ιι) {α, β } Γ dacă şi numai dacă {(α ∧ β )} Γ.

ιιι) Pentru orice n ≥ 2 şi α1,...,αn ∈ FORM , {α1,...,αn} Γ, dacă şinumai dacă {δ n} Γ, unde δ 1 = α1, δ k = (δ k−1 ∨ αk) , 2 ≤ k ≤ n.

Demonstrat ̧ie

ι) ∅ Γ dacă şi numai dacă Γ ⊥ deci, dacă şi numai dacă Γ estemulţime incompatibilă.

31


32/40

ιι) Presupunem {α, β } Γ, deci, aplicând rezultatul stabilit de Lema 1.5.1.

rezultă Γ {(α) , (β )} . Din Teorema1.5.1. (ιι)obţinem Γ ((α) ∨ (β )) deci Γ ∪ ( ((α) ∨ (β ))) ⊥, adică

T (Γ ∪ ( ((α) ∨ (β )))) = FORM.

Secvenţa

γ 1 = ((α ∧ β ) ↔ ( ((α) ∨ (β )))) = α9 {α | a, β | b}

γ 2 = ((α ∧ β ) → ( ((α) ∨ (β )))) , γ 1

γ 2EI

γ 3 = (( ((α) ∨ (β ))) → (α ∧ β )) ,

γ 1

γ 3 EI

este o demonstraţie formală, deci

{((α ∧ β ) → ( ((α) ∨ (β )))) , (( ((α) ∨ (β ))) → (α ∧ β ))} ⊂ T h.

Utilizând rezultatul stabilit de aplicaţia 1.4.15., obţinem

T (Γ ∪ {( ((α) ∨ (β )))}) = T (Γ ∪ {(α ∧ β )})

deci T (Γ ∪ {(α ∧ β )}) = FORM . Rezultă Γ ∪ {(α ∧ β )} ⊥, adică

{(α ∧ β )} Γ.Reciproc dacă {(α ∧ β )} Γ atunci Γ ∪ {(α ∧ β )} ⊥ deci

T (Γ ∪ {(α ∧ β )}) = F ORM.

Obţinem astfel T (Γ ∪ {( ((α) ∨ (β )))}) = FORM deciΓ ∪ {( ((α) ∨ (β )))} ⊥, ceea ce implică Γ {((α) ∨ (β ))} .Pe baza rezultatului stabilit de Teorema 1.5.1. (ιι) obţinem ı̂n continuare

Γ {((α) , (β ))} , deci Γ ∪ {α, β } ⊥ din care rezultă {α, β } Γ.In concluzie, {α ∧ β } Γ, dacă şi numai dacă {α, β } Γ.ιιι) Demonstrăm prin inducţie că pentru orice n ≥ 2 şiα1,...,αn ∈ FORM , {α1,...,αn} Γ, dacă şi numai dacă {δ n} Γ,unde δ 1 = α1, δ k = (δ k−1 ∧ αk) , 2 ≤ k ≤ n.Pentru n = 2 proprietatea este evident verificată. Presupunem că pentru

orice 2 ≤ k ≤ n, orice Γ ⊂ FORM, {α1,...,αk} ⊂ F ORM, {α1,...,αk} Γ,dacă şi numai dacă {δ k} Γ, unde δ 1 = α1,

δ j = (δ j−1 ∧ α j) , 2 ≤ j ≤ k.Fie {α1,...,αn+1} ⊂ FORM, Γ ⊂ F ORM.Presupunem {α1, ...αn, αn+1} Γ. Utilizând rezultatul stabilit de Lema 1.5.1.

obţinem {α1,...,αn} Γ ∪{(αn+1)} , deci conform ipotezei inductive {δ n}

32


33/40

Γ∪{(αn+1)} . Rezultă Γ {(αn+1) , (δ n)} deci utilizând Teorema 1.5.1 (ιι)

obţinem Γ ((αn+1) ∨ (δ n)) ceea ce evident implică Γ {((αn+1) ∨ (δ n))}şi deci

Γ ∪ {( ((αn+1) ∨ (δ n)))} ⊥ .

Pe baza unui argument similar argumentului considerat la (ιι) obţinem Γ ∪{(δ n ∧ αn+1)} ⊥ deci {(δ n ∧ αn+1)} Γ adică {δ n+1} Γ. Presupunem{δ n+1} Γ. Rezultă Γ ∪ {δ n+1} ⊥ adică

T (Γ ∪ {δ n+1}) = FORM.Deoarece

{(δ n+1 → ( ((αn+1) ∨ (δ n)))) , (( ((αn+1) ∨ (δ n))) → δ n+1)} ⊂ T h

obţinem T (Γ ∪ {( ((αn+1) ∨ (δ n)))}) = FORM ,deci

Γ ∪ {( ((αn+1) ∨ (δ n)))} ⊥ .

În continuare rezultă Γ {((αn+1) ∨ (δ n))} , deci pe baza rezultatuluistabilit de Teorema 1.5.1. (ιι) , Γ {(αn+1) , (δ n)} .Evident, obţinem {δ n} Γ ∪ {(αn+1)} , deci pe baza ipotezei inductiverezultă {α1,...,αn} Γ∪{(αn+1)} , ceea ce ı̂n final implică {α1, ...αn, αn+1} Γ.

Observat ̧ie Convenim să notăm δ n =

ni=1 αi.

Caracterizarea deductibilităţii globale ı̂n cazul particular cândambele mulţimi H, Γ sunt mulţimi finite este formulată de teorema următoare.

Teorema 1.5.3. Fie H = {α1,...,αn}, Γ = {β 1,...,β m} . Mulţimea Γ este

global deductibilă sub mulţimea de ipoteze H, dacă şi numai dacă

ni=1

αi

m j=1

β j, unde δ 1 = α1, δ k = (δ k−1 ∧ αk) , 2 ≤ k ≤ n, γ 1 = β 1, γ k = (γ k−1 ∨ β k) ,

2 ≤ k ≤ m; δ n =n

i=1αi; γ m =

m

j=1β j.

Demonstrat ̧ie Utilizând proprietăţi anterior stabilite şi rezultatele formu-late ı̂n T eorema 1.5.1. şi Teorema 1.5.2. obţinem H Γ, dacă şi numai dacă{α1,...,αn} γ m ,dacă şi numai dacă {δ n} γ m, deci, dacă şi numai dacă

ni=1

αi

m j=1

β j.

Observat ̧ie Utilizând concluzia stabilită de Corolarul 1.3.2., rezultă

ni=1

αi

m j=1

β j, dacă şi numai dacă

ni=1

αi →m

j=1

β j

∈ T h. Concluzia stabilită de

33


34/40

Teorema1.5.3. exprimă principiul f undamental al programării logice şi

constituie baza unei clase importante de algoritmi de demonstrare automată.Conform definiţiei, {α1,...,αn} {β 1,...,β m} , dacă şi numai dacă{α1,...,αn, (β 1) , ..., (β m)} ⊥ .Dacă notăm αn+k = (β k) , 1 ≤ k ≤ m, obţinem{α1,...,αn} {β 1,...,β m} , dacă şi numai dacă {δ n+m} ⊥, undeδ 1 = α1, δ k = (δ k−1 ∧ αk) , 2 ≤ k ≤ n + m.Convenim să notăm

δ n+m =n

i=1αi ∧

m

j=1(β j) .

Să observăm că pentru orice α, β ∈ F ORM, {α} β , dacă şi numai dacă(α → β ) ∈ T h. Într-adevăr, dacă (α → β ) ∈ T h, atunci evident α, (α → β ) , β este {α} − secvenţă deductivă, deci {α} β . Dacă {α} β , atunci aplicândteorema deducţiei, rezultă ∅ (α → β ) , deci (α → β ) ∈ T (∅) = T h.

Obţinem astfel {δ n+m} ⊥, dacă şi numai dacă (δ n+m →⊥) ∈ T h.Presupunem (δ n+m →⊥) ∈ T h şi considerăm demonstraţia formală

ζ 1 = (δ n+m →⊥) ∈ T h

ζ 2 = ((δ n+m →⊥) → (( ⊥) → (δ n+m))) ∈ T h

ζ 3 = (( ⊥) → (δ n+m)) , ζ 1, ζ 2ζ 3M P

ζ 4 = ( ⊥) ∈ T h

ζ 5 = (δ n+m) , ζ 4, ζ 3

ζ 5M P,

deci (δ n+m) ∈ T h.Dacă (δ n+m) ∈ T h, atunci pe baza demonstraţiei formale

ξ 1 = (

δ n+m) ∈ T hξ 2 = ((δ n+m) → (δ n+m →⊥)) ∈ T h

ξ 3 = (δ n+m →⊥) , ξ 1, ξ 2

ξ 3M P

obţinem (δ n+m →⊥) ∈ T h, deci (δ n+m →⊥) ∈ T h, dacă şi numai dacă (δ n+m) ∈T h.

Rezultă astfel următoarea caracterizare a deductibilităţii globale ı̂n cazulı̂n care mulţimea ipotezelor şi mulţimea concluzie sunt finite, {α1,...,αn}

34


35/40

{β 1,...,β m} , dacă şi numai dacă n

i=1 αi

m j=1 β j, dacă şi numai dacă

ni=1

αi ∧m

j=1

(β j)

∈ T h, dacă şi numai dacă

ni=1

αi ∧m

j=1

(β j) este

logic falsă.Teorema 1.5.4. Pentru orice α, β ∈ FORM şi H, Γ mulţimi de formule,

ι) H ∪ {(α)} Γ, dacă şi numai dacă H Γ ∪ {α} (regula negat ̧ie stˆ anga ).

ιι) H ∪ {α, β } Γ, dacă şi numai dacă H ∪ {(α ∧ β )} Γ (regula

conjunct ̧ie stˆ anga ).

ιιι) H ∪ {(α ∨ β )} Γ, dacă şi numai dacă H ∪ {α} Γ şi

H ∪ {β } Γ (regula disjunct ̧ie stˆ anga ).

ιυ) H ∪ {(α → β )} Γ, dacă şi numai dacă H ∪ {β } Γ şi

H Γ ∪ {α} (regula implicat ̧ie stˆ anga ).

υ) H Γ ∪ {(α)} , dacă şi numai dacă H ∪ {α} Γ (regula negat ̧ie dreapta ).

νι) H Γ ∪ {(α ∧ β )} , dacă şi numai dacă dacă şi numai dacăH Γ ∪ {α} şi H Γ ∪ {β } (regula conjunct ̧ie dreapta ).

νιι) H Γ ∪ {α, β } , dacă şi numai dacă H Γ ∪ {(α ∨ β )} (regula disjunct ̧ie dreapta ).

νιιι) H Γ ∪ {(α → β )} , dacă şi numai dacă H ∪ {α} Γ ∪ {β } (regula implicat ̧ie dreapta ).

Demonstrat ̧ie Afirmaţiile (ι) şi (υ) sunt stabilite de Corolarul 1.5.1.ιι) Presupunem H ∪ {α, β } Γ, deci H ∪ Γ {(α) , (β )} . Din

Teorema1.5.1 rezultă H ∪ Γ {((α) ∨ (β ))} deciH ∪ Γ ∪ {( ((α) ∨ (β )))} ⊥, adicăT (H ∪ Γ ∪ {( ((α) ∨ (β )))}) = F ORM.Deoarece

{((α ∧ β ) → ( ((α) ∨ (β )))) , (( ((α) ∨ (β ))) → (α ∧ β ))} ⊂ T h,

pe baza proprietăţii stabilite de aplicaţia 1.4.15. rezultă

T (H ∪ Γ ∪ {(α ∧ β )}) = FORM,

35


36/40

deci H ∪ Γ ∪ {(α ∧ β )} ⊥, adică H ∪ {(α ∧ β )} Γ.

Reciproc, dacă H ∪ {(α ∧ β )} Γ, atunci H ∪ Γ ∪ {(α ∧ β )} ⊥, deciT (H ∪ Γ ∪ {(α ∧ β )}) = F ORM .

Utilizând din nou concluzia aplicaţiei 1.4.15. obţinemT (H ∪ Γ ∪ {( ((α) ∨ (β )))}) = FORM , deciH ∪ Γ ∪ {( ((α) ∨ (β )))} ⊥, ceea ce implicăH ∪ Γ {((α) ∨ (β ))} .În continuare, din teorema 1.5.1 rezultă H ∪ Γ {(α) , (β )} , deci

H ∪ Γ ∪ {α, β } ⊥ din care obţinem ı̂n final H ∪ {α, β } Γ.ιυ) Presupunem H ∪ {(α → β )} Γ, deci H ∪ Γ ∪ {(α → β )} ⊥ . Pe

baza rezultatului stabilit de aplicaţia 1.4.16. obţinem

T (H ∪ Γ ∪ {((α) ∨ β )}) = FORM,

deci H ∪ Γ {( ((α) ∨ β ))} . Notăm ∆ = H ∪ Γ şi fie ∆− secvenţadeductivă

δ 1 = ( ((α) ∨ β )) ∈ T (∆)

δ 2 = ((β → ((α) ∨ β ))) ∈ T h, (aplicaţia 1.4.10.)

δ 3 = ((β → ((α) ∨ β )) → (( ((α) ∨ β )) → (β ))) ∈ T h,

(aplicaţia 1.4.7.)

δ 4 = (( ((α) ∨ β )) → (β )) , δ 2, δ 3δ 4

M P

δ 5 = (β ) , δ 1, δ 4

δ 5M P.

Obţinem H ∪ Γ (β ) , deci H ∪ Γ {(β )} , ceea ce implică H ∪Γ ∪ {β } ⊥, deci H ∪ {β } Γ.

Considerăm de asemenea ∆− secvenţa deductivă

γ 1 = ( ((α) ∨ β )) ∈ T (∆)

γ 2 = (((α) → ((α) ∨ β ))) ∈ T h, (aplicaţia 1.4.10.)

γ 3 = (((α) → ((α) ∨ β )) → (( ((α) ∨ β )) → α)) ∈ T h,


γ 4 = (( ((α) ∨ β )) → α) , γ 2, γ 3

γ 4M P

γ 5 = α, γ 1, γ 4

γ 5M P.

Obţinem H ∪ Γ α, deci H ∪ Γ {α} , ceea ce implicăH ∪ Γ ∪ {(α)} ⊥, deci H ∪ (Γ ∪ {α}) ⊥,

36


37/40

adică H Γ ∪ {α} .

Dacă H ∪ {β } Γ şi H Γ ∪ {α} , atunci rezultă H ∪ Γ {α} şiH ∪ Γ {(β )} , deci H ∪ Γ α şi H ∪ Γ (β ) .

Fie Ω = H ∪ Γ ∪ {(α → β )} , evident {α, (β )} ⊂ T (Ω) .Considerăm Ω− secvenţa deductivă

θ1 = α ∈ T (Ω)

θ2 = (α → β ) ∈ Ω

θ3 = β, θ1, θ2

θ3M P

θ4 = (β ) ∈ T (Ω)

θ5 = ((β ) → (β →⊥)) ∈ T h, (aplicaţia 1.4.5.)

θ6 = (β →⊥) , θ4, θ5

θ6M P

θ7 = ⊥ .

Rezultă H ∪ Γ ∪ {(α → β )} ⊥, deci H ∪ {(α → β )} Γ.νι) Presupunem H Γ ∪ {(α ∧ β )} , deci H ∪ Γ ∪ {( (α ∧ β ))} ⊥ .Din demonstraţia formală

ϑ1 = ((α ∧ β ) ↔ ( ((α) ∨ (β )))) = α9 {α | a, β | b}

ϑ2 = ((α ∧ β ) → ( ((α) ∨ (β )))) , ϑ1

ϑ2EI

ϑ3 = (((α ∧ β ) → ( ((α) ∨ (β ))))

→ (( ( ((α) ∨ (β )))) → ( (α ∧ β )))) ∈ T h

ϑ4 = (( ( ((α) ∨ (β )))) → ( (α ∧ β ))) , ϑ2, ϑ3

ϑ4M P

ϑ5 = (((α) ∨ (β )) → ( ( ((α) ∨ (β ))))) ∈ T h,


ϑ6 = (((α) ∨ (β )) → ( (α ∧ β ))) , ϑ5, ϑ4

ϑ6

RS

ϑ7 = (( ((α) ∨ (β ))) → (α ∧ β )) , ϑ1

ϑ7EI

ϑ8 = ((( ((α) ∨ (β ))) → (α ∧ β ))

→ (( (α ∧ β )) → ( ( ((α) ∨ (β )))))) ∈ T h

ϑ9 = (( (α ∧ β )) → ( ( ((α) ∨ (β ))))) , ϑ7, ϑ8

ϑ9M P

37


38/40

ϑ10 = (( ( ((α) ∨ (β )))) → ((α) ∨ (β ))) ∈ T h


ϑ11 = (( (α ∧ β )) → ((α) ∨ (β ))) , ϑ9, ϑ10

ϑ11RS

rezultă

{(((α) ∨ (β )) → ( (α ∧ β ))) , (( (α ∧ β )) → ((α) ∨ (β )))} ⊂ T h,

deci

T (H ∪ Γ ∪ {( (α ∧ β ))}) = T (H ∪ Γ ∪ {((α) ∨ (β ))}) .

Obţinem astfel H ∪ Γ ∪ {((α) ∨ (β ))} ⊥, deci, aplicând teoremadeducţiei, rezultă H ∪ Γ (((α) ∨ (β )) →⊥) .

Fie H 1 = H ∪ Γ ∪ {(α)} , H 2 = H ∪ Γ ∪ {(β )}; evident,

H j (((α) ∨ (β )) →⊥) , j = 1, 2.

Construim H 1− secvenţa deductivă

γ 1 = (α)

γ 2 = ((α) → ((α) ∨ (β ))) ∈ T h, (aplicaţia 1.4.10.)

γ 3 = ((α) ∨ (β )) , γ 1, γ 2

γ 3M P

γ 4 = (((α) ∨ (β )) →⊥) ∈ T (H 1)

γ 5 = ⊥, γ 3, γ 4

γ 5M P,

deci H ∪ Γ ∪ {(α)} ⊥, adică H Γ ∪ {α} .Analog,

η1 = (β )

η2 = ((β ) → ((α) ∨ (β ))) ∈ T h, (aplicaţia 1.4.10.)η3 = ((α) ∨ (β )) ,

η1, η2

η3M P

η4 = (((α) ∨ (β )) →⊥) ∈ T (H 1)

η5 = ⊥, γ 3, γ 4

γ 5M P,

deci H ∪ Γ ∪ {(β )} ⊥, adică H Γ ∪ {β } .Reciproc, presupunem H Γ ∪ {α} şi H Γ ∪ {β } deciH ∪ Γ ∪ {(α)} ⊥ şi H ∪ Γ ∪ {(β )} ⊥ .

38


39/40

Aplicând teorema deducţiei, rezultă H ∪ Γ ((α) →⊥) şi

H ∪ Γ ((β ) →⊥) .Considerăm H ∪ Γ− secvenţa deductivă

δ 1 = ((α) →⊥) ∈ T (H ∪ Γ)

δ 2 = (((α) →⊥) → (( ⊥) → α)) ∈ T h, (aplicaţia 1.4.8.)

δ 3 = (( ⊥) → α) , δ 1, δ 2

δ 3M P

δ 4 = ( ⊥) ∈ T h

δ 5 = α, δ 4, δ 3

δ 5M P

δ 6 = ((β ) →⊥) ∈ T (H ∪ Γ)

δ 7 = (((β ) →⊥) → (( ⊥) → β )) ∈ T h, (aplicaţia 1.4.8.)

δ 8 = (( ⊥) → β ) , δ 6, δ 7

δ 8M P

δ 9 = β, δ 4, δ 8

δ 9M P

δ 10 = (α → (β → (α ∧ β ))) ∈ T h, (aplicaţia 1.4.13.)

δ 11 = (β → (α ∧ β )) ,

δ 5, δ 10

δ 11 M P

δ 12 = (α ∧ β ) , δ 9, δ 11

δ 12M P,

deci rezultă H ∪ Γ (α ∧ β ) , adică H ∪ Γ {(α ∧ β )} din care obţinemı̂n final H Γ ∪ {(α ∧ β )} .

νιι) Utilizând proprietăţile stabilite de Teorema 1.5.1., rezultăH Γ ∪ {α, β } , dacă şi numai dacă H ∪ Γ {α, β } , dacă şi numai dacăH ∪ Γ {(α ∨ β )} , dacă şi numai dacă H Γ ∪ {(α ∨ β )} .

νιιι) Din aplicaţia 1.4.16. a rezultat

{((α → β ) → ((α) ∨ β )) , (((α) ∨ β ) → (α → β ))} ⊂ T h.

39


40/40


δ 1 = ((α → β ) → ((α) ∨ β )) ∈ T h

δ 2 = (((α → β ) → ((α) ∨ β ))

→ (( ((α) ∨ β )) → ( (α → β )))) ∈ T h

δ 3 = (( ((α) ∨ β )) → ( (α → β ))) , δ 1, δ 2

δ 3M P

δ 4 = (((α) ∨ β ) → (α → β )) ∈ T h

δ 5 = ((((α) ∨ β ) → (α → β ))

→ (( (α → β )) → ( ((α) ∨ β )))) ∈ T h

δ 6 = (( (α → β )) → ( ((α) ∨ β ))) , δ 4, δ 5δ 6

M P.

Rezultă

{(( ((α) ∨ β )) → ( (α → β ))) , (( (α → β )) → ( ((α) ∨ β )))} ⊂ T h,

deci pentru orice mulţime de formule ∆

T (∆ ∪ {( ((α) ∨ β ))}) = T (∆ ∪ {( (α → β ))}) .

Obţinem astfel, H Γ ∪ {(α → β )} , dacă şi numai dacăH ∪ Γ ∪ {( (α → β ))} ⊥ dacă şi numai dacăH ∪ Γ ∪ {( ((α) ∨ β ))} ⊥ deci, dacă şi numai dacăH ∪ Γ {((α) ∨ β )} .Utilizând rezultatul stabilit de Teorema 1.5.1., obţinem ı̂n continuare

H ∪ Γ {((α) ∨ β )} , dacă şi numai dacăH ∪ Γ {(α) , β } , deci, dacă şi numai dacă H ∪ {α} Γ ∪ {β } .Lema 1.5.2. Fie H, Γ ⊂ FORM. Dacă H ∩ Γ = ∅, atunci H Γ.Demonstrat ̧ie Fie α ∈ H ∩ Γ, deci {α, (α)} ⊂ H ∪ Γ.Considerăm următoarea H ∪ Γ− secvenţă deductivă

γ 1 = ((α) → (α → ⊥)) ∈ T h, (aplicaţia 1.4.5.)γ 2 = (α) ∈ H ∪ Γ

γ 3 = (α → ⊥) , γ 2, γ 1

γ 3M P

γ 4 = α ∈ H ∪ Γ

γ 5 = ⊥, γ 4, γ 3

γ 5M P.

Rezultă H ∪ Γ ⊥, deci H Γ.

Logica Computationala Curs Partea I

Documents

Transcript of Logica Computationala Curs Partea I