Tautologii și negații corecte

Pasul 1 din 8

Mereu adevărat

„Mâine plouă sau mâine nu plouă.” Nu știi ce vreme va fi mâine, dar știi sigur că propoziția e adevărată. Orice s-ar întâmpla, una dintre cele două părți e adevărată.

Notăm $p$ : „Mâine plouă”. Propoziția de mai sus este $p \vee \overline{p}$ . Verificăm ambele cazuri:

$p$	$\overline{p}$	$p \vee \overline{p}$
1	0	1
0	1	1

O propoziție compusă care e adevărată oricare ar fi valorile părților ei se numește tautologie.

Verifică-te

Care dintre aceste propoziții e adevărată oricare ar fi

p

Negația negației

„Nu e adevărat că nu mi-am făcut tema.” Ce înseamnă, pe scurt? „Mi-am făcut tema.”

Primul „nu” întoarce valoarea, al doilea o întoarce înapoi. Două negații una peste alta se anulează.

$p$	$\overline{p}$	$\overline{\overline{p}}$	$\overline{\overline{p}} \leftrightarrow p$
1	0	1	1
0	1	0	1

Coloana lui

\overline{\overline{p}}

e identică cu a lui

p

, deci echivalența din ultima coloană e mereu adevărată: e o tautologie. Se numește legea dublei negații.

Ce spune medicul

Medicul îți spune: „Nu este indicat să faci abuz de produse făinoase sau de dulciuri.”

Ce ai voie? Abuz de făinoase: nu e indicat. Abuz de dulciuri: nici asta. Deci medicul spune, de fapt, două lucruri deodată:

„Nu este indicat să faci abuz de făinoase și nu este indicat să faci abuz de dulciuri.”

Notăm

p

: „faci abuz de făinoase” și

q

: „faci abuz de dulciuri”. Medicul spune

\overline{p \vee q}

, iar asta înseamnă

\overline{p} \wedge \overline{q}

De ce funcționează?

Comparăm

\overline{p \vee q}

\overline{p} \wedge \overline{q}

pe toate cele patru cazuri:

$p$	$q$	${p \!\vee\! q}$	$\overline{p \!\vee\! q}$	$\overline{p}$	$\overline{q}$	${\overline{p} \!\wedge\! \overline{q}}$
1	1	1	0	0	0	0
1	0	1	0	0	1	0
0	1	1	0	1	0	0
0	0	0	1	1	1	1

Coloanele 4 și 7 sunt identice: 0, 0, 0, 1. Cele două propoziții au mereu aceeași valoare.

Același lucru, desenat. Să zicem că $p$ înseamnă că un punct e în cercul $A$ , iar $q$ , că e în cercul $B$ . Zona colorată e în afara lui $A \cup B$ , adică exact zona care e și în afara lui $A$ , și în afara lui $B$ .

Colorat: în afara lui $A \cup B$ , adică în afara lui $A$ și în afara lui $B$ .

Negăm „și”

Spui: „Am făcut tema la mate și la română.” Când ai minți? Dacă lipsește măcar una dintre ele.

Deci negația este: „Nu am făcut-o la mate sau nu am făcut-o la română.”

E regula de la medic, întoarsă: când negi un „și”, „și” devine „sau”, iar ambele părți se neagă. Adică $\overline{p \wedge q}$ înseamnă $\overline{p} \vee \overline{q}$ .

Verifică-te

Care este negația propoziției „

x > 0

și

x < 5

”?

Negăm „dacă… atunci”

„Dacă plouă, deschid umbrela.” Ca la promisiunea din lecția trecută, întrebăm: în ce situație am mințit?

Plouă?	Deschid umbrela?	„Dacă plouă, deschid umbrela”
da	da	adevărată
da	nu	falsă
nu	da	adevărată
nu	nu	adevărată

Am mințit doar dacă plouă și nu deschid umbrela. Deci negația este:

„Plouă și nu deschid umbrela.”

Notăm $p$ = plouă, $q$ = deschid umbrela. În simboluri, $\overline{p \to q}$ înseamnă $p \wedge \overline{q}$ : ipoteza are loc, iar concluzia nu.

Verifică-te

Care este negația propoziției „Dacă învăț, iau notă mare”?

Contrapoziția: aceeași propoziție, întoarsă

„Dacă plouă, strada e udă.”

Acum vezi că strada e uscată. Ce poți spune? Că nu plouă, altfel strada ar fi udă. Deci:

„Dacă strada nu e udă, atunci nu plouă.”

Cele două propoziții spun același lucru. Cu $p$ : „plouă” și $q$ : „strada e udă”, a doua este ${\overline{q} \to \overline{p}}$ și se numește contrapoziția lui ${p \to q}$ .

$p$	$q$	$p \to q$	$\overline{q}$	$\overline{p}$	${\overline{q} \!\to\! \overline{p}}$
1	1	1	0	0	1
1	0	0	1	0	0
0	1	1	0	1	1
0	0	1	1	1	1

Coloanele lui

p \to q

și

\overline{q} \to \overline{p}

sunt identice: 1, 0, 1, 1.

Cum scrie manualul

Manualul numește tautologii enunțurile adevărate pentru orice valori de adevăr ale propozițiilor din care sunt formate, iar contradicții formulele false pentru orice valori. Când între două formule apare

\leftrightarrow

și totul e o tautologie, cele două formule au mereu aceeași valoare, ca în tabelele din această lecție. Manualul dă opt exemple de tautologii:

1. Legea dublei negații: $\overline{\overline{p}} \leftrightarrow p$

2. Legile lui De Morgan: ${\overline{p \vee q} \leftrightarrow \overline{p} \wedge \overline{q}}$ și ${\overline{p \wedge q} \leftrightarrow \overline{p} \vee \overline{q}}$

3. Negarea implicației: $\overline{p \to q} \leftrightarrow p \wedge \overline{q}$

4. Modus Ponens: ${[p \wedge (p \to q)] \to q}$

5. Contrapoziția: ${(p \to q) \leftrightarrow (\overline{q} \to \overline{p})}$

6. Tranzitivitatea: ${[(p \to q) \wedge (q \to r)] \to (p \to r)}$

7. Principiul terțului exclus: $p \vee \overline{p}$

8. Principiul necontradicției: $\overline{p \wedge \overline{p}}$

Două dintre ele nu au apărut mai sus. Modus Ponens: dacă știi că $p$ e adevărată și că $p \to q$ e adevărată, atunci știi că $q$ e adevărată. Tranzitivitatea: din $p \to q$ și $q \to r$ rezultă $p \to r$ , ca un lanț.

În manual vei vedea și $\Rightarrow$ în loc de $\to$ , $\Leftrightarrow$ în loc de $\leftrightarrow$ , $\neg p$ sau „non $p$ ” în loc de $\overline{p}$ . Înseamnă același lucru.