Logica propozitionala - sintaxa logici propozitiilor, semantica logici preopozitionale, principiul rezolutiei in logica propozitiilor

LOGICA PROPOZITIONALA

este un limbaj destinat reprezentari de cunostiinte. Logica propozitionala ca orice alt limbaj trebuie sa aiba un vocabular, o sinteza si o semantic.

Vocabularul logicii propozitionale consta dintr-o multime de simboluri numite constant propozitionale. Aceste simboluri se noteaza cu litere mici p,q,r, . -constanta propozitionala. O constanta propozitionala reprezinta de obicei o afirmatie despre lumea reala.

Ex: p-"Afara ninge"

q-"Afara se aluneca"

SINTAXA LOGICI PROPOZITIILOR

stabileste ce combinatii de simboluri reprezinta formele corecte in limbajul logicii propozitiilor.

Definitie:

Formulele in logica propozitionala se defines dupa cum urmeaza:

1.orice constanta propozitionala este o formula

2.daca A si B sunt formule atunci :AΛB,AVB,A→B,A↔B,ΓA -sunt formule.

3.orice formula din logica propozitiilor se obtina aplicand regulile 1 si 2 de unu numar finit de ori

Ex: P₁vP₂vP₃ . vPn

Segventa de pe table nu este o formula in logica propozitionala.

(p 2→r)) (p-q))→(p→r) -axioma de distribuire a implicatiei. Este o formula in logica predicatelor.

SEMANTICA LOGICI PREOPOZITIONALE

O interpretare este o functie care asocieaza fiecarei constante  propozitionale o valoare de adevar sau fals.

C-multimea constantelor propozitionale.

i:C→.

i:→.

i(p)=T.

i(q)=F.

i(r)=F.

F-multimea formulelor.

i:F→.

i(ΓA)=Γi(A).

i(AΛB)=i(A)Λi(B).

i(AvB)=i(A)vi(B).

i(A→B)=i(A)→i(B).

i(A↔B)=i(A)↔i(B).

x Γx T F F F

x	y	x→y
T	T	T
T Document online: Saracia in societatea romaneasca Referat: Sociologie economica rurala - intrebari	F	F
F	T	T
F	F	T

Definitie:

O formula se numeste valida daca este adevarata in raport cu orice interpretare posibila.

O formula este numita nesatisfacuta daca este falsa in raport cu orice interpretare "p^Γp"-formula nesatisfacuta.

O formula este numita satisfacuta daca este adevarata in raport cu anumite interpretari si falsa in rapor cu altele p-formula satosfacuta.

Consideram o formula in care apare n constante propozitionale.

O astfrl de formula are 2ⁿ interpretari.

Observatii:

Calculul propozitiilor este decidabil fiind data o formula care contine n constante propozitionale un n este un numar finit se poate stabili intr-un numar finit de pasi daca formula respectiva este valida sau nu.

Algoritmul de verificare a validitati care se bazeaza pe analiza tuturor interpretarilor are o complexitate exponential. Pentru valorile lui n relativ mici numarul de interpretari care trebuie verificat este mare.

NOTIUNEA DE CONSECINTA

multinea de formule din logica propozitionala.

-p o formula din logica propozitionala.

Spunem ca P este o consecinta a lui Δ si notam Δ implica P daca si numai daca pentru orice interpretare toate formularile din Δ sunt adevarate P este si el adevarat.

dc.i(Δ)=T at. i(P)=T

Unul din obiectivele cursului nostrum este acela de a identifica metode eficiente de demonstrare a consecintei logice.

PRINCIPIUL REZOLUTIEI IN LOGICA PROPOZITIILOR

-principiul   rezolutiei este una din cele mai eficiente metode de rationament din logica propozitiilor. Rezolutia lucreaza cu formule in forma clauzala.

Definitie:

Un literal este o constanta propozitionala sau negatia unei cinstante propozitionale.

P-literal

Γg- literal(negativ)

p,q-constanta propozitionala.

O clauza este o dijunctie de literali.

O formula se numeste in forma clauzala daca se reprezinta ca o cojunctie de clause.

pvΓqvΓr-clauza

Rezolutia lucreaza numai cu clause deci cu dijunctii de literali.

Observatie

Orice formula din logica propozitiei poate fi reprezentata ca o multime de clauze (ca o conjunctive de clauze).

ALGORITMUL DE ADUCERE LA FORMA CLAUZALA

1.Eliminarea implicatiei si echivalentei:

A→B) se inlocuieste cu (ΓAvB) .

A↔B) se inlocuieste cu (A→B)Λ(B→A).

Γp v(Γqѵr))ѵ(Γ(Γpѵq)ѵ(Γpѵr)).

2.Transferul negatiei in interior:
-ΓΓA se inlocuieste cu A.

AΛB) se inlocuieste cu ΓAΛΓB .

AVB) se inlocuieste cu ΓAΛΓB.

- (ΓΓpΛΓ(ΓqΛr))V(ΓΓpΛΓq)ѵ(Γpѵr))

(pΛ(ΓΓqΛΓr))V(pΛΓq)V(ΓppVr)

(pΛqΛΓr)V(pΛΓq)VΓpVr.

3.Transferulm dijunctiei in interior:

Formula trebuie sa devina o conjunctive de dijunctii

-AV(BΛC) se inlocuieste cu (AVB)Λ(AVC).

AΛB)VC se inlocuieste cu (AVC)Λ(BVC).

Ex: [(pVΓpVr (qVΓpVr)Λ(ΓrVpVr)]V(pΛq)

=qVΓpVrV(pΛΓq)

qVΓqVrVp)Λ(qVΓpVrVΓq)

↑clauza             ↑clauza.

PRINCIPIUL REZOLUTIEI  

-consideram doua clauze care contin o pereche de literali complementari.

P₁VP₂VP₃ . .PmVPn

r₁Vr₂Vr₃V . VrVΓq    -literali complementari.

p₁Vp₂V . VpmVr₁Vr₂V . Vrk.