PH203A - TD - semaine 3
Dernier TD
•	Syntaxe du calcul propositionnel
–	Portée des connecteurs
–	Ordre d'applications des connecteurs (arbres de formules)
•	Tables de vérité
–	Calcul d'une interprétation
–	Calcul d'une table
–	Tautologies
Aujourd'hui
•	Conséquence valide et preuve
•	Tables de vérité pour les déductions valides
–	exercice 1.9
•	La méthode des arbres
–	exercice 1.10 (tautologie) et 1.11
•	La déduction naturelle
Conséquence valide et preuve
•	Le raisonnement valide
–	Admettant que certaines croyances sont vraies, puis-je en tirer de nouvelles croyances, dont la vérité soit garantie par celle des premières? Ou: l'ensemble de mes croyances est-il cohérent?
–	La notion intuitive de raisonnement valide peut être définie de deux façons: preuve et conséquence valide
Preuve : A |- B
•	= "dérivation"
•	Notion syntaxique
–	Une preuve est une suite finie de formules. Une preuve conditionnelle a des prémisses, une preuve inconditionnelle n'en a pas.
–	On peut arriver à la conclusion par l'application d'un nombre finis de règles préservant la vérité.
–	Une proposition démontrable est un théorème.
•	La méthode des arbres et la déduction naturelle fonctionnent par l'application d'un nombre fini de règles aux formules.
Conséquence valide : A |= B
•	= "conséquence logique" = "argument valide"
•	Notion sémantique
–	Dans toutes les situations où A est vrai, B est vrai.
–	Une proposition vraie dans toutes les situations  est une proposition valide (ou tautologie).
•	La méthode des tables de vérité fonctionnent par l'examen des situations où une formule est vraie.
Preuve et conséquence valide (I)
•	Les deux notions sont-elles équivalentes?
–	Non. La conséquence valide ne requiert pas qu'on puisse aller de A à B en un nombre fini d'étapes basées sur un nombre fini de règles.
–	Or il pourrait y avoir une preuve infinie: ex, prouver "tout corbeau est noir" à partir d'énoncés singuliers.
Preuve et conséquence valide (II)
•	Les deux notions sont-elles coextensives?
–	Complétude du CP. Dans le calcul propositionnel, les deux notions sont coexstensives. Toute conséquence valide de A est démontrable à partir de A. 
–	Dans les autres langages ça ne marche pas (Gödel).
Correction des exercices
•	Exercice 1.9 Tables de vérité pour les arguments valides
•	Méthode de la contradiction correspondante
–	A, B -> C ssi A & B & -C est une contradiction
•	Méthode directe
La méthode des arbres (I)
•	Ce que fait la méthode
–	La méthode est une procédure effective pour trouver les interprétations qui satisfont une formule.
–	C'est une méthode syntaxique: elle fonctionne par l'application un nb fini de fois d'un nb fini de règles.
–	Les branches de l'arbre sont les différentes interprétations possibles.
La méthode des arbres (II)
•	Comment fonctionne la méthode
–	Une branche est fermée si elle aboutit à une situation impossible (q et -q). Elle est ouverte sinon.
–	Chaque branche entièrement développée et ouverte est une interprétation qui satisfait la proposition
–	Si toutes les branches sont fermées, la formule est une contradiction
La méthode des arbres (III)
•	Les règles
–	Deux règles de base: p&q et pvq
–	Les autres règles se ramènent à celles-ci
•	Application aux tautologies: exercice 1.10
•	Application aux preuves: exercice 1.11.
–	A, B |- C ssi l'arbre de A, B, -C est fermé
Prochain TD
•	Déduction naturelle
–	Exercice 3.1.
•	Logique et langue naturelle (si, si!)
–	Vérifonctionalité et non vérifonctionalité
–	Négation, disjonction et implication en langue naturelle.
–	Traduction et évaluation d'arguments en langue naturelle.