Exercice 1.1. Phrases et propositions.
Dites combien de propositions exprime chacune des expressions suivantes, et s’il y en a plusieurs formulez-les.
(1) Beaucoup plus de gens parlent anglais que moi.
(2) Il pleut.
(3) Que l’argent pousse dans les arbres.
(4) Si tu veux grandir, mange ta soupe.
(5) Paul a loué sa maison.
(6) Si Pierre a fait son travail, il peut se reposer, mais s’il ne l’a pas fait, il ne peut pas.
(7) La plupart des grosses fortunes sont entre les mains d’une seule personne.
(8) Tous les étudiants parlent deux langues.
Exercice 1.2. Propositions simples et propositions complexes.
Dites si ces phrases expriment des propositions atomiques ou complexes.
(1) L’ami de Pierre est parti se promener près de l’étang du parc.
(2) L’ami que Pierre héberge est parti se promener près de l’étang qui est dans le parc.
(3) L’ami de Pierre, que je ne peux pas supporter, est parti se promener près de l’étang, où il passe toutes ses journées.
(4) Si tu veux grandir, tu as tort de ne pas manger de soupe.
(5) On s’amuse quand Pierre vient.
(6) On s’amuse bien avec Pierre.
(7) Il est gentil mais il m’ennuie.
(8) Il est arrivé à point nommé comme dans un vieux western la cavalerie ferait soudain entendre, au moment où tout semble perdu, le chant hardi de sa trompette, et viendrait arracher à la mort la veuve et l’orphelin.
Exercice 1.3. Connecteurs vérifonctionnels.
Dites combien il y a de connecteurs vérifonctionnels unaires et écrivez leur table de vérité.
Exercice 1.4. Arbres syntaxiques.
Ecrivez les arbres syntaxiques des formules suivantes. A chaque fois, dites quel est le connecteur principal, et quelle est la portée de «  ».
(1) (p & q)  (q  p)
(2) p & (q  (q  p))
(3) (q & p)  r
(4) p  ((q  (q  r)) & p)
Exercice 1.5. Parenthésage.
Pour chacune des expressions suivantes, dites combien de propositions distinctes elle peut exprimer,  et donnez ces propositions en utilisant des parenthèses.
(1) p & q  r
(2) p &  q
(3)  p & q
(4)  p   q & r
Exercice 1.6. Usage et mention. 
Dites si les énoncés suivants sont vrais :
(1) « Raffarin » est premier ministre.
(2) Le premier ministre s’appelle « Raffarin ».
(3) « Raffarin » contient huit lettres.
(4) « Raffarin » commence par des guillemets.
(5) « Raffarin » est le véritable nom de Raffarin.
Exercice 1.7. Tables de vérité pour une interprétation.
A l’aide de la méthode des tables de vérité, dites si les formules suivantes sont vraies ou fausses pour l’interprétation selon laquelle p est vrai, q est faux et r est vrai. (Il est inutile d’écrire les tables complètes.)
(1) (p & q)  r
(2) (p & r)  q
(3) (p  q)  (r  q)
(4) (r & (p  q))  q
(5) (p  (q & r))  (p  (q  r))
(6) ((q  (p & q))  q)  r
(7) ((r  p)  q)  (r & p)
Exercice 1.8. Tables de vérité pour les tautologies
Vérifier par la méthode des tables de vérité que les formules suivantes sont valides.
(1) (p & (q & r))  ((p & q) & r)		associativité de &
(2) (p  (q  r))  ((p  q)  r)		associativité de 
(3) (p & q)  (p  q)		loi de Morgan (interdéfinissabilité de & et )
(4) (p  q)  (p & q)		loi de Morgan (interdéfinissabilité de & et )
(5) (p  q)  (q  p)			contraposition
Exercice 1.9. Tables de vérité pour les arguments valides
Vérifier par la méthode des tables de vérité que les arguments suivants sont valides (les différentes prémisses sont séparées par des virgules) :
(1) p  q, p  q
(2) p  q, q  p
(3) p  q   (p & q)
(4) p  q  p  q
Exercice 1.10. Arbres pour les tautologies.
Vérifier par la méthode des arbres que les formules suivantes sont des tautologies :
(1) p  (q  p)
(2) (p  p)  p
(3) (p  q)  ((p  q)  q)
Dire par la méthode des arbres si les énoncés suivants sont des tautologies. S’ils ne le sont pas, dire quelle interprétation les rend faux.
(4) p  (p  q)
(5) (p & q)  (p & q)
(6) ((p  q) & (q  r))  (p  r)
Exercice 1.11. Arbres pour les arguments valides.
Vérifier par la méthode des arbres que les arguments suivants sont valides :
(1) p  q, p  q  p
(2) (p  q)  p  p
(3) (p  (q  r)  (p & q)  r)
Dire par la méthode des arbres si les arguments suivants sont valides. S’ils ne le sont pas, donner un contrexemple.
(4) p  r, q  r  p  q
(5) p  (q  r), r  q  p
(6) p  (q  r), q  (r  p)  p  r
Exercice 1.12. Transformations de base.
Transformer les formules suivantes comme indiqué. Vérifier avec une table que la formule originale et votre résultat concordent.
(1) (p  q)		en formule contenant uniquement  et &
(2) (p  q)		en formule contenant uniquement  et 
(3) p  (q  r)	en formule contenant uniquement  et &
(4) p & (q & r)	en formule contenant uniquement  et 
Annexe. Tautologies de base.
Principes logiques fondamentaux :
p  p					principe identité propositionnel
 (p & p)				principe de non-contradiction
p  p					principe du tiers exclu
p  p					principe de la double négation
Ces tautologies décrivent les propriétés de base de & et  :
(p & p)   p				idempotence de &
(p  p)   p				idempotence de 
(p & p)   (p & p)				commutativité de &
(p  p)   (p  p)				commutativité de 
(p & (q & r))  ((p & q) & r)		associativité de &
(p  (q  r))  ((p  q)  r)		associativité de 
Ces tautologies donnent les transformation de base pour aller d’une formule à une autre, ou traduire un connecteur en d’autres :
(p & (q  r))  ((p & q)  (q & r))	distributivité de & sur 
(p  (q & r))  ((p  q) & (q  r))	distributivité de sur &
(p & q)  (p  q)			loi de Morgan (interdéfinissabilité de & et )
(p  q)  (p & q)			loi de Morgan (interdéfinissabilité de & et )
p & q  (p  q)			loi de Morgan (interdéfinissabilité de & et )
p  q  (p & q)			loi de Morgan (interdéfinissabilité de & et )
(p  q)  (q  p)			contraposition
(p  q)  (p  q)			interdéfinissabilité de  et 
(p  q)  ((p  q)  (q  p))		interdéfinissabilité de  et