20
Logique des propositions Fascicule principal Lucien Vinciguerra FEUILLE D'EXERCICES 1 Raisonnement en langue naturelle Exercice 1. Arguments valides ou non-valides (avec mes remerciements à Pascal Ludwig) Dites si les arguments suivants sont déductivement valides ou non. Justifiez votre réponse. S’ils ne le sont pas, donnez un contre-exemple. 1. Tout homme est mortel. Aucun mortel n’est parfait. Donc, aucun homme n’est parfait 2. La plupart des villes sont des endroits pollués. Tous les endroits pollués sont dangereux. Donc, la plupart des villes sont dangereuses. 3. Antoine croit que la planète Mars est rouge. La planète Mars est la quatrième planète du système solaire. Donc, Antoine croit que la quatrième planète du système solaire est rouge. 4. Si le gouvernement fait une bonne politique, les salaires augmentent, ou l’endettement de l’Etat diminue. Mais l’endettement de l’Etat ne diminue pas, et les salaires n’augmentent pas non plus. Donc, le gouvernement ne fait pas une bonne politique. 5. Tous les patrons fument le cigare. La plupart des fumeurs de cigares sont des hommes. Donc la plupart des patrons sont des hommes. 6. Si Pierre ou Antoine ne se souviennent plus de l’endroit où ils ont garé la voiture, ils ne rentreront pas avant le matin. Pierre ne se souvient plus de l’endroit où ils ont garé la voiture. Donc, ils ne rentreront pas avant le matin. 7. Les chauves-souris ont des ailes. Seuls les oiseaux ont des ailes. Donc les chauves- souris sont des oiseaux. 8. Toutes les étoiles sont des astres qui émettent de la lumière. Le soleil est un astre qui émet de la lumière. Donc, le soleil est une étoile. Exercice 2. Discutez la validité des arguments suivants. 1. Tous les députés sont riches. La plupart des gens riches ont une résidence secondaire. Donc la plupart des députés ont une résidence secondaire. 2. La plupart des cygnes sont des oiseaux blancs. La plupart des oiseaux blancs sont sauvages. Donc, la plupart des cygnes sont sauvages. 3. Si le parti dit qu’il faut interdire les manifestations, alors il faut interdire les manifestations. Le parti dit qu’il faut interdire les manifestations. Donc, il faut interdire les manifestations. 4. La réglementation actuelle ne permet pas à la police de faire face à une menace terroriste. Si celle-ci augmente, il faut donner plus de pouvoirs à la police. Mais selon le gouvernement, la menace terroriste augmente. Donc, il faut accroître les pouvoirs de la police. 5. Il ne faut pas faire le mal. Le mal qu’on fait aux criminels est un mal. Donc, il ne faut pas faire de mal aux criminels. 6. Les alchimistes croyaient qu’on peut changer le plomb en or. Mais les alchimistes n’étaient que des farfelus cupides. Et ils ne s’appuyaient sur aucune base scientifique. Donc, on ne peut pas changer le plomb en or. 7. - Présupposons que cette pierre ait été mise dans un grand feu, dont on l'ait retirée depuis quelque temps; donc cette pierre doit être encore chaude: or elle est chaude; par conséquent, elle a été mise au feu (Pascal, lettre du 29 octobre 1647 au père Noël). 1

Logique des propositions Fascicule ... - Université de Lilleperso.univ-lille3.fr/~lvinciguerra/propositions/fascicule_logique... · conclusion, c'est-à-dire lorsque la conclusion

Embed Size (px)

Citation preview

Page 1: Logique des propositions Fascicule ... - Université de Lilleperso.univ-lille3.fr/~lvinciguerra/propositions/fascicule_logique... · conclusion, c'est-à-dire lorsque la conclusion

Logique des propositions

Fascicule principalLucien Vinciguerra

FEUILLE D'EXERCICES 1

Raisonnement en langue naturelle

Exercice 1. Arguments valides ou non-valides (avec mes remerciements à Pascal Ludwig)

Dites si les arguments suivants sont déductivement valides ou non. Justifiez votre réponse.S’ils ne le sont pas, donnez un contre-exemple. 1. Tout homme est mortel. Aucun mortel n’est parfait. Donc, aucun homme n’est parfait 2. La plupart des villes sont des endroits pollués. Tous les endroits pollués sont dangereux. Donc, la plupart des villes sont dangereuses. 3. Antoine croit que la planète Mars est rouge. La planète Mars est la quatrième planète du système solaire. Donc, Antoine croit que la quatrième planète du système solaire est rouge. 4. Si le gouvernement fait une bonne politique, les salaires augmentent, ou l’endettement de l’Etat diminue. Mais l’endettement de l’Etat ne diminue pas, et les salaires n’augmentent pas non plus. Donc, le gouvernement ne fait pas une bonne politique. 5. Tous les patrons fument le cigare. La plupart des fumeurs de cigares sont des hommes. Donc la plupart des patrons sont des hommes. 6. Si Pierre ou Antoine ne se souviennent plus de l’endroit où ils ont garé la voiture, ils ne rentreront pas avant le matin. Pierre ne se souvient plus de l’endroit où ils ont garé la voiture. Donc, ils ne rentreront pas avant le matin. 7. Les chauves-souris ont des ailes. Seuls les oiseaux ont des ailes. Donc les chauves- souris sont des oiseaux. 8. Toutes les étoiles sont des astres qui émettent de la lumière. Le soleil est un astre qui émet de la lumière. Donc, le soleil est une étoile. Exercice 2. Discutez la validité des arguments suivants. 1. Tous les députés sont riches. La plupart des gens riches ont une résidence secondaire. Donc la plupart des députés ont une résidence secondaire. 2. La plupart des cygnes sont des oiseaux blancs. La plupart des oiseaux blancs sont sauvages. Donc, la plupart des cygnes sont sauvages. 3. Si le parti dit qu’il faut interdire les manifestations, alors il faut interdire les manifestations. Le parti dit qu’il faut interdire les manifestations. Donc, il faut interdire les manifestations. 4. La réglementation actuelle ne permet pas à la police de faire face à une menace terroriste. Si celle-ciaugmente, il faut donner plus de pouvoirs à la police. Mais selon le gouvernement, la menace terroriste augmente. Donc, il faut accroître les pouvoirs de la police. 5. Il ne faut pas faire le mal. Le mal qu’on fait aux criminels est un mal. Donc, il ne faut pas faire de mal aux criminels. 6. Les alchimistes croyaient qu’on peut changer le plomb en or. Mais les alchimistes n’étaient que des farfelus cupides. Et ils ne s’appuyaient sur aucune base scientifique. Donc, on ne peut pas changer le plomb en or.

7. - Présupposons que cette pierre ait été mise dans un grand feu, dont on l'ait retirée depuis quelque temps; donc cette pierre doit être encore chaude: or elle est chaude; par conséquent, elle a été mise au feu (Pascal, lettre du 29 octobre 1647 au père Noël).

1

Page 2: Logique des propositions Fascicule ... - Université de Lilleperso.univ-lille3.fr/~lvinciguerra/propositions/fascicule_logique... · conclusion, c'est-à-dire lorsque la conclusion

À retenir :• Un argument (ou raisonnement) est une suite de phrases dont les premières sont appelées

prémisses et la dernière (souvent précédée par « donc ») est la conclusion.• Un argument est valide lorsque la vérité des prémisses entraîne nécessairement la vérité de la

conclusion, c'est-à-dire lorsque la conclusion est vraie dans tous les cas (réels ou possibles) où les prémisses sont vraies.

• Un argument est non valide lorsque la situation précédente n’est pas vérifiée, c’est à dire lorsqu’il existe un cas possible où les prémisses sont vraies et la conclusion fausse.

• La validité d’un argument est indépendante de la vérité ou de la fausseté effective des prémisses. Ce que dit le fait qu’un argument est valide, c’est que SI les prémisses sont vraies, alors la conclusion doit l’être.

• La logique est la théorie de la manière dont la vérité se propage de phrases en phrases, c’est-à-dire de ce que veut dire le fait que la vérité de certaines phrases « entraîne nécessairement » la vérité d’autres phrases.

Exercice 3:Compléter les syllogismes suivants1- aucun B n'est A

tout C est B?

2- aucun B n'est Aquelque C est B?

3- tout B est Aquelque C est B?

4- tout B est Aquelque C n'est pas A?

5- tout B est Aquelque C n'est pas B?

6- aucun B n'est Atout C est A?

7- quelque A est Btout A est C

8- aucun B n'est A?quelque C n'est pas A

Exercice 4 (facultatif): déduire des 8 propositions suivantes a) à i) les cinq propositions 1 à 5, en mettanten évidence la forme du syllogisme utilisé:a- quelques femmes sont blondesb- tout amateur de chocolat est mineurc- quelques mineurs portent des lunettesd- les amateurs de cassoulet portent des lunettesf- aucune femme ne porte de lunettesg- aucune personne blonde n'aime le coq au vinh- tout amateur de chocolat est blondi- aucun mineur n'est de sexe féminin

1- aucune femme n'aime le cassoulet2- quelques femmes n'aiment pas le coq au vin3- quelques mineurs n'aiment pas le cassoulet4- aucune femme n'aime le chocolat5- personne n'aime le coq au vin et le chocolat

2

Page 3: Logique des propositions Fascicule ... - Université de Lilleperso.univ-lille3.fr/~lvinciguerra/propositions/fascicule_logique... · conclusion, c'est-à-dire lorsque la conclusion

Qu'est-ce qu'un syllogisme ? 1 - Un jugement a :

- un noyau de la forme : A est B. Par exemple homme est mortel.A et B sont deux notions : A est le sujet, B est l'attribut (ou le prédicat), « est » est la

copule.- une qualité : affirmatif ou négatif- une quantité : universel ou particulier

universel affirmatif : tout particulier affirmatif : certains (ou quelque)universel négatif : aucun particulier négatif : certains ... ne ... pas

exemple de jugement affirmatif particulier : quelque homme est mortel (ou certains hommes sont mortels).exemple de jugement affirmatif universel : tout homme est mortel.exemple de jugement négatif particulier : quelque homme n'est pas mortel.exemple de jugement négatif universel : aucun homme n'est mortel.

Un syllogisme est une suite de trois jugements, deux prémisses et une conclusion, comportant en tout trois notions reliées deux à deux dans chacun des jugements de manières différentes. Comme tout argument, un syllogisme peut être valide ou non valide.

Notion de vérifonctionnalité dans le langage des propositions:La logique des propositions a pour principe de décomposer toute proposition complexe en propositions élémentaires reliées par des signes particuliers, les connecteurs. Les propositions élémentaires peuvent être soit vraies, soient fausses. Cette logique s'appuie sur le principe de vérifonctionnalité : la vérité ou la fausseté d'une proposition complexe ne doit dépendre que de la vérité et de la fausseté des propositions élémentaires qui la composent. Il y a des connecteurs qui sont tels que le principe de vérifonctionnalité n'est pas vérifié lorsqu'ils interviennent dans une proposition complexe. Un connecteur est dit vérifonctionnel lorsqu'il vérifie le principe de vérifonctionnalité. Exemple :1- La connaissance de la vérité de p et de q ne me permet pas à elle seule de connaître la vérité ou la fausseté de « p parce que q ». Le connecteur « parce que » n'est pas vérifonctionnel.2- La connaissance de la vérité de p et de q me permet à elle seule de connaître la vérité ou la fausseté de « p et q », ainsi que de « p ou q ». Donc les connecteurs « et » et « ou » sont vérifonctionnels.

Exercice 5 : Transcrivez en calcul des propositions les énoncés suivants, en indiquant les propositions élémentaires par des lettres:

1. - S'il pleut, je prends un parapluie ou je reste à la maison2. - Pierre et Marie sont étudiants3. - Pierre et Marie sont mariés4. - Si Darius attaque par l'Est nous le prendrons à revers et nous appellerons du renfort.5. - Si Darius attaque par l'Est nous le prendrons à revers et je suis un bon stratège.6. - Il ne fait pas beau et je ne vais pas me promener ou je reste sous les arcades.7. - Il ne fait pas beau et je reste à la maison ou j'irai bronzer sur la plage.8. - Je partirai, à moins qu'il ne vienne9. - un concept est vide de contenu, sauf si un objet donné lui correspond dans l'intuition10. - le monde existe, à moins que je rêve ou qu'un malin génie me trompe.11. - les idées claires sont vraies seulement si Dieu n'est pas trompeur12. - Descartes dit que les idées claires sont vraies13. - Descartes dit que si Dieu n'est pas trompeur les idées claires sont vraies.14. - on ne devient pas un musicien accompli sans apprendre à lire les notes et jouer d'un instrument. 15. - pour que cette enveloppe ait été ouverte, il est nécessaire que Jean en ait été

3

Page 4: Logique des propositions Fascicule ... - Université de Lilleperso.univ-lille3.fr/~lvinciguerra/propositions/fascicule_logique... · conclusion, c'est-à-dire lorsque la conclusion

informé, à moins que Pierre ait oublié de la coller16. - si mon raisonnement est valide, je ne raterai pas mon exercice. Or, ou bien je rate mon exercice, ou bien la logique est facile. Et précisément la logique n'est pas facile. Donc mon raisonnement n'est pas valide.

Traduction d'un argument en langage des propositions :

On traduit séparément chaque prémisse et la conclusion, sans chercher à traduire l'ensemble de l'argument en une seule phrase. En revanche, on traduit par des lettres identiques les propositions élémentaires identiques dans des lignes différentes de l'argument.

Feuille 1, exercice1, n°4 :p : Le gouvernement fait une bonne politique ;q : Les salaires augmentent ;r : L'endettement de l'État diminue.

Traduction de l'argument : p→(q∨r )¬r∧¬q

donc ¬ p

Exercice 7 : Quel est le connecteur principal des formules suivantes ? Faites leur arbre syntaxique :(¬( p→q)→( p∨r ))

¬(( p∧q)→r )¬(¬(¬q→r )∨¬(r→ p))

Exercice 8 : indiquez quelles expressions ci-dessous sont des formules (au sens strict): faites l'arbre de chaque formule quand cela a un sens. Certaines sont-elles des formules au sens large. Rétablissez alors les parenthèses manquantes

1- r2- (( p∧q))3- ¬¬¬ p4- ( p→(( p→ p)→ p))→( p∨p)

5- ¬( p∧(q∧(r∧(s∧t))))6- ( p→q)→ r7- (¬(¬(¬ p)∨q)∨¬ p∨q)8- (¬(¬( p∨q))→(r→ s))

Exercice 9 : Les expressions ci-dessous sont-elles des formules ? Si oui, démontrez-le, sinon, expliquezpourquoi.1- (¬p∨(q→¬p))2- ((( p∨q)→¬p)∧q)3- ¬(¬(¬(r∨p)∧q)∧r )4- ¬(¬( p∨¬(q→s)))5- ((¬( pv r )∨(q∧(r∨p)))∨q)

4

Page 5: Logique des propositions Fascicule ... - Université de Lilleperso.univ-lille3.fr/~lvinciguerra/propositions/fascicule_logique... · conclusion, c'est-à-dire lorsque la conclusion

Construction formelle du langage pour le calcul des propositionspetit bréviaire

SYNTAXE

Langage-objet: c'est le langage formel dont on étudie les propriétés. Ce langage est décrit dans un « métalangage », qui est ici notre langage quotidien.

Alphabet ou symboles primitifs: ensemble des symboles élémentaires avec lesquels sont construits tous les objets (formules) du langage-objet. Ce sont: les connecteurs: ¬,∨ ,∧ ,→ , ; les parenthèses ouvrantes et fermantes ; les atomes : p, q, r, s, t, etc., en nombre indéfini.

Expression: une expression est une suite quelconque de symboles primitifs: pq )( rq par exemple.

Formule: une formule est une expression qui vérifie les propriétés suivantes: (i) un atome est une formule(ii) si A est une formule, alors ¬A est une formule.(iii) si A et B sont des formules, alors (A∨B) ,(A∧B)et (A→ B) sont des

formules.(iv) Toute formule l'est en vertu des règles précédentes.

Une telle définition est dite récursive : le terme à définir apparaît dans la définition sans que la définition soit pour autant circulaire, grâce à (i).

Propriété : Toute formule a un connecteur principal. Si ce connecteur principal est la négation (connecteur dit unaire), alors elle s’écrit sous la forme ¬A , et on appelle A la sous-formule principale. Si le connecteur principal est un connecteur binaire (l’un des trois autres), la formule s’écrit sous la forme (A∨B) ou (A∧B) ou (A→B) , et A et B sont les deux sous-formules principales. Cette écriture est unique, et le connecteur principal est donc unique.

Arbre d'une formule: c'est un arbre qui donne la structure de la formule à partir du connecteur principal et des sous-formules: ex: (¬ p→(r∨¬( p∧q)))

La profondeur d'une formule est le nombre d'étages de l'arbre. Ici 5.

5

Page 6: Logique des propositions Fascicule ... - Université de Lilleperso.univ-lille3.fr/~lvinciguerra/propositions/fascicule_logique... · conclusion, c'est-à-dire lorsque la conclusion

SÉMANTIQUE

Rappel en guise d'introduction : qu'est-ce qu'une fonction ? Une fonction est un procédé qui fait correspondre à chaque élément d'un ensemble (dit ensemble de

départ) un élément d'un autre ensemble (d'arrivée). On note f : A→Bx→ f ( x)

Ce procédé peut être donné – par une expression algébrique : par exemple f : x→ x 2 ;– par un graphique avec les valeurs de l'ensemble de départ en abscisse et celles de l'ensemble

d'arrivée en ordonnée ;– par des catalogues empiriques : par exemple la fonction qui à tout objet manufacturé associe son

code-barre ; – par une technique pratique, comme l'opération de mesure qui associe à un individu sa taille.

Vrai et Faux: ce sont deux objets supplémentaires, notés V et F. Ils n'appartiennent pas au langage-objet, mais au métalangage.

Assigner une valeur de vérité aux formules du langage objet, (dire par exemple p est vrai ou (q→ p) est faux, c'est fixer la valeur de la formule pour une distribution de valeurs de vérité. Définition 1 : une distribution de valeurs de vérité (dvv) est une fonction de l'ensemble des formules versl'ensemble à deux éléments {V, F}, qui a pour propriété que sa valeur pour une formule est caractérisée de manière unique par ses valeurs sur les atomes p, q, r, etc., au moyen des règles suivantes:

1- La table de vérité des connecteurs, qui définit la valeur de ¬ p ,( p∨q) ,( p∧q) ,( p→ q)pour une dvv quelconque en fonction de ses valeurs sur p et q (ou n'importe quel atome).

p q ( p∨q) ( p∧q) ( p→q) p ¬ pV V V V V V FV F V F F F VF V V F VF F F F V

2- Pour une dvv donnée dont on connait la valeur pour chaque atome, sa valeur pour une formulequelconque est déterminée au moyen de l'arbre syntaxique, en mettant les valeurs de la dvv pour les atomes au bout des branches, puis en remontant le long des branches en utilisant les tables de vérité des connecteurs.(Il existe une définition plus rigoureuse, qui est récursive comme la définition des formules)

Ex : formule (( p∨q)→ r ) . On recherche sa valeur pour la dvv δ telle que δ (p)= F, δ (q)=V, δ (r)=F

Définition 2 :Table de vérité d'une formule quelconque: c'est la détermination des valeurs de la formule

6

Page 7: Logique des propositions Fascicule ... - Université de Lilleperso.univ-lille3.fr/~lvinciguerra/propositions/fascicule_logique... · conclusion, c'est-à-dire lorsque la conclusion

pour toutes les dvv, chaque dvv étant représentée par une ligne de la table, correspondant à ses valeurs sur les atomes. Pour une formule avec n atomes, il y a 2n dvv différentes, donc 2n lignes dans la table de vérité.

Définition 3 : une dvv δ satisfait une formule A lorsque δ(A)= V.

Une formule est satisfiable lorqu'il existe au moins une dvv qui la satisfait. Elle est contingente lorsqu'il existe à la fois des dvv qui la satisfont et des dvv qui ne la satisfont pas.

Définition 4 : une tautologie est une formule satisfaite par toutes les dvv. Cela correspond au fait que « sa table de vérité ne comporte que des V ». On note A pour «⊨ A est une tautologie ».

Définition 5:deux formules sont tautologiquement équivalentes lorsqu'elles ont les mêmes valeurs pour toutes les dvv. Cela correspond au fait qu'elles ont la même table de vérité (on note A eq B ).

Théorème: A eq B si et seulement si ⊨ ((A→B)∧(B→ A))

rem: " " et "eq" ne sont pas des symboles du langage-objet, mais du métalangage. ⊨

Définition 6: Un ensemble de formules A1, …, An, a pour conséquence logique B si et seulement si toute dvv qui satisfait simultanément A1, …, et An, satisfait aussi B. On note: A1, …, An, B⊨Cela se traduit par le fait que si on fait les tables de vérité des formules, B est vrai pour toutes les lignes où A1, …, An sont simultanément vraies.

La notion de conséquence logique formalise le concept d'argument valide : « A1, …, et An donc B » est valide signifie que A1, …, An B. A⊨ 1, …, An sont les prémisses, B est la conclusion.

Théorème sémantique de la déduction: A1, …, An a pour conséquence logique B si et seulement si(A1∧…∧An)→B est une tautologie

Autrement dit : A1,…, An B si et seulement si ⊨ ⊨ (A1∧…∧An)→B

Si les prémisses sont réduites à une seule formule A, on a :A a pour conséquence logique B ssi toute dvv qui satisfait A satisfait B.Dans ce cas, le théorème sémantique de la déduction est : A B ssi ⊨ A→ B est une tautologie.

7

Page 8: Logique des propositions Fascicule ... - Université de Lilleperso.univ-lille3.fr/~lvinciguerra/propositions/fascicule_logique... · conclusion, c'est-à-dire lorsque la conclusion

Les principaux schémas de tautologies et équivalences du calcul despropositions

Aeq A Identité

¬¬Aeq A double négation

A∨¬A tiers exclu

¬(A∧¬A) non contradiction

(A∨A)eq A

(A∧A)eq A

Associativité:

(A∧(B∧C ))eq((A∧B)∧C )

(A∨(B∨C ))eq((A∨B)∨C )

Commutativité:

(A∨B)eq (B∨A)

(A∧B)eq (B∧A)

Distributivité:

A∧B∨Ceq A∧B∨A∧C

A∨B∧C eq A∨B ∧ A∨C

Interdéfinissabilité des connecteurs (lois de De Morgan):

¬(A∧B)eq (¬A∨¬B)

¬(A∨B)eq (¬A∧¬B)

(A→B)eq (¬A∨B)

¬(A→ B)eq (A∧¬B)

Lois de l'implication:

A B∧A B modus ponens

A B∧¬B¬A modus tollens

AB A verum...

¬A A B ex false...

(A→B)eq (¬B→¬A)

A B∧BC AC

ABC eq A∧BC

Théorème de substitution : Si A est une tautologie, alors la formule obtenue en remplaçant toutes les occurrences d'un même atome dans A par une formule quelconque est aussi une tautologie (idem pour les équivalences ).

Ex : ( p∨q)→(q→( p∨q)) est une tautologie car on obtient la formule à partir de ... ?

Théorème de remplacement :Si A eq B et si A est une sous-formule de C, alors la formule obtenue en remplaçant dans C une ou plusieurs occurrences de A par B est équivalente à C.

Ex : ¬¬q→ p eq q→ p car ... ?

8

Page 9: Logique des propositions Fascicule ... - Université de Lilleperso.univ-lille3.fr/~lvinciguerra/propositions/fascicule_logique... · conclusion, c'est-à-dire lorsque la conclusion

Démonstration qu'une formule est conséquence logique de trois autres : méthode pratique par les tables de vérité.

Soit 4 formules A, B, C et D. Examinons si A, B, C D (A,B,C a pour conséquence logique D)⊨On regarde le nombre total des atomes dans l'ensemble des quatre formules. Imaginons que ces formulescomportent en tout 3 atomes p, q, r. On fait les tables de vérité à 8 lignes de A, B, C. On regarde les lignes où A, B et C sont toutes les 3 vraies et pour ces ligne on évalue aussi si D est vraie ou fausse. S'il y a une ligne où A, B, C sont toutes vraies et où D est fausse, D N'EST PAS conséquence logique de A, B, C. S'il n'y en a pas, D est conséquence logique.

Exemple 1 :p q r A B C D

V V V V V F

V V F F F F

V F V V V V V

V F F F V F

F V V V F V

F V F V V V F

F F V V V F

F F F V V V VÀ la ligne 6, A, B, C sont vraies et D fausse. D n'est pas conséquence logique

Exemple 2 :p q r A B C D

V V V V V F

V V F F F F

V F V F F V

V F F F V F

F V V V F V

F V F F F F

F F V V V F

F F F V V FIl n'y a pas de ligne où A, B, C soient toutes vraies. D est conséquence logique

Exemple 3 :p q r A B C D

V V V V V V V

V V F F V F

V F V V V V V

V F F F V V

F V V F F V

F V F V V V V

F F V V V F

F F F V V V VÀ toutes les lignes où A, B, C sont vraies, c'est-à-dire 1, 3, 6, 8, D est aussi vraie. D est conséquence logique

9

Page 10: Logique des propositions Fascicule ... - Université de Lilleperso.univ-lille3.fr/~lvinciguerra/propositions/fascicule_logique... · conclusion, c'est-à-dire lorsque la conclusion

FEUILLE D'EXERCICES 3

Exercice 1 : construire l'arbre syntaxique des formules suivantes. Pour les 3 premières, démontrez qu'elles sont des formules.

1- (((t q) r)→ s)∧ ∧ ⅂⅂2- ( ((t t) s) q)⅂ ∨ ∨ ∨⅂3- (p ((s t) q))∨ ∧⅂ ∧⅂4- ((r→( t→p)) ( p t))⅂ ⅂ ∧ ⅂ ∨5- ( (t s) ((q→ s) s))⅂ ∨ ∧ ⅂ ∧6- (r→( t ((q→r) q)))⅂ ∧ ∧

7- ((q→(r→q)) (s (q q)))∧ ∨⅂ ∧8- ( s ((p→s)→(((r r)→s)→ q)))⅂ ⅂⅂ ∨ ∨ ⅂9- ( (s→t) (( (s t) p)→(q→r)))⅂ ∧ ⅂ ∧ ∧10- (((t p) r)→ ( (q t) s))∨ ∧ ⅂ ⅂ ∧ ∨11- (((q t)→p) ( p t))∧ ∧⅂ ⅂ ∨

Exercice 2 : un mauvais génie a supprimé toutes les parenthèses des formules, ce qui donne les expressions ci-dessous. Quelles pouvaient être les formules d’origine (attention, il y a un intrus) ?

1. p→¬q∨r

2. ¬q∨r→ s

3. ¬¬q→ r∨s

4. p∨¬q∨¬s→ p

5. q→ s∨¬¬q∧p

6. ¬q¬r → s∨ p

Exercice 3 : notation polonaise (de Lukasiewicz): cette notation permet d'éliminer les parenthèses, en écrivant le connecteur devant les formules sur lesquelles il porte. On note , , , , par N, K, A, C.

Par exemple, ( p∨q) s'écrit Apq, et (p (q r)) s'écrit CpKNqr.Transcrire dans cette notation les formules: (q r)p, (rq) (s∧p), et les cinq premières formules de l'exercice 1.Inversement, transcrire en notation standard les fomules ANpCqq, CqKNprs, KCCNKAqrpprq

Exercice 4 : évaluer les formules 1, 3, 5, 8, 9, 10 de l'exercice 1 pour la dvv : p:F q:F r:V s:F t:V

Exercice 5 : faire la table de vérité des formules suivantes :

1. ((p q)→ p)∨ ⅂

2. ((p→q) (q p))∨ ∨⅂

3. (((r p)→q) (q p))∨ ∨ ∨

4. ((q ( q p)) p)⅂ ∨ ⅂ ∧ ∧

5. (p ((q (p→q)) r))∨ ∧ ∨

6. ( ( q p) p)⅂ ⅂ ∧ ∧⅂

7. (( p (r→q))→ p)⅂ ∧ ⅂

8. ((q r) ((r→p) r))∧ ∨ ∧

9. ((((p p)→r)→q)→ r)⅂ ∧⅂ ⅂

10. (((r q)→q) ((r→p) q))∨⅂ ∨⅂ ∨

11. (( (r p)→(p q))→q)⅂ ⅂ ∧ ∨

12. ( p→ (p (q→(p q))))⅂ ⅂ ∧ ∧

13. (r ((q q) (q r)))⅂ ∨ ∨ ∨ ∨

14. ((q→p)→((q p) ((p q)→q)))∧ ∧ ∨

Exercice 6 : pouvez-vous dire sans calculer la table de vérité si les formules suivantes sont des tautologies :

1. ( p→(r∧p))∨¬( p→(r∧ p))

2. ¬(q→r )→((q→ r )→( p→ r ))

3. (( p→(q∨r ))∧p)→(q∨r )

4. ((( p→q)→ p)∧( p→(q→ p)))→(( p→ q)→(q→ p))

5. ( p→q)∨¬(¬ p∨q)

6. ¬( p→ q)→((q→( p→q))→( p∧¬q))

10

Page 11: Logique des propositions Fascicule ... - Université de Lilleperso.univ-lille3.fr/~lvinciguerra/propositions/fascicule_logique... · conclusion, c'est-à-dire lorsque la conclusion

Exercice 7 : les formules suivantes sont-elles (tautologiquement) équivalentes (méthode de votre choix sauf l'arbre sémantique) ?

1. p→(q∧r )eq ( p→q)∧( p→ r )2. ( p∧q)→r eq( p→ r )∧(q→ r)3. ( p∨q)→r eq( p→ r )∨(q→ r)4. p→(q∨r )eq ( p→q)∨( p→ r )

5. (( p∧q)→ r )eq¬( p∧q)∨r6. (( p∧q)→ r )eq(¬ p∨¬q)∨r7. ¬( p→(q→ r ))eq( p∧¬(q→ r ))8. ( p→ p)eq(q∨¬q)

Exercice 8 : les arguments suivants sont-ils valides ? (transformer en affirmation de conséquence logique, puis appliquer la définition)

pq→¬ pdonc¬q

(( p∧q)→¬r )r

donc¬ p

p→ qr∧¬r

donc q→ s

p→(q∨r )r→¬ pq→ rdonc¬ p

p∨qq→ p

donc r∨¬r

p∧qp→ rr →¬qdonc s

(q∧ p)→¬qdonc¬ p

Exercice 9 : exprimer (avec bienveillance) sous la forme d'une formule de calcul propositionnel le raisonnement suivant. Est-il logiquement valide?"S'il n'y avait pas ce que nous appelons vide, espace ou nature impalpable, les corps n'auraient pas où se placer ni où se mouvoir, ce qu'ils semblent bien faire. Donc il faut admettre l'existence du vide" (d'après Epicure).

Exercice 10 : Traduisez en langage des propositions les raisonnements suivants, et examinez s'ils sont valides :1- Si l'on ne cherche pas de nouvelles sources d'énergie et si les États acceptent des normes contraignantes, alors le pouvoir d'achat des citoyens diminuera. Mais si le pouvoir d'achat des citoyens diminue, on ne cherchera pas de nouvelles sources d'énergie. Donc si les États acceptent des normes contraignantes, on ne cherchera pas de nouvelles sources d'énergie.2- Si l'on ne peut pas éradiquer le paludisme et si les moustiques anophèles se développent, alors, on n'éradiquera pas le paludisme.3- Si Dieu existe, alors le mal n'existe pas ou il joue un rôle dans la création. Mais s'il joue un rôle dans la création et si Dieu est bon, alors le mal n'est pas un mal. Or c'est absurde. Donc si Dieu et le mal existent, Dieu n'est pas bon.

Exercice 11 : montrer qu'on peut trouver pour n'importe quelle formule une formule équivalente qui ne comporte pas le connecteur →. On peut donc se passer de ce connecteur. Peut-on se passer d'autres connecteurs ?

Exercice 12 : On introduit un nouveau connecteur, le connecteur ni...ni... (ou plus élégamment flèche de Peirce). Il est noté ↓ et sa table de vérité est la suivante : |p|q| p↓q ||V|V| F ||V|F| F ||F|V| F ||F|F| V |Démontrer qu'il est possible de trouver pour n'importe quelle formule une formule équivalente qui ne comporte pas d'autre connecteur que ↓ (on essaiera d'exprimer ¬ p , p∧q , p∨q , p→q , dans cet ordre, au moyen de ce connecteur).

11

Page 12: Logique des propositions Fascicule ... - Université de Lilleperso.univ-lille3.fr/~lvinciguerra/propositions/fascicule_logique... · conclusion, c'est-à-dire lorsque la conclusion

SÉMANTIQUE (SUITE) : MÉTHODE DE L'ARBRE SÉMANTIQUE

La méthode de l'arbre sémantique (aussi appelé tableau sémantique) est une autre technique permettant de déterminer si une formule est ou non une tautologie, en construisant un arbre (différent de l'arbre syntaxique) Cette méthode est en général plus simple que celle de la table de vérité lorsque la formule comporte plus de trois atomes.

Les règles:

V :¬A V : A∨B V : A∧B V : AB

F : A V:A V:B

V:A V:B F:A V:B

F:¬A F: A∨B F: A∧B F: AB

V : A F:A F:B F:A F:B

V: A F: B

La méthode: on écrit des formules signées, c'est-à-dire précédées de V ou F.

1. Pour examiner si une formule A est une tautologie, on part toujours de: F: A2. on construit l'arbre au moyen des règles ci-dessus qui disent comment traiter chaque formule en

fonction de sa signature (V ou F) et de son connecteur principal.3. Traiter une formule revient à générer une autre formule (si le connecteur principal est la

négation) ou deux autres formules (dans tous les autres cas) , et à les mettre soit l'une au dessous de l'autre, soit de part et d'autre de deux branche. On continue ensuite à traiter les formules générées en dessous selon les mêmes règles.

4. Toutes les formules qui apparaissent dans l'arbre doivent avoir été traitées (on les coche au fur et à mesure).

5. La ou les formules générées selon les règles doivent être reportées au bout de toutes les branches déjà ouvertes qui sont situées EN DESSOUS de la formule que vous traitez.

6. Vous êtes libres de traiter les formules présentes dans l'arbre dans l'ordre que vous souhaitez. Mais vous avez intérêt à traiter d'abord les formules qui n'ouvrent pas de branche.

7. Une fois que toutes les formules (sauf les atomes) ont été traitées, on examine chaque branche del'arbre en remontant du bas jusqu'en haut. Si on trouve à un moment donné un atome signé puis le même atome avec sa signature opposée (par exemple: q:V puis q:F), la branche est barrée (on met une croix). On ne s'intéresse à ce moment-là qu'aux atomes et non aux formules complexes.

8. Si TOUTES les branchent sont barrées, la formule est une tautologie. Sinon, non. 9. On peut examiner si les branches sont barrées au fur et à mesure qu'on traite les formules. Si une

branche est barrée, on peut mettre une croix et cesser d'en tenir compte dans la construction de l'arbre. De toute manière, tout ce qui passera par là sera toujours barré ensuite.

12

Page 13: Logique des propositions Fascicule ... - Université de Lilleperso.univ-lille3.fr/~lvinciguerra/propositions/fascicule_logique... · conclusion, c'est-à-dire lorsque la conclusion

Exemple 1:

Exemple 2

:

Autre arbre, juste mais plus complexe, résultat de choix moins judicieux pour la même formule:

13

Page 14: Logique des propositions Fascicule ... - Université de Lilleperso.univ-lille3.fr/~lvinciguerra/propositions/fascicule_logique... · conclusion, c'est-à-dire lorsque la conclusion

FEUILLE D'EXERCICES 4Arbres sémantiques

Exercice 1 : examinez au moyen de la méthode de l'arbre sémantique si les formules suivantes sont des tautologies.

1. ((s p)→(r→r))∨⅂2. (( p→r )∧(r→(q∨s)))→(¬s∧ p)3. (((q→r) (r→s))→(q s))∧ ∨4. ((r→t) ((r→q)→s))∨5. ( (r→q)→ (((s p) r)→s))⅂ ⅂ ∨ ∨6. (p (( p p)→ t))∨ ⅂ ∨ ⅂

7. ((q (s t)) (s ((s q) t)))∨⅂ ∧ ∨ ∨ ∧⅂ ∧8. (r (( (r t)→p) r))∨ ⅂ ∨ ∨⅂9. ((s→r)→(r ((p t) s)))∨⅂ ∨ ∧10. (((r→(r (p (p t)))) t)→(t→t))∨ ∨ ∧⅂ ∨11. (s (r (q→( r (s→q)))))∨ ∨ ⅂ ∧12. ( t→(q→(r→( t))))⅂ ⅂

Exercice 2 : examinez au moyen de la méthode de l'arbre sémantique si les équivalences suivantes sont valides :(q→(r∨s))eq (¬r→ q) ( p∨q)eq (q→¬ p) ( p→(q∧r ))eq((q→¬r )→¬ p)( p∨¬ p)eq(q→ q)

Exercice 3 : soit l'ensemble B composé des formules suivantes : p ,q→ r , p∨qExaminez au moyen de la méthode de l'arbre sémantique si les formules suivantes sont conséquence logique de B :p→q ¬ p→ r (t∧r )→(r∧t) (r → s)→( p∨s ) r→(¬q∨(q→ p))

Exercice 4 : mêmes questions pour les mêmes formules avec B composé de r→q ,¬( p∧q) , q

Exercice 5 : même question avec B composé de s→ t , q∧r ,( p∨s)∧¬( p∨s ) . Pouvez-vous conclureplus rapidement ?

14

Page 15: Logique des propositions Fascicule ... - Université de Lilleperso.univ-lille3.fr/~lvinciguerra/propositions/fascicule_logique... · conclusion, c'est-à-dire lorsque la conclusion

Corrigé feuille d'exercice 4, Exercice 1

3/

5/

9/

15

Page 16: Logique des propositions Fascicule ... - Université de Lilleperso.univ-lille3.fr/~lvinciguerra/propositions/fascicule_logique... · conclusion, c'est-à-dire lorsque la conclusion

10/

11/

12/

16

Page 17: Logique des propositions Fascicule ... - Université de Lilleperso.univ-lille3.fr/~lvinciguerra/propositions/fascicule_logique... · conclusion, c'est-à-dire lorsque la conclusion

Indications feuille 3 exercice 5

En suivant l'ordre standard pour les lignes de la table de vérité, vous devez trouver pour :10 : VVFFVVVF11 : VVVFVVFF12 : VVVV13 : FFFV

Indications feuille 3 exercice 71:oui 2:non 3:non 4:oui 5:oui 6:oui 7:oui 8:oui

Corrigé partiel feuille 3 exercice 81- valide (non démontré)2-

(( p∧q)→¬r )

rdonc¬ p

est-il un raisonnement valide ?

Il faut examiner si {( p∧q)→¬r , r } a pour conséquence logique ¬ p . Faisons la table de vérité de ces trois formules :p q r ( p∧q)→¬r r ¬ p

v v v f v f

v v f v f f

v f v v v f

v f f v f f

f v v v v v

f v f v f v

f f v v v v

f f f v f vA la ligne 3, les deux premières formules sont vraies et ¬ p est fausse. Celle-ci n'est donc pas leur conséquence logique et le raisonnement n'est pas valide. Les raisonnements 3, 4, 5 sont valides.Les raisonnements 1, 6 et 7 ne sont pas valides.

3- valide car la deuxième prémisse n'est jamais vraie (antilogie). Il n'y a donc pas de ligne où les prémisses sont vraies et la conclusion fausse.

4-p→(q∨r )r→¬ pq→rdonc¬ p

est-il un raisonnement valide ?

Il faut examiner si { p→(q∨r ) , r→¬ p ,q→r } a pour conséquence logique ¬ p . Faisons la table devérité des trois prémisses :(voir page suivante)

17

Page 18: Logique des propositions Fascicule ... - Université de Lilleperso.univ-lille3.fr/~lvinciguerra/propositions/fascicule_logique... · conclusion, c'est-à-dire lorsque la conclusion

p q r p→(q∨r ) r→¬ p q→r ¬p

v v v v f v f

v v f v v f f

v f v v f v f

v f f f v v f

f v v v v v v

f v f v v f v

f f v v v v v

f f f v v v vLes prémisses sont toutes vraies aux lignes 5, 7, 8 seulement.La conclusion ¬p est aussi vraie à ces trois lignes. Donc le raisonnement est valide

5- le raisonnement est valide car la conclusion est une tautologie. Comme elle est toujours vraie, il ne peut y avoir de ligne où les prémisse soient vraies et où elle soit fausse. Les raisonnements 6 et 7 ne sont pas valides (non démontré).

Corrigé feuille 3, exercice 10, n°1 :Mise en forme logique :p : on cherche des nouvelles sources d'énergieq : les États acceptent des normes contraignantesr : le pouvoir d'achat des citoyens diminueLe raisonnement est : (¬ p∧q)→r , r→¬ p donc q→¬ pCe raisonnement n’est pas valide. En effet Il est valide ssi (¬ p∧q)→ r , r→¬ p a pour conséquence logique q→¬ p , et donc ssi : (((¬ p∧q)→r )∧(r→¬ p))→(q→¬ p)est une tautologie.Pour le démontrer, on utilise la méthode de l’arbre sémantique en partant de la formule signée :

F :(((¬ p∧q)→r )∧(r→¬ p))→(q→¬ p)

18

Page 19: Logique des propositions Fascicule ... - Université de Lilleperso.univ-lille3.fr/~lvinciguerra/propositions/fascicule_logique... · conclusion, c'est-à-dire lorsque la conclusion

L1 philosophieLogique

Épreuve du 17 décembre 2015

AUCUN DOCUMENT AUTORISÉ

1- Que faut-il faire, aussi bien en logique aristotélicienne, logique des propositions et logique des prédicats, pour prouver qu’un argument n’est pas valide ?

2- Qu'est-ce qu'un syllogisme ? Le raisonnement suivant est-il un syllogisme ?Certaines poules ont des dents.Or toutes les dents ont des cariesDonc certaines poules ont des caries.Dites si ce raisonnement est ou non valide (ne pas le démontrer)

3- Soit la formule : ((¬(( p→ r )→¬(q∨r ))∨ p)∧s)Faites l’arbre syntaxique de cette formule et évaluez la formule pour la distribution de valeurs de vérité :

p:V q:V r:F s:V

4- Les formules suivantes sont-elles équivalentes :(¬( p∧q)→(q→ p)) et ( p→¬q)

5- Examinez par la méthode de votre choix si le raisonnement suivant est valide :¬(( p→q)→ p)((q∨p)→ q)→ p

donc p

6- Traduisez en langage des propositions le raisonnement suivant, et examinez par la méthode de votre choix s’il est valide :

S’il pleut la cérémonie est annulée. Mais si je chante il pleut. Et toutes les fois que les étudiants réussissent leur examen de logique je chante. Donc si la cérémonie n'est pas annulée, les étudiants ne réussissent pas leur examen de logique.

7- Au moyen de la méthode de l’arbre sémantique, examinez si la formule suivante est une tautologie :¬( p∨¬(q∧r ))∨(q→(¬r→ p))

8- Donnez la définition de la notion de satisfaction en logique des propositions.

9- Donnez la définition d'une expression en langage des propositions

10- Donnez la définition de la notion de conséquence logique en langage des propositions

19

Page 20: Logique des propositions Fascicule ... - Université de Lilleperso.univ-lille3.fr/~lvinciguerra/propositions/fascicule_logique... · conclusion, c'est-à-dire lorsque la conclusion

L1 philosophieLogique

Deuxième session juin 2017

AUCUN DOCUMENT AUTORISÉ

1- Que faut-il faire, aussi bien en logique aristotélicienne, logique des propositions et logique des prédicats, pour prouver qu’un argument n’est pas valide ?

2- Qu'est-ce qu'un connecteur vérifonctionnel ?

3- Donnez la définition d'une expression et d'une formule pour le langage des propositions.

4- Démontrez que l'expression (¬(¬( p∨¬r )→q)∨(q→r )) est une formule.

5- Faites l'arbre syntaxique des deux formules suivantes, puis faites leur table de vérité :a- (¬(¬( p∨¬r )→q)∨(q→r ))b- (q∨( p∧¬(¬r→q )))

Ces deux formules sont-elles équivalentes ? Pourquoi ?

6- Examinez au moyen de la méthode de l'arbre sémantique si les formules suivantes sont des tautologies:

a- (((( p∧q)→s)∧s)∨(q∧(s→ p)))b- ((( p→(q∨r ))∧(r→¬ p))→(q∨¬ p))

7- Examinez si { ¬q , p∧r q } a pour conséquence logique r¬ p sans faire d’arbre sémantique, en expliquant votre méthode.

8- Quel est le théorème sémantique de la déduction ?

9- Quelles sont les lois de De Morgan ?Pouvez-vous démontrer, au moyen entre autres de ces dernières, sans utiliser de table de vérité ni d’arbresémantique, que :¬( p→(q∧r ))eq. p∧(q→¬r )(¬( p∧q)→(r∨s ))eq.( p∨r∨s)∧(q∨r∨s)

10- Expliquez pourquoi il n’est pas possible de définir la vérité d’un langage à l’intérieur de ce langage.

20