Concepte semantice in logica propozitiilor

Concepte semantice in logica propozitiilor

Pe multimea cu doua elemente consideram o lege de compozitie unara

si patru legi de compozitie binare

a caror definitie o prezentam pe scurt cu ajutorul urmatoarelor tabele:

, .

Pentru aplicatia folosim notatia , si deci conform tabelului de mai sus avem:

, .

Pentru oricare dintre legile de compozitie folosim notatia standard , , si rezulta:

;

;

;

.

1. Definitie. O valoare de adevar( sau valorizare) pe S(Q) este o aplicatie

v: S(Q)

care satisface urmatoarele conditii: pentru orice doua propozitii S(Q) avem:

, , ,

, .

2. Teorema. Daca S(Q)sunt doua valorizari astfel incat pentru orice Q atunci .

Demonstratie. Fie P{S. Daca Q atunci, prin ipoteza, si P. Presupunem acum ca P deci . Rezulta

ceea ce implica P. Acum fie P. Avem si si rezulta ca mai sus deci P pentru orice ; astfel de exemplu:

.

Astfel multimea de propozitii P satisface conditiile (a),(b),(c) ale Teoremei 2.5. ceea ce demonstreaza ca pentru orice propozitie S(Q) si deci .

3 Corolar. Fie S(Q ) doua valorizari,S(Q ) si multimea tuturor simbolurilor propozitionale care apar in expresia lui . Daca pentru orice avem atunci .

Demonstratie. Consideram alfabetul Q . Deoarece QQ avem, evident S(Q)S(Q) si, in plus, S(Q). Restrictiile w si ale lui v si respectiv la S(Q) sunt, evident, valorizari pe S(Q) si, prin ipoteza, avem, pentru orice Q,. Conform Teoremei 2., avem pentru orice S(Q) si in particular .

4. Teorema. Pentru orice aplicatie Qexista si este unica o valorizare

v: S(Q)

astfel incat restrictia lui v la Q coincide cu w.

Demonstratie. Afirmatia de unicitate din enunt rezulta din Teorema 2.. Pentru a demonstra afirmatia de existenta construim v: S(Q)recursiv astfel: pentru orice Q; daca S(Q) si , au fost definite atunci luam

, , , , .

Aplicatia v astfel constuita este, evident, o valorizare pe S(Q) care satisface conditia din enunt.

Observatie. Teorema 4. ne permite, evident, sa identificam valorizarile S(Q) cu aplicatiile w: Q motiv pentru care astfel de aplicatii se vor numi tot valorizari pe S(Q); mai mult ne putem permite sa notam o valorizare pe S(Q) si restrictia sa la Q cu aceiasi litera.

De asemenea este clar ca ne putem permite, prin abuz de notatie , sa scriem in loc de , in loc de , in loc de , in loc de si in loc de si sa mentinem pentru legile de compozitie aceleas reguli de reducere a parantezelor ca si pentru conectorii logici corespunzatori.

5. Definitie. Fie v o valorizare pe S(Q) si S(Q). Daca spunem ca propozitia este falsa in raport cu valorizarea v si daca spunem ca propozitia adevarata in raport cu v; in general se numeste valoarea de adevar a lui σ in raport cu v.

6. Exemplu. Luam Q si definim valorizarea v pe S(Q) luand si . Avem:

,

,

.

Astfel, in raport cu valorizarea v data , propozitiile si sunt false in timp ce propozitia este adevarata.

7. Definitie. O propozitie S(Q) se numeste logic adevarata sau tautologie daca este adevarata in raport cu orice valorizare v pe S(Q); propozitia se numeste logic falsa sau contradictie daca este falsa in raport cu orice valorizare pe S(Q); notam faptul ca este tautologie cu .

8.Teorema. Fie S(Q) o tautologie, n un numar intreg pozitiv, S(Q) si Q. Atunci este de asemenea o tautologie.

Demonstratie. Fie v o valorizare oarecare pe S(Q). Putem defini o valorizare w pe S(Q) astfel incat pentru orice si pentru oriceQ. Atunci, deoarece σ este tautologie, avem ; pe de alta parte avem, evident, v() deci v().

9.Exemplu. Propozitia este o contradictie iar propozitia este o tautologie. Pentru a demonstra aceasta observam ca

, , ,

si astfel pentru orice avem , . Pntru orice valorizare v pe S(Q) daca notam rezulta

,

.

Astfel este falsa in raport cu valorizarea v in timp ce este adevarata.

10.Exemplu. Fie Q si S(Q). Consideram valorizarea v pe S(Q) astfel incat Avem :

, ,

,

astfel ca propozitia este adevarata in raport cu valorizarea v.

Pe de alta parte putem considera valorizarea w pe S(Q) astfel incat , , Avem:

, ,

,

astfel incat propozitia este falsa in raport cu valorizarea w si in particular σ nu este tautologie.

11.Exemplu. Deoarece

, , ,

rezulta ca propozitia este o tautologie. Conform Teoremei 8, propozitia care se obtine din σ prin inlocuirea lui A cu este de asemenea tautologie.

Exercitii

1. Consideram, in limbajul cotidian, urmatoarele propozitii:

5 este numar prim, 15 se divide cu 3, 2 se divide cu 3, 12 se divide cu 5,

notam aceste propozitii respectiv cu si luam Q.

(a) Definiti o valorizare v pe S(Q) care, eventual, sa corespunda intuitiei noastre.

(b) In raport cu valorizarea v definita la punctul (a) calculati valoarea de adevar a propozitiei S(Q).

2. Fie v o valorizare pe S(Q) astfel incat In raport cu aceasta valorizare determinati valoarea de adevar pentru urmatoarele propozitii:

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

(e), (f), (g)

(h).

Aratati ca propozitia este tautologie.

4. Aratati ca urmatoarele propozitii sunt tautologii:

(a) , (b).

5. (a)Aratati ca legile de compozitie si pe sunt comutative, asociative si ca au element neutru. Ce tautologii rezulta din aceste proprietati?

(b) Studiati comutativitatea si asociativitatea si pentru legile de compozitie si pe .

6. Aratati ca propozitia nu este tautologie si nici contradictie

Rezolvari

1. (a) Luam .

(b) Avem: .

2. , , ,

,

, ,, .

Fie v o valorizare oarecare pe S(Q). Notam si . Este suficient sa aratam ca pentru orice avem . Sunt exact patru posibilitati si anume:

si ; in acest caz avem ,

si ; in acest caz avem ,

si ; in acest caz avem ,

si ; in acest caz avem .

4. (a). Fie v o valorizare oarecare pe S(Q) si . Daca atunci:

iar daca atunci:

.

(b) Fie v o valorizare oarecare pe S(Q) si .Daca atunci, pentru orice , avem:

.

Daca atunci:

iar daca atunci

.

5. a) Comutativitatea lui rezulta din

iar asociativitatea din

( mai precis asociativitatea rezulta din faptul ca in tabla de mai sus coloanele 4 si 6 coincid). Elementul neutru pentru este, evident,1. Analog se arata ca este comutativa si asociativa; elementul neutru pentru este 0. Comutativitatea lui si implica tautologiiile

,;

asociativitatea implica tautologiile

,

iar elementul neutru implica tautologiile

.

b) Deoarece si legea de compozitie nu este comutativa. De asemenea nu este asociativa deoarece

, .

Legea de compozitie este comutativa si asociativa si rezulta ca propozitiile:

,

sunt tautologii.

6. . Consideram o valorizare v astfel incat , , , si o valorizare w astfel incat , , , . Avem:

astfel ca nu este adevarata in raport cu v si nu este tautologie. De asemenea:

astfel ca este adevarata in raport cu w si nu este contradictie.