Introducere în Logică și Teoria Mulțimilor

Notele de curs prezentate aparțin profesorului Aurelian Claudiu Volf de la Universitatea "Al. I. Cuza" din Iași. Aceste note sunt rezultatul colaborării cu mai mulți specialiști, inclusiv regretatul profesor Ioan Vrabie și doctori în matematică precum Andrei Cuzub și Silviu Lazorec.

Bine de știut! Matematica nu este doar despre formule, ci și despre comunicare clară a ideilor. Aceste note te vor ajuta să înțelegi limbajul matematic fundamental.

Cursul acoperă noțiuni esențiale de logică, limbaj matematic și teoria mulțimilor - instrumente de care vei avea nevoie în toate ramurile matematicii și în științele exacte.

Cuprins și Structura Cursului

Cursul este organizat în mai multe secțiuni principale, începând cu noțiuni de logică și limbaj matematic. Structura include:

1. Logică și Limbaj Matematic
   • Definiții și exerciții
   • Elemente de logică naivă
   • Operatori logici și calcul propozițional
   • Predicate și demonstrații

Fiecare secțiune conține atât explicații teoretice cât și exerciții practice pentru a-ți consolida înțelegerea.

Această organizare te ajută să progresezi gradat, de la conceptele de bază până la raționamente matematice complexe. Exercițiile incluse după fiecare secțiune sunt esențiale pentru a verifica înțelegerea și pentru a-ți dezvolta abilitatea de a aplica conceptele teoretice.

Definiții și Limbaj Matematic

O definiție matematică trebuie să fie consistentă - adică genul proxim trebuie să conțină cel puțin un obiect care să aibă toate proprietățile cerute de diferența specifică. Acest obiect se numește exemplu pentru definiția respectivă.

Când lucrezi cu definiții, trebuie să identifici:

• Numele noțiunii definite
• Genul proxim (categoria mai largă)
• Diferența specifică (ce o face unică)

De exemplu, în definiția "Se numește număr prim un număr natural, mai mare decât 1, ai cărui singuri divizori sunt 1 și numărul însuși", genul proxim este "număr natural mai mare decât 1", iar diferența specifică este "ai cărui singuri divizori sunt 1 și numărul însuși".

Important! Textele matematice sunt texte corect scrise în limba română (sau în altă limbă naturală). Când redactezi, acordă atenție maximă folosirii corecte a limbii și punctuației!

Este recomandat să înveți bine limba engleză (și eventual franceză) pentru a avea acces la o gamă largă de resurse matematice care nu sunt disponibile în limba română.

Propoziții și Operatori Logici

În logică, o propoziție este o constatare care este fie adevărată, fie falsă. Valorile de adevăr sunt notate cu a/1 (adevărat) sau f/0 (fals).

Pentru ca o formulare să fie o propoziție, trebuie să poată primi o valoare de adevăr, chiar dacă noi nu putem să-i determinăm valoarea în acel moment. De exemplu, "Mihai are părul blond" este o propoziție, în timp ce "Cînd plouă?" nu este.

Există o diferență între forma de exprimare a unei propoziții și propoziția însăși. Aceeași propoziție poate fi exprimată în moduri diferite.

Logica matematică se bazează pe patru principii fundamentale:

1. Principiul identității - în orice raționament, noțiunile trebuie utilizate într-o singură accepțiune
2. Principiul non-contradicției - o propoziție nu poate fi și adevărată și falsă în același timp
3. Principiul terțului exclus - orice propoziție este fie adevărată, fie falsă
4. Principiul rațiunii suficiente - orice afirmație trebuie să aibă o justificare

Atenție! Încălcarea principiului identității duce la raționamente eronate, ca în exemplul: "Bluza este roșie. Roșia este o legumă. Deci bluza este o legumă."

Operatori Logici Fundamentali

Operatorii logici ne permit să construim propoziții complexe din propoziții simple. Iată cei mai importanți:

1. Conjuncția (ȘI): Notată cu $p \land q$, este adevărată doar când ambele propoziții componente sunt adevărate.

2. Negația: Notată cu $\neg p$, inversează valoarea de adevăr a propoziției.

Când negăm propoziții, trebuie să fim atenți la formulare. De exemplu:

• Negația propoziției "Orice om este muritor" este "Există un om care nu este muritor"
• Negația propoziției "Există un triunghi cu două unghiuri drepte" este "Nu există un triunghi care să aibă două unghiuri drepte"

3. Implicația: Notată cu $p \to q$ ("p implică q"), este o prescurtare pentru $(\neg p) \lor q$. Acest operator este esențial în matematică pentru a exprima relații de tipul "dacă..., atunci...".

Sfat practic: Când întâlnești o implicație în matematică, gândește-te întotdeauna dacă este adevărată verificând că nu există situația în care prima parte este adevărată dar a doua falsă.

Tabele de Adevăr și Implicații

Conjuncția $(p \land q)$ este adevărată doar când ambele propoziții sunt adevărate:

Negația $(\neg p)$ inversează valoarea de adevăr:

Implicația $(p \to q)$ este falsă doar când $p$ este adevărată și $q$ este falsă:

Faptul că propoziția $p \to q$ este adevărată se poate exprima în diverse moduri:

• Dacă $p$, atunci $q$
• $p$ este condiție suficientă pentru $q$
• Din $p$ rezultă $q$
• $q$ este condiție necesară pentru $p$

Trucul util: Implicația $p \to q$ este echivalentă logic cu $(\neg p) \lor q$. Acest lucru este extrem de util când trebuie să negi o implicație, mai ales în demonstrațiile prin reducere la absurd.

Echivalența și Calculul Propozițional

Echivalența $(p \leftrightarrow q)$ înseamnă că propozițiile $p$ și $q$ au aceeași valoare de adevăr. Se definește ca: $(p \to q) \land (q \to p)$. Tabelul de adevăr arată că $p \leftrightarrow q$ este adevărată doar când ambele propoziții au aceeași valoare de adevăr.

Când propoziția $p \leftrightarrow q$ este adevărată, putem spune:

• $p$ este condiție necesară și suficientă pentru $q$
• $p$ echivalent cu $q$
• $p$ dacă și numai dacă $q$

Când ți se cere "Să se demonstreze că afirmațiile A și B sunt echivalente", trebuie să demonstrezi atât $A \to B$ cât și $B \to A$.

Calculul propozițional permite construirea de expresii complexe folosind operatorii logici. O expresie propozițională este un șir de simboluri din:

• Variabile propoziționale ($p$, $q$, $r$, ...)
• Operatori logici ($\lor$, $\land$, $\to$, $\leftrightarrow$)
• Simboluri auxiliare (paranteze)

Exemplu important: Expresia $((p \rightarrow q) \wedge p) \rightarrow q$ este o tautologie, adică este adevărată indiferent de valorile de adevăr ale lui $p$ și $q$. Această proprietate este fundamentală în raționamentele matematice.

Tautologii și Legile Logicii

O tautologie este o propoziție care este întotdeauna adevărată, indiferent de valorile de adevăr ale propozițiilor componente.

Pentru două propoziții $p$ și $q$, scriem $p \leftrightarrow q$ doar când ambele implicații $p \rightarrow q$ și $q \rightarrow p$ sunt adevărate. O greșeală frecventă este folosirea abuzivă a simbolului $\leftrightarrow$ când ar trebui folosit $\rightarrow$.

Demonstrarea tautologiilor se poate face prin:

1. Folosirea tabelelor de adevăr
2. Folosirea calculului propozițional (transformări algebrice)
3. Raționament direct

Exemple importante de tautologii:

• Comutativitatea: $p \vee q \leftrightarrow q \vee p$ și $p \wedge q \leftrightarrow q \wedge p$
• Asociativitatea: $p \vee (q \vee r) \leftrightarrow (p \vee q) \vee r$ și $p \wedge (q \wedge r) \leftrightarrow (p \wedge q) \wedge r$
• Distributivitatea: $p \wedge (q \vee r) \leftrightarrow (p \wedge q) \vee (p \wedge r)$
• Legea terțiului exclus: $p \vee \neg p$
• Principiul contradicției: $(p \wedge \neg p) \rightarrow q$

Atenție! Este esențial ca o teorie matematică să nu conțină contradicții. Dacă ar exista o contradicție, atunci orice afirmație ar putea fi demonstrată ca fiind adevărată, făcând teoria inutilă.

Principii de Demonstrație și Reguli Logice

În matematică, demonstrațiile folosesc diverse principii bazate pe tautologii logice:

1. Principiul demonstrației prin contrapoziție: $(p \rightarrow q) \rightarrow (\neg q \rightarrow \neg p)$

   • Pentru a demonstra $p \rightarrow q$, se poate demonstra echivalent $\neg q \rightarrow \neg p$

2. Principiul demonstrației prin reducere la absurd:

   • Pentru a demonstra $p \rightarrow q$, se presupune că $p$ este adevărat și $q$ fals, apoi se deduce o contradicție

3. Regula silogismului (tranzitivitatea implicației):

   • $[(p \rightarrow q) \wedge (q \rightarrow r)] \rightarrow (p \rightarrow r)$

4. Legea de negare a implicației:

   • $\neg (p \rightarrow q) \leftrightarrow (p \wedge \neg q)$

Alte tautologii importante includ:

• Legile lui De Morgan: $\neg (p \vee q) \leftrightarrow (\neg p \wedge \neg q)$ și $\neg (p \wedge q) \leftrightarrow (\neg p \vee \neg q)$
• Dubla negație: $\neg (\neg p) \leftrightarrow p$

Sfat pentru examene: Învață să recunoști aceste principii de demonstrație în probleme. Când te blochezi într-o demonstrație, încearcă să aplici unul dintre aceste principii, în special contrapoziția sau reducerea la absurd.

Înțelegerea acestor legi logice îți permite să construiești demonstrații riguroase și să identifici erori în raționamente.

Legile lui De Morgan și Alte Tautologii

Legile lui De Morgan (sau legile de dualitate) sunt esențiale în logică și simplificarea expresiilor:

• $\neg [p \vee q] \leftrightarrow (\neg p \wedge \neg q)$
• $\neg [p \wedge q] \leftrightarrow (\neg p \vee \neg q)$

Alte tautologii importante includ:

• Distributivitatea disjuncției față de conjuncție: $p \vee (q \wedge r) \leftrightarrow (p \vee q) \wedge (p \vee r)$
• Reguli pentru negarea implicației: $\neg (p \rightarrow q) \leftrightarrow (p \wedge \neg q)$
• Legea demonstrației prin divizare în cazuri: $[p \rightarrow (q \vee r)] \leftrightarrow [(p \wedge \neg q) \rightarrow r]$

Consecință importantă: Pornind de la o contradicție, se poate deduce orice propoziție: $(p \wedge \neg p) \rightarrow q$. Aceasta arată de ce teoriile matematice trebuie să fie non-contradictorii.

Aplicație practică: Când rezolvi probleme complexe, încearcă să le împarți în cazuri și să folosești tautologiile potrivite. De exemplu, folosește legile lui De Morgan pentru a simplifica negațiile expresiilor compuse.

Prin stăpânirea acestor tautologii, vei putea construi demonstrații elegante și vei înțelege mai bine structura logică a matematicii.