2019/10/07

(dernière modification : 2019/11/04)

Tautologie, contradiction et validité (suite)

Le langage LP (suite)

Classification des énoncés de LP

La valeur de vérité des énoncés déclaratifs que nous faisons dépend du monde, de l’état du monde. Nous disons qu’un énoncé déclaratif est contingent si et seulement si il est possible qu’il soit vrai et qu’il est possible qu’il soit faux.

Exemple d’énoncé contingent : les premiers hominidés sont apparus il y a environ 6 millions d’années.

Nous disons qu’un énoncé déclaratif est une tautologie si et seulement si il est impossible qu’il soit faux.

Exemples :

« Il pleut ou il ne pleut pas. »
« Si Montréal est en Europe, alors Montréal est en Europe. »
« Si 1 est égal à 0, alors Bertrand Russel est le Pape François. »

On peut vérifier que ce sont des contradictions en faisant la table de vérité!

La table de vérité des tautologies est toujours vraie ou toujours fausse :

Il pleut OU il ne pleut pas.

p : il pleut (un seul énoncé atomique).

`p`	`¬p`	`p ∨ ¬p`
V	F	V
F	V	V

Il pleut ET il ne pleut pas.

p : il pleut (un seul énoncé atomique).

`p`	`¬p`	`p ∧ ¬p`
V	F	F
F	V	F

Avec une contradiction, tout devient possible; tout est vrai. D’un point de vue logique, tout le discours s’effondre; c’est pour cela que l’on traque scrupuleusement les contradictions.

(Avenue alternative : paralogique, pas examinée dans ce cours.)

L’équivalence logique

Nous disons que deux fbfs sont logiquement équivalentes si et seulement si elles ont la même table de vérité.

Exemple :

A = (p ∧ ¬P)
B = ¬(p ⊃ P)

A = p ⊃ q
B = ¬p ∨ q.

Table de vérité équivalente :

`p`	`p ∧ ¬p`	`¬(p ⊃ ¬p)`
V	F	F
F	V	F

Les formes d’arguments

Nous pouvons maintenant explorer les formes d’arguments dans LP et lesquelles sont valides.

Exemple :

1. Si Montréal est au Québec, alors Montréal est au Canada.
2. Montréal est au Québec.
C. Montréal est au Canada.

1. A ⊃ B.
2. A.
C. B

Cet argument est-il formellement valide?

Dans la table de l’implication, la conclusion ne peut pas être fausse. B ne peut pas être faux (l’implication serait fausse).

L’argument peut-il être invalide si les prémisses sont toutes vraies et la conclusion fausse?

Si A est vrai, alors l’énoncé est vrai. On ne peut pas essayer de rendre cet argument invalide (i.e. prémisses vraies, conclusion fausse).

Autre exemple :

1. Si Montréal est en Italie, alors Montréal est en Europe.
2. Montréal n'est pas en Europe.
C. Montréal n'est pas en Italie.

p : Montréal est en Italie
q : Montréal est en Europe

1. p ⊃ q
2. ¬p.
C. ¬q

La forme abstraite de l’argument :

1. A ⊃ B.
2. ¬B.
C. ¬A

B ne peut donc pas être faux.

Autre exemple :

1. Si la peine de mort réduit la criminalité,
    alors la peine de mort est justifiée.
2. Des études ont montré que la peine de mort
   ne réduit pas la criminalité.
C. La peine de mort n'est pas justifiée.

p : la peine de mort réduit la criminalité.
q : la peine de mort est justifiée.

L’argument traduit en LP :

1. p ⊃ q.
2. ¬p.
C. ¬q

La forme abstraite de l’argument :

1. A ⊃ B.
2. ¬A
C. ¬B

Cet argument est-il formellement valide?
Non.

Autre exemple :

1. Si la peine de mort réduit la criminalité, alors la peine de mort est justifiée.
2. La peine de mort est justifiée.
C. La peine de mort réduit la criminalité.

1. p ⊃ q.
2. q.
C. p

La forme abstraite de l’argument :

1. A ⊃ B.
2. B.
C. A

Si A est faux, alors (selon la table de l’implication), l’énoncé est vrai. Les prémisses sont vraies en même temps que la conclusion est fausse : l’argument est donc invalide.

Métacognition

Nous avons réussi à déterminer si ces formes d’arguments sont valides ou invalides, par essai et erreur.

On cherche à attribuer des valeurs de vérité aux fbfs qui composent les prémisses et la conclusion et à montrer que l’argument est invalide.

Pour trouver des valeurs de vérité des fbfs, il faut considérer les différentes attributions de valeurs de vérité des énoncés atomiques.

On se sert ensuite des tables de vérité pour déterminer les valeurs de vérité des fbfs.

p	q	p ⊃ q	p	q (conclusion)
V	V	V	V	V
V	F	F	V	F valide
F	V	V	F	V
F	F	V	F	F

Y a-t-il des cas où les prémisses sont vraies et la conclusion est fausse?
Non, donc c’est valide.

p	q	p ⊃ q	q	p (conclusion)
V	V	V	V	V
V	F	F	F	V
F	V	V	V	F invalide
F	F	V	F	F

On a une méthode systématique pour découvrir si un argument est valide ou invalide. Problème : cette méthode est exponentielle : 3 énoncés font 8 lignes, 4 énoncés font 16 lignes, 5 font 32 lignes… Cette méthode n’est donc pas souhaitable pour des énoncés complexes.

Ça marche, en théorie.
Mais peut-on faire mieux?

La méthode des arbres

La méthode des arbres est beaucoup plus facile à transposer dans d’autres situations.
Elle est (souvent) plus économique, elle est systématique, et a l’avantage de se transposer dans des situations dans lesquelles on a plusieurs valeurs de vérité.

Détour par la notion de cohérence logique.

Question de cohérence

Une des propriétés importantes d’un discours est sa cohérence.

La cohérence a une signification plus large en philosophie (adhérence). Notion de vérité : correspondance à ce qu’un énoncé est. Un énoncé énonce ce qu’il y a dans le monde adéquatement; adéquation; correspondance entre ce qu’un énoncé dit et ce qu’il y a dans le monde.

Nous parlons ici de cohérence logique.

Nous disons qu’un discours, une suite d’énoncés, est logiquement incohérent si et seulement si il contient une contradiction, c’est-à-dire s’il contient un énoncé p et sa négation ¬p.

Un discours est cohérent si et seulement si il n’est pas incohérent. Ce discours s’effondre dès qu’on y trouve une contradiction (incohérence).

Pouvons-nous vérifier si un discours est cohérent?

C’est compliqué : il y a les conséquences logiques qui nous sont données. Il n’est pas impossible qu’une des conséquences logiques des arguments mène à une contradiction. Toutes les conséquences logiques sont à considérer dans un discours.

Une stratégie : au lieu de chercher les contradictions, étant donné une suite d’énoncés, est-ce que ces derniers peuvent tous être vrais en même temps?

Il est clair que si cette suite d’énoncés est incohérente, c’est impossible.

Nous devons donc examiner une notion plus faible ou plus générale que la notion de cohérence, c’est-à-dire si une collection d’énoncés peuvent tous être vrais en même temps.

Soit une collection donnée d’énoncés (dans un discours, un livre, un témoignage, une convention collective, etc. où la cohérence est évidemment importante). Une collection qui est telle que tous ses énoncés peuvent être vrais en même temps est appelée une collection satisfiable.

Une collection qui n’est pas satisfiable est dite insatisfiable, c’est-à-dire s’il est impossible de faire en sorte que tous les énoncés de cette collection sont vrais en même temps.

Un discours incohérent est nécessairement insatisfiable.

Exemple : la collection des énoncés suivants est-elle satisfiable?

p ⊃ q
p
¬q

Si p est vraie et q fausse, alors p ⊃ q est fausse. Il est impossible que les trois propositions soient toutes vraies en même temps; cette collection est donc insatisfiable.

Autre exemple : la collection des énoncés suivants est-elle satisfiable?

p ⊃ q
¬p
q

Cette collection est satisfiable.

Autre exemple : la collection des énoncés suivants est-elle satisfiable?

p ⊃ q
¬q
p

Si p est vraie et q fausse, alors p ⊃ q est fausse. Cette collection est donc insatisfiable.

Il y a un lien à faire entre satisfiabilité et validité.

Autre exemple : la collection des énoncés suivants est-elle satisfiable?

p ⊃ q
¬q
¬p

Si p est vraie et q est vraie, alors p ⊃ q est vraie. Cette collection est donc satisfiable.

Validité et satisfaction

Magritte cheval

Rappel : un argument est valide si et seulement s’il est impossible que les prémisses soient vraies et, en même temps, la conclusion fausse.
Rappel : un argument est invalide si et seulement si il n’est pas valide, c’est-à-dire s’il est possible que les prémisses soient vraies et, en même temps, la conclusion fausse.
Donc, si un argument est invalide et si on prend les prémisses et la négation de la conclusion, alors cette collection d’énoncés est satisfiable.

En d’autres mots : si un argument est invalide et si on prend les prémisses et la négation de la conclusion, alors il est possible d’attribuer des valeurs de vérité aux propositions atomiques de telle sorte que les propositions de cette collection soient toutes vraies en même temps.

Peut-on trouver une méthode qui permet de vérifier systématiquement si une collection de propositions est satisfiable?

Si oui, nous avons également à notre disposition une méthode qui nous permet de déterminer si un argument est invalide.

La méthode des arbres

Nous devons d’abord savoir comment déployer un arbre à partir de chacun des connecteurs logiques. Ce sont les règles simples.

Une fois que nous savons comment développer un arbre à partir des règles simples, il est possible de construire un arbre pour un ensemble de formules.

Première règle (convention) :

dans un arbre, lorsqu’une proposition positive apparaît (i.e. absence de négation), par exemple A, ceci revient à affirmer que A est vraie.
Une proposition qui n’est pas niée est considérée comme vraie.
Lorsque nous avons ¬A dans un arbre, ceci revient à affirmer que A est fausse.

Les règles pour l’implication

 A ⊃ B
   /\  R⊃
  /  \
¬A    B

A ⊃ B est vrai si :

A est faux ou
B est vrai.

Négation d’une implication (dans quelles circonstances l’implication est-elle fausse?) :

¬(A ⊃ B)
    |
    |  R¬⊃
    A
   ¬B

A ⊃ B est faux si et seulement si :

A est vrai et
B est faux.

La règle pour la négation

¬¬A
 |
 | R¬
 A

¬¬A est vrai si et seulement si A est vrai.

Définitions et conventions

Si la collection de propositions d’une branche d’un arbre est satisfiable, alors nous disons que cette branche est ouverte.

Si la collection de propositions d’une branche d’un arbre est insatisfiable, alors nous disons que cette branche est fermée.

Lorsqu’une branche est fermée, nous inscrivons un « X » sous la branche.

Premier exemple

L’argument suivant est-il valide?

p ⊃ q, p ∴ q

Important : pour vérifier la validité de cet argument, nous devons nier la conclusion avant de construire l’arbre.

p ⊃ q
p
¬q
R ⊃ – 1 : 2 branches
- ¬p
- q

Il est impossible que cette liste soit satisfiable.

1. p ⊃ q 
2.   p
3.  ¬q
     /\ R⊃ – 1.
    /  \
4. ¬p   q
   X     X <-- 2 branches fermées

Lorsqu’on lit l’arbre de bas en haut, jusqu’au sommet, on constate que dans chaque branche, on trouve une proposition et sa négation, c’est-à-dire que la collection de propositions dans chaque branche est incohérente.

Selon cet arbre, ¬p et q ne peuvent être vrais en même temps.

Dans cet arbre, les deux branches sont insatisfiables. Elles sont donc toutes deux fermées.

Il faut donc inscrire un « X » sous chacune d’entre elles. Ceci signifie que nous ne pouvons pas attribuer de valeurs de vérité aux propositions dans cette branche de telle sorte qu’elles soient toutes vraies en même temps.

L’argument est donc valide.

Deuxième exemple

L’argument suivant est-il valide?

Important : pour vérifier la validité de cet argument, nous devons nier la conclusion avant de construire l’arbre.

1.  p ⊃ q
2.   ¬p
3.  ¬¬p
      |
      |  R¬ – 3
4.    p
     /\
    /  \ R ⊃ – 1
5. ¬p   q
     X   X <-- Valide!

Dans cet arbre, les deux branches sont insatisfiables. Elles sont donc toutes deux fermées.

L’argument est donc valide.

On a toujours intérêt à ne pas ouvrir des branches si on peut ne pas en ouvrir.

Troisième exemple

L’argument suivant est-il valide?

Important : pour vérifier la validité de cet argument, nous devons nier la conclusion avant de construire l’arbre.

p ⊃ q, ¬p ∴ q

1. p ⊃ q
2.  ¬p
3. ¬¬q
     | R¬ – 3
4.   q
     /\
    /  \ R ⊃ – 1
5. ¬p.  q

Dans cet arbre, les deux branches sont satisfiables! Elles sont donc toutes deux ouvertes, car je ne peux plus appliquer de règles.

Lorsque p est fausse et q est vraie, les propositions dans les branches sont satisfiables.

L’argument est donc invalide, car lorsque p est fausse et q est vraie, les prémisses sont vraies et la conclusion fausse.

Quatrième exemple

L’argument suivant est-il valide?

Important : pour vérifier la validité de cet argument, nous devons nier la conclusion avant de construire l’arbre.

p ⊃ q, q ∴ p

      1. p ⊃ q
      2. q
      3. ¬p
         /\
        /  \ R ⊃ – 1 
   4. ¬p    q

Les deux branches sont satisfiables. Elles sont donc toutes deux ouvertes, car il n’est plus possible d’appliquer de règle.

Ceci signifie que nous pouvons attribuer des valeurs de vérité aux propositions dans ces branches pour qu’elles soient toutes vraies en même temps.

L’argument est donc invalide.

Les règles pour la conjonction

Escaliers Escher

A ∧ B
  |
  | R∧
  |
  A
  B

A ∧ B est vrai si et seulement si :

A est vrai et
B est vrai.

¬(A ∧ B)
   /\
  /  \ R¬∧
¬A.  ¬B

A ∧ B est faux si et seulement si :

A est faux ou
B est faux.

Une fois qu’on connaît la règle, le système pense pour nous.

Les règles pour la disjonction

 A ∨ B
  /\
 /  \ R∨
A    B

A ∨ B est vrai si et seulement si :

A est vrai ou
B est vrai.

¬(A ∨ B)
    |
    | R¬∨
    |
   ¬A
   ¬B

A ∨ B est faux si et seulement si :

A est faux et
B est faux.

Les règles pour l’équivalence (biconditionnel)

 A ≡ B
   /\
  /  \ R≡
 A   ¬A
 B   ¬B

A ≡ B est vrai si et seulement si :

A est vrai et B est vrai ou
A est faux et B est faux.

¬(A ≡ B)
    /\
   /  \ R¬≡
  A   ¬A
 ¬B    B

A ≡ B est faux si et seulement si :

A est vrai et B est faux ou
A est faux et B est vrai.

Un exemple de satisfaction d’une proposition

Question : quelles valeurs de vérité les atomes p, q et r doivent-ils avoir pour que la formule ¬(p ∨ (q ∧ ¬r)) soit satisfaite?

1. ¬(p ∨ (q ∧ ¬r))
       | R¬∨ – (1)
2.    ¬p
3. ¬(q ∧ ¬r)
       /\
      /  \  R¬∧ – (3)
4.   ¬q  ¬¬r
           |  R¬ – (4)
           r

(2 branches ouvertes)

Note : on ne nie pas la proposition, elle l’est déjà. On ne cherche pas à savoir si c’est un argument valide.

Les branches sont ouvertes.

Réponse :

p fausse et q fausse ou;
p fausse et r vraie.

On peut vérifier la solution en remplaçant les valeurs de p, q et r et en remontant dans l’arbre.

La méthode des arbres

Un arbre est terminé ou complètement développé si et seulement si :

L’arbre est fermé ou;
Il n’y a plus que des propositions atomiques ou atomiques niées (« négatomiques ») au bas des branches et des règles ont été appliquées à toutes les propositions qui apparaissent plus haut dans les branches.

Il faut compléter un arbre pour conclure quoi que ce soit.

Validité : exemple

L’argument :

1. p ⊃ q
2. r ⊃ s
3. q ∨ r
------ 
C. p ∨ q

Commencer en niant la conclusion :

1.   p ⊃ q
2.   r ⊃ s
3.   q ∨ r <-- 2 branches
4. ¬(p ∨ q) <-- 1 branche

1.   p ⊃ q
2.   r ⊃ s
3.   q ∨ r
4. ¬(p ∨ q)
       |  R¬∨–(4)
5.    ¬p
6.    ¬q
      /\
     /  \  R∨–(3)
7.  q    r
8.  X   / \  R⊃¬(2)
       ¬r  s
        X / \  R⊃¬(1)
        ¬q   q
             X

L’argument est invalide. Un contre-exemple (pour valider) :

p faux
q faux
r vrai
s vrai.

Convention terminologique

Lorsque nous employons la méthode des arbres pour tester la validité d’un argument et que la méthode nous indique que l’argument est invalide, les valeurs de vérité attribuées aux propositions dans une branche ouverte constituent ce qu’on appelle un contre-exemple.

Tautologie : un test

Une tautologie est toujours vraie. Donc, sa négation est toujours fausse. Elle ne peut être satisfaite. Par conséquent, l’arbre de la négation d’une tautologie est fermé.