vineri, 16 noiembrie 2012

Noţiuni elementare de matematică pentru programatori (2) – Tipul logic

În matematică, nu e deloc simplu de definit conceptul de propoziţie. Putem spune că o propoziţie este o expresie verbală a unei judecăţi (adică un enunţ) despre care se poate spune dacă este adevărată sau falsă. Intrând puţin în metateorie, putem să ne întrebăm: bine, bine, dar ceea ce  „putem spune” e, oare, adevărat, sau fals? Şi, mai ales, are sens?

Dar, să lăsă, lucrurile acestea sterile şi să ne concentrăm asupra esenţialului. Iar acesta este că, în logica noastră clasică, de sorginte aristotelică, există doar două valori de adevăr, cele pe care le-am enunţat, şi orice enunţ – orice enunţ decidabil – este, fie adevărat, fie fals. Cale de mijloc nu există. Acceptăm, aşadar, următoarele două principii:

Principiul terţului exclus: O propoziţie este sau adevărată, sau falsă, altă variantă nu există.
Principiul noncontradicţiei: O propoziţie nu poate fi în acelaşi timp şi adevărată şi falsă.

Propoziţiile sunt de două feluri: simple (atomice, elementare), şi compuse. Propoziţiile simple sunt de forma subiect+predicat (de data asta, din punct de vedere lingvistic).

Exemple:
S: Soarele + P: străluceşte (acum).
S: 2 + P: e un număr natural.
S: Capitala României + P: este oraşul Bucureşti.
Propoziţiile compuse au în componenţa lor, cuvinte precum „şi”, „sau”, „deoarece”, „prin urmare”, „dacă”, şi aşa mai departe. Şi, obligatoriu, au mai multe predicate, şi mai multe subiecte (chiar dacă acest lucru nu este explicit).

Exemplu: „Toţi elevii (din clasa ...) au promovat” pare o propoziţie simplă (şi, uneori, poate fi tratată ca atare), dar, de fapt, este o formă condensată a propoziţiei compuse „Elevul 1 a promovat, şi elevul 2 a promovat, şi ...”.

În fapt, această distincţie nu este prea importantă în practică.Esenţial este faptul că putem combina două sau mai multe propoziţii pentru a obţine o altă propoziţie, şi facem acest lucru cu ajutorul operatorilor (conectorilor, functorilor) logici

Operatorul
Simbol (aici)
Numele operaţiei
    Non
Negaţia
      Şi
and
Conjuncţia
    Sau
or
Disjuncţia
Ori … ori
xor
Sau exclusiv
Dacă ... atunci
=>
Implicaţia
Dacă şi numai dacă
<=>
Echivalenţa

Dintre aceşti operatori numai primii patru sunt utilizaţi, în mod curent, în majoritatea limbajelor de programare.

Primul dintre cei şase operatori este unar (se aplică doar unei propoziţii), pe câtă vreme ceilalţi sunt binari (se aplică mai multor propoziţii). Modul cum funcţionează aceşti operatori este prezentat în tabelul de mai jos:

p
q
⌐p
p and q
p or q
p xor q
p => q
p<=>q
A
A
F
A
A
F
A
A
A
F
F
F
A
A
F
F
F
A
A
F
A
A
A
F
F
F
A
F
F
F
A
A

O propoziţie compusă adevărată tot timpul, indiferent de valoarea de adevăr a propoziţiilor componente, se numeşte tautologie. Un exemplu banal de tautologie este reprezentat de p or ⌐p (operatorul non are prioritate), care nu e altceva decât ilustrarea principiului terţului exclus !

 O inferenţă logică este o metodă de a obţine noi propoziţii adevărate din propoziţii despre care s-a stabilit deja că sunt adevărate. Orice tautologie conduce la o regulă de inferenţă.

Inferenţele sunt importante în informatică atunci când lucrăm cu sisteme expert, sisteme inteligente, când vizăm domenii de inteligenţă artificială precum demonstrarea automată a teoremelor etc.

Tipul logic (boolean)

Este un tip de date implementat, practic, în majoritatea limbajelor de programare. Datele de tip logic pot avea una din cele două valori: adevărat (true) sau fals (false). Sunt implementaţi de asemenea, şi operatorii mai sus-amintiţi (mai puţin ultimii doi).

Principalele probleme care pot apărea în legătură cu acest tip de date sunt reprezentate de conversia tipurilor. Sau, de întrebarea: ce este o dată de acest tip?

Sunt limbaje (de ex. C, C++, în specificaţiile originale) în care tipul logic nu era definit, altele (variantele moderne ale aceloraşi limbaje) în care întregii 0 şi 1 sunt trataţi ca fiind echivalenţi cu false şi true, fără niciun cast (conversie) explicit.   În altele (Java) acest lucru nu este permis, fiind necesară întodeauna o convertire explicită. În fine, în altele (PHP), practic, orice poate fi interpretat ca fiind de tip logic, fără niciun cast.

Observăm că, în unele cazuri, putem evalua o propoziţie compuse, fără a evalua ambele (în cazul în care sunt două) propoziţii componente. Bunăoară, propoziţia compusă p sau q, este adevărată dacă propoziţia p este adevărată, indiferent de valoarea propoziţiei q.

Cum în informatică, timpul de execuţie este, întotdeauna o resursă critică, numeroase limbaje de programare implementează câte doi operatori pentru operaţiile de sau şi şi, unul din ei – cel numit leneş (lazy) – realizând, dacă este cazul, evaluarea unei date logice compuse, fără a evalua ambii operanzi. Acest lucru poate fi benefic, dar poate genera şi unele efecte pe care nu le dorim, dacă avem nevoie de evaluarea şia celui de-al doilea operand, în toate situaţiile posibile. 

Ţinând cont de cele de mai sus, şi de faptul că reprezentarea internă a unei date de orice tip este, de fapt, o secvenţă de biţi, sau de 0 şi 1, unele limbaje implementează operatori logici pe biţi, care operează asupra reprezentărilor binare ale unor altor tipuri de date (de exemplu întregi) şi returnează un rezultat de acelaşi tip. Aceşti operatori pot crea numeroase confuzii în rândul programatorilor începători, şi de aceea, mulţi îi evită, dar, la fel de bine pot reprezenta un instrument puternic de lucru atunci când cunoaştem şi astfel de aspecte.
 
O altă problemă vizează instrucţiunile de decizie şi ciclare, care funcţionează pe baza evaluării unei date de tip logic. Dacă acea dată este, de fapt, o tautologie, atunci instrucţiunile respective se vor efectua, probabil, altfel decât am dorit, de exemplu se va intra într-un ciclu infinit, iar astfel de greşeli logice nu vor fi semnalate niciodată de compilator/interpretor. 

Sigur, există posibilitatea ca expresiile logice foarte complicate să poată fi analizate mai uşor prin transformarea lor în forme normale, dar, mult mai sigură şi uşoară este urmarea recomandării folosirii unor date logice cât mai simple, şi evitarea oricăror artificii periculoase.

Niciun comentariu:

Trimiteți un comentariu