Premiers éléments de logique mathématique - Exercice 1

On a :
$$\begin{array}{|c|c|c|} \hline P & Q & P \Longrightarrow Q \\ \hline V & V & V \\ \hline V & F & F \\ \hline F & V & V \\ \hline F & F & V \\ \hline\end{array}$$
On a également la table de vérité suivante :
$$\begin{array}{|c|c|c|c|} \hline P & Q & \neg P & \neg Q \\ \hline V & V & F & F \\ \hline V & F & F & V \\ \hline F & V & V & F \\ \hline F & F & V & V\\ \hline\end{array}$$
En faisant usage des deux tables de vérités précédentes, on peut donc construire la table de vérité suivante :
$$\begin{array}{|c|c|c|c|c|} \hline P & Q & \neg Q & \neg P & \neg Q \Longrightarrow \neg P \\ \hline V & V & F & F & V \\ \hline V & F & V & F & F\\ \hline F & V & F & V & V \\ \hline F & F & V & V & V \\ \hline\end{array}$$
On constate alors que :
$$\begin{array}{|c|c|c|c|} \hline P & Q & P \Longrightarrow Q & \neg Q \Longrightarrow \neg P \\ \hline V & V & V & V \\ \hline V & F & F & F \\ \hline F & V & V & V \\ \hline F & F & V & V \\ \hline\end{array}$$
Les deux dernières colonnes étant identiques, on a donc bien démontrer l'équivalence entre ces deux colonnes. Donc :
$${\color{red}{\boxed{(P \Longrightarrow Q) \Longleftrightarrow (\neg Q \Longrightarrow \neg P)}}}$$

On a :
$$\begin{array}{|c|c|c|c|} \hline P & Q & P \wedge Q & \neg (P \wedge Q) \\ \hline V & V & V & F \\ \hline V & F & F & V \\ \hline F & V & F & V \\ \hline F & F & F & V \\ \hline\end{array}$$
Puis, on a également :
$$\begin{array}{|c|c|c|c|c|} \hline P & Q & \neg P & \neg Q & \neg P \vee \neg Q \\ \hline V & V & F & F & F \\ \hline V & F & F & V & V \\ \hline F & V & V & F & V \\ \hline F & F & V & V & V \\ \hline\end{array}$$
On constate alors que :
$$\begin{array}{|c|c|c|c|} \hline P & Q & \neg (P \wedge Q) & \neg P \vee \neg Q \\ \hline V & V & F & F \\ \hline V & F & V & V \\ \hline F & V & V & V \\ \hline F & F & V & V \\ \hline\end{array}$$
Les deux dernières colonnes étant identiques, on a donc bien démontrer l'équivalence entre ces deux colonnes. Donc :
$${\color{red}{\boxed{\neg (P \wedge Q) \Longleftrightarrow (\neg P \vee \neg Q)}}}$$

On a :
$$\begin{array}{|c|c|c|c|} \hline P & Q & P \Longrightarrow Q & \neg (P \Longrightarrow Q) \\ \hline V & V & V & F \\ \hline V & F & F & V \\ \hline F & V & V & F \\ \hline F & F & V & F \\ \hline\end{array}$$
On a également la table de vérité suivante :
$$\begin{array}{|c|c|c|c|} \hline P & Q & \neg Q & P \wedge \neg Q \\ \hline V & V & F & F \\ \hline V & F & V & V \\ \hline F & V & F & F \\ \hline F & F & V & F \\ \hline\end{array}$$
On constate alors que :
$$\begin{array}{|c|c|c|c|} \hline P & Q & \neg (P \Longrightarrow Q) & P \wedge \neg Q \\ \hline V & V & F & F \\ \hline V & F & V & V \\ \hline F & V & F & F \\ \hline F & F & F & F \\ \hline\end{array}$$
Les deux dernières colonnes étant identiques, on a donc bien démontrer l'équivalence entre ces deux colonnes. Donc :
$${\color{red}{\boxed{\neg (P \Longrightarrow Q) \Longleftrightarrow (P \wedge \neg Q)}}}$$

On a :
$$\begin{array}{|c|c|c|c|} \hline P & Q & P \Longrightarrow Q & P \wedge \left(P \Longrightarrow Q\right) \\ \hline V & V & V & V \\ \hline V & F & F & F \\ \hline F & V & V & F \\ \hline F & F & V & F \\ \hline\end{array}$$
On a donc également la table de vérité suivante (la dernière colonne se déduit de celle de l'implication) :
$$\begin{array}{|c|c|c|} \hline P \wedge \left(P \Longrightarrow Q\right) & Q & (P \wedge \left(P \Longrightarrow Q\right)) \Longrightarrow Q \\ \hline V & V & V \\ \hline F & F & V \\ \hline F & V & V \\ \hline F & F & V \\ \hline\end{array}$$
On constate que la dernière colonne présente la valeur de vérité vraie $$(V)$$ dans tous les cas. C'est donc une tautologie. On a donc bien montré la règle du détachement (ou règle d'inférence, ou encore règle du modus ponens) :
$${\color{red}{\boxed{(P \wedge \left(P \Longrightarrow Q\right)) \Longrightarrow Q}}}$$

On a :
$$\begin{array}{|c|c|c|} \hline P & Q & P \Longrightarrow Q \\ \hline V & V & V \\ \hline V & F & F \\ \hline F & V & V \\ \hline F & F & V \\ \hline\end{array}$$
Puis, on a également :
$$\begin{array}{|c|c|c|c|} \hline P & \neg P& Q & \neg P \vee Q \\ \hline V & F & V & V \\ \hline V & F & F & F \\ \hline F & V & V & V \\ \hline F & V & F & V \\ \hline\end{array}$$
On a alors :
$$\begin{array}{|c|c|c|c|} \hline P & Q & P \Longrightarrow Q & \neg P \vee Q \\ \hline V & V & V & V \\ \hline V & F & F & F\\ \hline F & V & V & V \\ \hline F & F & V & V\\ \hline\end{array}$$
Les deux dernières colonnes étant identiques, on a donc bien démontrer l'équivalence entre ces deux colonnes. Donc :
$${\color{red}{\boxed{ \left(P \Longrightarrow Q\right) \Longleftrightarrow (\neg P \vee Q) }}}$$