Conectori logici

Conectori logici

In afara conectorilor logici uzuali anume puem defini si alte tipuri de conectori logici astfel:

1. Definitie. Fie n un numar intreg pozitiv. O aplicatie se numeste functie de adevar. Data functia de adevar o aplicatie

S(Q) S(Q)

astfel incat pentru orice valorizare v si orice S(Q) sa avem

se numeste un conector logic corespunzator functiei de adevar f. Evident, doi conectori logici corespunzatori aceleiasi functii de adevar f au proprietatea ca pentru orice S(Q) avem

.

In ceea ce urmeaza vom analiza numai cazurile si si deci vom vorbi despre conectori logici unari si binari.

Evident, negatia este un conector logic unar. Pentru a descrie toti conectorii unari vom descrie mai intai toate aplicatiile . Acestea sunt in numar de , le notam cu si putem sa le descriem, pe scurt, folosind urmatoarele tabele:

Conectori logici corespunzatori functiilor de adevar de mai sus sunt ,evident,

apicatiile S(Q) S(Q) definite respectiv prin:

, , ,

Conectorii sunt, evident triviali: si corespund unor functii de adevar constante iar corespunde functiei identice; retinem ca conector logic unar si netrivial numai pe .

Pentru descrierea conectorilor logici binari procedam in mod asemanator: numarul functiilor de adevar este si anume :

Conectori logici corespunzatori functiilor de adevar de mai sus sunt aplicatiile S(Q) S(Q) ,, definite prin:

,,,

,, , ,

, , , ,

,,,.

Dintre conectorii logici binari de mai sus am luat in consideratie pana acum numai pe , , , . si sunt intrun anumit sens constanti si deci triviali iar sunt practic conectori unari( in sensul ca ei actioneaza numai pe o singura componenta). sunt respectiv negatii pentru . este un conector dual cu iar este negatia sa. Conectorul se mai noteaza si cu si se numeste disjunctie excusiva( vezi Sectiunea 1): iar se mai noteaza si : . Un rol special in logica il au conectorii ( negatia conjunctiei) si( negatia disjunctiei). Conectorul se noteaza cu : iar conectorul se noteaza cu : ; tabelele de adevar ale acestor conectori sunt, evident:

..

Din aceste tabele de adevar razulta ca este o propozitie adevarata daca si numai daca si sunt ambele false iar este o propozitie falsa daca si numai daca si sunt ambele adevarate. In particular avem:

si .

2. Definitie. O multime C de conectori logici se numeste adecvata( sau suficienta) daca pentru orice propozitie S(Q) exista o propozitie S(Q) in a carei expresie apar numai conectori din C astfel incat .

Urmatorea propozitie ofera cateva exemple de multimi adecvate de conectori logici. Acestea sunt importante deoarece exprimarea propozitiilor numai cu conectori logici dintr-o multime adecvata de conectori C poate conduce, dupa cum vom vedea la noi metode de a studia propozitiile respective.

3. Propozitie. Urmatoarele multimi sunt multimi adecvate de conectori

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

Demonstartie. (a) Pentru orice doua propozitii atomice Q avem, conform uneia dintre legile lui De Morgan si legii dublei negatii,

(1) .

De asemenea o echivalenta bine cunoscuta este:

(2) .

Din cele doua echivalente de mai sus rezulta:

si retinem

(3) .

Acum faptul ca este o multime adecvata de conectori rezulta aplicand principiul de inductie pentru propozitii. Intr-adevar fie

PS(Q) exista S(Q) astfel incat si in expresia lui apar

numai conectorii si }.

Evident, avem QP. Fie P, si in expresia lui apar numai conectorii si . Conform Lemei 5.7, avem si, evident, in expresia lui apar numai conectorii si astfel ca P. Acum fie P, , , si in expresiile lui si apar numai conectorii si . Conform Lemei 5.7, avem si, evident, in expresa lui apar numai conectorii si astfel ca P. Conform lui (1) , Lemei 5.7 si Corolarului 5.3, avem si, evident, in expresa lui apar numai conectorii si astfel ca P. In mod asemanator, dar folosind (2) si respectiv (3), deducem P si P. Conform principiului de inductie pentru propozitii, avem PS(Q) ceea-ce nu inseamna altceva decat ca este o multime adecvata de conectori.

(b) Din legea lui De Morgan si legea dublei negatii rezulta:

.

Avem

si retinem

.

In fine

deci

.

Faptul ca este o multime adecvata de conectori rezulta acum aplicand principiul de inductie pentru propozitii ca in demonstratia lui (a).

(c) Avem

si retinem

.

De asemenea

deci

.

In fine

.

4.Propozitie. Multimile si sunt multimi adecvate de conectori.

Demonstratie. Reamintim ca, pentru S(Q) avem:

si .

In particular, pentru Q, avem

,

,

.

Faptul ca este o multime adecvata de conectori rezulta acum din Propozitia 4.(a) iar faptul ca este o multime adecvata de conectori rezulta din Propozitia 4. (b).

5. Propozitie. Fie un conector logic binar astfel incat este o multime adecvata de conectori. Atunci avem pentru orice S(Q) sau pentru orice S(Q).

Demonstaratie. Conectorul corespunde unei functii de adevar

si, conform Definitiei 1., pentru orice doua propozitii S(Q) si pentru orive valorizare v avem

.

Presupunem sau Fie Q . Conform Definitiei 2., exista o propozitie S(Q) in a carei expresie apare numai conectorul astfel incat si fie atomii care apar in aceasta expresie. In cazul consideram o valorizare v astfel incat ; din rezulta si deci

ceea ce este o contradictie. Analog, in cazul consideram o valorizare v astfel incat

si rezulta:

ceea ce este de asemenea o contradictie. Prin urmare avem si . Acum presupunem si sau si . Tabelul de adevar pentru conectorul este

sau

si arata ca in primul ca pentru orice doua propozitii S(Q) avem, in primul caz si in al doilea caz . Deoarece este o multime adecvata de conectori logici rezulta, in ambele cazuri, ca este de asemenea o multime adecvata si vom arata acum ca acest lucru este imposibil. Intr-adevar daca este multime adecvata atunci avem, pentru un atom Q, unde este o propozitie in expresia careia apare numai conectorul ; evident, exista o valorizare v astfel incat in timp ce . Am demonstrat astfel ca tabelul de adevar pentru conectorul este

sau

adica pentru orice S(Q) sau pentru orice S(Q).

Exercitii

1. Demonstrati urmatoarele echivalente:

a) ;

b) si ;

c);

d) ;

e) .

2. Demonstrati ca nu este o multime adecvata de conectori.

3. Aratati ca nici una dintre propozitiile:

a) , b) , c)

nu poate fi echivalenta cu o propozitie in expresia careia apare numai conectorul .

4. Demonstrati ca aplicatia S(Q)S(Q) definita,pentru orice S(Q), prin este un conector logic ternar si ca este o multime adecvata de conectori.

Rezolvari

1.a) Avem , .

b) . Analog .

c) .

d) Avem, conform Exercitiului 5.2.j):

,

si afirmatia rezulta deoarece .

e) Folosim tablele de adevar:

,

2. Presupunem, prin absurd, ca este o multime adecvata de conectori si consideram propozitia . Atunci exista o propozitie in a carei expresie apar numai conectorii si astfel incat . Consideram o valorizare v astfel incat si avem, evident, si ceea ce este o contradictie.

3. a) Presupunem ca unde este o propozitie in expresia careia apare numai conectorul si fie atomii distincti care apar in expresia lui . Putem considera o valorizare v astfel incat . In raport cu aceasta valorizare avem, evident, si ceea ce este o contradictie.

b) Se repeta rationamentul de la a).

c) Presupunem ca unde este o propozitie in expresia careia apare numai conectorul . Vom demonstra, prin inductie dupa lungimea lui , ca exista o valorizare v astfel incat si ceea ce, evident contrazice ipoteza. Pentru propozitia este un atom. Daca luam si ; daca luam si . Daca luam , si . Presupunem . Atunci unde sunt propozitii in expresia careia apare numai conectorul si care au lungimea strict mai mica decat n. Conform ipotezei de inductie exista o valorizare v astfel incat si . Dar implica, evident, .

4. Avem: iar este o tautologie; notam aceasta tautologie cu T si avem:

deci

.

Afirmatia rezulta acum deoarece este o multime adecvata de conectori.