Logique propositionnelle et conditionnel mat´erielmikael.cozic.free.fr/logphil0607-da1.pdf · conditionnel comme conditionnel mat´eriel ... (ii) si φest une formule, alors ¬φest

Logique propositionnelle

et conditionnel materiel

M. Cozic (DEC, ENS) & P. Egre (CNRS, IJN)

[notes 26/02/2007, version 2]

1 Preambule

• Pourquoi s’interesser aux enonces conditionnels ? Place dans les raisonnementsmathematiques, pratiques, causaux :

(1) Si c’est un carre, alors c’est un rectangle

(2) Si je me depeche, j’arriverai a l’heure

(3) Si Napoleon n’avait pas perdu la guerre a Waterloo, la France serait un Empire.

• L’etude des conditionnels fait partie de l’analyse semantique du langage (analyse de lasignification, via celle des conditions de verite des enonces).

(4) Si c’est un carre, alors c’est un rectangle

(5) Si c’est un rectangle, alors c’est un carre.

• La notion de conditionnalite et voisine de celle de consequence logique, qui constitue l’objetmeme de la logique :

(6) Si c’est un carre, alors c’est un rectangle.

(7) C’est un carre. Donc c’est un rectangle.

• Les conditionnels representent par ailleurs une sorte de fil conducteur de l’histoire de la lo-gique. Les conditionnels ont ete discutes d’abord chez les Megariques (debat Diodore Cronosvs Philon), puis chez les Stoıciens. L’analyse du conditionnel proposee par Philon ressurgitdans l’Ideographie de Frege (1879), elle est reprise chez Russell et Whitehead dans les Prin-cipia Mathematica (1910). Jugee insatisfaisante, elle donne lieu a la naissance de la logiquemodale (C. I. Lewis, ca. 1920). Puis l’analyse semantique de la logique modale (notammentKripke, 1959) nourrit a son tour des analyses nouvelles des conditionnels, en particulier desconditionnels contrefactuels (Goodman 1947, Stalnaker 1968, D. Lewis 1973). L’analyse desconditionnels a egalement donne lieu a des avancees en theorie de la preuve (logiques de lapertinence ou relevance, Anderson et Belnap ca. 1970).• Par ou commencer ? Par la logique propositionnelle, qui constitue l’analyse de reference duconditionnel comme conditionnel materiel (cf. Philon, Frege).

1

M. Cozic & P. Egre - Logique philosophique - DA n 1 - LP et conditionnel materiel

2 Logique propositionnelle

2.1 Morphologie de L−

2.1.1 Alphabet et formules

Definition 1L’alphabet A d’un langage propositionnel est la donnee

1. d’un ensemble de formules atomiques At = {p, q, r, ...}

2. d’un ensemble de connecteurs : {∨,∧,¬}

3. d’une parenthese ouvrante et d’une parenthese fermante {), (}

Definition 2Une expression formee a partir d’un alphabet A est une suite finie d’elements de l’alphabet.Le langage propositionnel L−(A) fonde sur l’alphabet A est l’ensemble des expressionsformees a partir de A.

Exemple 1”))))¬ ∨ p→ q”, ”(p ∧ r)”, ”q” sont des expressions du langage propositionnel.

Notation 1On utilise

1. φ, ψ, χ pour designer des expressions quelconques du langage propositionnel

2. ◦ pour designer un connecteur binaire quelconque (∨ ou ∧)

φ, ψ, χ,..., et ◦ appartiennent au meta-langage, pas au langage objet.

Definition 3L’ensemble F(L−(A)) des formules du langage propositionnel L−(A) est l’ensemble desexpressions tel que

(i) toute formule atomique p ∈ At est une formule(ii) si φ est une formule, alors ¬φ est une formule(iii) si φ et ψ sont des formules et ◦ un connecteur propositionnel, alors (φ ◦ ψ) est une

formule(iv) seules les expressions engendrees par un nombre fini d’applications des regles

precedentes sont des formules

Exemple 2¬¬p, (p ∧ (r ∨ s)), (p ∧ ¬¬¬q) sont des formules.(q ∨ r ∧ p), )q ∨ r), ¬(p) ne sont pas des formules.

2.1.2 Sous-formules et arbre de formation

Definition 4Soit φ ∈ F(L(A)) une formule ; le sous-ensemble sf(φ) des sous-formules de φ est

(i) si φ := p pour p ∈ At, sf(φ) = {p}(ii) si φ := ¬ψ, sf(φ) = {φ} ∪ sf(ψ)(iii) si φ := ψ ◦ χ, sf(φ) = {φ} ∪ sf(ψ) ∪ sf(χ)

2


Exemple 3sf((p ∨ (q ∧ r))) = {(p ∨ (q ∧ r)), p, (q ∧ r), q, r}

Definition 5Soit φ une formule non-atomique ; l’ensemble sfi(φ) des sous-formules immediates de φ est

(i) sfi(φ) = {ψ} si φ := ¬ψ(ii) sfi(φ) = {ψ,χ} si φ := (ψ ◦ χ)

Definition 6L’arbre de formation d’une formule φ est un arbre

(i) dont la racine est constituee de φ(ii) dont chaque noeud est une sous-formule immediate de son predecesseur(iii) dont chaque noeud terminal est une formule atomique

Exemple 4(p ∨ (q ∧ r))

p (q ∧ r)

q r

2.2 Semantique de L−

La semantique est la partie de la logique qui s’occupe de l’interpretation du langage formel.

2.2.1 Interpretation des connecteurs

Negation

V (φ) V (¬φ)

1 00 1

V (¬φ) = 1 ssi V (φ) = 0V (¬φ) = 1 − V (φ)La negation est interpretee par une fonction neg : {0, 1} → {0, 1} : neg(x) = 1 − x.

Conjonction

V (φ) V (ψ) V ((φ ∧ ψ))

1 1 11 0 00 1 00 0 0

V ((φ ∧ ψ)) ssi V (φ) = V (ψ) = 1V ((φ ∧ ψ)) = min(V (φ), V (ψ))La conjonction est interpretee par une fonction conj : {0, 1} × {0, 1} → {0, 1} : conj(x, y) =min(x, y).

3


Disjonction

V (φ) V (ψ) V ((φ ∨ ψ))

1 1 11 0 10 1 10 0 0

V ((φ ∨ ψ)) = 1 ssi V (φ) = 1 ou V (φ) = 1V ((φ ∨ ψ)) = max(V (φ), V (ψ))La disjonction est interpretee par la fonction disj : {0, 1} × {0, 1} → {0, 1} : disj(x, y) =max(x, y).

2.2.2 Valuation, evaluation, tables de verite

Valuation

Definition 7Une valuation pour le langage L(A)) est une fonction V : F(L(A)) → {0, 1} qui associe achaque formule une valeur de verite telle que

(i) V (¬φ) = 1 ssi V (φ) = 0(ii) V ((φ ∧ ψ)) = 1 ssi V (φ) = V (ψ) = 1(iii) V ((φ ∨ ψ)) = 1 ssi V (φ) = 1 ou V (ψ) = 1

Exemple 5La fonction V (.) telle que V (φ) = 1, V (¬ψ) = 1 n’est pas une valuation.

Definition 8Une assignation (ou valuation atomique) est une fonction qui assigne une valeur de veritea toute formule atomique p ∈ At.

Theoreme 1Soit v : At → {0, 1} une valuation atomique ; il existe une et une seule valuation V :F(L−(A)) → {0, 1} qui etend v, i.e. t.q. pour toute formule atomique p ∈ At, v(p) = V (p).

Proposition 1Soient V et V ′ deux valuations qui s’accordent sur les sous-formules atomiques d’une formuleφ (pour toute formule atomique p ∈ At ∩ sf(φ), V (p) = V ′(p)) ; alors V (φ) = V ′(φ)

Exemple 6La formule φ := (p ∧ (q ∨ r)) contient trois formules atomiques : p, q, r. La proposition nousgarantit que la valeur de verite de φ ne depend que de celles de p, q, r.

Tables de verite

Exemple 7φ := ¬(¬p ∨ ¬q)

4


¬(¬p ∨ ¬q)

(¬p ∨ ¬q)

¬p

p

¬q

q

p q ¬q ¬p (¬p ∨ ¬q) ¬(¬p ∨ ¬q)1 1 0 0 0 11 0 1 0 1 00 1 0 1 1 00 0 1 1 1 0

Remarque : la table de verite montre que la formule ¬(¬p∨¬q) se comporte comme la formule(p ∧ q).

2.2.3 Proprietes et relations semantiques

Definition 9Soit une formule φ ∈ F(L−(A)) et une valuation V ; quand V (φ) = 1, on dit que φ est vraiedans V ou que V est un modele de φ ou satisfait φ. Notation : V |= φ

Remarque : toutes les valuations qui s’accordent avec une ligne de table de verite ou la valeurde la formule est 1 sont des modeles de cette formule.

Definition 10Soit une formule φ ∈ F(L(A)) ;

(i) φ est satisfiable s’il existe une valuation V qui la satisfait.(ii) φ est une tautologie ou une formule valide si toute valuation la satisfait. Notation :

|= φ.(ii) φ est une antilogie si aucune valuation ne la satisfait ;

Exemple 8formule tautologique : (p ∨ ¬p) (principe du tiers-exclu)formule antilogique : (p ∧ ¬p)formule neutre : (p ∨ q)

Definition 11Deux formules φ,ψ ∈ F(L−(A)) sont logiquement equivalentes si pour toute valuation V ,V (φ) = V (ψ). On le note φ ≡ ψ

Proposition 2Soient φ,ψ, χ ∈ F(L−(A)) des formules ;

Double negationφ ≡ ¬¬φLois de De Morgan :¬(φ ∧ ψ) ≡ (¬φ ∨ ¬ψ)¬(φ ∨ ψ) ≡ (¬φ ∧ ¬ψ)Idempotence de ∨ et ∧ :

5


φ ≡ (φ ∨ φ) ≡ (φ ∧ φ)Associativite de ∨ et ∧ :(φ ∨ (ψ ∨ χ)) ≡ ((φ ∨ ψ) ∨ χ)(φ ∧ (ψ ∧ χ)) ≡ ((φ ∧ ψ) ∧ χ)Commutativite de ∨ et ∧ :(φ ∨ ψ) ≡ (ψ ∨ φ)(φ ∧ ψ) ≡ (ψ ∧ φ)Distributivite de ∨ sur ∧ et de ∧ sur ∨ :(φ ∨ (ψ ∧ χ)) ≡ (φ ∨ ψ) ∧ (φ ∨ ψ)(φ ∧ (ψ ∨ χ)) ≡ (φ ∧ ψ) ∨ (φ ∧ ψ)

2.2.4 Consequence logique

Definition 12Soit un ensemble de formules Γ ⊆ F(L(A)) ;

(i) Γ est satisfait par une valuation si pour toute formule φ ∈ Γ, V (φ) = 1. On note [[Γ]]l’ensemble des valuations qui satisfont Γ, de meme que l’on note [[φ]] l’ensemble desvaluations qui satisfont φ.

(ii) Γ est satisfiable s’il existe une valuation qui le satisfait, i.e. [[Γ]] 6= ∅

(iii) Γ est contradictoire s’il n’existe aucune valuation qui le satisfait, i.e. [[Γ]] = ∅

(iv) Deux ensembles de formules Γ et ∆ sont equivalents s’ils sont satisfaits par lesmemes valuations, i.e. [[Γ]] = [[∆]].

Definition 13Soit Γ ⊆ F(L(A)) un ensemble de formules et φ ∈ F(L(A)) une formule. φ est consequence(semantique) de Γ si toute valuation qui satisfait Γ satisfait φ, i.e. [[Γ]] ⊆ [[φ]].Notation : Γ |= φ. Si Γ = {ψ}, on s’autorise a ecrire ψ |= φ.

Exemple 9Considerons l’argument suivant :

(8)

(p ∨ q)¬p

q

(8) est un schema d’argument valide ssi q est consequence logique de Γ = {¬p, (p ∨ q)}.

p q ¬p (p ∨ q)1 1 0 11 0 0 10 1 1 10 0 1 0

Il y a une seule ligne ou les valuations satisfont Γ : la ligne 0, 1. Sur cette ligne, V (q) = 1. Parconsequent, p est consequence logique de Γ.

6


Proposition 3Soient φ,ψ, χ ∈ F(L−(A)) des formules et Γ,Γ′ ⊆ F(L−(A)) des ensembles de formules ;

(i) φ |= φ (reflexivite)(ii) si Γ ⊆ Γ′ et Γ |= φ, alors Γ′ |= φ (monotonie)(iii) si φ |= ψ et ψ |= χ, alors φ |= χ (transitivite)

Proposition 4Soit une formule φ ∈ F(L−(A)). φ est une tautologie ssi φ est consequence logique de toutensemble de formules Γ :

|= φ ssi pour tout Γ, Γ |= φ

2.2.5 Fonctions booleennes et connecteurs

• fonctions booleennes binaires f : {0, 1} × {0, 1} → {0, 1}.• 22

n

fonctions booleennes n-aires.

f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 f13 f14 f15 f16

1 1 0 0 0 0 1 0 0 0 1 1 1 0 1 1 1 11 0 0 0 0 1 0 0 1 1 0 0 1 1 0 1 1 10 1 0 0 1 0 0 1 0 1 0 1 0 1 1 0 1 10 0 0 1 0 0 0 1 1 0 1 0 0 1 1 1 0 1

• f5 = conj

• f15 = disj

Definition 14Un connecteur ◦ (muni de son interpretation) est definissable par un ensemble de connecteursC(munis de leurs interpretations) si pour toute formule (φ ◦ ψ) on trouve une formule χ

logiquement equivalente a (φ ◦ ψ) et ne contenant que des connecteurs de C.

Exemple 10Les equivalences remarquables nous donnent immediatement des resultats de definissabilite :les lois de De Morgan impliquent que ∨ est definissable par {¬,∧} et que ∧ est definissablepar {¬,∨}

3 Le conditionnel materiel

3.1 Definition et proprietes

3.1.1 Morphologie de L

• on ajoute a L− un nouveau connecteur propositionnel que l’on note → - il est parfoisnote ⊃ (le ”fer a cheval”) - et qu’on appelle le conditionnel materiel.

• les definitions morphologiques precedentes sont etendues : → est un connecteur binairequi forme des formules a partir de paires de formules. On note L le nouveau langagepropositionnel obtenu, et F(L)) l’ensemble des formules de ce nouveau langage.

7


3.1.2 Interpretation du conditionnel materiel

• Sextus Empiricus, Adv. Math, VIII”Philon disait que le conditionnel est vrai lorsqu’il ne commence pas avec le vrai pourfinir avec le faux ; de sorte qu’il y a pour ce conditionnel trois facons d’etre vrai et uned’etre faux”

• Frege a Husserl 1906“Mais supposons que les lettres ‘A’ et ‘B’ designent des propositions propres. Alors iln’y a pas seulement des cas dans lesquels A est vrai et des cas dans lesquels A est faux ;mais soit A est vrai, soit A est faux ; tertium non datur. La meme chose vaut de B. Ona donc quatre combinaisons :A est vrai et B est faux,A est vrai et B est vraiA est faux et B est vraiA est faux et B est faux.De celles-ci la premiere, troisieme et quatrieme sont compatibles avec la proposition “siA alors B”, mais non la seconde.”

V (φ) V (ψ) V ((φ→ ψ))

1 1 11 0 00 1 10 0 1

V ((φ→ ψ)) = 0 ssi V (φ) = 1 et V (ψ) = 0L’implication est interpretee par une fonction impl : {0, 1} × {0, 1} → {0, 1} : impl(x, y) = 0ssi x = 1 et y = 0

3.1.3 Proprietes du conditionnel materiel

Tautologies

1. |= ((p → q) → (¬q → ¬p)) (contraposition)

2. |= ((p → q) ∧ (q → r) → (p → r)) (transitivite)

3. |= (((p ∧ q) → r) → (p→ (q → r))) (exportation)

4. |= ((p → (q → r)) → ((p ∧ q) → r)) (importation)

5. |= (¬p→ (p → q)) (faussete de l’antecedent)

6. |= (p → (q → p)) (verite du consequent)

7. |= ((p → q) → p) → p) (loi de Peirce )

Consequences logiques• Les 5 syllogismes fondamentaux ”indemontrables”) de Chrysippe :

1) Modus (ponendo) ponens : p→ q ; p ∴ q

2) Modus (tollendo) tollens : p→ q ; ¬q ∴ ¬p3) ¬(p ∧ q) ; p ∴ ¬q4) p ou q ; p ∴ ¬q5) Syllogisme disjonctif : p ou q ; ¬q ; ∴ p

8


1. {p, (p → q)} |= q (modus ponens)

2. {¬q, (p → q)} |= ¬p (modus tollens)

3. ¬p |= (p→ q) (faussete de l’antecedent, bis)

4. p |= (q → p) (verite du consequent, bis)

5. (p → q) |= ((p ∧ r) → q) (renforcement de l’antecedent)

6. (p ∨ q) |= (¬p→ q) (”du-ou-au-si”)

Theoreme de la deduction• Sextus Empiricus, Adv. Math, VIII, 417

”Ainsi, un argument est reellement valide quand, apres qu’on a conjoint les premisseset forme le conditionnel ayant la conjonction des premisses comme antecedent et laconclusion comme consequent, on trouve que le conditionnel est vrai”

Theoreme 2 (Theoreme semantique de la deduction)Soient φ,ψ des formules.

φ |= ψ ssi |= (φ→ ψ)

Corollaire 1Si Γ = {φ1, ..., φn} est un ensemble fini de formules et ψ une formule quelconque, alors

Γ |= ψ ssi |= ((φ1 ∧ ... ∧ φn) → ψ)

Ce corollaire nous donne une autre methode pour examiner avec les tables de verite lavalidite d’un argument.

Exemple 11Nous avons vu que si {(p → q), p} |= q. Ceci est equivalent a

|= (((p → q) ∧ p) → q)

Theoreme 3 (Theoreme semantique generalise de la deduction)Soient φ1, ...φn, ψ des formules.

{φ1, ..., φn} |= ψ ssi |= (φ1 → ...(φn−1 → (φn → ψ))...)

Equivalences remarquables(φ→ ψ) ≡ (¬φ ∨ ψ)(φ→ ψ) ≡ (¬ψ → ¬φ) (contraposition)

3.2 ”→” et ”si...alors...”

3.2.1 Arguments en faveur de → (“splendeurs” de →)

1. (p → q) est faux quand p est vrai et q est faux.

(9) Jean est venu

(10) Marie n’a pas ete contente

9


(11) Si Jean est venu, Marie a ete contente

2. le modus ponens : la regle d’inference fondamentale

Voir cependant le contre-exemple de V. McGee, ”A Counterexample to Modus Ponens”,Journal of Philosophy, 1985 :

Si un Republicain gagne, alors si Reagan ne gagne pas, Anderson gagnera.Un Republicain gagnera.

Si Reagan ne gagne pas, Anderson gagnera.

3. argument par elimination parmi les fonctions booleennes binaires

4. formalisation des mathematiques :

(12) Si deux nombres ont le meme successeur, alors ils sont identiques

(13) ∀x1∀x2(Sx1 = Sx2 → x1 = x2)

(14) Si 0 a la propriete exprimee par F et si, quand un nombre x a la proprieteexprimee par F , alors son successeur l’a egalement, alors tous les nombres ont lapropriete exprimee par F

(15) (F (0) ∧ ∀x(F (x) → F (Sx)) → ∀x(F (x))

3.2.2 Miseres de → ?

1. les paradoxes de l’implication materielle :

(a) paradoxe de la faussete de l’antecedent :

¬p |= (p→ q) (faussete de l’antecedent, bis)

”si p est faux, p implique n’importe quelle proposition”

(16) Si Paris est en Bretagne, alors 2+2=4

(17) Si Paris est en Bretagne, alors la Lune est en fromage

(18)

Les socialistes ne gagneront pas les prochaines legislatives.

Si les socialistes gagnent les prochaines legislatives,ils instaureront la dictature du proletariat.

(b) paradoxe de la verite du consequent :

p |= (q → p) (verite du consequent, bis)

”si p est vrai, p est implique par n’importe quelle proposition”

(19) Si Chirac est president, alors Paris est en Ile-de-France

(20) Si la Lune est en fromage, alors Paris est en Ile-de-France

(21)Jean fera cours a 10 heures.

Si Jean meurt a 9 heures, alors il fera cours a 10 heures.

(22)2 est pair.

Si la conjecture de Goldbach est fausse, alors 2 est pair.

G. Frege, (1879, Ideographie, Vrin, 1999 :

”la liaison causale qui reside dans le mot ”si” n’est pas exprimee par nos signes”

10


2. RTC (renforcement-transitivite-contraposition) :

(a) renforcement de l’antecedent (p → q) |= ((p ∧ r) → q)

(23) Si Jean ajoute du sucre dans son cafe, il le trouvera meilleur

(24) Si Jean ajoute du sucre et un peu d’essence dans son cafe, il le trouverameilleur

(b) transitivite

(25) Si Jacques gagne l’election, Lionel se consacrera a sa vie familiale

(26) Si Lionel meurt demain, Jacques gagnera l’election

(27) Si Lionel meurt demain, il se consacrera a sa vie familiale

(c) contraposition

(28) Si Goethe avait survecu au-dela de 1832, il serait mort aujourd’hui

(29) Si Goethe n’etait pas mort aujourd’hui, il n’aurait pas survecu au-dela de1832

3. verifonctionnalite : le conditionnel materiel est une fonction de verite (fonctionbooleenne binaire) : si φ,ψ, χ, θ sont des formules telles que

- V (φ) = V (χ)

- V (ψ) = V (θ)

alors necessairement V (φ→ ψ) = V (χ→ θ)

(30) Si je pese 150 kg, je pese moins de 25 kg

(31) Si je pese 150 kg, je pese plus de 100 kg

4. la negation : ¬(p→ q) ≡ (p ∧ ¬q)

(32)Il n’est pas vrai que si Dieu existe, alors les criminels iront au paradis.

Dieu existe et les criminels n’iront pas au paradis.

Couramment, on tend a interpreter la negation d’un conditionnel “si A alors B”plutot comme signifiant “si A, alors non-B”, et non comme une conjonction.

11

Documents

Logique propositionnelle et conditionnel mat´erielmikael.cozic.free.fr/logphil0607-da1.pdf · conditionnel comme conditionnel mat´eriel ... (ii) si φest une formule, alors ¬φest