Exercice 1.9 Tautologies pour les arguments valides
Il y a deux méthodes pour vérifier la validité d’un argument par les tables de vérité. Soit A, B  C l’argument. A et B sont les prémisses, C la conclusion.
1) (Celle qu’on peut appeler la:) méthode directe. On vérifie que pour chaque interprétation (donc chaque ligne) où toutes les prémisses sont vraies, la conclusion est vraie. On fait deux colonnes pour cela: la colonne P, qui donne la conjonction des prémisses, et la colonne C, pour la conclusion. On regarde uniquement les lignes où P est vraie; si C est vraie à toutes ces lignes, l’argument est valide. (Par exemple, si on trouve que la colonne P est toujours fausse, l’argument est trivialement valide).
2) (Celle qu’on peut appeler la:) méthode de la contradiction correspondante. Si l’argument A, B  C est valide, alors (A & B) & C est une contradiction. Il suffit donc de faire la table de A & B & C. (Pourquoi (A & B) & C doit-il être une tautologie? Par définition, si l’argument est valide, alors si les prémisses sont vraies, alors la conclusion est vraie. Donc: on ne peut pas avoir les prémisses vraies et la conclusion fausse. Donc (A & B) & C, qui dit précisément “ prémisses vraies et conclusion fausse ” est une contradiction.)
La méthode 2 revient à la vérification des tautologies. J’utiliserai donc la méthode 1 ici. Comme précédent j’indique par des numéros l’ordre dans lequel la table est calculée. P et C indiquent les colonnes “ conjonction des prémisses ” et “ conclusion ”.

(1) p  q, p  q
p	q		(p		q)	&	p		q							
v	v			1v		Pv	1v		Cv							
v	f			f		f	v		f							
f	v			v		f	f		v							
f	f			v		f	f		f							
Il n’y a qu’une ligne où la conjonction des prémisses est vraie: la première. Dans cette situation, la conclusion (q) est vraie. Donc l’argument est valide.
Remarquez qu’à la troisième ligne aussi, la conclusion est vraie. Mais à cette ligne, les prémisses ne le sont pas. Est-ce un pb? Que dit la troisième ligne? Qu’il y a une situation dans laquelle q est vrai, même si ((p  q), p) ne sont pas vraies. Cela signifie qu’il y a d’autres moyens de rendre q vrai que d’avoir ((p  q), p); cela ne signifie pas que ((p  q), p) n’est pas un moyen infaillible d’avoir q. L’argument reste valide.
Comparez: p  q, q  p
p	q		(p		q)	&	q		p							
v	v			1v		P- v	1v		C- v							
v	f			f		f	f		v							
f	v			v		v	v		f							
f	f			v		f	f		f							
Il y a deux lignes sur lesquelles P est vrai: la première et la troisième. A la troisième, C est faux. Donc l’argument n’est pas invalide: il y a une situation dans laquelle P est vrai mais C n’est pas vrai: P n’implique donc pas C. (Ce faux syllogisme est appelé l’affirmation du conséquent. Exemple: “ S’il a pris la voiture il a pris les clefs, or il a pris les clefs, donc il a pris la voiture ”.)

En résumé:
P	C		P	C	
f	v		v	f	
l’argument peut être valide (selon les valeurs de P et C autres lignes)		l’argument n’est pas valide

(2) p  q, q  p
p	q		(p		q)	&	q		p							
v	v			1v		P- F	1F		C- F							
v	f			f		F	V		F							
f	v			v		F	F		V							
f	f			v		V	V		V							
Les prémisses sont vraies uniquement à la quatrième ligne. Dans cette interprétation la conclusion est vraie aussi. Argt valide.

(3) p  q  (p & q)
p	q		(p		q)		(	p	&	q)						
v	v			P- v			C- v	1 F	2 f	1 v						
v	f			f			v	f	f	f						
f	v			v			f	v	v	v						
f	f			v			v	v	f	f						
Prémisses vraies aux lignes 1, 3 et 4. A la ligne 3 la conclusion n’est pas vraie. L’argt n’est pas valide. Le contre-exemple est: p faux et q vrai. En ce cas p  q est vrai, mais (p & q) ne l’est pas.

(4) p  q  p  q
p	q		(p		q)			p		q						
v	v			P- v				1 F	C- V	1 v						
v	f			f				f	f	f						
f	v			v				v	v	v						
f	f			v				v	V	f						
Prémisses vraies aux lignes 1, 3, et 4, conclusion vraie à toutes ces lignes. L’argument est valide.

Question: que se passe-t-il quand les prémisses sont toujours fausses (contradiction)? Est-ce que l’argument est valide? Oui: dans toute situation où les prémisses sont vraies, la conclusion est vraie... parce qu’il n’y a pas de situation où les prémisses sont vraies! Peu importe la conclusion, finalement: si les prémisses sont toujours fausses, l’argument est automatiquement valide. Comme on disait au bon vieux temps: “ du faux on peut tout déduire ”.
La méthode de la contradiction correspondante dit la même chose. Supposons que les prémisses sont toujours fausses: A&B est une contradiction. (A et B sont les prémisses). Qu’en est-il de (A&B) & C ? Pour que cette formule soit vraie, il faut que 1) (A&B) soit vraie, et que 2) C soit vraie. Or (A&B) n’est jamais vrai. Donc la formule est toujours fausse. Donc l’argument correspondant est valide. Un argument dont les prémisses sont toujours fausses est automatiquement valide.
Exercice 1.10 Arbres pour les tautologies
La méthode des arbres: elle consiste à chercher une interprétation qui satisfait une formule donnée. Si la formule est de type A&B, alors elle n’est vraie que si A et B sont vrais en même temps. (=seule l’int° où A et B sont vrais satisfait cette formule). Si la formule est de type AvB, alors il y a deux types d’int°s qui la satisfont: celles où A est vraie, et celles où B est vraie.
D’où les règles pour & et v. Les autres règles sont obtenues en transformant les connecteurs en & ou en v. Par exemple, la règle pour pq est celle de pvq. Celle de pq est celle de (p&q)v(p&q), etc.
On développe l’arbre d’une formule en appliquant ces règles aux ‘bourgeons’ de l’arbre. (Un bourgeon est une formule qui n’est ni atomique (p) ni la négation d’une formule atomique (p).) Il est conseillé d’appliquer les règles “ et ” avant les règles “ ou ”, parce que ces dernières augmentent le nb de branches.
Lorsqu’on applique une règle à une formule en haut de l’arbre, il faut reporter le résultat sur toutes les branches. [donner un exemple]
Une branche est dite “ fermée ” si elle contient une proposition et sa négation. Cela signifie que la situation que décrit cette branche est impossible. Il n’y a donc pas d’interprétation pouvant satisfaire la formule ici.
Si une formule A est une tautologie, sa négation A est une contradiction. Si A est une contradiction, son arbre est fermé. On peut ainsi vérifier que A est une tautologie.
(Pourquoi on ne vérifie pas en faisant l’arbre de A? Essayez pour voir. Est-ce qu’il suffit qu’il y ait des branches ouvertes? Non, cela montre seulement que A est vrai (satisfait) dans certaines situations, pas toutes. Pour que A soit une tautologie, il faut qu’il soit vrai dans toutes les situations. Cela veut dire que son arbre inclut toutes les situations possibles. Par exemple, qu’il décrive 16 situations distinctes dans un cas à p, q, r, s. Les inconvénients sont clairs: 1) cela fait des arbres énormes. 2) cela cause des erreurs. Le nombre de branches ouvertes n’indique pas clairement si toutes les situations sont là: deux branches distinctes peuvent décrire la même situation, et une même branche peut décrire plusieurs situations. Les deux cas peuvent être illustrés avec l’arbre de AvB. La situation dans laquelle A et B sont vraie est aussi bien décrite par la branche A que par la branche B. Et la branche A décrit en fait deux situations: A et non-B, et A et B.)
Correction: pas ici, trop fastidieux de faire des arbres.
Exercice 1.11 Arbres pour les arguments valides
On utilise un équivalent de la méthode de la contradiction correspondante pour les arbres. Si l’argument A, B -> C est valide, alors A et B et -C n’est pas valide. On aligne donc ces trois formules A, B, -C, et on vérifie que l’arbre correspondant est fermé. Si c’est le cas il n’y a pas de situation où A & B & -C = l’argument n’a pas de contre-exemple =  l’argument est valide.
Exercice 1.12 Transformation des formules
(1) (pq)
conversion de :		(p v q) 
loi de Morgan:		p & q
ce qui était demandé.
(2) (pq)
conversion de :		( (pq) v (qp) )
conversion de :		 ( (pvq) v (qvp) )
ce qui était demandé.
(3) p v (q v r)
conversion de p v (...) suivant la loi de Morgan:	p & (...)
soit:	p & ( q v r )
loi du Morgan sur ( q v r ) :	q & r
soit:	p & (q & r)
ce qui était demandé.
(4) p & (q & r)
conversion de p & (...) suivant la loi de Morgan:	p v  (...)
soit:	 p v  (q & r)
conversion de (q & r) suivant la loi de Morgan:	q v r
soit:	p v  (q v r)
conversion de q v r en :	q  r
soit:	p v  (q  r)
conversion de p v (...) en :	p  (...)
soit:	p  (q  r)
ce qui était demandé.