Alfabetul si sintaxa in logica propozitiilor

Alfabetul si sintaxa in logica propozitiilor

Vom prezenta logica propozitiilor ca un limbaj formal. Un limbaj formal este, in general, format dintr-un alfabet care contine toate simbolurile limbajului, o sintaxa care stabileste modul in care sunt folosite simbolurile limbajului pentru a forma cu ele formule si o semantica care stabileste interpretarea acestor formule. Alfabetul in logica propozitilor contine printre altele simboluri de propoziti elementare( care se vor numi si propozitii elementare, propozitii atomice sau atomi). Formule, in logica propozitiilor, se vor numi, propozitii astfel incat sintaxa va consta in metodologia de a forma pe baza propozitiilor elementare date, si a celorlalte simboluri ale limbajului, toate celelalte propozitii. Interpretarea propozitiilor si deci semantica va avea insa mai multe aspecte: atribuirea unei valori de adevar pentru fiecare propozitie, clasificarea propozitiilor in raport cu valoarea lor de adevar, introducerea notiunii de consecinta a unei multimi de propozitii si studiul aceste notiuni.

Alfabetul In logica propozitiilor alfabetul este format din trei categorii de simboluri:

a) Simboluri propozitionale care se vor nota cu litere mari ale alfabetului latin, eventual insotite de indici: Vom nota multimea acestor simboluri propozitionale cu Q. In general multimea simbolurilor propozitionale Q este o multime nevida oarecare.

b) Simboluri ale conectorilor logici care sunt in numar de cinci si anume:

este simbolul negatiei; este simbolul conjunctiei; este simbolul disjunctiei,

este simbolul implicatiei; este simbolul echivalentei.

c)     Un simbol, ( , numit paranteza deschisa si un simbol, ), numit paranteza inchisa.

Sintaxa. Orice secventa de simboluri ale alfabetului se numeste expresie. Astfel orice expresie se reprezinta, in mod unic, sub forma:

unde m este un numar natural iar sunt simboluri. In particular, doua expresii:

si

sunt egale si scriem , daca si , ,., . Rezulta ca pentru orice expresie numǎrul natural m este unic determinat si numim m lungimea expresiei E.

Exista o unica expresie de lungime care se numeste expresia vidǎ. Expresiile de lungime 1 sunt exact simbolurile alfabetului; de exemplu:

sunt expresii de lungime1. Ca exemple de expresii de lungime 2 avem:

Alte exemple de expresii, de diverse lungimi , sunt:

Dacǎ si sunt doua expresii atunci, evident,

sunt de asemenea expresii.

1. Definitie. Un sistem ordonat , unde n este un numar intreg pozitiv si sunt expresii se numeste consructie formativa daca pentru orice cel putin una din urmatoarele conditii este satisfacuta:aa

1) Q, adica este un simbol propozitional;

2) exista astfel incat si ;

3) exista astfel incat si avem sau sau sau . ( Pe scurt unde este unul dintre simbolurile propozitionale .)

( In general un sistem ordonat de elemente se noteaza dar in cazul nostru inlocuim parantezele (, ) cu paranteze [, ] pentru a evita confuzia cu simbolurile limbajului.)

Definitie. O expresie se numeste propozitie daca exista un numar intreg pozitiv n si o constructie formativa astfel incat . Vom nota cu S(Q) sau simplu cu S multimea tuturor propozitiilor care se pot forma folosind alfabetul Q.

3. Propozitie. Avem:

1) orice simbol propozitional Q este propozitie sau, altfel spus, QS(Q);

2) dacǎ este o propozitie atunci este, de asemenea, o propozitie;

3) dacǎ sunt douǎ propozitii atunci sunt, de asemenea, propozitii.

Demonstratie. 1) Pentru orice Q, este, evident, o constructie formativa si deci A este o propozitie.

2) Deoarece este o propozitie, exista o constuctie formativa astfel incat Atunci este de asemenea o constructie formativa ceeea ce demonstreaza ca este o propozitie.

3) Deoarece sunt propozitii, exista constructii formative , astfel incat si . Dacǎ este unul dintre simbolurile atunci, evident, este, de asemenea o constructie formativa, ceea ce demonstreaza ca este o propozitie.

4. Definitie. Din propozitia 3. rezulta, evident, ca expresia vida nu este propozitie. Rezulta de asemenea ca singurele propozitii de lungime 1 sunt simbolurile propozitionale; acestea se vor numi propozitii elementare, propozitii atomice sau simplu atomi. In limbajul cotidian propozitiile elementare ar corespunde acelor propozitii care nu se pot exprima cu ajutorul altor propozitii folosind conectorii logici din sectiunea 1.

Propozitiile de lungime mai mare ca 1 se numesc si propozitii compuse. Evident, orice propozitie compusa este de forma , unde este o propozitie sau de forma unde si sunt propozitii iar este unul dintre simbolurile

Ca si in Sectiuna 1, daca si sunt doua propozitii atunci propozitia se numeste negatia propozitiei iar propozitiile se numesc respectiv, conjunctia, disjunctia, implicatia, echivalenta propozitiilor si .

Simbolurile conectorilor logici se vor numi simplu conectori logici.

5. Exemplu. Consideram, in limbajul cotidian, urmatoarele doua propozitii:

Ploua

Merg la plimbare

Notam prima dintre aceste doua propozitii cu A si a doua cu B. Putem considera alfabetul Q. Atunci putem scrie propozitia:

Daca nu ploua atunci merg la plimbare

intr-un mod formalizat, ca propozitie din S(Q) , sub forma . Remarcam ca, in acest caz, nu avem nici o indicatie precisa asupra valorilor de adevar ale propozitiilor elementare A, B si, cu atat mai mult, asupra valorii de adevar a propozitiei compuse insa, putem analiza toate posibilitatile, dupa modelul urmator: daca A este adevarata si B este adevarata atunci este adevarata; daca A este adevarata si B este falsa atunci este adevarata; daca A este falsa si B adevarata atunci este adevarata; daca A este falsa si B este falsa atunci este falsa.

6.Exemplu. Ne propunem sa demonstram ca expresia, este propozitie. Pentru aceasta putem folosi Propozitia 3. parcurgand urmatorii pasi astfel:

1. este un simbol propozitional si deci este propozitie.

Din 1 rezulta ca este propozitie.

3. B este simbol propozitional si deci este propozitie.

4. Din 2 si 3 rezulta ca este propozitie.

7.Exemplu. Expresia nu este propozitie deoarece singurele expresii de lungime 1 sunt simbolurile propozitionale iar nu este un simbol propozitional. Expresia , de asemenea nu este propozitie. Intr-adevar conectorul logic pote apare intr-o propozitie numai cand in "capetele" sale apar alte doua propozitii pe care putem eventual, sa le numim sursa si capatul impicatiei acestor doua propozitii; in cazul nostru lipseste sursa implicatiei.

Reducerea numarului de paranteze. Deoarece abundenta parantezelor poate deveni la un moment dat greoaie, pentru scrierea si propozitiilor se introduc cateva reguli simple prin care, putem sterge unele dintre pareanteze si consideram ca expresia obtinuta este tot propozitia data si anume o forma redusa a sa otinuta prin stregerea parantezelor. Aceste reguli sunt:

Mai intai se sterg perechile de paranteze exteiroare ale propozitiilor compuse(in propozitiile elementare nu exista paranteze exterioare).

In al doilea rand conectorii logici se ordoneaza astfel: ( aceasta este ceea ce se numeste ordinea de prioritate a conectorilor) si parantezele se sterg dupa urmatoarea regula: in primul rand conectorul sa se aplice primei propozitii care urmeaza dupa el, in al doilea rand sa se aplice celor doua propozitii mai apropiate de el ( obligatoriu este una in stanga lui si una in dreapta lui), in al treilea rand sa se aplice celor doua propozitii mai apropiate de el si, similar, pentru si apoi .

In cazul cand dorim stergerea a cat mai multe paranteze putem introduce o regula si pentru cazul aparitiei multiple a aceluiasi conector si anume pentru aparitia multipla a fiecaruia dintre conectorii ordinea de prioritate a aplicarii va fi intotdeauna de la stanga la dreapta in timp ce pentru aparitia multipla a conectorului ordinea de prioritate a aplicarii va fi intotdeauna de la dreapta la stanga.

Pentru ca sa nu avem dificultati in citirea corecta a propozitiei vom aplica partial regulile de mai sus adica vom sterge cat mai multe paranteze dar nu intotdeauna pe toate cele ce pot fi sterse conform regulilor de mai sus.

8.Exemplu. Ne propunem sa demonstram ca urmatoarea expresie este propozitie:

Pentru aceasta procedam ca si in Exemplul 2) si parcurgem urmatorii pasi:

1. A si B sunt simboluri propozitionale deci propozitii.

Din 1 rezultǎ cǎ este propozitie.

3. Din 2 rezultǎ cǎ este propozitie si prin stergerea parantezelor exterioare acesta propozitie devine .

4. C este simbol propozitional deci este propozitie.

5. Din 3 si 4 rezulta ca este propozitie si prin stergerea parantezelor exterioare aceastǎ propozitie devine .

Forma completa a propozitiei noastre este, evident:

.

Remarcam de asemenea ca, este forma redusa a propozitiei:

,

si deci este o propozitie diferita de propozitia anterioara; pentru aceasta propozitie putem considera si alte forme reduse care se obtin stergand numai anumite paranteze, cum ar fi:

, sau

9.Exemplu. Propozitia devine, prin reducerea parantezelor, in timp ce este o propozitie care, prin refacerea parantezelor este si difera, evident, de propozitia precedenta. De asemenea propozitia este, prin refacerea parantezelor, . Pentru propozitia refacerea parantezelor se poate face si parcurgand urmatorii pasi:

,,,.

Propozitia este, prin refacerea parantezelor, .

10.Teorema.( Principiul inductiei pentru propozitii) Fie P o multime de propozitii astfel incat

(a) QP;

(b).daca P atunci P;

(c) daca P atunci P unde este oricare dintre simbolurile

In aceste conditii PS.

Demonstratie. Consideram o propozitie oarecare S si fie n lungimea lui .Vom demonstra, prin inductie dupa n, ca P. Pentru avem Q si, conform lui (a), rezulta P. Presupunem si ca orice propozitie de lungime mai mica ca n apartine lui P. In acest caz avem, conform Definitiei 4., cu S sau unde S si . Evident au lungimea mai mica ca n si deci, conform ipotezei de inductie, avem,P. In cazul avem, conform lui (b), P iar in cazul avem P, conform lui (c). Astfel, conform principiului inductiei matematice, avem PS.

11. Corolar. Fie o propozitie. Atunci in expresia lui numǎrul de paranteze deschise este egal cu numǎrul de paranteze inchise si acelasi lucru se intamplǎ in orice formǎ redusa a lui .

Demonstratie. Pentru o propozitie oarecare S notam cu numarul de paranteze deschise ale lui si cu numǎrul de paranteze inchise ale lui . Fie

PS.

Daca    Q atunci si P. Presupunem acum ca P deci . Rezulta ceea ce implica P De asemenea daca P atunci si . Rezulta ca, pentru orice conector logic , avem

ceea ce implica P. Astfel multimea de propozitii P satisface conditiile (a),(b),(c) ale Teoremei 5. ceea ce demonstreaza egalitatea PS si deci afirmatia din enunt.

1 Observatie.Egalitatea din enuntul Corolarului 11 ramine valabila si in cazul formelor reduse ale lui deoarece, pentru a obtine o forma redusa, cand se sterge o paranteza deschisa automat se sterge si o paranteza inchisa.

13.Definitie. Fie o propozitie. Construim inductiv o multime notata astfel:

(1) dacǎ Q atunci ;

(2) dacǎ atunci iar dacǎ unde atunci .

Elementele multimii se numesc subpropozitii ale lui . O subpropozitie τ se numeste subpropozitie proprie a lui σ daca.

14.Exemplu.. Fie si . Avem:

,

.

15. Definitie. Fie SS(Q) si Q. Definim inductiv, pentru orice propozitieS, o propozitie notata , astfel:

(1) si daca Q, atunci ;

(2) daca atunci si daca , unde , atunci .

Propozitia se numeste substitutia lui A cu in. Evident propozitia se obtine prin simpla inlocuire a tuturor aparitiilor atomului A cu in expresia lui ; in particular, daca A nu apare in expresia lui atunci =. Mai general, daca n este un numar intreg pozitiv, S(Q) si Q atunci

iar propozitia se obtine prin inlocuirea tuturor aparitiilor atomilor in expresia lui σ cu respectiv.

Conceptul de substitutie poate fi generalizat considerand in locul unui atom Q o propozitie S arbitrara. Astfel, daca S si este o subpropozitie a lui atunci substitutia lui cu in este propozitia notata cu si care se obtine prin inlocuirea lui cu in expresia lui in toate aparitiile lui in ; daca nu este subpropozitie a lui Atunci .

16.Exemplu. Avem:

=

.

Exercitii

Decideti care dintre urmatoarele expresii este propozitie si care nu:

a) , b) , c) ,

d) , e) , f) ;

in caz afirmativ scrieti forma completa a lor.

Demonstrati ca urmatoarele expresii sunt propozitii:

a), b) , c).

Pentru fiecare dintre ele scrieti mai multe forme cu mai multe sau mai putine paranteze

In particular scrieti forma completa si forma cea mai redusa, adica cea care are cele mai

putine paranteze.

3. Determinati forma cea mai redusa pentru urmatoarele propozitii:

a) , b) , c) ,

d) , e) ,

f) , g) ,

h) .

4. Refaceti parantezele pentru a gasi forma completa pentru urmatoarele propozitii:

a) , b) , c) ,

d)

5. Care dintre urmatoarele expresii sunt forme reduse ale unor propozitii:

a) , b) , c) ,

d) , e) .

Prezentati propozitiile respective sub forma completa.

6. Determinati multimea subpropozitiilor propozitiei .

7.( Notatia Poloneza) Pentru orice doua propozitii S vom scrie in loc de si in loc de unde este oricare dintre conectorii logici . In acest mod rezulta un mod de a scrie propozitiile care nu mai foloseste paranteze si care se numeste notatia Poloneza.

a) Scrieti propozitiile:

, ,

mai intai sub forma completa si apoi in notatie Poloneza.

b) Scrieti propozitiile care apar in exercitiul 3. in notatie Poloneza.

c) Retranscrieti urmatoarele propozitii scrise in notatia Poloneza in forma standard:

, .

Rezolvari

1. (a) Nu este propozitie. (b) Este propozitia . (c) Nu este

propozitie. (d) Nu este propozitie. (e) Este propozitia . (e) Este propozitia

.

Forma completa este:

, ,

iar forma cea mai redusa este:

, , .

3. (a) , (b) , (c) ,

(d) , e) , f) ,

g) , h)

4.(a) , (b),

(c) , (d) .

5. (a) Se obtine, prin refacerea parantazelor si, evident, este o propozitie. (b) . (c) .

(d) nu este propozitie deoarece numarul de paranteze interioare nu este egal cu numarul de paranteze exterioare. (e) .

6. Forma completa este si avem:

7. (a) Forma completa este:

, ,

iar scrierea in notatie poloneza este:

, , .

(b)    (a) , (b)(c) , (d) ,

(e) , (f) , (g) ,

(h) .

(c) , .