Lepage Éléments de Logique Contemporaine 2e Édition

F. Lepage : Elements de logique contemporaine(2e edition)

Solutions aux exercices

1 Les concepts fondamentaux

Exercice 1

(a) Il s’agit d’un enonce (complexe).

(b) Ce n’est pas un enonce. Il s’agit d’un ordre.

(c) Il s’agit d’un enonce (atomique).

(d) Il s’agit d’un enonce (complexe).

Exercice 2

(a) Le tout n’est pas un enonce. On donne un ordre dans la premiere partie, qui n’est pasun enonce, tandis que la seconde partie est un enonce ; or, bien que cette seconde partiesoit grammaticalement independante, elle peut etre interpretee comme etant la cause del’ordre.

(b) Il s’agit d’un enonce. Malgre son caractere apparemment absurde, cette affirmation pour-rait etre verifiable dans un contexte donne.

(c) Il s’agit d’un enonce. Si la personne est sincere lorsqu’elle jure, on peut verifier ce qu’elleaffirme.

Exercice 3

(a) Il ne s’agit pas d’un enonce. On ne fait que donner des ordres.

(b) Il s’agit d’un enonce. Malgre son caractere apparemment absurde, cette affirmation pour-rait etre verifiable dans un contexte donne.

(c) Il s’agit d’un enonce. On pourrait verifier ce qui est ainsi declare.

Exercice 4

(a) Cas indetermine, car p et q s’excluent mutuellement : une porte ne peut etre a la foisouverte et fermee.

(b) Le « ou» est exclusif. On impose une alternative : soit il fait beau et je vais a la campagne,soit il ne fait pas beau et je n’y vais pas ; or, il ne s’agit de possibilites s’excluant pasmutuellement a la base.

(c) Le « ou » est inclusif. Il pourrait a la fois pleuvoir et neiger au cours du meme mois.

(d) Le cas est indetermine : du fait que les « ou » inclusifs et exclusifs s’excluent mutuelle-ment, je ne peux les dire en meme temps.

(e) Le cas est indetermine : un nombre a ne peut-etre a la fois egal ou plus grand quelui-meme ou a un nombre b.

Exercice 5

(a) Deux reponses sont possibles. Dans la mesure ou l’on est dans un monde ou il est possibled’etre a la fois pour et contre quelqu’un, cet enonce serait faux et le « ou » exclusif. Or,dans un monde ou cela est impossible, le cas demeure indetermine.

(b) Le « ou » est exclusif. On peut presumer qu’il s’agit d’un choix.

(c) Le « ou » est inclusif. L’interdiction s’applique autant au fait de manger que de fumer.

Exercice 6

(a) Le cas est indetermine. On considere, en effet, que les deux types d’action s’excluentmutuellement.

(b) Le « ou » est exclusif. C’est une alternative : la personne ne peut rester si elle ne se taitpas ; or, ce sont tout de meme deux possibilites qui ne s’excluent pas naturellement a labase.

(c) Le « ou » est inclusif. La realite humaine comporte a la fois tous ces aspects.

Exercice 7

(a) Faux. Ce n’est qu’une expression de la langue-objet. Un nom ne chante pas.

(b) Vrai. On parle de l’expression pour expliquer ce qu’elle signifie.

(c) Vrai. On parle de l’expression, soit le nombre de lettres qu’elle contient.

(d) Faux. L’expression dont on parle commence par un R.

(e) Vrai. L’expression dont on parle est placee entre guillemets.

(f) Vrai. C’est le nom que l’on donne a un nom.

Exercice 8

Vrai, car Aristote n’est alors plus un nom, mais une personne (une chose).

Exercice 9

Curieusement, « Venus », « Etoile du matin » et « Etoile du soir » designent un seul etmeme astre : Venus. Les anciens ont mis un certain temps a decouvrir cette identite. Venusayant un orbite infraterrestre, elle ne s’eloigne jamais (visuellement parlant) beaucoup duSoleil. C’est egalement l’astre le plus brillant apres la Lune et le Soleil. Cela explique quependant quelques mois, elle apparaıt aussitot le Soleil couche, un peu avant les etoiles, c’est

l’Etoile du soir. Durant une autre periode, elle apparaıt un peu avant le lever du soleil pouretre la derniere a palir dans l’aube naissante, c’est l’Etoile du matin. « Etoile du matin » et« Etoile du soir » designent le meme objet, l’Etoile du matin ou l’Etoile du soir ou Venus.Cela n’empeche pas que si vous vous exclamez par une belle soiree de juin devant la beautede l’Etoile du matin, l’excuse d’avoir suivi le cours de logique ne sera pas suffisante pourvous epargner d’etre ridicule : le soir, on voit l’Etoile du soir que, dans ces circonstances, onne peut pas appeler « Etoile du matin ».

Exercice 10

(a) Il y a 21 = 2 lignes pour les connecteurs unaires. Or, il y a donc 22 = 4 facons de remplirla deuxieme colonne et autant de tables de verite differentes. Par consequent, il y a 4connecteurs possibles. Voici leurs tables :

p p u1 pV VF V

p p u2 pV VF F

p p u3 pV FF V

p p u4 pV FF F

(b) Voici les autres tables pour les connecteurs binaires :

p q p b8 qV V VV F VF V VF F V

p q p b9 qV V VV F VF V FF F V

p q p b10 qV V FV F FF V FF F F

p q p b11 qV V VV F VF V FF F F

p q p b12 qV V VV F FF V VF F F

p q p b13 qV V FV F FF V VF F V

p q p b14 qV V FV F VF V FF F V

p q p b15 qV V FV F FF V VF F F

p q p b16 qV V FV F VF V FF F F

Exercice 11

Il y a 23 = 8 lignes pour les connecteurs ternaires. Or, il y a donc 28 = 256 facons de remplirla quatrieme colonne et autant de tables de verite differentes. Par consequent, il y a 256connecteurs possibles.

Exercice 12

(a)

p q r ¬p ∨ q p ≡ q r ⊃ (p ≡ q) (¬p ∨ q) ∧ (r ⊃ (p ≡ q))V V V V V V VV V F V V V VV F V F F F FV F F F F V FF V V V F F FF V F V F V VF F V V V V VF F F V V V V

(b)

p q p ⊃ q (p ⊃ q) ⊃ q ((p ⊃ q) ⊃ q) ⊃ pV V V V VV F F V VF V V V FF F V F V

(c)

p q p ⊃ ¬q ((p ⊃ ¬q) ≡ pV V F FV F V VF V V FF F V F

(d)

p q r p ∧ ¬p q ∨ r r ⊃ ¬p (q ∨ v) ⊃ (r ⊃ ¬p) ¬((p ∧ ¬p) ⊃ ((q ∨ r) ⊃ (r ⊃ ¬p)))V V V F V F F FV V F F V V V FV F V F V F F FV F F F F V V FF V V F V V V FF V F F V V V FF F V F V V V FF F F F F V V F

(e)

p q p ⊃ q (p ⊃ q) ≡ qV V V VV F F VF V V VF F V F

(f)

p p ≡ p (p ≡ p) ≡ pV V VF V F

Exercice 13

(a) L’enonce est vrai :

p q r ¬p ⊃ q p ≡ q r ≡ (p ≡ q) (¬p ⊃ q) ∨ (r ≡ (p ≡ q))V F F V F V V

(b) L’enonce est vrai :

p q r q ∨ r p ∨ (q ∨ r) r ⊃ q (p ∨ (q ∨ r)) ∧ (r ⊃ q)V F F F V V V

(c) L’enonce est faux :

p q r q ∧ r p ∧ (q ∧ r)V F F F F

(d) L’enonce est vrai :

p q r p ⊃ q p ⊃ r (p ⊃ q) ⊃ (p ⊃ r)V F F F F V

(e) L’enonce est vrai :

p p ⊃ pV V

(f) L’enonce est vrai :

p q r q ∨ r r ⊃ ¬p (q ∨ r) ⊃ (r ⊃ ¬p)V F F F V V

2 Connecteurs logiques et langue naturelle

Exercice 1

(a) Tout ce qui brille est or.

(b) Il y a des chemins qui ne menent pas a Rome.

(c) Aucun Quebecois n’a plus d’une voiture.

(d) Cette salle n’est pas a moitie vide.

(e) Moins de 80 pour cent des Francais savent lire.

Exercice 2

(a) Ces enonces ne sont pas la negation l’un de l’autre. Si les deux sont vrais, tous les cheminspourraient mener a Rome alors que certains menent a la fois a Rome et a Paris. Si lesdeux sont faux, on pourrait imaginer que tous les chemins menent nulle part.

(b) Ces enonces ne sont pas la negation l’un de l’autre. S les deux enonces sont faux, ilspourraient etre d’egale valeur.

(c) Ces enonces ne sont pas la negation l’un de l’autre. Dans un aeroport, il pourrait a lafois y avoir des avions qui arrivent a l’heure et d’autres qui arrivent en retard. Les deuxne s’excluent pas.

(d) Ces enonces sont la negation l’un de l’autre.

(e) Ces enonces sont la negation l’un de l’autre.

(f) Ces enonces sont la negation l’un de l’autre.

Exercice 3

(a) Je le ferai encore.

(b) Toute verite est bonne a dire.

(c) Tous les etudiants travaillent suffisamment.

(d) Tous les hommes aiment les femmes.

(e) Moins de dix pour cent des Quebecois ont au moins deux voitures.

Exercice 4

(a) Parfois le mot « toujours » ne prend pas de « s ».

(b) Toute personne ferait mieux de parler.

(c) La majorite des Quebecois ne va pas voter oui au referendum.

(d) Ce que j’ai fait, certaines betes l’auraient fait.

(e) Plus de 65 pour cent des Quebecois vont voter non ou vont s’abstenir.

Exercice 5

Les deux enonces ne sont pas la negation l’un de l’autre, car ils sont synonymes. Si sontemoignage n’est pas a moitie non-vrai, c’est qu’il est a moitie vrai.

Exercice 6

(a) Pierre et Marie s’aiment.

(b) Ou Pierre aime Marie, ou Marie aime Pierre, ou alors ils s’aiment tous les deux.

(c) Pierre n’aime pas Marie, ou Marie n’aime pas Pierre, ou ils ne s’aiment ni un ni l’autre.

(d) Pierre et Mairie ne s’aiment pas.

(e) Il n’est pas vrai que Pierre et Marie s’aiment.

(f) Pierre n’aime pas Marie ou Marie n’aime pas Pierre, ainsi il n’est vrai qu’ils s’aimentmutuellement.

(g) Il n’est pas vrai que Pierre n’aime pas Marie.

Exercice 7

(a) p ∧ q

(b) ¬p ∧ ¬q

(c) p ∧ ¬q

(d) ¬(p ∧ ¬q)(e) p ∧ ¬(p ∧ q)(f) ¬(q ∧ p)(g) ¬q ∨ ¬p

(h) p ∧ ¬q

Exercice 8

(a) p : Les traductions proposees par le professeur sont adequates.q : Les traductions sont acceptees par les etudiants.

p ⊃ q. Le monde actuel peut correspondre a n’importe quelle ligne. L’enonce peut doncetre vrai comme il peut etre faux.

(b) p : Les traductions proposees par le professeur sont adequates.q : Les traductions sont acceptees par les etudiants.

q ⊃ p. Le monde actuel peut correspondre a n’importe quelle ligne. L’enonce peut doncetre vrai comme il peut etre faux.

(c) p : Le cours se deroule.q : Le professeur est arrive.

p ⊃ q. Le monde actuel ne correspond pas a la deuxieme ligne, donc l’enonce est vrai.Voyons cela :– Pour p vrai et q vrai : si le cours se deroule, alors c’est que le professeur est arrive.

Dans le monde actuel, cela correspond au deroulement du cours (possible, vrai).– Pour p vrai et q faux : si le cours se deroule, alors c’est que le professeur n’est pas arrive.

Le monde actuel ne peut correspondre avec cette interpretation, car il est impossibleque le cours soit donne sans le professeur (pas de monde possible).

– Pour p faux et q vrai : si le cours ne se deroule pas, alors c’est que le professeur estarrive. Dans le monde actuel, cela correspond a la situation apres le deroulement ducours (possible, vrai).

– Pour p faux et q faux : si le cours ne se deroule pas, alors c’est que le professeur n’estpas arrive. Dans le monde actuel, cela correspond a la situation avant le deroulementdu cours (possible, vrai).

(d) p : Les souris sont des oiseaux.q : Les souris ont des ailes.

p ⊃ q. Le monde actuel correspond seulement a p faux et q faux, donc l’enonce est vrai.

(e) p : Les etudiants reussissent.q : Les etudiants etudient.

p ⊃ q. Le monde actuel peut correspondre a n’importe quelle ligne. L’enonce peut doncetre vrai comme il peut etre faux.

(f) p : Pierre reussit le cours de logique.q : Pierre assiste au cours.

¬(q ⊃ p). Le monde actuel peut correspondre a n’importe quelle ligne. Il peut donc etrevrai comme il peut etre faux.

(g) p : L’accuse est innocent.q : L’accuse a un alibi.

¬(p ⊃ q). Le monde actuel ne peut correspondre au cas ou p est faux et q vrai, car uncoupable ne peut avoir d’alibi. L’enonce est donc vrai.

(h) p : L’accuse est coupable.q : L’accuse a un alibi.

p ⊃ ¬q. Le monde actuel ne peut correspondre au cas ou p est vrai et q vrai, car uncoupable ne peut avoir d’alibi. L’enonce est donc vrai.

(i) p : Dieu existe.q : Il y a un etre superieur a l’homme.

q ⊃ p. Le monde actuel peut correspondre a n’importe quelle ligne.

(j) p : L’accuse sera condamne.q : On capture le vrai coupable.

¬p ⊃ q. Le monde actuel peut correspondre a n’importe quelle ligne.

(k) p : 1+1=4.q : 1=2.

(p ⊃ q)∧ (q ⊃ p) ou p ≡ q. Le monde actuel correspond a p faux et q faux, donc l’enonceest vrai.

(l) p : Ce quadrilatere est un carre.q : Ce quadrilatere est un losange.

(p ⊃ q). Le monde actuel ne correspond pas a la deuxieme ligne, donc l’enonce est vrai.

Exercice 9

(a) p : Pierre travaille.q : Pierre reussit.

q ⊃ p.

(b) p : Pierre devient richeq : Pierre devient celebre.r : Pierre travaille tres fort.s : Le pere de Pierre est tres riche.

(r ∨ s) ⊃ (p ∧ q).(c) p : Marie aime bien le cours de logique.

q : Pierre aime bien le cours de logique.

p ∧ ¬q.

(d) p : La Suede perd le prochain match.q : Les Americains sont battus par les Tcheques.

r : L’equipe canadienne a une chance de remporter la coupe.

¬(p ∧ q) ⊃ ¬r.

(e) p : Je prends mon parapluie.q : Il pleut.r : Je me trompe completement.

¬r ⊃ (p ⊃ ¬q).

Exercice 10

(a) Pierre ne travaille pas et il reussira. q ∧ ¬p

(b) Bien que Pierre travaille tres fort ou que son pere est tres riche, il ne deviendra pas richeet celebre. (r ∨ s) ∧ ¬(p ∧ q)

(c) Si Marie aime le cours de logique, alors Pierre l’aime aussi. p ⊃ q

(d) Bien que la Suede ne perde pas le prochain match et que les Americains seront battuspar les Tcheques, l’equipe canadienne a une chance de remporter la coupe. ¬(p∧ q)∧ r.

(e) Je ne me trompe pas completement, mais je prends mon parapluie et il pleuvra. ¬r ∧(p ∧ q).

Exercice 11

(a) Si les poules n’ont pas de dents et sont des mammiferes, alors les mammiferes sans dentssont ovipares.

(b) Si les poules ont des dents ou les mammiferes sans dents sont ovipares, alors les poulessont des mammiferes.

(c) Les poules n’ont pas de dents et ne sont pas des mammiferes, et pourtant les mammiferessans dents sont ovipares.

(d) Si les mammiferes sans dents sont ovipares, ou les poules ont des dents ou sont desmammiferes, mais elles ne sont pas les deux.

Exercice 12

(a) p : Tu te calmes.q : On t’ecoute.

q ⊃ p

(b) p : Parizeau devient president de la Republique du Quebec.q : Le oui l’emporte.r : Lucien Bouchard se retire de la politique.

p ≡ (q ∧ r)(c) p : Je vais au party.

q : Sylvie y va.r : Johanne y va.

p ⊃ (q ∨ r)

(d) p : Neige en novembre.q : Noel en decembre.

p ⊃ q

(e) p : Pierre a obtenu une moyenne de 4, 2 au bac.q : Pierre a triche.r : Je peux aller en France a la nage.

(p ∧ ¬q) ⊃ r

Exercice 13

(a) Tu te calmes, mais on ne t’ecoute pas. q ∧ ¬p

(b) Le fait que le oui l’emporte et que Lucien Bouchard se retire de la politique ne signifiepas que Parizeau deviendra president de la Republique du Quebec. ¬(p ≡ (q ∧ r))

(c) Je vais au party, alors que ni Sylvie, ni Johanne n’y vont. p ∧ (¬q ∧ ¬r)(d) Neige en novembre, mais pas de Noel en decembre. p ∧ ¬q

(e) Pierre a obtenu une moyenne de 4.2 au bac sans tricher, mais je ne peux pas aller enFrance a la nage. (p ∧ ¬q) ∧ ¬r

Exercice 14

(a) p : Le monde a un commencement.q : Le monde a une fin.

Le monde n’a ni commencement ni fin : ¬p ∧ ¬q. Pour la negation : le monde a uncommencement ou une fin : p ∨ q. Voici les deux tables de verite :

¬p ∧ ¬q p ∨ qF VF VF VV F

(b) p : L’ornithorynque est un mammifere.q : L’ornithorynque pond des œufs.

Bien que l’ornithorynque soit un mammifere, il pond des œufs : p∧ q. Pour la negation :l’ornithorynque n’est pas un mammifere ou il ne pond pas d’œufs : ¬p ∨ ¬q. Voici lesdeux tables de verite :p ∧ q ¬p ∨ ¬q

V FF FF FF V

(c) p : Le reglement est tres strict.q : Le reglement est le meme pour tout le monde.

r : Les etudiants ont tort de contester le reglement.

Si le reglement est tres strict mais est le meme pour tout le monde, alors les etudiantsont tort de le contester : (p∧q) ⊃ r. Pour la negation : le reglement est tres strict et est lememe pour tout le monde, mais les etudiants n’ont pas tort de le contester : (p∧ q)∧¬r.Voici les deux tables de verite :(p ∧ q) ⊃ r (p ∧ q) ∧ ¬r

V FF VV FV FV FV FV FV F

(d) p : Il pleut.q : Je prends mon parapluie.

Qu’il pleuve ou non, je prends mon parapluie : (p ∨ ¬p) ⊃ q. Pour la negation : il pleutou il ne pleut pas, mais je ne prends pas mon parapluie : (p ∨ ¬p) ∧ ¬q. Voici les deuxtables de verite :(p ∨ ¬p) ⊃ q (p ∨ ¬p) ∧ ¬q

V FF VV FF V

(e) p : L’oisivete est mere de tous les vices.q : La luxure naıt de l’oisivete.r : La luxure est un vice.

Si l’oisivete est mere de tous les vices et que la luxure ne peut naıtre de l’oisivete, alorsla luxure n’est pas un vice : (p∧¬q) ⊃ ¬r. Pour la negation : l’oisivete est mere de tousles vices et la luxure ne peut naıtre de l’oisivete, mais la luxure un vice : (p ∧ ¬q) ∧ r.Voici les deux tables de verite :(p ∧ ¬q) ⊃ ¬r (p ∧ ¬q) ∧ r

V FV FF VV FV FV FV FV F

3 Les tautologies et les contradictons

Exercice 1

(a) Effective : bien que la methode soit laborieuse, voire inutilisable pour un n tres grand,on peut passer en revue tous les entiers inferieurs.

(b) Non-effective : on ne sait pas s’il existe une telle sequence. On pourrait ne jamais entrouver une. Cette procedure fonctionne avec certitude si la reponse a la question estoui, mais ne fonctionne pas si la reponse est non. Une veritable procedure doit fonctionnerdans les deux cas.

(c) Non-effective : il y a une infinite de combinaisons possibles de nombres pour remplacerx tandis que la racine pourrait ne pas exister. On pourrait ne jamais en trouver une.

(d) Effective : comme une telle equation donne toujours la racine, quand elle existe, on peutsavoir s’il existe ou non une racine entiere positive.

(e) Impossible a determiner. Sur le plan theorique, cela est evidemment possible, car onpourrait prendre les grains un a un jusqu’a ce que le compte soit complet. Or, d’un pointde vue pratique, on risque des le depart de ne pas s’entendre sur la definition d’un grainde sable.

Exercice 2

p ⊃ ¬q p ⊃ ¬¬qV VF FV VV V

Exercice 3

(a) (p ⊃ q) |= (¬q ⊃ ¬p). Du fait que q decoule de p, on peut conclure que non p decoule denon q.

(b) (p ⊃ q) ∧ (q ⊃ r) |= (p ⊃ r). Si q decoule de p et que r decoule de q, on peut conclureque r decoule de p.

(c) (p ∧ q) ⊃ r |= p ⊃ (q ⊃ r). De l’hypothese que de p et de q il decoule que r, on peutconclure que de p il decoule que de q decoule r.

(d) p ⊃ (q ⊃ r) |= (p∧ q) ⊃ r. Du fait que de p decoule que de q decoule r, on peut conclureque r decoule de l’hypothese que p et q.

(e) (p ⊃ q) ∧ (p ⊃ ¬q) |= ¬p. Si p entraıne le vrai comme le faux, c’est que p est faux.

(f) (p ⊃ ¬p) |= ¬p. Si p entraıne sa propre negation, c’est que p est faux.

(g) (¬p ⊃ q) ∧ (¬p ⊃ ¬q) |= p. Si, de l’hypothese que p est faux, nous pouvons deduire levrai comme le faux, c’est que p est vrai.

(h) (¬p ⊃ p) |= p. Si, de l’hypothese que p est faux, il decoule que p est vrai, c’est que p estvrai.

(i) p |= (q ⊃ p). De l’hypothese que p est vrai, on peut conclure que p decoule de n’importequel q. Autre interpretation : le vrai decoule du vrai comme du faux.

(j) ¬p |= (p ⊃ q). De l’hypothese que p est faux, on peut conclure que p entraıne n’importequel q. Autre interpretation : le faux entraıne le vrai comme le faux.

Exercice 4

(a) L’enonce n’est pas une tautologie :

p q p ⊃ q q ⊃ p (p ⊃ q) ⊃ (q ⊃ p)V V V V VV F F V VF V V F FF F V V V

(b) L’enonce est une tautologie :

p q p ∧ q q ∨ p (p ∧ q) ⊃ (q ∨ p)V V V V VV F F V VF V F V VF F F F V

(c) L’enonce n’est pas une tautologie :

p q p ∨ q q ∧ p (p ∨ q) ⊃ (q ∧ p)V V V V VV F V F FF V V F FF F F F V

(d) L’enonce est une tautologie :

p q r p ⊃ q q ⊃ r ¬(p ⊃ q) ⊃ (q ⊃ r)V V V V V VV V F V F VV F V F V VV F F F V VF V V V V VF V F V F VF F V V V VF F F V V V

Exercice 5

(a) Si p entraıne q, alors q entraıne p. Ce principe n’est pas intuitivement valide et l’enoncecorrespondant n’est pas une tautologie.

(b) Si p et q sont tous les deux vrais, alors l’un des deux au moins est vrai. Ce principe estintuitivement valide et l’enonce correspondant est une tautologie.

(c) Si p ou q est vrai, alors les deux le sont. Ce principe n’est pas intuitivement valide etl’enonce correspondant n’est pas une tautologie.

(d) Si p n’entraıne pas q, alors q entraıne r. Ce principe ne semble pas intuitivement valideet pourtant l’enonce est tautologique. Ceci decoule du principe de bivalence : en effet,si p n’entraıne pas q, c’est que p est vrai et que q est faux ; mais si q est faux, alors ilentraıne r, que ce dernier soit vrai ou faux.

Exercice 6

Cela correspond au schema de la matrice.p q ¬(¬p ∨ q) q ∧ p ¬(¬p ∨ q) ∨ (q ∧ p)V V F V VV F V F VF V F F FF F F F F

Exercice 7

(a) p ⊃ (q ⊃ p) ≡ ¬p ∨ (¬q ∨ p) > >⊥ ⊥

∨

> ⊥> ⊥

∨ > >⊥ ⊥

⊥ ⊥> >

∨ ⊥ >⊥ >

∨ > >⊥ ⊥

⊥ ⊥> >

∨ > >⊥ >

> >> >

C’est donc une tautologie.

(b) ((p ⊃ q)∧ (p ⊃ ¬q)) ⊃ ¬p ≡ ¬((p ⊃ q)∧ (p ⊃ ¬q))∨¬p ≡ ¬((¬p∨ q)∧ (¬p∨¬q))∨¬p

> >⊥ ⊥

∨ > ⊥> ⊥

∧

> >⊥ ⊥

∨ > ⊥> ⊥

∨ > >⊥ ⊥

⊥ ⊥> >

∨ > ⊥> ⊥

∧ ⊥ ⊥> >

∨ ⊥ >⊥ >

∨ ⊥ ⊥> >

> ⊥> >

∧ ⊥ >> >

∨ ⊥ ⊥> >

⊥ ⊥> >

∨ ⊥ ⊥> >

> >⊥ ⊥

∨ ⊥ ⊥> >

> >> >

C’est donc une tautologie.

(c) ((p ⊃ q) ≡ p) ≡ ((p ⊃ q) ⊃ p) ∧ (p ⊃ (p ⊃ q)) ≡ (¬(¬p ∨ q) ∨ p) ∧ (¬p ∨ (¬p ∨ q))

> >⊥ ⊥

∨ > ⊥> ⊥

∨

> >⊥ ⊥

∧

> >⊥ ⊥

∨

> >⊥ ⊥

∨ > ⊥> ⊥

⊥ ⊥> >

∨ > ⊥> ⊥

∨ > >⊥ ⊥

∧

⊥ ⊥> >

∨ ⊥ ⊥> >

∨ > ⊥> ⊥

> ⊥> >

∨ > >⊥ ⊥

∧

⊥ ⊥> >

∨ > ⊥> >

⊥ >⊥ ⊥

∨ > >⊥ ⊥

∧ > ⊥> >

> >⊥ ⊥

∧ > ⊥> >

> ⊥⊥ ⊥

Ce n’est donc pas une tautologie.

(d) (p ∧ q) ⊃ (p ∨ q) ≡ ¬(p ∧ q) ∨ (p ∨ q)

> >⊥ ⊥

∧ > ⊥> ⊥

∨ > >⊥ ⊥

∨ > ⊥> ⊥

> ⊥⊥ ⊥

∨ > >> ⊥

⊥ >> >

∨ > >> ⊥

> >> >

C’est donc une tautologie.

Exercice 8

Soit : p ⊃ (q ⊃ p) ou p |= (q ⊃ p). On a : p ⊃ (q ⊃ p) ≡ ¬p ∨ (¬q ∨ p). En effectuant latransformation duale, on peut verifier que : p ∧ ¬(¬q ∨ p) est une contradiction :

> >⊥ ⊥

∧

> ⊥> ⊥

∨ > >⊥ ⊥

> >⊥ ⊥

∧ ⊥ >⊥ >

∨ > >⊥ ⊥

> >⊥ ⊥

∧ > >⊥ >

> >⊥ ⊥

∧ ⊥ ⊥> ⊥

⊥ ⊥⊥ ⊥

Exercice 9

Il y a 2n nœuds ou matrices pour n = 2m ou m represente le nombre de connecteurs. Donc,il y aura 2(25) = 232 matrices.

4 Methodes syntaxiques elementaires

Exercice 1

(a) |= (p ⊃ q) ∨ (q ⊃ p)

Demonstration.

(¬p ∨ q) ∨ (¬q ∨ p) Elimination de ⊃((¬p ∨ q) ∨ ¬q) ∨ p Associativite

(¬p ∨ (q ∨ ¬q)) ∨ p Associativite

(¬p ∨ 1) ∨ p Tiers exclu

1 ∨ p Element absorbant

1 Element absorbant

(b) |= (p ≡ q) ⊃ (p ⊃ q)

Demonstration.

((p ∧ q) ∨ (¬p ∧ ¬q)) ⊃ (p ⊃ q) Elimination de ≡¬((p ∧ q) ∨ (¬p ∧ ¬q)) ∨ (¬p ∨ q) Elimination de ⊃

(¬(p ∧ q) ∧ ¬(¬p ∧ ¬q)) ∨ (¬p ∨ q) Loi de De Morgan

((¬p ∨ ¬q) ∧ (p ∨ q)) ∨ (¬p ∨ q) Loi de De Morgan/Double negation

((¬p ∨ ¬q) ∨ (¬p ∨ q)) ∧ ((p ∨ q) ∨ (¬p ∨ q)) Distributivite de ∨ sur ∧(¬p ∨ (¬q ∨ (¬p ∨ q))) ∧ (((p ∨ q) ∨ ¬p) ∨ q) Associativite

(¬p ∨ (¬q ∨ (q ∨ ¬p))) ∧ (((q ∨ p) ∨ ¬p) ∨ q) Commutativite

(¬p ∨ (¬q ∨ q) ∨ ¬p) ∧ (q ∨ (p ∨ ¬p) ∨ q) Associativite

(1 ∨ ¬p) ∧ (1 ∨ q) Tiers exclu et idempotence

1 ∧ 1 Element absorbant

1 Idempotence

(c) |= ((p ⊃ q) ∧ (q ⊃ r)) ⊃ (p ⊃ r)

Demonstration.

¬((¬p ∨ q) ∧ (¬q ∨ r)) ∨ (¬p ∨ r) Elimination de ⊃(¬(¬p ∨ q) ∨ ¬(¬q ∨ r)) ∨ (¬p ∨ r) Loi de De Morgan

((p ∧ ¬q) ∨ (q ∧ ¬r)) ∨ (¬p ∨ r) Loi de De Morgan/Double negation

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

((p ∨ ¬p) ∧ (¬q ∨ ¬p)) ∨ ((q ∨ r) ∧ (¬r ∨ r)) Distributivite de ∨ sur ∧(1 ∧ (¬q ∨ ¬p)) ∨ ((q ∨ r) ∧ 1) Tiers exclu

(¬q ∨ ¬p) ∨ (q ∨ r) Element neutre

(¬p ∨ ¬q) ∨ (q ∨ r) Commutativite

(¬p ∨ (¬q ∨ q)) ∨ r Associativite

(¬p ∨ 1) ∨ r Tiers exclu

1 ∨ r Element absorbant

1 Element absorbant

(d) |= (p ⊃ q) ∨ (q ⊃ r)

Demonstration.

(¬p ∨ q) ∨ (¬q ∨ r) Elimination de ⊃(¬p ∨ ((q ∨ ¬q)) ∨ r Associativite

(¬p ∨ 1) ∨ r Tiers exclu

1 ∨ r Element absorbant

1 Element absorbant

Exercice 2

(a) |= (p ⊃ ¬p) ⊃ ¬p

Demonstration.

¬(¬p ∨ ¬p) ∨ ¬p Elimination de ⊃¬(¬p) ∨ ¬p Idempotence

p ∨ ¬p Double negation

1 Tiers exclu

(b) |= (p ∧ (p ∨ q)) ≡ p

Demonstration.

((p ∧ (p ∨ q)) ∧ p) ∨ (¬(p ∧ (p ∨ q)) ∧ ¬p) Elimination de ≡(((p ∨ 0) ∧ (p ∨ q)) ∧ p) ∨ (¬(p ∧ (p ∨ q)) ∧ ¬p) Element neutre

(((p ∨ (0 ∧ q)) ∧ p) ∨ (¬(p ∧ (p ∨ q)) ∧ ¬p) Anti-distributivite de ∨ sur ∧((p ∨ 0) ∧ p) ∨ (¬(p ∧ (p ∨ q)) ∧ ¬p) Element absorbant

((p ∧ p) ∨ (¬(p ∧ (p ∨ q)) ∧ ¬p) Element neutre

p ∨ (¬(p ∧ (p ∨ q)) ∧ ¬p) Idempotence

p ∨ ((¬p ∨ ¬(p ∨ q)) ∧ ¬p) Loi de De Morgan

(p ∨ (¬p ∨ ¬(p ∨ q))) ∧ (p ∨ ¬p) Distributivite de ∨ sur ∧((p ∨ ¬p) ∨ ¬(p ∨ q))) ∧ 1 Associativite et Tiers exclu

(p ∨ ¬p) ∨ ¬(p ∨ q) Element neutre

1 ∨ ¬(p ∨ q) Tiers exclu

1 Element absorbant

Exercice 3

(a) |= ¬(p ⊃ q) ⊃ (p ∧ ¬q))

Demonstration.

(¬p ∨ q) ∨ (p ∧ ¬q) Elimination de ⊃¬p ∨ (q ∨ (p ∧ ¬q)) Associativite

¬p ∨ ((q ∨ p) ∧ (q ∨ ¬q)) Distributivite de ∨ sur ∧¬p ∨ ((q ∨ p) ∧ 1) Tiers exclu

¬p ∨ (q ∨ p) Element neutre

¬p ∨ (p ∨ q) Commutativite

(¬p ∨ p) ∨ q Associativite

1 ∨ q Tiers exclu

1 Element absorbant

(b) |= (p ⊃ (q ⊃ r)) ⊃ ((p ∧ q) ⊃ r)

Demonstration.

¬(¬p ∨ (¬q ∨ r)) ∨ (¬(p ∧ q) ∨ r) Elimination de ⊃(p ∧ ¬(¬q ∨ r)) ∨ ((¬p ∨ ¬q) ∨ r) Loi de De Morgan

(p ∧ (q ∧ ¬r)) ∨ ((¬p ∨ ¬q) ∨ r) Loi de De Morgan

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

(p ∧ q ∧ ¬r) ∨ ¬(p ∧ q ∧ ¬r) Loi inversee de De Morgan

1 Tiers exclu

Exercice 4

(a) |= p ∨ (p ∧ q) ≡ p.

Demonstration.

((p ∨ (p ∧ q)) ∧ p) ∨ (¬(p ∨ (p ∧ q)) ∧ ¬p) Elimination de ≡(p ∧ p) ∨ (p ∧ q ∧ p) ∨ (¬p ∧ ¬(p ∧ q) ∧ ¬p) Distributivite de ∧ sur ∨/Loi de De Morgan

p ∨ (p ∧ q) ∨ (¬p ∧ (¬p ∨ ¬q)) Idempotence/Loi de De Morgan

(p ∧ q) ∨ p ∨ (¬p ∧ (¬p ∨ ¬q)) Commutativite

(p ∧ q) ∨ (p ∨ (¬p ∧ (¬p ∨ ¬q))) Associativite

(p ∧ q) ∨ ((p ∨ ¬p) ∧ (p ∨ (¬p ∨ ¬q))) Distributivite de ∨ sur ∧(p ∧ q) ∨ (1 ∧ (p ∨ (¬p ∨ ¬q))) Tiers exclu

(p ∧ q) ∨ (p ∨ (¬p ∨ ¬q)) Element neutre

(p ∧ q) ∨ (p ∨ ¬p) ∨ ¬q Associativite

(p ∧ q) ∨ 1 ∨ ¬q Tiers exclu

(p ∧ q) ∨ ¬q ∨ 1 Commutativite

((p ∧ q) ∨ ¬q) ∨ 1 Associativite

1 Element absorbant

(b) On doit montrer que p ∨ (p ∧ q) ≡ p.

Demonstration.

p ∨ (p ∧ q)(p ∧ 1) ∨ (p ∧ q) Element neutre

p ∧ (1 ∨ q) Anti-distributivite de ∨ sur ∧p ∧ 1 Element absorbant

p Element neutre

Exercice 5

(a) (q ∨ r) ⊃ (r ⊃ ¬p)¬(q ∨ r) ∨ (¬r ∨ ¬p) Elimination de ⊃

(¬q ∧ ¬r) ∨ (¬r ∨ ¬p) Loi de De Morgan

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

. . . . . .

(p ∧ ¬q ∧ ¬r) ∨ (¬p ∧ ¬q ∧ ¬r) ∨ (p ∧ q ∧ ¬r)∨...(¬p ∧ q ∧ ¬r) ∨ (¬p ∧ q ∧ r) ∨ (¬p ∧ ¬q ∧ r) FNDTD

(b) p ≡ q

(p ∧ q) ∨ (¬p ∧ ¬q) Elimination de ≡ et FNDTD

(c) p ⊃ (p ∧ q)

¬p ∨ (p ∧ q) Elimination de ⊃ et FND

. . . . . .

(¬p ∧ q) ∨ (¬p ∧ ¬q) ∨ (p ∧ q) FNDTD

(d) (p ⊃ q) ⊃ (q ⊃ p)

¬(¬p ∨ q) ∨ (¬q ∨ p) Elimination de ⊃(p ∧ ¬q) ∨ ¬q ∨ p Loi de De Morgan, associativite et FND

. . . . . .

(p ∧ ¬q) ∨ (p ∧ q) ∨ (¬p ∧ ¬q) FNDTD

Exercice 6

(a) (p ⊃ q) ⊃ r

¬(¬p ∨ q) ∨ r Elimination de ⊃(p ∧ ¬q) ∨ r Loi de De Morgan et FND

. . . . . .

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

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

(b) (p ∨ ¬q) ∧ (¬p ∨ q)

((p ∨ ¬q) ∧ ¬p) ∨ ((p ∨ ¬q) ∧ q) Distributivite de ∧ sur ∨((p ∧ ¬p) ∨ (¬p ∧ ¬q)) ∨ ((p ∧ q) ∨ (q ∧ ¬q)) Distributivite de ∧ sur ∨

(0 ∨ (¬p ∧ ¬q)) ∨ ((p ∧ q) ∨ 0) Non-contradiction

(¬p ∧ ¬q) ∨ (p ∧ q) Element neutre et FNDTD

Exercice 7

(a) p ⊃ (p ⊃ q)

¬p ∨ (¬p ∨ q) Elimination de ⊃(¬p ∨ ¬p) ∨ q Associativite

¬p ∨ q Idempotence et FND

(¬p ∧ 1) ∨ (q ∧ 1) Element neutre

(¬p ∧ (q ∨ ¬q)) ∨ (q ∧ (p ∨ ¬p)) Tiers exclu

((¬p ∧ q) ∨ (¬p ∧ ¬q)) ∨ ((q ∧ p) ∨ (q ∧ ¬p)) Distributivite de ∧ sur ∨((¬p ∧ q) ∨ (¬p ∧ q)) ∨ (¬p ∧ ¬q) ∨ (p ∧ q) Commutativite et associativite

(¬p ∧ q) ∨ (¬p ∧ ¬q) ∨ (p ∧ q) Idempotence et FNDTD

(b) p ∧ (p ⊃ (q ⊃ p))

p ∧ (¬p ∨ (¬q ∨ p)) Elimination de ⊃(p ∧ ¬p) ∨ (p ∧ (¬q ∨ p)) Distributivite de ∧ sur ∨

0 ∨ (p ∧ (¬q ∨ p)) Non-contradiction

p ∧ (¬q ∨ p)) Element neutre

(p ∧ ¬q) ∨ (p ∧ p) Distributivite de ∧ sur ∨(p ∧ ¬q) ∨ p Idempotence et FND

(p ∧ ¬q) ∨ (p ∧ 1) Element neutre

(p ∧ ¬q) ∨ (p ∧ (q ∨ ¬q)) Tiers exclu

(p ∧ ¬q) ∨ ((p ∧ q) ∨ (p ∧ ¬q)) Distributivite de ∧ sur ∨((p ∧ ¬q) ∨ (p ∧ ¬q)) ∨ (p ∧ q) Commutativite et associativite

(p ∧ ¬q) ∨ (p ∧ q) Idempotence et FNDTD

(c) p ∨ q

(p ∧ 1) ∨ (1 ∧ q) Element neutre

(p ∧ (q ∨ ¬q)) ∨ ((p ∨ ¬p) ∧ q) Tiers exclu

((p ∧ q) ∨ (p ∧ ¬q)) ∨ ((p ∧ q) ∨ (¬p ∧ q)) Distributivite de ∧ sur ∨((p ∧ q) ∨ (p ∧ q)) ∨ (p ∧ ¬q) ∨ (¬p ∧ q) Associativite et commutativite

(p ∧ q) ∨ (p ∧ ¬q) ∨ (¬p ∧ q) Idempotence et FNDTD

Exercice 8

(a) Oui. Pour former une FNCTD correspondant a un enonce donne, il suffit de lui fairesubir la suite de transformations suivantes pour obtenir minimalement une FNC :

1. Eliminer les connecteurs autres que ¬, ∧, ∨ ;2. Appliquer les ¬ jusqu’aux atomes et eliminer les doubles negations ;3. Distribuer les ∨ et les ∧ jusqu’a epuisement et appliquer les regles d’idempotence et

d’absorption.Pour completer le processus, au besoin, jusqu’a l’obtention d’une FNCTD, on fait subirles transformations suivantes :1. Pour chaque terme qui n’est pas totalement developpe, on fait la disjonction avec 0

que l’on transforme en (x∧¬x), ou x est un atome n’apparaissant pas dans le terme ;2. On distribuer les ∨ et les ∧ jusqu’a epuisement et appliquer les regles d’idempotence

et d’absorption.

(b) Une FNCTD d’une tautologie se ramene toujours a 1 et celle d’une contradiction donnerala conjonction de toutes les disjonctions possibles d’atomes et de negations d’atomes.

Exercice 9

(a) (p ∧ q ∧ r) ∨ (¬p ∧ ¬q ∧ ¬r)(b) (p ⊃ (q ∧ r)) ∧ (r ⊃ (p ∧ q)) ∧ (q ⊃ (r ∧ p))

Demonstration.

(¬p ∨ (q ∧ r)) ∧ (¬r ∨ (p ∧ q)) ∧ (¬q ∨ (r ∧ p)) Elimination de ⊃{(¬p ∨ (q ∧ r)) ∧ (¬r ∨ (p ∧ q))} ∧ (¬q ∨ (r ∧ p)) Associativite

{[(¬p ∨ (q ∧ r)) ∧ ¬r] ∨ [(¬p ∨ (q ∧ r)) ∧ (p ∧ q)]} ∧ (¬q ∨ (r ∧ p)) Distributivite de ∧ sur ∨{[(¬p ∧ ¬r) ∨ ((q ∧ r) ∧ ¬r)] ∨ [(¬p ∧ (p ∧ q)) . . .

· · · ∨ ((q ∧ r) ∧ (p ∧ q))]} ∧ (¬q ∨ (r ∧ p)) Distributivite de ∧ sur ∨{[(¬p ∧ ¬r) ∨ (q ∧ (r ∧ ¬r))] ∨ [((¬p ∧ p) ∧ q) . . .

· · · ∨ (r ∧ (q ∧ q) ∧ p)]} ∧ (¬q ∨ (r ∧ p)) Commu./Assoc.

{[(¬p ∧ ¬r) ∨ (q ∧ 0)] ∨ [(0 ∧ q) ∨ (r ∧ q ∧ p)]} ∧ (¬q ∨ (r ∧ p)) Non-contrad./Idemp.

{[(¬p ∧ ¬r) ∨ 0] ∨ [(0 ∨ (r ∧ q ∧ p)]} ∧ (¬q ∨ (r ∧ p)) Non-contradiction

{(¬p ∧ ¬r) ∨ (r ∧ q ∧ p)} ∧ (¬q ∨ (r ∧ p)) Tiers exclu

[(¬p ∧ ¬r) ∧ (¬q ∨ (r ∧ p))] ∨ [(r ∧ q ∧ p) ∧ (¬q ∨ (r ∧ p))] Distributivite de ∧ sur ∨[(¬p ∧ ¬r ∧ ¬q) ∨ ((¬p ∧ ¬r) ∧ (r ∧ p))] ∨ [(r ∧ q ∧ p ∧ ¬q) . . .

· · · ∨ ((r ∧ q ∧ p) ∧ (r ∧ p))] Distributivite de ∧ sur ∨[(¬p ∧ ¬r ∧ ¬q) ∨ ((¬p ∧ p) ∧ (¬r ∧ r))] . . .

· · · ∨ [(r ∧ p ∧ (q ∧ ¬q)) ∨ ((p ∧ p) ∧ q ∧ (r ∧ r))] Commu./Assoc.

[(¬p ∧ ¬r ∧ ¬q) ∨ (0 ∧ 0)] ∨ [(r ∧ p ∧ 0) ∨ (p ∧ q ∧ r)] Non-contrad./Idemp.

[(¬p ∧ ¬r ∧ ¬q) ∨ 0] ∨ [(r ∧ (p ∧ 0)) ∨ (p ∧ q ∧ r)] Non-contrad./Associativite.

(¬p ∧ ¬r ∧ ¬q) ∨ [(r ∧ 0) ∨ (p ∧ q ∧ r)] Tiers exclu./Non-contrad.

(¬p ∧ ¬r ∧ ¬q) ∨ [0 ∨ (p ∧ q ∧ r)] Non-contradiction

(¬p ∧ ¬r ∧ ¬q) ∨ (p ∧ q ∧ r) Tiers-exclu

(c)

Exercice 10

p : Pierre vient a la soiree.q : Il reste de la biere.r : Il reste du vin.Le propos de Marie : ¬p ⊃ (q ∨ r). Le propos de Pierre : (¬p ∧ ¬q) ⊃ r. On peut verifierl’equivalence de ces deux enonces en verifiant s’ils ont la meme FND :

Demonstration.

¬p ⊃ (q ∨ r)p ∨ (q ∨ r) Elimination de ⊃

p ∨ q ∨ r FND

(¬p ∧ ¬q) ⊃ r

(p ∨ q) ∨ r Elimination de ⊃p ∨ q ∨ r FND

Exercice 11

p : Cette voiture est japonaise.q : Cette voiture est americaine.r : Cette voiture est allemande.Le propos de Marie : ¬p ⊃ (q ∨ r). Le propos de Pierre : (¬p ∧ ¬q) ⊃ r. On peut verifierl’equivalence de ces deux enonces en verifiant s’ils ont la meme FND :

Demonstration.

¬p ⊃ (q ∨ r)p ∨ (q ∨ r) Elimination de ⊃

p ∨ q ∨ r FND

(¬p ∧ ¬q) ⊃ r

(p ∨ q) ∨ r Elimination de ⊃p ∨ q ∨ r FND

Exercice 12

On a ¬(p ∨ (q ∧ ¬r)) et on verifie que (¬p ∧ ¬q) ∨ (¬p ∧ r) en est une FND.

Demonstration.

¬(p ∨ (q ∧ ¬r))¬p ∧ ¬(q ∧ ¬r) Loi de De Morgan

¬p ∧ (¬q ∨ ¬¬r) Loi de De Morgan

¬p ∧ (¬q ∨ r) Double negation

(¬p ∧ ¬q) ∨ (¬p ∧ r) Distributivite de ∧ sur ∨

Exercice 13

Conformement a la table de verite de la barre de Sheffer |, on a : |= (p|q) ≡ ¬(p ∧ q), ce quidonne l’un ou l’autre des arbres suivants :

¬(p ∧ q)

¬p ¬q

p|q

¬p ¬q

Exercice 14

Par les transformations booleennes, on verifie que ¬(p∧ (q ≡ r)) ⊃ (q∨¬(r ⊃ q)) donne lieua la FND suivante : (p ∧ q ∧ r) ∨ (p ∧ ¬q ∧ ¬r) ∨ q ∨ (r ∧ ¬p).

Demonstration.

¬¬{p ∧ [(q ∧ r) ∨ (¬q ∧ ¬r)]} ∨ (q ∨ ¬(¬r ∨ q)) Elimination de ⊃ et ≡{p ∧ [(q ∧ r) ∨ (¬q ∧ ¬r)]} ∨ (q ∨ (¬¬r ∧ ¬q)) Double negation/Loi de De Morgan

{[p ∧ (q ∧ r)] ∨ [p ∧ (¬q ∧ ¬r)]} ∨ (q ∨ (r ∧ ¬q)) Distributivite de ∧ sur ∨/Double negation

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

Exercice 15

(a) |= (p ⊃ ¬p) ⊃ ¬p

Demonstration.

¬((p ⊃ ¬p) ⊃ ¬p)

p ⊃ ¬p¬¬p

p

¬p

×

¬p

×

(b) |= p ⊃ (q ⊃ p)

Demonstration.

¬(p ⊃ (q ⊃ p))

p¬(q ⊃ p)

q¬p

×

(c) |= (p ∧ (p ∨ q)) ≡ p

Demonstration.

¬((p ∧ (p ∨ q)) ≡ p)

(p ∧ (p ∨ q))¬p

p(p ∨ q)

×

¬(p ∧ (p ∨ q))p

¬p

×

¬(p ∨ q)

¬p¬q

×

(d) |= (¬q ⊃ p) ⊃ (¬p ⊃ (¬q ⊃ p))

Demonstration.

¬[(¬q ⊃ p) ⊃ (¬p ⊃ (¬q ⊃ p))]

(¬q ⊃ p)¬(¬p ⊃ (¬q ⊃ p))

¬p¬(¬q ⊃ p)

¬q¬p

¬¬q

q

×

p

×

(e) |= ((p ⊃ q) ∧ (q ⊃ r)) ⊃ (p ⊃ r)

Demonstration.

¬[((p ⊃ q) ∧ (q ⊃ r)) ⊃ (p ⊃ r)]

(p ⊃ q) ∧ (q ⊃ r)¬(p ⊃ r)

p¬r

p ⊃ qq ⊃ r

¬p

×

q

¬q

×

r

×

(f) |= ¬(p ≡ q) ≡ (p ≡ ¬q)

Demonstration.

¬(¬(p ≡ q) ≡ (p ≡ ¬q))

¬(p ≡ q)¬(p ≡ ¬q)

p¬q

p¬¬q

q

×

¬p¬q

×

¬pq

p¬¬q

q

×

¬p¬q

×

¬¬(p ≡ q)p ≡ ¬q

p ≡ q

pq

p¬q

×

p¬¬q

×

¬p¬q

p¬q

×

¬p¬¬q

q

×

(g) |= (p ∨ q) ≡ ((p ⊃ q) ⊃ q)

Demonstration.

¬[(p ∨ q) ≡ ((p ⊃ q) ⊃ q)]

p ∨ q¬((p ⊃ q) ⊃ q)

p ⊃ q¬q

p

¬p

×

q

×

q

×

¬(p ∨ q)(p ⊃ q) ⊃ q

¬p¬q

¬(p ⊃ q)

p¬q

×

q

×

Exercice 16

(a) On a : (p ⊃ q) ≡ (q ⊃ p).

(p ⊃ q) ≡ (q ⊃ p)

p ⊃ qq ⊃ p

¬p

¬q p

×

q

¬q

×

p

¬(p ⊃ q)¬(q ⊃ p)

p¬q

q¬p

×

On trouve donc la FND suivante : (p ∧ q) ∨ (¬p ∧ ¬q).(b) Par les transformations booleennes, on obtient la meme FND :

[(p ⊃ q) ∧ (q ⊃ p)] ∨ [¬(p ⊃ q) ∧ ¬(q ⊃ p)] Elimination de ≡[(¬p ∨ q) ∧ (¬q ∨ p)] ∨ [¬(¬p ∨ q) ∧ ¬(¬q ∨ p)] Elimination de ⊃

[((¬p ∨ q) ∧ ¬q) ∨ ((¬p ∨ q) ∧ p)] ∨ [(¬¬p ∧ ¬q) ∧ (¬¬q ∧ ¬p)] Dis. ∧ sur ∨/De Morgan

[((¬p ∧ ¬q) ∨ (q ∧ ¬q)) ∨ ((¬p ∧ p) ∨ (q ∧ p))] ∨ [(p ∧ ¬q) ∧ (q ∧ ¬p)] Dis. ∧ sur ∨/D.Neg

[((¬p ∧ ¬q) ∨ 0) ∨ (0 ∨ (q ∧ p))] ∨ [p ∧ (¬q ∧ q) ∧ ¬p)] Non-Contr./Associativite

[(¬p ∧ ¬q) ∨ (q ∧ p)] ∨ [p ∧ 0 ∧ ¬p)] El. Neutre/Non-Contr.

(p ∧ q) ∨ (¬p ∧ ¬q) ∨ [(p ∧ 0) ∧ ¬p] Comm./Ass.

(p ∧ q) ∨ (¬p ∧ ¬q) ∨ [0 ∧ ¬p] Comm./Non-Contr.

(p ∧ q) ∨ (¬p ∧ ¬q) ∨ 0 Non-Contr.

(p ∧ q) ∨ (¬p ∧ ¬q) El. Neutre

Exercice 17

(a) Demonstration.

pq

(q ∧ p) ⊃ r¬(q ⊃ r)

q¬r

¬(q ∧ p)

¬q

×

¬p

×

r

×

(b) Demonstration.

(p ⊃ q) ⊃ rs ∨ p¬(s ∨ ¬t)

t ⊃ q¬r

¬s¬¬t

t

¬(p ⊃ q)

p¬q

¬t

×

q

×

r

×

(c) Demonstration.

(p ∧ q) ≡ (p ∧ r)¬(p ⊃ (q ≡ r))

p¬(q ≡ r)

q¬r

p ∧ qp ∧ r

pr

×

¬(p ∧ q)¬(p ∧ r)

¬p

×

¬q

×

¬qr

p ∧ qp ∧ r

pq

×

¬(p ∧ q)¬(p ∧ r)

¬p

×

¬r

×

(d) Demonstration.

¬p ∨ qq ⊃ ¬r¬(p ⊃ ¬r)

p¬¬r

r

¬p

×

q

¬q

×

¬r

×

(e) Demonstration.

(p ∧ q) ⊃ rr ⊃ sq ∧ ¬s¬¬p

p

q¬s

¬r

¬(p ∧ q)

¬p

×

¬q

×

r

×

s

×

Exercice 18

(a) Valide.

Demonstration.

p ≡ qq ∧ rr ⊃ s¬(s ⊃ p)

qr

s¬p

¬r

×

s

pq

×

¬p¬q

×

(b) Valide.

Demonstration.

(p ≡ q) ≡ p¬q

p ≡ qp

pq

×

¬p¬q

×

¬(p ≡ q)¬p

p¬q

×

¬pq

×

(c) Invalide : le chemin (¬p ∧ q ∧ r) reste ouvert.

Demonstration.

p ⊃ rq ⊃ rp ⊃ q¬(p ≡ q)

p¬q

¬p

×

r

¬p

×

q

×

¬pq

¬q

×

r

¬p

¬p q

r

¬p q

(d) Invalide : le chemin (p ∧ ¬q ∧ ¬r) reste ouvert.

Demonstration.

p ⊃ (q ⊃ r)q ⊃ (r ⊃ p)¬(p ⊃ r)

p¬r

¬p

×

q ⊃ r

¬q

¬q q ⊃ r

¬q r

×

r

×

Exercice 19

(a) p : Les poules ont des dents.q : Les poules sont des mammiferes.

On verifie que p ⊃ q,¬q |= ¬p. On a :

p ⊃ q¬q¬¬p

p

¬p

×

q

×

La deduction est donc valide.

(b) p : Les poules ont des dents.q : Les poules ont une carapace.

On verifie que p ⊃ ¬q, q |= ¬p. On a :

p ⊃ ¬qq¬¬p

p

¬p

×

¬q

×

La deduction est donc valide.

(c) p : Pierre reussit le cours de logique.q : Pierre assiste au cours.r : Pierre parle avec sa voisine.s : Pierre ecoute le professeur.

On verifie que p ≡ (q ∧ ¬r ∧ s), s ⊃ (q ∧ ¬r) |= s ≡ p. On a :

p ≡ (q ∧ ¬r ∧ s)s ⊃ (q ∧ ¬r)¬(s ≡ p)

p(q ∧ ¬r ∧ s)

q¬rs

s¬p

×

¬sp

×

¬p¬(q ∧ ¬r ∧ s)

¬q

s¬p

¬s

×

q ∧ ¬r

q¬r

×

¬sp

×

¬¬r

r

s¬p

¬s

×

q ∧ ¬r

q¬r

×

¬sp

×

¬s

s¬p

×

¬sp

×

La deduction est donc valide.

Exercice 20

(a) Valide.

Demonstration.

p ⊃ (q ⊃ r)¬q ⊃ ¬p

p¬r

¬p

×

q ⊃ r

¬q

¬¬q

q

×

¬p

×

r

×

(b) Valide. Nul besoin d’utiliser la deuxieme premisse.

Demonstration.

(p ≡ ¬q) ∧ q(q ∨ ((r ⊃ p) ∧ r)) ⊃ ¬p

¬(q ⊃ ¬p)

q¬¬p

p

p ≡ ¬qq

p¬q

×

¬p¬¬q

×

Exercice 21

(a) Valide.

Demonstration.

p ∧ (q ≡ r)¬p ∨ (q ⊃ ¬r)¬(p ⊃ ¬r)

p¬¬r

r

pq ≡ r

qr

¬p

×

q ⊃ ¬r

¬q

×

¬r

×

¬q¬r

×

(b) Valide. Nul besoin d’utiliser la deuxieme premisse.

Demonstration.

(p ≡ ¬q) ∧ q(¬q ∨ ((r ≡ p) ∧ r)) ⊃ ¬p

¬(r ⊃ ¬p)

r¬¬p

p

p ≡ ¬qq

p¬q

×

¬p¬¬q

×

Exercice 22

On verifie que : q ≡ ¬r, p ≡ ¬q |= r ≡ p

Demonstration.

q ≡ ¬rp ≡ ¬q¬(r ≡ p)

r¬p

p¬q

×

¬p¬¬q

q

q¬r

×

¬q¬¬r

r

×

¬rp

q¬r

p¬q

×

¬p¬¬q

×

¬q¬¬r

r

×

Exercice 23

(a) On a : (p ⊃ q) ≡ (q ⊃ p). On cherche une FND :

(p ⊃ q) ≡ (q ⊃ p)

p ⊃ qq ⊃ p

¬p

¬q p

×

q

¬q

×

p

¬(p ⊃ q)¬(q ⊃ p)

p¬q

q¬p

×

On trouve donc : (p ∧ q) ∨ (¬p ∧ ¬q)

(b) Par les transformations booleennes, on obtient :

[(p ⊃ q) ∧ (q ⊃ p)] ∨ [¬(p ⊃ q) ∧ ¬(q ⊃ p)] Elim. ≡[(¬p ∨ q) ∧ (¬q ∨ p)] ∨ [¬(¬p ∨ q) ∧ ¬(¬q ∨ p)] Elim. ⊃

[((¬p ∨ q) ∧ ¬q) ∨ ((¬p ∨ q) ∧ p)] ∨ [(¬¬p ∧ ¬q) ∧ (¬¬q ∧ ¬p)] Dis. ∧ sur ∨/Morgan

[((¬p ∧ ¬q) ∨ (q ∧ ¬q)) ∨ ((¬p ∧ p) ∨ (q ∧ p))] ∨ [(p ∧ ¬q) ∧ (q ∧ ¬p)] Dis. ∧ sur ∨/D. Neg.

[((¬p ∧ ¬q) ∨ 0) ∨ (0 ∨ (q ∧ p))] ∨ [p ∧ (¬q ∧ q) ∧ ¬p] Non-Contr./Ass.

[(¬p ∧ ¬q) ∨ (q ∧ p)] ∨ [p ∧ 0 ∧ ¬p] El. Neutr/Non-Contr.

[(p ∧ q) ∨ (¬p ∧ ¬q)] ∨ [(p ∧ 0) ∧ ¬p] Comm./Ass.

[(p ∧ q) ∨ (¬p ∧ ¬q)] ∨ [0 ∧ ¬p] Comm./El. Abs.

[(p ∧ q) ∨ (¬p ∧ ¬q)] ∨ 0 Element absorbant

(p ∧ q) ∨ (¬p ∧ ¬q) Element neutre

Exercice 24

(a) p : Pierre vient a la fete.q : Marie est triste.r : Jean vient a la fete.

On a : p ⊃ q, q ⊃ ¬r,¬r ⊃ ¬p |= ¬p.

(b) On a : ((p ⊃ q) ∧ (q ⊃ ¬r) ∧ (¬r ⊃ ¬p)) ⊃ ¬p.

(c) Selon le theoreme (p. 59), on sait que ((p ⊃ q) ∧ (q ⊃ ¬r) ∧ (¬r ⊃ ¬p)) ⊃ ¬p est validesi (p ⊃ q) ∧ (q ⊃ ¬r) ∧ (¬r ⊃ ¬p) |= ¬p. On verifie que :

(p ⊃ q) ∧ (q ⊃ ¬r) ∧ (¬r ⊃ ¬p)

¬¬p

p

p ⊃ qq ⊃ ¬r¬r ⊃ ¬p

¬p

×

q

¬q

×

¬r

¬¬r

r

×

¬p

×

La deduction est donc valide.

Exercice 25

(a) L’enonce n’est pas une tautologie, car les chemins ne sont pas tous ouverts.

(p ≡ q) ≡ (p ⊃ q)

p ≡ qp ⊃ q

¬p

pq

×

¬p¬q

q

pq¬p¬q

×

¬(p ≡ q)¬(p ⊃ q)

p¬q

p¬q

¬pq

×

(b) Considerant, par exemple, la premiere branche fermee de l’arbre, c’est le cas ou p estfaux et q est vrai.

(c) FNDTD : (p ∧ q) ∨ (p ∧ ¬q) ∨ (¬p ∧ ¬q).

Exercice 26

p : L’augmentation des frais de scolarite est une bonne chose.q : Les etudiants sont obliges de travailler.r : Les revenus des etudiants diminuent.On verifie que : p ⊃ ¬q, r ⊃ q |= ¬r ∨ ¬p.

Demonstration.

p ⊃ ¬qr ⊃ q

¬(¬r ∨ ¬p)

¬¬r¬¬p

rp

¬r

×

q

¬p

×

¬q

×

La deduction est donc valide.

5 La deduction naturelle

Exercice 1

(a) p ∧ q, p ⊃ (q ⊃ r) ` r

1 p ∧ q H

2 p ⊃ (q ⊃ r) H

3 p ∧ q R-1

4 p ∧E-3

5 q ∧E-3

6 p ⊃ (q ⊃ r) R-2

7 q ⊃ r ⊃E-4,6

8 r ⊃E-5,7

(b) p ⊃ (q ⊃ r) ` q ⊃ (p ⊃ r)

1 p ⊃ (q ⊃ r) H

2 q H

3 p H

4 p R-3

5 p ⊃ (q ⊃ r) R-1

6 q ⊃ r ⊃E-4,5

7 q R-2

8 r ⊃E-6,7

9 p ⊃ r ⊃I-3,8

10 q ⊃ (p ⊃ r) ⊃I-2,9

(c) p, q ⊃ (p ⊃ r) ` q ⊃ r

1 p H

2 q ⊃ (p ⊃ r) H

3 q H

4 q R-3

5 q ⊃ (p ⊃ r) R-2

6 p ⊃ r ⊃E-4,5

7 p R-1

8 r ⊃E-6,7

9 q ⊃ r ⊃I-3,8

(d) p ⊃ (q ⊃ r) ` (p ∧ q) ⊃ r

1 p ⊃ (q ⊃ r) H

2 p ∧ q H

3 p ∧ q R-2

4 p ∧E-3

5 p ⊃ (q ⊃ r) R-1

6 q ⊃ r ⊃E-4,5

7 q ∧E-3

8 r ⊃E-6,7

9 (p ∧ q) ⊃ r ⊃I-2,8

Exercice 2

(a) ¬(p ⊃ q) ` ¬q

1 ¬(p ⊃ q) H

2 q H

3 p H

4 q R-2

5 p ⊃ q ⊃I-3,4

6 ¬(p ⊃ q) R-1

7 ¬q ¬I-2,5,6

(b) ¬(p ⊃ (p ⊃ q)) ` ¬q

1 ¬(p ⊃ (p ⊃ q)) H

2 q H

3 p H

4 p H

5 q R-2

6 p ⊃ q ⊃I-4,5

7 p ⊃ (p ⊃ q) ⊃I-3,6

8 ¬(p ⊃ (p ⊃ q)) R-1

9 ¬q ¬I-2,7,8

Exercice 3

(a) ¬(p ⊃ q) ` (p ⊃ ¬q)

1 ¬(p ⊃ q) H

2 p H

3 q H

4 p H

5 q R-3

6 p ⊃ q ⊃I-4,5

7 ¬(p ⊃ q) R-1

8 ¬q ¬I-3,6,7

9 p ⊃ ¬q ⊃I-2,8

(b) (p ⊃ q) ` (p ∧ r) ⊃ q

1 p ⊃ q H

2 p ∧ r H

3 ¬q H

4 p ∧ r R-2

5 p ∧E-4

6 p ⊃ q R-1

7 q ⊃E-5,6

8 ¬q R-3

9 ¬¬q ¬I-3,7,8

10 q ¬E-9

11 (p ∧ r) ⊃ q ⊃I-2,10

(c) p ⊃ (q ⊃ r) ` (p ⊃ q) ⊃ (p ⊃ r)

1 p ⊃ (q ⊃ r) H

2 p ⊃ q H

3 p H

4 p R-3

5 p ⊃ q R-2

6 q ⊃E-4,5

7 p ⊃ (q ⊃ r) R-1

8 q ⊃ r ⊃E-4,7

9 r ⊃E-6,8

10 p ⊃ r ⊃I-3,9

11 (p ⊃ q) ⊃ (p ⊃ r) ⊃I-2,10

(d) (p ⊃ q) ` ¬(p ∧ ¬q)

1 p ⊃ q H

2 p ∧ ¬q H

3 p ∧ ¬q R-2

4 p ∧E-3

5 p ⊃ q R-1

6 q ⊃E-4,5

7 ¬q ∧E-3

8 ¬(p ∧ ¬q) ¬I-2,6,7

(e) p, p ⊃ (p ⊃ r) ` r

1 p H

2 p ⊃ (p ⊃ r) H

3 ¬r H

4 p R-1

5 p ⊃ (p ⊃ r) R-2

6 p ⊃ r ⊃E-4,5

7 r ⊃E-4,6

8 ¬r R-3

9 ¬¬r ¬I-3,7,8

10 r ¬E-9

Exercice 4

(a) ¬(p ⊃ q) ` (q ⊃ r)

1 ¬(p ⊃ q) H

2 q H

3 ¬r H

4 p H

5 q R-2

6 p ⊃ q ⊃I-4,5

7 ¬(p ⊃ q) R-1

8 ¬¬r ¬I-3,6,7

9 r ¬E-8

10 q ⊃ r ⊃I-2,9

(b) (p ∧ q) ⊃ r ` (q ∧ ¬r) ⊃ ¬p

1 (p ∧ q) ⊃ r H

2 q ∧ ¬r H

3 p H

4 q ∧ ¬r R-2

5 q ∧E-4

6 p R-3

7 p ∧ q ∧I-5,6

8 (p ∧ q) ⊃ r R-1

9 r ⊃E-7,8

10 ¬r ∧E-4

11 ¬p ¬I-3,9,10

12 (q ∧ ¬r) ⊃ ¬p ⊃I-2,11

Exercice 5

(a) ¬(p ⊃ q) ` (¬p ⊃ q)

1 ¬(p ⊃ q) H

2 ¬p H

3 ¬q H

4 p H

5 ¬q H

6 p R-4

7 ¬p R-2

8 ¬¬q ¬I-5,6,7

9 q ¬E-8

10 p ⊃ q ⊃I-4,9

11 ¬(p ⊃ q) R-1

12 ¬¬q ¬I-3,10,11

13 q ¬E-12

14 ¬p ⊃ q ⊃I-2,13

(b) ¬(p ⊃ q) ` (¬q ⊃ p)

1 ¬(p ⊃ q) H

2 ¬q H

3 ¬p H

4 p H

5 ¬q H

6 p R-4

7 ¬p R-3

8 ¬¬q ¬I-5,6,7

9 q ¬E-8

10 p ⊃ q ⊃I-4,9

11 ¬(p ⊃ q) R-1

12 ¬¬p ¬I-3,10,11

13 p ¬E-12

14 ¬q ⊃ p ⊃I-2,13

(c) ¬(p ∨ q) ` p ⊃ q

1 ¬(p ∨ q) H

2 p H

3 ¬q H

4 p R-2

5 p ∨ q ∨I-4

6 ¬(p ∨ q) R-1

7 ¬¬q ¬I-3,5,6

8 q ¬E-7

9 p ⊃ q ⊃I-2,8

(d) (p ⊃ q) ` (¬q ⊃ ¬p)

1 p ⊃ q H

2 ¬q H

3 p H

4 p R-3

5 p ⊃ q R-1

6 q ⊃E-4,5

7 ¬q R-2

8 ¬p ¬I-3,6,7

9 ¬q ⊃ ¬p ⊃I-2,8

(e) (¬p ⊃ ¬q) ` (q ⊃ p)

1 ¬p ⊃ ¬q H

2 q H

3 ¬p H

4 ¬p R-3

5 ¬p ⊃ ¬q R-1

6 ¬q ⊃I-4,5

7 q R-2

8 ¬¬p ¬I-3,6,7

9 p ¬E-8

10 q ⊃ p ⊃I-2,9

(f) (p ⊃ q) ` (p ∧ r) ⊃ (q ∧ (r ⊃ r))

1 p ⊃ q H

2 p ∧ r H

3 p ∧ r R-2

4 p ∧E-3

5 p ⊃ q R-1

6 q ⊃E-4,5

7 r H

8 r R-7

9 r ⊃ r ⊃I-7,8

10 q ∧ (r ⊃ r) ∧I-6,9

11 (p ∧ r) ⊃ (q ∧ (r ⊃ r)) ⊃I-2,10

(g) ((p ⊃ q) ⊃ ¬q) ` ¬q

1 (p ⊃ q) ⊃ ¬q H

2 q H

3 p H

4 q R-2

5 p ⊃ q ⊃I-3,4

6 (p ⊃ q) ⊃ ¬q R-1

7 ¬q ⊃E-5,6

8 q R-2

9 ¬q ¬I-2,7,8

(h) ((p ⊃ q) ∧ (p ⊃ ¬q)) ` ¬p

1 (p ⊃ q) ∧ (p ⊃ ¬q) H

2 p H

3 (p ⊃ q) ∧ (p ⊃ ¬q) R-1

4 p ⊃ q ∧E-3

5 p ⊃ ¬q ∧E-3

6 p R-2

7 q ⊃E-4,6

8 ¬q ⊃E-5,7

9 ¬p ¬I-2,7,8

(i) (p ∧ q) ⊃ r ` p ⊃ (q ⊃ r)

1 (p ∧ q) ⊃ r H

2 p H

3 q H

4 p R-2

5 q R-3

6 p ∧ q ∧I-4,5

7 (p ∧ q) ⊃ r R-1

8 r ⊃E-6,7

9 q ⊃ r ⊃I-3,8

10 p ⊃ (q ⊃ r) ⊃I-2,9

(j) ` ¬(p ∧ ¬p)

1 p ∧ ¬p H

2 p ∧ ¬p R-1

3 p ∧E-2

4 ¬p ∧E-2

5 ¬(p ∧ ¬p) ¬I-2,3,4

(k) (p ⊃ ¬p) ` ¬p

1 p ⊃ ¬p H

2 p H

3 p R-2

4 p ⊃ ¬p R-1

5 ¬p ⊃I-3,4

6 ¬p ¬I-2,3,5

(l) p ⊃ (q ⊃ r) ` (p ∧ q) ⊃ r

1 p ⊃ (q ⊃ r) H

2 p ∧ q H

3 p ∧ q R-2

4 p ∧E-3

5 p ⊃ (q ⊃ r) R-1

6 q ⊃ r ⊃I-4,5

7 q ∧E-3

8 r ⊃I-6,7

9 (p ∧ q) ⊃ r ⊃I-2,8

(m) ¬p ` (p ⊃ q)

1 ¬p H

2 p H

3 ¬q H

4 ¬p R-1

5 p R-2

6 ¬¬q ¬I-3,4,5

7 q ¬E-6

8 p ⊃ q ⊃I-2,7

(n) ¬p ⊃ q,¬p ⊃ ¬q ` p

1 ¬p ⊃ q H

2 ¬p ⊃ ¬q H

3 ¬p H

4 ¬p ⊃ q R-1

5 ¬p R-3

6 q ⊃E-4,5

7 ¬p ⊃ ¬q R-2

8 ¬q ⊃E-5,7

9 ¬¬p ¬I-3,6,8

10 p ¬E-9

Exercice 6

(a) ` (p ⊃ q) ⊃ (p ⊃ (q ∨ r))

1 p ⊃ q H

2 p H

3 p ⊃ q R-1

4 p R-2

5 q ⊃I-3,4

6 q ∨ r ∨I-5

7 p ⊃ (q ∨ r) ⊃I-2,6

8 (p ⊃ q) ⊃ (p ⊃ (q ∨ r)) ⊃I-1,7

(b) ` p ⊃ (q ∨ ¬q)

1 p H

2 ¬(q ∨ ¬q) H

3 ¬q H

4 q ∨ ¬q ∨I-3

5 ¬(q ∨ ¬q) R-2

6 ¬¬q ¬I-3,4,5

7 q ¬E-6

8 q ∨ ¬q ∨I-7

9 ¬(q ∨ ¬q) R-2

10 ¬¬(q ∨ ¬q) ¬I-2,8,9

11 q ∨ ¬q ¬E-10

12 p ⊃ (q ∨ ¬q) ⊃I-1,11

(c) ` ¬(p ∨ q) ⊃ (p ⊃ q)

1 ¬(p ∨ q) H

2 p H

3 ¬q H

4 p R-2

5 p ∨ q ∨I-4

6 ¬(p ∨ q) R-1

7 ¬¬q ¬I-3,5,6

8 q ¬E-7

9 p ⊃ q ⊃I-2,8

10 ¬(p ∨ q) ⊃ (p ⊃ q) ⊃I-1,9

(d) ` ¬(p ∧ ¬q) ⊃ (¬p ∨ q)

1 ¬(p ∧ ¬q) H

2 ¬(¬p ∨ q) H

3 p H

4 q H

5 q R-4

6 ¬p ∨ q ∨I-5

7 ¬(¬p ∨ q) R-2

8 ¬q ¬I-4,6,7

9 p R-3

10 p ∧ ¬q ∧I-8,9

11 ¬(p ∧ ¬q) R-1

12 ¬p ¬I-3,10,11

13 ¬p ∨ q ∨I-12

14 ¬(¬p ∨ q) R-2

15 ¬¬(¬p ∨ q) ¬I-2,13,14

16 ¬p ∨ q ¬E-15

17 ¬(p ∧ ¬q) ⊃ (¬p ∨ q) ⊃I-1,16

(e) ` (¬p ∨ q) ⊃ ¬(p ∧ ¬q)

1 ¬p ∨ q H

2 p ∧ ¬q H

3 p ∧ ¬q R-2

4 ¬p H

5 ¬p R-4

6 q H

7 p H

8 p ∧ ¬q R-2

9 ¬q ∧E-8

10 q R-6

11 ¬p ¬I-7,9,10

12 ¬p ∨E-1,4,5,6,11

13 p ∧E-3

14 ¬(p ∧ ¬q) ¬I-2,12,13

15 (¬p ∨ q) ⊃ ¬(p ∧ ¬q) ⊃I-1,14

(f) ` (p ∧ ¬q) ∨ (¬p ∨ q)

1 ¬((p ∧ ¬q) ∨ (¬p ∨ q)) H

2 ¬(¬p ∨ q) H

3 q H

4 ¬p ∨ q ∨I-3

5 ¬(¬p ∨ q) R-2

6 ¬q ¬I-3,4,5

7 ¬p H

8 ¬p ∨ q ∨I-7

9 ¬(¬p ∨ q) R-2

10 ¬¬p ¬I-7,8,9

11 p ¬E-10

12 p ∧ ¬q ∧I-6,11

13 (p ∧ ¬q) ∨ (¬p ∨ q) ∨I-12

14 ¬((p ∧ ¬q) ∨ (¬p ∨ q)) R-1

15 ¬¬(¬p ∨ q) ¬I-2,13,14

16 ¬p ∨ q ¬E-15

17 (p ∧ ¬q) ∨ (¬p ∨ q) ∨I-16

18 ¬((p ∧ ¬q) ∨ (¬p ∨ q)) R-1

19 ¬¬((p ∧ ¬q) ∨ (¬p ∨ q)) ¬I-1,17,18

20 (p ∧ ¬q) ∨ (¬p ∨ q) ¬E-19

(g) p ∧ q ` p ∨ q

1 p ∧ q H

2 p ∧ q R-1

3 p ∧E-2

4 p ∨ q ∨I-3

(h) p ∧ q ` ¬(¬p ∨ ¬q)

1 p ∧ q H

2 p ∧ q R-1

3 p ∧E-2

4 q ∧E-2

5 ¬p ∨ ¬q H

6 ¬p H

7 ¬p R-6

8 ¬q H

9 p H

10 q R-4

11 ¬q R-8

12 ¬p ¬I-9,10,11

13 ¬p ∨E-6,7,8,12

14 p R-3

15 ¬(¬p ∨ ¬q) ¬I-5,13,14

(i) p ⊃ q, r ∨ ¬q,¬(p ∧ r) ` ¬p

1 p ⊃ q H

2 r ∨ ¬q H

3 ¬(p ∧ r) H

4 p H

5 p R-4

6 r H

7 r R-6

8 ¬q H

9 ¬r H

10 p R-4

11 p ⊃ q R-1

12 q ⊃E-10-11

13 ¬q R-8

14 ¬¬r ¬I-9,12,13

15 r ¬E-14

16 r ∨E-6,7,8,15

17 p ∧ r ∧I-5,16

18 ¬(p ∧ r) R-3

19 ¬p ¬I-4,17,18

(j) p ∨ q, q ⊃ r,¬q ∨ ¬r ` p

1 p ∨ q H

2 q ⊃ r H

3 ¬q ∨ ¬r H

4 p H

5 p R-4

6 q H

7 ¬p H

8 ¬r H

9 ¬r R-8

10 ¬q H

11 r H

12 q R-6

13 ¬q R-10

14 ¬r ¬I-11,12,13

15 ¬r ∨E-8,9,10,14

16 q R-6

17 q ⊃ r R-2

18 r ⊃E-16,17

19 ¬¬p ¬I-7,15,18

20 p ¬E-19

21 p ∨E-4,5,6,20

(k) ` (¬p ⊃ q) ⊃ (p ∨ q)

1 ¬p ⊃ q H

2 ¬(p ∨ q) H

3 ¬p H

4 ¬p R-4

5 ¬p ⊃ q R-1

6 q ⊃E-4,5

7 p ∨ q ∨I-6

8 ¬(p ∨ q) R-2

9 ¬¬p ¬I-3,7,8

10 p ¬E-9

11 p ∨ q ∨I-10

12 ¬(p ∨ q) R-2

13 ¬¬(p ∨ q) ¬I-2,11,12

14 p ∨ q ¬E-13

15 (¬p ⊃ q) ⊃ (p ∨ q) ⊃I-1,14

(l) ` (¬p ∨ q) ⊃ (p ⊃ q)

1 ¬p ∨ q H

2 p H

3 ¬p H

4 ¬q H

5 p R-2

6 ¬p R-3

7 ¬¬q ¬I-4,5,6

8 q ¬E-7

9 q H

10 q R-9

11 q ∨E-3,8,9,10

12 p ⊃ q ⊃I-2,11

13 (¬p ∨ q) ⊃ (p ⊃ q) ⊃I-1,12

(m) ` ((p ⊃ p) ⊃ q) ⊃ q

1 (p ⊃ p) ⊃ q H

2 p H

3 p R-3

4 p ⊃ p ⊃I-2,3

5 (p ⊃ p) ⊃ q R-1

6 q ⊃E-4,5

7 ((p ⊃ p) ⊃ q) ⊃ q ⊃I-1,6

(n) q ⊃ (q ⊃ p), (q ⊃ p) ⊃ q ` q ⊃ p

1 q ⊃ (q ⊃ p) H

2 (q ⊃ p) ⊃ q H

3 q H

4 q R-3

5 q ⊃ (q ⊃ p) R-1

6 q ⊃ p ⊃E-4,5

7 p ⊃E-4,6

8 q ⊃ p ⊃I-3,7

Exercice 7

(a) p ∧ q ` (p ≡ (p ⊃ q))

1 p ∧ q H

2 p H

3 p H

4 p ∧ q R-1

5 q ∧E-4

6 p ⊃ q ⊃I-3,5

7 p ⊃ q H

8 p ∧ q R-1

9 p ∧E-8

10 p ≡ (p ⊃ q) ≡I-2,6,7,9

(b) p ≡ (p ⊃ q) ` p ∧ q

1 p ≡ (p ⊃ q) H

2 p H

3 p R-2

4 p ≡ (p ⊃ q) R-1

5 p ⊃ q ≡E-3,4

6 q ⊃E-3,5

7 p ⊃ q ⊃I-2,6

8 p ≡ (p ⊃ q) R-1

9 p ≡E-7,8

10 q ⊃E-7,9

11 p ∧ q ∧I-9,10

(c) ` p ≡ p

1 p H

2 p R-1

3 p H

4 p R-3

5 p ≡ p ≡I-1,2,3,4

(d) ` (p ∧ p) ≡ p

1 p ∧ p H

2 p ∧ p R-1

3 p ∧E-2

4 p H

5 p R-4

6 p R-4

7 p ∧ p ∧I-5,6

8 (p ∧ p) ≡ p ≡I-1,3,4,7

(e) (p ≡ q) ≡ p ` q

1 (p ≡ q) ≡ p H

2 ¬(p ≡ q) H

3 p H

4 ¬q H

5 p R-3

6 (p ≡ q) ≡ p R-1

7 p ≡ q ≡E-5,6

8 ¬(p ≡ q) R-2

9 ¬¬q ¬I-4,7,8

10 q ¬E-9

11 q H

12 q R-12

13 p ≡ q ≡I-3,10,11,12

14 ¬(p ≡ q) R-2

15 ¬¬(p ≡ q) ¬I-2,13,14

16 p ≡ q ¬E-15

17 (p ≡ q) ≡ p R-1

18 p ≡E-16,17

19 q ≡E-16,18

(f) p ≡ q,¬p ` ¬q

1 p ≡ q H

2 ¬p H

3 q H

4 p ≡ q R-1

5 q R-3

6 p ≡E-4,5

7 ¬p R-2

8 ¬q ¬I-3,6,7

(g) p ≡ q ` ¬p ≡ ¬q

1 p ≡ q H

2 ¬p H

3 q H

4 p ≡ q R-1

5 q R-3

6 p ≡E-4,5

7 ¬p R-2

8 ¬q ¬I-3,6,7

9 ¬q H

10 p H

11 p ≡ q R-1

12 p R-10

13 q ≡E-11,12

14 ¬q R-9

15 ¬p ¬I-10,13,14

16 ¬p ≡ ¬q ≡I-2,8,9,15

(h) ¬(p ≡ q) ` p ≡ ¬q

1 ¬(p ≡ q) H

2 p H

3 q H

4 p H

5 q R-3

6 q H

7 p R-2

8 p ≡ q ≡I-4,5,6,7

9 ¬(p ≡ q) R-1

10 ¬q ¬I-3,8,9

11 ¬q H

12 ¬p H

13 p H

14 ¬q H

15 ¬p R-12

16 p R-13

17 ¬¬q ¬I-14,15,16

18 q ¬E-17

19 q H

20 ¬p H

21 ¬q R-11

22 q R-19

23 ¬¬p ¬I-20,21,22

24 p ¬E-23

25 p ≡ q ≡I-13,18,19,24

26 ¬(p ≡ q) R-1

27 ¬¬p ¬I-12,25,26

28 p ¬E-27

29 p ≡ ¬q ≡I-2,10,11,28

(i) p ≡ q ` (p ∧ q) ∨ (¬p ∧ ¬q)

1 p ≡ q H

2 ¬((p ∧ q) ∨ (¬p ∧ ¬q)) H

3 p H

4 p R-3

5 p ≡ q R-1

6 q ≡E-4,5

7 p ∧ q ∧I-4,6

8 (p ∧ q) ∨ (¬p ∧ ¬q) ∨I-7

9 ¬((p ∧ q) ∨ (¬p ∧ ¬q)) R-2

10 ¬p ¬I-3,8,9

11 q H

12 q R-11

13 p ≡ q R-1

14 p ≡E-12,13

15 p ∧ q ∧I-12,14

16 (p ∧ q) ∨ (¬p ∧ ¬q) ∨I-15

17 ¬((p ∧ q) ∨ (¬p ∧ ¬q)) R-2

18 ¬q ¬I-11,16,17

19 ¬p ∧ ¬q ∧I-10-18

20 (p ∧ q) ∨ (¬p ∧ ¬q) ∨I-19

21 ¬((p ∧ q) ∨ (¬p ∧ ¬q)) R-2

22 ¬¬((p ∧ q) ∨ (¬p ∧ ¬q)) ¬I-2,20,21

23 (p ∧ q) ∨ (¬p ∧ ¬q) ¬E-22

(j) p ≡ q ` (p ∨ q) ⊃ (p ∧ q)

1 p ≡ q H

2 p ∨ q H

3 p H

4 p R-3

5 q H

6 p ≡ q R-1

7 q R-5

8 p ≡E-6,7

9 p ∨E-3,4,5,8

10 p H

11 p ≡ q R-1

12 p R-10

13 q ≡E-11,12

14 q H

15 q R-14

16 q ∨E-10,13,14,15

17 p ∧ q ∧I-9,16

18 (p ∨ q) ⊃ (p ∧ q) ⊃I-2,17

(k) q ≡ ¬r, p ⊃ ¬q ` p ⊃ r

1 q ≡ ¬r H

2 p ⊃ ¬q H

3 p H

4 ¬r H

5 ¬r R-4

6 q ≡ ¬r R-1

7 q ≡E-5,6

8 p R-3

9 p ⊃ ¬q R-2

10 ¬q ⊃E-8,9

11 ¬¬r ¬I-4,7,10

12 r ¬E-11

13 p ⊃ r ⊃I-3,12

Exercice 8

Consideront la table de verite de p ∗ q :

p q p ∗ qV V VV F VF V FF F F

On peut etablir une regle d’introduction de ∗ en considerant que la valeur de verite de p ∗ qdepend entierement de la valeur de verite de p. Ainsi, si p est vrai, alors p ∗ q est vrai :

1 A1...

n An

...

...

o A ← Si nous avons reussi a ecrire A...

p A ∗B ← Si nous avons reussi a ecrire A ∗B...

Inversement, la regle d’elimination de ∗ est egalement etablie en regard de p. Ainsi, si p ∗ qest vrai, c’est que q est vrai :

1 A1...

n An

...

...

o A ∗B ← Si nous avons reussi a ecrire A ∗B...

p A ← Si nous avons reussi a ecrire A...

Exercice 9

On cherche a demontrer que : A ⊃ ¬B ` B ⊃ ¬A.

Demonstration.

1 A ⊃ ¬B H

2 B H

3 A H

4 A R-3

5 A ⊃ ¬B R-1

6 ¬B ⊃E-4,5

7 B R-2

8 ¬A ¬I-3,6,7

9 B ⊃ ¬A ⊃I-2,8

6 Les concepts fondamentaux de calcul des predicats

Exercice 1

(a) (∀x)Px est une f.p. si et seulement si Px est une f.p. (clause (ii)), ce qui est le cas (clause(i) en tant que predicat unaire).

(b) (∀x)(∃y)(Rxy ⊃ (∃z)Pz) est une f.p. si et seulement si (∃y)(Rxy ⊃ (∃z)Pz) est une f.p(clause (ii)). Or, (∃y)(Rxy ⊃ (∃z)Pz) est une f.p si et seulement si (Rxy ⊃ (∃z)Pz) estune f.p. (clause (ii)) ; donc si et seulement si Rxy est une f.p et si (∃z)Pz est une f.p, cequi est le cas pour Rxy (clause (i) en tant que predicat binaire). Or, selon la clause (ii),(∃z)Pz est une f.p si et seulement si Pz est une f.p, ce qui est le cas (clause (i) en tantque predicat unaire). Donc, (∀x)(∃y)(Rxy ⊃ (∃z)Pz) est une f.p..

(c) (∃x)¬Rab est une f.p si Rab est une f.p (clause (ii)), ce qui est le cas (clause (i) en tantque predicat binaire).

(d) (∃x)Py∧Rab est une f.p. si et seulement si Py∧Rab est un f.p., ce qui n’est pas le cas, caril aurait fallu mettre l’expression entre parentheses : (∃x)(Py∧Rab) ou ((∃x)Py∧Rab).

Exercice 2

(a) (∀x)(Px ⊃ (Ox ∨ Fx))(b) (∀x)(V x ⊃ Bx)(c) (∀x)(∀y)(∀z)((Hx ∧Bly ∧Brz) ⊃ Pxyz)(d) (∀x)(∀y)((Hx ∧ Fx) ⊃ Ixy)(e) (∀x)(∀y)((Fx ∧Hy) ⊃ Ixy) ⊃ (∃z)(Fz ∧ Iza)(f) ¬[(∀x)(Bx ⊃ Ox)] ≡ (∃x)(Bx ∧ ¬Ox)

(g) (∃x)(Pex) ∧ (∃x)(Plx) ∧ ¬[(∃x)(Pex ∧ Plx)](h) (∀x)((Pex ∧ Plx) ⊃ Pax)(i) (∃x)(Ax ∧ ¬Rx) ∧ ¬[(∃x)(¬Ax ∧Rx)]

Exercice 3

(a) i.

¬[(∀x)(Px ⊃ (Ox ∨ Fx))] ≡ (∃x)¬(Px ⊃ (Ox ∨ Fx))≡ (∃x)¬(¬Px ∨ (Ox ∨ Fx))≡ (∃x)¬(¬Px ∨Ox ∨ Fx)≡ (∃x)(Px ∧ ¬Ox ∧ ¬Fx)

ii. Il y a des portes qui ne sont ni ouvertes ni fermees.

(b) i.

¬[(∀x)(V x ⊃ Bx)] ≡ (∃x)¬(V x ⊃ Bx)≡ (∃x)¬(¬V x ∨Bx)≡ (∃x)(V x ∧ ¬Bx)

ii. Il y a des verites qui ne sont pas dans la Bible.

(c) i.

¬[(∀x)(∀y)(∀z)((Hx ∧Bly ∧Brz) ⊃ Pxyz))]≡ (∃x)(∃y)(∃z)¬((Hx ∧Bly ∧Brz) ⊃ Pxyz))≡ (∃x)(∃y)(∃z)¬(¬(Hx ∧Bly ∧Brz) ∨ Pxyz))≡ (∃x)(∃y)(∃z)((Hx ∧Bly ∧Brz) ∧ ¬Pxyz))≡ (∃x)(∃y)(∃z)((Hx ∧Bly ∧Brz ∧ ¬Pxyz))

ii. Il y a au moins un homme, une blonde et une brune tels cet homme ne prefere pasla blonde a la brune.

(d) i.

¬[(∀x)(∀y)((Hx ∧ Fx) ⊃ Ixy)] ≡ (∃x)(∃y)¬((Hx ∧ Fx) ⊃ Ixy)≡ (∃x)(∃y)¬(¬(Hx ∧ Fx) ∨ Ixy)≡ (∃x)(∃y)(Hx ∧ Fx) ∧ ¬Ixy)≡ (∃x)(∃y)(Hx ∧ Fx ∧ ¬Ixy)

ii. Il y a au moins un homme et une femme tels que cette femme n’est pas plus intelli-gente que lui.

(e) i.

¬[(∀x)(∀y)((Fx ∧Hy) ⊃ Ixy) ⊃ (∃z)(Fz ∧ Iza)]≡ ¬[(∃x)(∃y)¬((Fx ∧Hy) ⊃ Ixy) ∨ (∃z)(Fz ∧ Iza)]≡ (∀x)(∀y)((Fx ∧Hy) ⊃ Ixy) ∧ ¬(∃z)(Fz ∧ Iza)≡ (∀x)(∀y)((Fx ∧Hy) ⊃ Ixy) ∧ (∀z)¬(Fz ∧ Iza)≡ (∀x)(∀y)((Fx ∧Hy) ⊃ Ixy) ∧ (∀z)(¬Fz ∨ ¬Iza)≡ (∀x)(∀y)((Fx ∧Hy) ⊃ Ixy) ∧ (∀z)(Fz ⊃ ¬Iza)

ii. Les femmes sont plus intelligentes que les hommes, mais aucune n’est plus intelligenteque le professeur.

(f) i.

¬{¬[(∀x)(Bx ⊃ Ox)]} ≡ (∀x)(Bx ⊃ Ox)

ii. Tout ce qui brille est or.

(g) i.

¬{(∃x)(Pex) ∧ (∃x)(Plx)∧¬[(∃x)(Pex ∧ Plx)]}≡ ¬{(∃x)(Pex) ∧ (∃x)(Plx) ∧ ¬[(∃x)(Pex ∧ Plx)]}≡ ¬[(∃x)(Pex)] ∨ ¬[(∃x)(Plx)] ∨ [(∃x)(Pex ∧ Plx)]

ii. Il n’y a pas de peines ou de plaisirs ou il y a au moins une peine qui est un plaisir.

(h) i.

¬[(∀x)((Pex ∧ Plx) ⊃ Pax)] ≡ (∃x)¬((Pex ∧ Plx) ⊃ Pax)≡ (∃x)¬(¬(Pex ∧ Plx) ∨ Pax)≡ (∃x)(Pex ∧ Plx) ∧ ¬Pax)≡ (∃x)(Pex ∧ Plx ∧ ¬Pax)

ii. Il y a des peines qui sont des plaisirs, mais ce ne sont pas des peines d’amour.

(i) i.

¬{[(∃x)(Ax ∧ ¬Rx)] ∧ ¬[(∃x)(¬Ax ∧Rx)]}≡ ¬[(∃x)(Ax ∧ ¬Rx)] ∨ [(∃x)(¬Ax ∧Rx)]≡ (∀x)¬(Ax ∧ ¬Rx)] ∨ [(∃x)(¬Ax ∧Rx)]≡ (∀x)(¬Ax ∨Rx)] ∨ [(∃x)(¬Ax ∧Rx)]≡ (∀x)(Ax ⊃ Rx)] ∨ [(∃x)(¬Ax ∧Rx)]

ii. Toutes les bonnes actions sont recompensees ou certaines mauvaises actions le sontaussi.

Exercice 4

Soit les enonces suivants :Ax : x est amour.Hx : x est heureuse.Ix : x est imaginaire.

(a) Les amours heureuses sont imaginaires. (∀x)((Ax ∧Hx) ⊃ Ix)(b) Les amours imaginaires sont heureuses. (∀x)((Ax ∧ Ix) ⊃ Hx)(c) Les amours malheureuses ne sont pas imaginaires. (∀x)((Ax ∧ ¬Hx) ⊃ ¬Ix).(d) Il n’y a pas d’amours heureuses qui ne soient imaginaires. ¬(∃x)((Ax ∧Hx ∧ ¬Ix)(e) Il n’y a d’imaginaire que les amours heureuses. (∀x)((Ax ∧ Ix) ⊃ Hx)(f) Toutes les amours imaginaires sont heureuses. (∀x)((Ax ∧ Ix) ⊃ Hx)Les enonces (b)-(c)-(e)-(f) sont equivalents. Les enonces (a)-(d) sont equivalents. En effet,on a :

(∀x)((Ax ∧ Ix) ⊃ Hx) ≡ (∀x)(¬(Ax ∧ Ix) ∨Hx)≡ (∀x)(¬Ax ∨ ¬Ix) ∨Hx)≡ (∀x)(¬Ax ∨Hx ∨ ¬Ix)≡ (∀x)(¬(Ax ∧ ¬Hx) ∨ ¬Ix)≡ (∀x)((Ax ∧ ¬Hx) ⊃ ¬Ix)

(∀x)((Ax ∧Hx) ⊃ Ix) ≡ ¬(∃x)¬((Ax ∧Hx) ⊃ Ix)≡ ¬(∃x)¬(¬(Ax ∧Hx) ∨ Ix)≡ ¬(∃x)((Ax ∧Hx) ∧ ¬Ix)≡ ¬(∃x)(Ax ∧Hx ∧ ¬Ix)

Aucun enonce n’est par ailleurs la negation d’un autre. En effet :

¬[(∀x)((Ax ∧ Ix) ⊃ Hx)] ≡ ¬[(∀x)(¬Ax ∨Hx ∨ ¬Ix)] ≡ (∃x)(Ax ∧ ¬Hx ∧ Ix)

Tandis que :

(∀x)((Ax ∧Hx) ⊃ Ix) ≡ ¬(∃x)(Ax ∧Hx ∧ ¬Ix)

Exercice 5

Pour les enonces (b)-(c)-(e)-(f), on a deja :

¬[(∀x)((Ax ∧ Ix) ⊃ Hx)] ≡ ¬[(∀x)(¬Ax ∨Hx ∨ ¬Ix)] ≡ (∃x)(Ax ∧ ¬Hx ∧ Ix)Il y a des amours malheureuses qui sont imaginaires.

Et pour les enonces (a)-(d), on a :

¬[(∀x)((Ax ∧Hx) ⊃ Ix)] ≡ (∀x)¬(¬(Ax ∧Hx) ∨ Ix) ≡ (∀x)(Ax ∧Hx ∧ ¬Ix)Il y a des amours heureuses qui ne sont pas imaginaires.

Exercice 6

(a) Px : x reussit a ramener la paix en Yougoslavie.Qx : x desire la fin des combats.

On a : (∃x)Px ⊃ (∀x)Qx

(b) Ix : x est pour l’independance du Quebec.Qx : x est quebecois.a : Chretien.

On a : (∃x)(Qx ∧ ¬Ix) ⊃ ¬Ia

Exercice 7

(a) (∀x)(∀y)((Px ∧ Ey ∧Dxy) ⊃Mx)(b) (∀x)(∀y)¬Axy

Exercice 8

(a)

(b) < a, b >∈ P , donc Pab est vrai.< b, c >6∈ P , donc Pbc est faux.< a, a >6∈ P , donc Paa est faux.< b, b >∈ P , donc Pbb est vrai.< c, c >6∈ P , donc Pcc est faux.< a, c >∈ P , donc Pac est vrai.

(c) A1 satisfait Pxy ssi < a, b >∈ P , ce qui est le cas.A1 satisfait Pxz ssi < a, c >∈ P , ce qui est le cas.A1 satisfait Pzx ssi < c, a >∈ P , ce qui n’est pas le cas.A1 satisfait Pax ssi < a, a >∈ P , ce qui n’est pas le cas.A1 satisfait Pab ssi < a, b >∈ P , ce qui est le cas.A1 satisfait Pbb ssi < b, b >∈ P , ce qui est le cas.

A1 satisfait Pxa ssi < a, a >∈ P , ce qui n’est pas le cas.A1 satisfait Pzb ssi < c, b >∈ P , ce qui est le cas.A1 satisfait Pcc ssi < c, c >∈ P , ce qui n’est pas le cas.A2 satisfait Pxy ssi < a, b >∈ P , ce qui est le cas.A2 satisfait Pxz ssi < a, b >∈ P , ce qui est le cas.A2 satisfait Pzx ssi < b, a >∈ P , ce qui est le cas.A2 satisfait Pax ssi < a, a >∈ P , ce qui n’est pas le cas.A2 satisfait Pab ssi < a, b >∈ P , ce qui est le cas.A2 satisfait Pbb ssi < b, b >∈ P , ce qui est le cas.A2 satisfait Pxa ssi < a, a >∈ P , ce qui n’est pas le cas.A2 satisfait Pzb ssi < b, b >∈ P , ce qui est le cas.A2 satisfait Pcc ssi < c, c >∈ P , ce qui n’est pas le cas.

(d) Il y aura nn assignations possibles ou n est le nombre d’individus du domaine. Pourn = 3, on a donc 27 assignations possibles.

Exercice 9

(a)

(b) Pour satisfaire A, considerant x < x, il faut que < x, x >∈<, ce qui n’est pas le cas, caraucun nombre de D n’est plus petit que lui-meme. Pour satisfaire A, considerant x ≤ x,il faut que < x, x >∈≤, ce qui est le cas pour tous les nombres de D.

Exercice 10

A1 satisfait Pxy ssi < x, y >∈ P , soit ssi < a, b >∈ P , ce qui est le cas. A1 satisfait Paxssi < a, x >∈ P , soit ssi < a, a >∈ P , ce qui n’est pas le cas. Donc, A1 ne satisfait pasPxy ⊃ Pax.

A1 satisfait Pxa ssi < x, a >∈ P , soit ssi < a, a >∈ P , ce qui n’est pas le cas. A1 satisfaitPaa ssi < a, a >∈ P , ce qui n’est pas le cas. Donc, A1 satisfait Pxa ⊃ Paa.

A1 satisfait Pax ssi < x, a >∈ P , soit ssi < a, a >∈ P , ce qui n’est pas le cas. A1 satisfaitPxa ssi < a, a >∈ P , ce qui n’est pas le cas. Donc, A1 ne satisfait pas Pax ∨ Pxa.

A1 satisfait Pax ssi < x, a >∈ P , soit ssi < a, a >∈ P , ce qui n’est pas le cas. Donc, A1satisfait Pax ∨ ¬Pax.

A1 satisfait Pax ssi < x, a >∈ P , soit ssi < a, a >∈ P , ce qui n’est pas le cas. A1 satisfaitPab ssi < a, b >∈ P , ce qui est le cas. Donc, A1 satisfait Pax ⊃ (Pab ⊃ Pax).

Exercice 11

(a) Quelqu’un aime Marie. A1 satisfait (∃x)Pxb ssi il y a une assignation A′1 qui attribue

une valeur a x qui est telle que < x, b >∈ P , par exemple x = b. Ceci correspond auraisonnement suivant : quelqu’un aime Marie, car Marie s’aime.

(b) Tout le monde aime z. A1 satisfait (∀x)Pxz ssi toute assignation A′1 qui attribue aux

variables la meme valeur que A1 sauf peut-etre a x satisfait Pxz, soit ssi < a, z >∈ P , <

b, z >∈ P , < c, z >∈ P , c’est-a-dire si < a, c >∈ P , < b, c >∈ P , < c, c >∈ P , ce quin’est pas le cas.

(c) Tout le monde aime Pierre. A1 satisfait (∀x)Pxa ssi toute assignation A′1 qui attribue

aux variables la meme valeur que A1 sauf peut-etre a x satisfait Pxa, ssi < a, a >∈ P , <b, a >∈ P , < c, a >∈ P , ce qui n’est pas le cas.

(d) Tout le monde aime Marie. A1 satisfait (∀x)Pxb ssi toute assignation A′1 qui attribue

aux variables la meme valeur que A1 sauf peut-etre a x satisfait Pxb, ssi < a, b >∈ P , <b, b >∈ P , < c, b >∈ P , ce qui est le cas. Ceci correspond au raisonnement suivant : toutle monde aime Marie, car Pierre aime Marie, Marie s’aime et Gerard aime Marie.

(e) Il y a quelqu’un que tout le monde aime. A1 satisfait (∃x)(∀y)Pyx ssi toute assignationA′

1 qui attribue aux variables la meme valeur que A1 sauf peut-etre a x satisfait (∀y)Pyx,c’est-a-dire ssi toute assignation A′

1 qui attribue aux variables les memes valeurs que A′1

sauf peut-etre a y satisfait Pyx. Prenant pour A′1 l’assignation x = b, on a < a, b >∈

P , < b, b >∈ P , < c, b >∈ P . Ceci correspond au raisonnement suivant : il y a quelqu’unque tout le monde aime, car Pierre aime Marie, Marie s’aime et Gerard aime Marie.

(f) Il y a quelqu’un qui aime tout le monde. A1 satisfait (∃x)(∀y)Pxy ssi toute assignationA′

1 qui attribue aux variables la meme valeur que A1 sauf peut-etre a x qui satisfait(∀y)Pxy, c’est-a-dire ssi toute assignation A′

1 qui attribue aux variables les memes valeursque A′

1 sauf peut-etre a y satisfait Pxy. Prenant pour A′1 l’assignation x = b, on a

< b, a >∈ P , < b, b >∈ P , < b, c >∈ P , ce qui n’est pas le cas.

(g) Si Pierre aime Marie, alors il y a quelqu’un qui aime Marie. A1 satisfait Pab ⊃ (∃x)Pxbssi A1 ne satisfait pas Pab ou que A1 satisfait (∃x)Pxb. Comme A1 satisfait Pab, il fautqu’il y ait une assignation A′

1 qui attribue une valeur a x qui est telle que < x, b >∈ P ,par exemple x = a.

(h) Si tout le monde aime Marie, alors Marie s’aime. A1 satisfait (∀x)Pxb ⊃ Pbb ssi A1 nesatisfait pas (∀x)Pxb ou que A1 satisfait Pbb, Or, A1 satisfait Pbb, donc A1 satisfait(∀x)Pxb ⊃ Pbb.

Exercice 12

(a) Faux.

(b) Faux.

(c) Faux.

(d) Vrai.

Exercice 13

(a) Vrai. Tout le monde aime Pierre.

(b) Vrai. Tout le monde s’aime et ce n’est pas tout le monde qui aime Marie.

(c) Vrai. Il y a quelqu’un que tout le monde aime.

(d) Faux. Tout le monde aime tout le monde.

Exercice 14

(a) Px

(b) (Px ⊃ Py)(c) (∃x)(Px ⊃ Py), (Px ⊃ Py)(d) Px, Py

(e) (Px ⊃ (∃x)Py), Py

(f) P (x), P (y)(g) (Px ⊃ (∀x)Px)), Px

Exercice 15

(a) (∀x)Px ⊃ ((∃y)Rxy)(b) (∀x)(∃y)(∀x)(Pxy ⊃ (∃x)Pzy)(c) (∀x)((Pxy ⊃ (∃y)(∀x)Pxy) ⊃ Rxx)

Exercice 2000

1 ∀y¬P (y)

2 ∃xP (x)

3 u P (u)

4 ∀y¬P (y) R, 1

5 ¬P (u) ∀E, 4

6 ⊥ ¬E, 3,5

7 ⊥ ∃E, 2, 3–6

8 ¬∃xP (x) ¬I, 2–7