, ? (?x) (?(x) ? ?(s(x))) ? ?x ?(x), i.e
, Il s'agit d'un exemple de système incomplet, c'est-à-dire que certaines affirmations vraies de ce système ne sont pas démontrables
, Exercices Donner des preuves des séquents suivants
, Les seuls animaux dans cette maison sont des chats
, Tout animal qui aime contempler la lune est apteà devenir un animal familier
, Quand je déteste un animal, je l'évite soigneusement
, Aucun animal n'est carnivore,à moins qu'il n'aille rôder dehors la nuit
, Aucun chat ne manque jamais de tuer les souris
, Aucun animal ne s'attache jamaisà moi, excepté ceux qui sont dans la maison
, Les kangourous ne sont pas aptesà devenir des animaux familiers
, Aucun animal non carnivore ne tue de souris
, Je déteste les animaux qui ne s'attachent pasà moi
, Les animaux qui vont rôder dehors la nuit aiment toujours contempler la lune
, Conclusion: J'évite toujours soigneusement les kangourous
, Tous les animaux dans cette maison tuent des souris. Pour cetteétape on peut utiliser un diagramme de Venn. De même, de (8) et (11), on déduit : Tous les animaux de cette maison sont carnivores, Pour vérifier ce raisonnementà l'aide des diagrammes de Venn, il faut le découper en parties. Ainsi, de (1) et (5), on conclut
, Les déductions dans le calcul des prédicats sont cependant beaucoup plus simples. Voici une transcription un peu plus formelle de l'exemple précédent, où la variable libre x est implicitement quantifiée universellement. Les déductions se font aisémentà l'aide du modus ponens
, On dit que A est vraie dans l'interprétation I, et onécrit |= I A, si et seulement si pour toute valuation ?, |= ? I A
, Lorsque I est une interprétation dans laquelle chaque formule dans ? est vraie, on dit que I est un modèle de ?
, nous disons que A est une conséquence logique de ? si A est vrai dans chaque modèle de ?
, on ajoute les définitions de ?, ? et ?, ainsi que la règle du modus ponens
, Deux nouveaux axiomes sont propres au calcul des prédicats : A4 ?? (? ? ?) ? (? ? ?? ?) où ? ne figure pasà titre d'occurence libre dans ?. A5 ?? ? ? ? ? /? où ? est libre pour tout ? dans ?
, GU: ? ?? ? Cette dernière règle signifie que si l'on déduit ?à l'aide des axiomes et des règles d'inférence, alors on peut déduire ?? ?. Si ? contient la variable libre ?, cela signifie que ? est variable libre dans l'un des axiomes, ce qui signifie que l'axiome est vrai pour un ? quelconque, donc pour tout ?, ce qui justifie la règle. Cette règle ne doit pasêtre confondue avec la déduction de ?? ?à partir de ? pris comme hypothèse. En effet, si ? figure comme variable libre dans une hypothèse, il ne s'agit pas d'un ? quelconque, mais d'un ? bien précis, et on ne peut alors pas quantifier universellement. Cette nuance est très importante, Les deux règles d'inférence sont le modus ponensétendu aux formules ouvertes (contenant des variables libres), et d'autre part la règle de généralisation universelle
, Le système de preuve reprend le calcul des séquents de la logique propositionnelle et le complète avec les règles suivantes : -Règle d' introduction de ? dans l'antécédent, notée G ? ?,?(r),(?x) ?(x) ? ? ?,(?x) ?(x) ? ? (G ? )
, ) et (?x) ?(x) on peut déduire ?, alors puisque de (?x) ?(x) on peut déduire ?(r), on peut aussi déduire la conclusion. Cette règle aussi est réversible. -Règle d'introduction de ? dans le succédent
, ?x) ?(x),? (D ? ) (r ne doitêtre libre ni dans ? ni dans ?)
, il est clair que l'on peut déduire ?(r) pour n'importe quel r. Dire que de ? on peut déduire (?x) ?(x) est la formalisation de cette idée. Inversement, on peut particulariser x. -Règle d'introduction de ? dans l'antécédent, notée G ? ?,?(r) ? ? ?,(?x) ?(x) ? ? (G ? ), Intuition Sià partir de ? ne dépendant pas de r, on peut déduire ?(r)
, Intuition De ? et (?x) ?(x) on peut déduire ? et ?(r), en supposant que r n'est pas libre dans ?, on peut donc en déduire ?. La règle réciproque est aussi vraie
, Cet ouvrage s'adresse plutôt auxétudiants de philosophie. -René Lalement : Logique, réduction, résolution, Masson, 1990. Seules quelques parties concernent le traitement classique de la logique, Bibliographie Les ouvrages sur la logique sont légion. Nous nous contenterons ici de citer des ouvrages en français. Pour des références plus complètes, nous suggérons de consulter la bibliographie de Gochet et Gribomont. Nous avons très brièvement commenté ces ouvrages. -François Rivenc : Introductionà la logique, Petite bibliothèque Payot, 1989.
, Que sais-je?, n ? 225, PUF, 1993. Bref, mais utile pour se faire une idée et s'ouvrir des horizons, La logique
, Méthodes de logique, PUF, 1973. Ouvrage très didactique, recommandé pour une première introductionà la logique