Langage de la logique et des ensembles

Pour vérifier que l'on sait faire - Exercice 1

50 min
75
Un exercice plus difficile.
Question 1
Par la méthode demandée, démontrer l'équivalence proposée.

PP, QQ et RR sont trois assertions. En utilisant les tables de vérités, démontrer que l'on a l'équivalence suivante :
((P¬Q)(¬(R¬Q)))(P(¬(QR)))\big( \left( P \wedge \neg Q \right) \wedge (\neg \left( R \wedge \neg Q \right)) \big) \Longleftrightarrow \big( P \wedge ( \neg \left( Q \vee R \right) ) \big)

Correction
On a :
PQPQVVVVFFFVFFFF\begin{array}{|c|c|c|} \hline P & Q & P \wedge Q \\ \hline V & V & V \\ \hline V & F & F \\ \hline F & V & F \\ \hline F & F & F \\ \hline\end{array}
Donc :
P¬QP¬QVFFVVVFFFFVF\begin{array}{|c|c|c|} \hline P & \neg Q & P \wedge \neg Q \\ \hline V & F & F \\ \hline V & V & V \\ \hline F & F & F \\ \hline F & V & F \\ \hline\end{array}
Dans cette dernière table de vérité, en remplaçant PP par RR, on en déduit immédiatement que :
R¬QR¬Q¬(R¬Q)VFFVVVVFFFFVFVFV\begin{array}{|c|c|c|c|} \hline R & \neg Q & R \wedge \neg Q & \neg \left( R \wedge \neg Q \right) \\ \hline V & F & F & V \\ \hline V & V & V & F \\ \hline F & F & F & V \\ \hline F & V & F & V\\ \hline\end{array}
On en déduit alors que :
PQRP¬Q¬(R¬Q)(P¬Q)(¬(R¬Q))VVVFVFVVFFVFVFVVFFVFFVVVFVVFVFFVFFVFFFVFFFFFFFVF\begin{array}{|c|c|c|c|c|c|} \hline P & Q & R & P \wedge \neg Q & \neg \left( R \wedge \neg Q \right) & \left( P \wedge \neg Q \right) \wedge (\neg \left( R \wedge \neg Q )\right) \\ \hline V & V & V & F & V & F \\ \hline V & V & F & F & V & F \\ \hline V & F & V & V & F & F \\ \hline V & F & F & V & V & V \\ \hline F & V & V & F & V & F \\ \hline F & V & F & F & V & F \\ \hline F & F & V & F & F & F \\ \hline F & F & F & F & V & F \\ \hline \end{array}
Puis, on a également :
PQRQR¬(QR)P(¬(QR))VVVVFFVVFVFFVFVVFFVFFFVVFVVVFFFVFVFFFFVVFFFFFFVF\begin{array}{|c|c|c|c|c|c|} \hline P & Q & R & Q \vee R & \neg \left( Q \vee R \right) & P \wedge (\neg \left( Q \vee R \right)) \\ \hline V & V & V & V & F & F \\ \hline V & V & F & V & F & F \\ \hline V & F & V & V & F & F \\ \hline V & F & F & F & V & V \\ \hline F & V & V & V & F & F \\ \hline F & V & F & V & F & F \\ \hline F & F & V & V & F & F \\ \hline F & F & F & F & V & F \\ \hline \end{array}
On a donc la table de vérité de synthèse suivante :
PQR(P¬Q)(¬(R¬Q))P(¬(QR))VVVFFVVFFFVFVFFVFFVVFVVFFFVFFFFFVFFFFFFF\begin{array}{|c|c|c|c|c|} \hline P & Q & R & \left( P \wedge \neg Q \right) \wedge (\neg \left( R \wedge \neg Q )\right) & P \wedge (\neg \left( Q \vee R \right)) \\ \hline V & V & V & F & F \\ \hline V & V & F & F & F \\ \hline V & F & V & F & F \\ \hline V & F & F & V & V \\ \hline F & V & V & F & F \\ \hline F & V & F & F & F \\ \hline F & F & V & F & F \\ \hline F & F & F & F & F \\ \hline \end{array}
On constate que les deux dernières colonnes ont les mêmes vérités, donc elles sont équivalentes. On a donc :
((P¬Q)(¬(R¬Q)))(P(¬(QR))){\color{red}{\boxed{ \big( \left( P \wedge \neg Q \right) \wedge (\neg \left( R \wedge \neg Q \right)) \big) \Longleftrightarrow \big( P \wedge ( \neg \left( Q \vee R \right) ) \big) }}}
Question 2

PP, QQ et RR sont trois assertions. En n'utilisant pas les tables de vérités, démontrer que l'on a l'équivalence suivante :
((P¬Q)(¬(R¬Q)))(P(¬(QR)))\big( \left( P \wedge \neg Q \right) \wedge ( \neg \left( R \wedge \neg Q \right) ) \big) \Longleftrightarrow \big( P \wedge (\neg \left( Q \vee R \right) )\big)

Correction
On a :
(P¬Q)(¬(R¬Q))(P¬Q)(¬R¬(¬Q))\left( P \wedge \neg Q \right) \wedge ( \neg \left( R \wedge \neg Q \right) ) \Longleftrightarrow \left( P \wedge \neg Q \right) \wedge ( \neg R \vee \neg(\neg Q) )
Or on sait que ¬(¬Q)Q\neg(\neg Q) \Longleftrightarrow Q. Donc :
(P¬Q)(¬(R¬Q))(P¬Q)(¬RQ)\left( P \wedge \neg Q \right) \wedge ( \neg \left( R \wedge \neg Q \right) ) \Longleftrightarrow \left( P \wedge \neg Q \right) \wedge ( \neg R \vee Q )
De plus, on a :
(P¬Q)(¬RQ)((P¬Q)¬R)((P¬Q)Q)\left( P \wedge \neg Q \right) \wedge ( \neg R \vee Q ) \Longleftrightarrow (\left( P \wedge \neg Q \right) \wedge \neg R) \vee (\left( P \wedge \neg Q \right) \wedge Q)
Mais on a :
((P¬Q)¬R)((P¬Q)Q)(P¬Q¬R)(P¬QQ)(\left( P \wedge \neg Q \right) \wedge \neg R) \vee (\left( P \wedge \neg Q \right) \wedge Q) \Longleftrightarrow (P \wedge \neg Q \wedge \neg R) \vee (P \wedge \neg Q \wedge Q)
L'assertion ¬QQ\neg Q \wedge Q est toujours fausse (F)(F), et de fait P¬QQP \wedge \neg Q \wedge Q sera donc, également, toujours fausse (F)(F).
Dans le cas de la disjonction logique (symbolisé par \vee), si dans la proposition XYX \vee Y la seconde assertion YY est de vérité fausse (F)(F) alors XYX \vee Y à la même vérité que celle de la première assertion XX. Donc, on en déduit alors que :
((P¬Q)¬R)((P¬Q)Q)(P¬Q¬R)(\left( P \wedge \neg Q \right) \wedge \neg R) \vee (\left( P \wedge \neg Q \right) \wedge Q) \Longleftrightarrow (P \wedge \neg Q \wedge \neg R)
Avec :
(P¬Q¬R)(P¬(QR))(P \wedge \neg Q \wedge \neg R) \Longleftrightarrow (P \wedge \neg(Q \vee R) )
Finalement, on a donc bien montré que :
((P¬Q)(¬(R¬Q)))(P(¬(QR))){\color{red}{\boxed{ \big( \left( P \wedge \neg Q \right) \wedge (\neg \left( R \wedge \neg Q \right)) \big) \Longleftrightarrow \big( P \wedge ( \neg \left( Q \vee R \right) ) \big) }}}
Dans cette question, on a fait usage exclusivement des lois de MorganMorgan.