start     Articole     Despre mine    

 

Cateva notiuni de logica necesare pentru programare

Nicio alta parte din matematica nu mi se pare mai utila pentru programare decat logica.

Era si logic sa fie asa, nu? πŸ™‚

Hai sa vedem care sunt notiunile fundamentale de logica pe care ar trebui sa le stapanesti ca sa poti programa eficient.

Baza

Baza o constituie faptul ca se lucreaza cu propozitii care pot avea doar una din doua valori de adevar posibile — adevarat si fals. Altfel spus, se lucreaza cu propozitii care pot fi fie adevarate, fie false.

Poti sa vezi logica, deci, ca pe un fel de aritmetica in care in loc sa folosesti numere folosesti propozitii, iar in loc sa folosesti operatori aritmetici (gen adunare, scadere, inmultire, impartire) folosesti operatori logici (gen si, sau, nu).

Propozitiile cu care operezi in logica pot avea fie valoarea “fals”, fie valoarea “adevarat”. Pentru simplitate, se lucreaza cu valoarea 0 in loc de “fals” si cu valoarea “1” in loc de “adevarat”.

Nu

Se zice ca e bine sa inveti sa spui “Nu”. (Mai ales intr-o societate ca cea din zilele noastre, in care educatia pune foarte mare pret pe conformism si obedienta.)

Bineinetels, insa, ca nu e valabil pentru toata lumea. In vreme ce unii trebuie sa invete sa spuna “Nu” multitudinii de oportunitati care altfel risca sa le acapareze intreg timpul si energia, altii trebuie sa invete sa spuna “Da” schimbarii starii in care se mentin dintr-o inertie lenesa si caldicica.

Oricum, si “Da”-ul tot din “Nu”-uri e facut, asa ca nu e de mirare ca am ales sa incep cu el.

Wait. What? πŸ™‚ Cum adica “Da”-ul e facut din “Nu”-uri?

Hai sa vedem mai intai cum functioneaza operatorul “Nu” in logica. Pentru a simplifica lucrurile, voi folosi pentru el notatia “!” (fara ghilimele). Operatorul “!” (citit “nu”, “non”, sau “not”) este un operator logic unar (ceea ce inseamna ca are un singur operand, si nu doi) care se pune inaintea operandului sau.

Asta inseamna ca daca am propozitia A, pot nega aceasta propozitie scriind !A. Tabelul urmator arata functionarea operatorului “Nu” pentru toate cazurile posibile.

A !A
0 1
1 0

Deci daca propozitia A este falsa, propozitia !A este adevarata. Iar daca propozitia A este adevarata, propozitia !A este falsa.

Dar propozitia !(!A) cum o fi? Daca A este falsa, (!A) este adevarata — deci !(!A) este falsa. Iar daca A este adevarata, (!A) este falsa — deci !(!A) este adevarata.

Altfel spus, propozia !(!A) este echivalenta ca valoare de adevar cu propozitia A. Prin urmare, negand-o de doua ori de fapt am afirmat-o. Iata, deci, cum l-am facut pe “Da” din doua “Nu”-uri. πŸ™‚

Si

Bun, pana aici ai invatat cum sa jonglezi cu o bila. Acuma trecem la jonglerii cu doua bile — adica la operatori logici binari (deci cu doi operanzi).

Daca ai doua propozitii A si B (fiecare dintre ele putand fi fie falsa, fie adevarata), propozitia “A si B” cum va fi? (Falsa, sau adevarata?)

Operatorul logic “Si” il voi nota cu “&&” (citit “si” sau “and”), iar tabelul lui de functionare pentru toate cazurile posibile e aratat in continuare.

A B A && B
0 0 0
0 1 0
1 0 0
1 1 1

Ce trebuie sa intelegi din acest tabel? Faptul ca propozitia A && B este adevarata doar daca ambele propozitii (adica atat A, cat si B) sunt adevarate.

In limbajul obisnuit daca iti zic ca “Am facut treaba X si am facut treaba Y.” spun o minciuna daca in realitate nu am facut niciuna dintre cele doua treburi sau am facut-o doar pe una dintre ele, nu-i asa?
(Poate ca daca esti mai ingaduitor vei zice ca in cazul din urma n-am spus o minciuna, ci o jumatate de minciuna. Trebuie sa retii ca logica (cel putin cea clasica, de care vorbim aici) nu permite nici jumatati de minciuna, si nici jumatati de adevar.)

Sau

Dar propozitia “A sau B” cum va fi (adevarata, sau falsa?), in functie de valorile celor doua propozitii?

Operatorul logic “sau” il voi nota cu “||” (citit “sau” sau “or”), iar tabelul lui de functionare pentru toate cazurile posibile e aratat in continuare.

A B A || B
0 0 0
0 1 1
1 0 1
1 1 1

Alfel spus, acest tabel imi spune ca zic o minciuna doar daca ambele propozitii sunt false. Deci daca zic ca am facut treaba A sau am facut treaba B, se considera ca am spus adevarul daca am facut cel putin una dintre ele (deci si daca le-am facut pe amandoua).

Sau exclusiv

Dar in limbajul natural cand zic ca “Am facut treaba A sau am facut treaba B.” intelegi de fapt ca am facut doar una dintre ele, nu? Adica “fie A, fie B”.

Exista un operator logic si pentru asa ceva — se cheama “Sau exclusiv”. Tabelul lui de functionare e la fel ca al operatorului “Sau”, cu diferenta ca propozitia “A sau-exclusiv B” este falsa atunci cand A e adevarata si B e adevarata.

Tinand cont de cele prezentate pana aici, ar trebui sa nu iti fie foarte greu sa verifici ca operatorul “Sau exclusiv” il poti construi folosind operatorii “Sau”, “Si”, si “Nu”. Cum? Astfel: (A || B) && (! (A && B)).

Adica propozitia “Am facut fie treaba A, fie treaba B.” este echivalenta ca valoare de adevar cu propozitia “Am facut treaba A sau am facut treaba B si nu am facut atat treaba A cat si treaba B”.

Legile lui De Morgan

Sunt destul de fascinante jongleriile astea cu propozitii si valori de adevar codate cu 0 si 1, nu-i asa? E tot un fel de matematica, dar o matematica foarte simpla. (O matematica binara, in care exista doar numerele 0 si 1, iar in loc de “+” avem “||” si in loc de “*” avem “&&”.)

Atunci cand aceste expresii logice (obtinute din combinarea de propozitii si operatori logici) devin mai complicate, e util sa putem face simplificari ale lor sau scrieri ale lor in forme echivalente. Sau ai doua expresii si iti pui problema sa verifici daca sunt sau nu echivalente.

In aceste situatii se pot dovedi uneori utile legile lui De Morgan.

Ce zic ele?

(1) Propozitia ! (A && B) e echivalenta cu (! A) || (! B).

Adica propozitia “E fals ca am facut treaba A si am facut treaba B.” are aceeasi valoare de adevar ca propozitia “Nu am facut treaba A sau nu am facut treaba B.”.

(2) Propozitia ! (A || B) e echivalenta cu (! A) && (! B).

Adica propozitia “E fals ca am facut treaba A sau am facut treaba B.” are aceeasi valoare de adevar ca propozitia “Nu am facut treaba A si nu am facut treaba B”.

 

La ce pot fi utile toate astea in practica, te intrebi?

Iata un exemplu simplu: Iti pui problema sa determini daca coordonata x a unui punct se gaseste in afara ecranului nostru virtual. Cum ecranul e de 10×10 puncte (valorile posibile pentru coordonata x fiind intre 1 si 10 inclusiv), poate ca iti e mai simplu sa pui conditia in forma “daca punctul se gaseste pe ecran” si sa o negi — deci sa zici “daca este fals ca punctul se gaseste pe ecran”.

Altfel spus, poti pune conditia asta in forma (!((x>=1)&&(x<=10))). Dar oare cum ai fi putut-o pune direct, fara sa folosesti negatia aia de la inceput? Legea (1) a lui De Morgan de mai sus iti zice ca puteai sa scrii intr-o forma echivalenta conditia asta asa: ((!(x>=1))||(!(x<=10))). Hooopa! dar propozitia (!(x>=1)) n-o mai pot simplifica nitel? Ba da — e destul de evident ca a spune ca “e fals ca x e mai mare sau egal cu 1” e acelasi lucru cu a spune ca “(e adevarat ca) x e mai mic ca 1”, nu?

Deci conditia (!((x>=1)&&(x<=10))) o poti scrie mai simplu fi mai eficient asa ((x<1)||(x>10)).

 

Gata cu logica deocamdata. Iti recomand sa (re)citesti articolul asta si iti urez spor la gandit! πŸ™‚

Cu drag,

Florin