Chap 1 - Logique et raisonnements - Démos PDF

BA AT AG Sa br in e Chapitre 1 – Logique et raisonnements – Démos TC H ———————————————————————– pl ai re de ———————————————————————– in e TC H AT AG BA Ex em ECG1 - Antoine Lagarde de Sa br Proposition (Opérations avec ET et OU) 2. (Associativité de ET) P et (Q et R) ≡ (P et Q...

BA AT AG Sa br in e Chapitre 1 – Logique et raisonnements – Démos TC H ———————————————————————– pl ai re de ———————————————————————– in e TC H AT AG BA Ex em ECG1 - Antoine Lagarde de Sa br Proposition (Opérations avec ET et OU) 2. (Associativité de ET) P et (Q et R) ≡ (P et Q) et R pl P ou (Q ou R) ≡ (P ou Q) ou R P ou Q ≡ Q ou P 4. (Commutativité de ET) P et Q ≡ Q et P AT AG 3. (Commutativité de OU) BA Ex em 1. (Associativité de OU) ai re Soient P, Q et R trois propositions. P ou (Q et R) ≡ (P ou Q) et (P ou R) 6. (Distributivité de ET sur OU) P et (Q ou R) ≡ (P et Q) ou (P et R) re de Sa br in e TC H 5. (Distributivité de OU sur ET) ai On démontre tout ceci avec des tables logiques : on vérifie à l’aide d’un tableau que les deux propositions sont toutes deux vraies ou em pl toutes deux fausses selon que P, Q et R soient vraies ou fausses. On note V (resp. F) les propositions vraies (resp. fausses). P Q P ou Q Q ou P V V V V V F V V F V V V F F F F pl ai re de Sa br in e TC H AT AG BA Ex Exemple avec le 3 : Ex em Puisque les deux dernières colonnes sont identiques, les propositions (P ou Q) et (Q ou P) sont donc logiquement équivalentes. H AT AG BA Le principe est le même pour toutes les autres propositions, mais c’est parfois fastidieux. Pour le 1 : 1 R (Q ou R) (P ou Q) P ou (Q ou R) (P ou Q) ou R V V V V V V V V F V V V V V F V F V V V V F F F F F F F V V F V V V V V F F F V V V F V V V V V V F F V V F V V AT AG BA Ex em pl ai re de Sa br in e TC H AT AG BA Q En regardant les deux dernières colonnes, on conclut alors que P ou (Q ou R) ≡ (P ou Q) ou R TC H Proposition re de Sa br in e La proposition (P ⇔ Q) est vraie si et seulement si P ≡ Q. pl ai Méthode 1 : en raisonnant par équivalence. Ex em Par définition de la relation d’équivalence, P ≡ Q signifie que ces propositions sont toutes les deux vraies ou toutes les deux fausses. BA Autrement dit, si P est vraie, Q doit être vraie, et si P est fausse, Q doit être fausse (et vice-versa par symétrie de P et Q). AG Ou encore : si P est vraie, Q est vraie, et si non P est vraie, non Q est vraie. AT C’est-à-dire qu’on a à la fois P ⇒ Q et non P ⇒ non Q. TC H Par contraposée, on a à la fois P ⇒ Q et Q ⇒ P. e Or par définition (P ⇔ Q) ≡ ((P ⇒ Q) et (P ⇐ Q)). Sa br in D’où le résultat. de Méthode 2 : en revenant à la définition des implications (beaucoup plus pénible). ai re Par définition (P ⇔ Q) signifie ((P ⇒ Q) et (P ⇐ Q)). em pl En revenant à la définition de l’implication, cela équivaut donc à ((non P ou Q) et (P ou non Q)). (P ⇔ Q) ≡ (non P ou Q) et (P ou non Q) ≡ (non P ou P) et (P ou non P) TC H AT AG BA Ex (⇐) Si P ≡ Q, alors on peut remplacer Q par P. On a donc : br in e Or (non P ou P) est toujours vraie par principe du tiers exclu. Puisque VRAI ET VRAI reste VRAI, alors (P ⇔ Q) est vraie. Sa (⇒) Si (P ⇔ Q) est vraie, alors par définition ((non P ou Q) et (P ou non Q)) est vraie. re de Donc (non P ou Q) est vraie ainsi que (P ou non Q)), par propriété du ET. pl ai Ainsi on a deux choses : Ex em (1) non P est vraie ou Q est vraie, autrement dit P est fausse ou Q est vraie. AG BA (2) P est vraie ou non Q est vraie, autrement dit P est vraie ou Q est fausse. AT H P Il faut vérifier ces deux propositions. Procédons par disjonction de cas : • Si P est vraie, P ne peut pas être fausse (principe du tiers exclu). Pour que (1) soit vérifiée, il faut alors que Q soit vraie. • De même, si P est fausse, P ne peut pas être vraie. Pour que (2) soit vérifiée, il faut alors que Q soit fausse. On a bien montré que soit les propositions P et Q sont vraies, soit elles sont fausses. Par définition de la relation d’équivalence, on a donc P ≡ Q. 2 Proposition (Opérations) 1. P ⇔ Q ≡ Q ⇔ P BA 2. non(P ⇒ Q) ≡ P et non(Q). Sa br in e TC H AT AG 3. non(P ⇔ Q) ≡ (P et non(Q)) ou (non(P) et Q). 1. Ici, il n’est pas nécessaire de se ramener à la définition de l’implication : de P ⇔ Q ≡ (P ⇒ Q) et (Q ⇒ P) pl ai re ≡ (Q ⇒ P) et (P ⇒ Q) par commutativité du ET Ex em ≡ Q⇔P AT AG BA 2. On a non(P ⇒ Q) ≡ non(non P ou Q) ≡ P et non(Q) H 3. Par définitions et opérations élémentaires : e TC non(P ⇔ Q) ≡ non ((P ⇒ Q) et (Q ⇒ P)) br in ≡ non ((non P ou Q) et (non Q ou P)) de Sa ≡ non(non P ou Q) ou non(non Q ou P) pl ai re ≡ (P et non Q) ou (non P et Q) Ex em Proposition (Contraposée) TC H AT AG BA L’implication (P ⇒ Q) est équivalente à sa contraposée (non Q ⇒ non P). br in e Par définition de l’implication et opérations élémentaires : ≡ Q ou non P par double négation ≡ non P ou Q par commutativité du OU ≡ P⇒Q par définition de l’implication H AT AG BA Ex em pl ai re de Sa br in e TC H AT AG BA Ex em pl ai re de Sa non Q ⇒ non P ≡ non(non Q) ou non P 3