Connecteurs logique
Définition : Conjonction "et"
On appelle conjonction de deux propositions P et Q, la proposition notée « \(P \wedge Q\) » qui est vraie, si \(P\) et \(Q\) sont vraies et fausse dans les autres cas.
\(P\) | \(Q\) | \(P\wedge Q\) |
1 | 1 | 1 |
1 | 0 | 0 |
0 | 1 | 0 |
0 | 0 | 0 |
Remarque :
Deux propositions sont incompatibles si leur conjonction est fausse.
Définition : Disjonction "ou"
On appelle disjonction la proposition P ou Q et on la note « \(P \vee Q\) ». Elle est vraie si l'une des deux propositions est vraie.
\(P\) | \(Q\) | \(P\vee Q\) |
1 | 1 | 1 |
1 | 0 | 1 |
0 | 1 | 1 |
0 | 0 | 0 |
Définition : Implication
Soient P et Q deux propositions données, on définit la
proposition ( P implique Q) notée ( \(P\Rightarrow Q\)) par \(\left( \overline{p}\vee q\right)\).
L'implication est fausse dans le seul cas où P est vraie et Q est fausse.
\(P\) | \(Q\) | \(P \Rightarrow Q\) |
1 | 1 | 1 |
1 | 0 | 0 |
0 | 1 | 1 |
0 | 0 | 1 |
Définition : Équivalence
Soient P et Q deux propositions données, on définit la proposition ( \(P\ \Leftrightarrow Q\)) dite aussi ( P est équivalente à Q) par (\(\left( P\Rightarrow Q\right) \wedge \left( Q \Rightarrow P\right)\)).
En traçant la table de vérité on remarque que l'équivalence est vraie si et seulement si P et Q sont vraies en même temps ou fausses en même temps.
\(P\) | \(Q\) | \(P \Rightarrow Q\) |
1 | 1 | 1 |
1 | 0 | 0 |
0 | 1 | 0 |
0 | 0 | 1 |
Remarque :
Deux propositions sont équivalentes si elles ont une même table de vérité.
Une tautologie est une proposition qui est toujours vraie.
Une contradiction est une proposition qui est toujours fausse.
Fondamental : Proposition :
Soient \(P,Q\) et \(R\) trois propositions données, nous avons alors les propriétés suivantes
\(\overline{\overline{P}}\Leftrightarrow P\).
\(( P\ \wedge \ P)\ \Leftrightarrow P\).
\(( P\ \vee \ P)\ \Leftrightarrow P\).
\(( P\ \wedge\ Q)\ \Leftrightarrow \ ( Q\ \wedge \ P)\) commutativité du connecteur \(\wedge\).
\(( P\ \vee\ Q)\ \Leftrightarrow \ ( Q\ \vee \ P)\) commutativité du connecteur \(\vee\).
\(\left[ (P\wedge Q)\wedge R\right] \Leftrightarrow \left[ P\wedge \left( Q\wedge R\right) \right]\) associativité du connecteur \(\wedge\).
\(\left[ (P\vee Q)\vee R\right] \Leftrightarrow \left[ P\vee \left( Q\vee R\right) \right]\) associativité du connecteur \(\vee\).
\(\overline{(P\wedge Q)}\Leftrightarrow \left( \overline{P}\vee \overline{Q}\right)\) loi de Morgan.
\(\overline{(P\vee Q)}\Leftrightarrow \left( \overline{P}\wedge \overline{Q}\right)\) loi de Morgan.
\(\left( p\Rightarrow q\right) \Leftrightarrow \left( \overline{q} \Rightarrow \overline{p}\right)\).
Pour démontrer ces propriétés, il suffit de tracer une table de vérité, à titre d'exemple nous allons démontrer la première loi de Morgan
\(P\) | \(Q\) | \(\overline{P} \) | \(\overline{Q}\) | \(P\wedge Q \) | \( \overline{(P\wedge Q)}\) | \( \left( \overline{P}\vee \overline{Q}\right)\) |
1 | 1 | 0 | 0 | 1 | 0 | 0 |
1 | 0 | 0 | 1 | 0 | 1 | 1 |
0 | 1 | 1 | 0 | 0 | 1 | 1 |
0 | 0 | 1 | 1 | 0 | 1 | 1 |