Metoda reducerii la absurd

Metoda de demonstraţie prin reducere la absurd se bazează pe echivalenţa:

\displaystyle \left ( \neg p\rightarrow \neg q \right )\leftrightarrow \left ( q\rightarrow p \right )

care este o tautologie (este adevărată oricare ar fi valorile de adevăr ale propoziţiilor componente).

Etape:

\displaystyle 1^{\circ} Se presupune că propoziţia contrară celei ce trebuie demonstrate este adevărată \displaystyle \left (\neg p \right ) .

\displaystyle 2^{\circ} Prin raţionamente logice se obţine o concluzie ce contrazice ipoteza iniţială sau o teoremă cunoscută \displaystyle \left ( \neg p\rightarrow \neg q \right ) .

\displaystyle 3^{\circ} Prin urmare, propoziţia iniţială trebuie să fie adevărată \displaystyle \left (q \rightarrow p \right ) .


Exemplu:

Arătaţi că mulţimile \displaystyle A=\left \{ 3n+1\, |\, n\in \mathbb{N} \right \} şi \displaystyle B=\left \{ 6m-1\, |\, m\in \mathbb{N} \right \} sunt disjuncte.

Se presupune că propoziţia iniţială nu este adevărată, iar mulţimile \displaystyle A şi \displaystyle B nu sunt disjuncte.

În acest caz, cele două mulţimi au cel puţin un element comun:

\displaystyle A\cap B\neq \varnothing

Deci trebuie să existe un număr natural \displaystyle t , astfel încât

\displaystyle 3t+1=6t-1

Prin urmare

\displaystyle 3t=2\; \Rightarrow \; t=\frac{2}{3}\notin \mathbb{N}

Numărul \displaystyle t astfel obţinut nu este, însă, număr natural, deci cele două mulţimi nu pot avea nici un element comun, adică este adevărat că \displaystyle A şi \displaystyle B sunt disjuncte.