Logique formelle

Tableaux sémantiques

Depuis les années 80, une autre technique pour déterminer la validité des arguments sur PC ou LPC a gagné en popularité, en raison à la fois de sa facilité d'apprentissage et de sa mise en œuvre simple par des programmes informatiques. Initialement suggéré par le logicien néerlandais Evert W. Beth, il a été plus développé et rendu public par le mathématicien et logicien américain Raymond M. Smullyan. Reposant sur l'observation qu'il est impossible que les prémisses d'un argument valable soient vraies alors que la conclusion est fausse, cette méthode tente d'interpréter (ou d'évaluer) les prémisses de telle manière qu'elles soient toutes simultanément satisfaites et la négation de la la conclusion est également satisfaite. Le succès d'un tel effort montrerait que l'argument n'est pas valable, tandis que le fait de ne pas trouver une telle interprétation montrerait qu'il est valide.

La construction d'un tableau sémantique se déroule comme suit: exprimer les prémisses et la négation de la conclusion d'un argument en PC en utilisant uniquement la négation (∼) et la disjonction (∨) comme connecteurs propositionnels. Éliminez chaque occurrence de deux signes de négation dans une séquence (par exemple, ∼∼∼∼∼a devient ∼a). Maintenant, construisez un diagramme d'arbre ramifiant vers le bas de telle sorte que chaque disjonction est remplacée par deux branches, une pour le disjoncteur gauche et une pour la droite. La disjonction d'origine est vraie si l'une ou l'autre branche est vraie. La référence aux lois de De Morgan montre qu'une négation d'une disjonction est vraie juste au cas où les négations des deux disjonctions sont vraies [ie, ∼ (p ∼ q) ≡ (∼p · ∼q)]. Cette observation sémantique conduit à la règle selon laquelle la négation d'une disjonction devient une branche contenant la négation de chaque disjonction:

Considérez l'argument suivant:

Écrire:

Maintenant, rayez la disjonction et formez deux branches:

Ce n'est que si toutes les phrases dans au moins une branche sont vraies qu'il est possible que les prémisses d'origine soient vraies et la conclusion fausse (de manière équivalente pour la négation de la conclusion). En traçant la ligne vers le haut dans chaque branche jusqu'au sommet de l'arbre, on observe qu'aucune évaluation de a dans la branche de gauche n'aura pour conséquence que toutes les phrases de cette branche recevront la valeur true (en raison de la présence de a et ∼a). De même, dans la branche de droite, la présence de b et ∼b rend impossible pour une évaluation que toutes les phrases de la branche reçoivent la valeur true. Ce sont toutes les branches possibles; ainsi, il est impossible de trouver une situation dans laquelle les prémisses sont vraies et la conclusion fausse. L'argument d'origine est donc valable.

Cette technique peut être étendue pour gérer d'autres connecteurs:

De plus, dans le LPC, des règles d'instanciation des wff quantifiés doivent être introduites. De toute évidence, toute branche contenant à la fois (∀x) ϕx et ∼ϕy est une branche dans laquelle toutes les phrases de cette branche ne peuvent pas être satisfaites simultanément (sous l'hypothèse de la cohérence ω; voir métalogique). Encore une fois, si toutes les branches ne sont pas simultanément satisfaisables, l'argument d'origine est valide.

Systèmes spéciaux de LPC

Le LPC exposé ci-dessus peut être modifié en restreignant ou en étendant la plage de wffs de diverses manières:

• 1.Systèmes partiels de LPC. Certains des systèmes les plus importants produits par restriction sont décrits ci-dessous:

  • Il peut être nécessaire que chaque variable de prédicat soit monadique tout en permettant un nombre infini de variables individuelles et de prédicat. Les wff atomiques sont alors simplement ceux constitués d'une variable de prédicat suivie d'une seule variable individuelle. Sinon, les règles de formation restent comme avant, et la définition de la validité est aussi comme avant, bien que simplifiée de manière évidente. Ce système est connu sous le nom de LPC monadique; il fournit une logique de propriétés mais pas de relations. Une caractéristique importante de ce système est qu'il est décidable. (Cependant, l'introduction d'une seule variable de prédicat dyadique rendrait le système indécidable et, en fait, même le système qui ne contient qu'une seule variable de prédicat dyadique et aucune autre variable de prédicat ne s'est révélé indécidable.)

  • bUn système encore plus simple peut être formé en exigeant (1) que chaque variable de prédicat soit monadique, (2) qu'une seule variable individuelle (par exemple, x) soit utilisée, (3) que chaque occurrence de cette variable soit liée, et (4) qu'aucun quantificateur n'apparaît dans le cadre d'un autre. Des exemples de wffs de ce système sont (∀x) [ϕx ⊃ (ψx · χx)] («Tout ce qui est ϕ est à la fois ψ et χ»); (∃x) (ϕx · ∼ψx) ("Il y a quelque chose qui est ϕ mais pas ψ"); et (∀x) (ϕx ⊃ ψx) ⊃ (∃x) (ϕx · ψx) («Si ce qui est ϕ est ψ, alors quelque chose est à la fois ϕ et ψ»). La notation de ce système peut être simplifiée en omettant x partout et en écrivant ∃ϕ pour «Quelque chose est ϕ», ∀ (ϕ ⊃ ψ) pour «Tout ce qui est ϕ est ψ», et ainsi de suite. Bien que ce système soit même plus rudimentaire que le LPC monadique (dont il est un fragment), les formes d'un large éventail d'inférences peuvent y être représentées. C'est aussi un système décidable, et des procédures de décision de type élémentaire peuvent lui être données.

• 2.Extensions de LPC. Des systèmes plus élaborés, dans lesquels un plus large éventail de propositions peuvent être exprimées, ont été construits en ajoutant au LPC de nouveaux symboles de différents types. Les plus simples de ces ajouts sont:

  • a.Une ou plusieurs constantes individuelles (disons, a, b,

    ): ces constantes sont interprétées comme des noms d'individus spécifiques; formellement, elles se distinguent des variables individuelles par le fait qu'elles ne peuvent pas apparaître dans les quantificateurs; par exemple, (∀x) est un quantificateur mais pas (∀a).

  • b.Une ou plusieurs constantes de prédicat (disons, A, B,

    ), chacune d'un certain degré spécifié, considérée comme désignant des propriétés ou des relations spécifiques.

Un autre ajout possible, qui appelle une explication un peu plus complète, consiste en des symboles conçus pour représenter des fonctions. La notion de fonction peut être suffisamment expliquée aux fins actuelles comme suit. On dit qu'il y a une certaine fonction de n arguments (ou, de degré n) quand il y a une règle qui spécifie un objet unique (appelé la valeur de la fonction) chaque fois que tous les arguments sont spécifiés. Dans le domaine des êtres humains, par exemple, «la mère de -» est une fonction monadique (une fonction d'un argument), car pour chaque être humain il y a un individu unique qui est sa mère; et dans le domaine des nombres naturels (ie, 0, 1, 2,

), «La somme de - et -» est fonction de deux arguments, car pour toute paire de nombres naturels, il existe un nombre naturel qui est leur somme. Un symbole de fonction peut être considéré comme formant un nom à partir d'autres noms (ses arguments); ainsi, chaque fois que x et y nomment des nombres, «la somme de x et y» nomme également un nombre, et de même pour d'autres types de fonctions et d'arguments.

Pour permettre l'expression de fonctions en LPC, il peut être ajouté:

• c.Une ou plusieurs variables de fonction (disons, f, g,

  ) ou une ou plusieurs constantes de fonction (par exemple, F, G,

  ) ou les deux, chacun d'un certain degré spécifié. Les premiers sont interprétés comme s'étendant sur les fonctions des degrés spécifiés et les seconds comme désignant des fonctions spécifiques de ce degré.

Lorsqu'un ou tous les a – c sont ajoutés au LPC, les règles de formation répertoriées dans le premier paragraphe de la section sur le calcul du prédicat inférieur (voir ci-dessus Le calcul du prédicat inférieur) doivent être modifiées pour permettre l'incorporation des nouveaux symboles dans wffs. Cela peut être fait comme suit: un terme est d'abord défini comme (1) une variable individuelle ou (2) une constante individuelle ou (3) toute expression formée en préfixant une variable de fonction ou une constante de fonction de degré n à n termes quelconques (ces termes - les arguments du symbole de fonction - sont généralement séparés par des virgules et placés entre parenthèses). La règle de formation 1 est alors remplacée par:

• 1 '. Une expression constituée d'une variable de prédicat ou d'une constante de prédicat de degré n suivie de n termes est un wff.

La base axiomatique donnée dans la section sur l'axiomatisation du LPC (voir ci-dessus Axiomatisation du LPC) nécessite également la modification suivante: dans le schéma d'axiome 2, tout terme est autorisé à remplacer un lorsque β est formé, à condition qu'aucune variable libre dans le terme devient lié dans β. Les exemples suivants illustreront l'utilisation des ajouts susmentionnés au LPC: que les valeurs des variables individuelles soient les nombres naturels; que les constantes individuelles a et b représentent respectivement les nombres 2 et 3; soit A signifie «est premier»; et que F représente la fonction dyadique «la somme de». Alors AF (a, b) exprime la proposition «La somme de 2 et 3 est premier» et (∃x) AF (x, a) exprime la proposition «Il existe un nombre tel que la somme de lui et 2 est premier."

L'introduction de constantes s'accompagne normalement de l'ajout à la base axiomatique d'axiomes spéciaux contenant ces constantes, conçus pour exprimer des principes qui détiennent les objets, les propriétés, les relations ou les fonctions qu'ils représentent - bien qu'ils ne contiennent pas d'objets, de propriétés, relations ou fonctions en général. On peut décider, par exemple, d'utiliser la constante A pour représenter la relation dyadique «est supérieur à» (de sorte que Axy signifie «x est supérieur à y» et ainsi de suite). Cette relation, contrairement à beaucoup d'autres, est transitive; c'est-à-dire, si un objet est supérieur à un second et que le second est à son tour supérieur au troisième, alors le premier est supérieur au troisième. Par conséquent, le schéma d'axiome spécial suivant pourrait être ajouté: si t ₁, t ₂ et t ₃ sont des termes, alors (à ₁ t ₂ · à ₂ t ₃) ⊃ à ₁ t ₃ est un axiome. De tels moyens peuvent être construits pour exprimer les structures logiques de diverses disciplines particulières. Le domaine dans lequel la plupart des travaux de ce type ont été effectués est celui de l'arithmétique des nombres naturels.

PC et LPC sont parfois combinés en un seul système. Cela peut être fait le plus simplement en ajoutant des variables propositionnelles à la liste des primitives LPC, en ajoutant une règle de formation à l'effet qu'une variable propositionnelle autonome est un wff et en supprimant «LPC» dans le schéma d'axiome 1. Cela donne en wffs de telles expressions comme (p ∨ q) ⊃ (∀x) ϕx et (∃x) [p ⊃ (∀y) ϕxy].

• 3.PCL avec identité. Le mot «est» n'est pas toujours utilisé de la même manière. Dans une proposition telle que (1) «Socrate a le nez retroussé», l'expression précédant le «est» désigne un individu et l'expression qui le suit représente une propriété attribuée à cet individu. Mais, dans une proposition telle que (2) «Socrate est le philosophe athénien qui a bu la pruche», les expressions précédant et suivant le «est» désignent toutes deux des individus, et le sens de la proposition globale est que l'individu nommé par le premier est le même individu que l'individu nommé par le second. Ainsi, en 2, «est» peut être étendu à «est le même individu que», tandis qu'en 1, il ne peut pas. Tel qu'utilisé en 2, «est» représente une relation dyadique - à savoir, l'identité - que la proposition affirme maintenir entre les deux individus. Une proposition d'identité doit être comprise dans ce contexte comme n'affirmant rien de plus que cela; en particulier, elle ne doit pas être considérée comme affirmant que les deux expressions de dénomination ont la même signification. Un exemple très discuté pour illustrer ce dernier point est «L'étoile du matin est l'étoile du soir». Il est faux que les expressions «l'étoile du matin» et «l'étoile du soir» signifient la même chose, mais il est vrai que l'objet auquel se réfère la première est le même que celui auquel se réfère la seconde (la planète Vénus).

Pour permettre l'expression des formes des propositions d'identité, une constante de prédicat dyadique est ajoutée au LPC, pour laquelle la notation la plus courante est = (écrite entre, plutôt qu'avant, ses arguments). L'interprétation voulue de x = y est que x est le même individu que y, et la lecture la plus pratique est «x est identique à y». Sa négation ∼ (x = y) est communément abrégée en x ≠ y. À la définition d'un modèle LPC donnée précédemment (voir ci-dessus Validité dans LPC), il est maintenant ajouté la règle (qui s'accorde de manière évidente avec l'interprétation voulue) que la valeur de x = y doit être 1 si le même membre de D est affecté à la fois à x et à y et sinon sa valeur doit être 0; la validité peut alors être définie comme précédemment. Les ajouts suivants (ou certains équivalents) sont apportés à la base axiomatique pour LPC: l'axiome x = x et le schéma de l'axiome qui, où a et b sont des variables individuelles et α et β sont des wffs qui ne diffèrent que par cela, à un ou plusieurs endroits où α a une occurrence libre de a, β a une occurrence libre de b, (a = b) ⊃ (α ⊃ β) est un axiome. Un tel système est connu sous le nom de calcul à prédicat inférieur avec identité; il peut bien sûr être encore augmenté des autres manières mentionnées ci-dessus dans "Extensions de LPC", auquel cas tout terme peut être un argument de =.

L'identité est une relation d'équivalence; c'est-à-dire qu'il est réflexif, symétrique et transitif. Sa réflexivité est directement exprimée dans l'axiome x = x, et les théorèmes exprimant sa symétrie et sa transitivité peuvent facilement être dérivés de la base donnée.

Certains wffs de LPC avec identité expriment des propositions sur le nombre de choses qui possèdent une propriété donnée. «Au moins une chose est ϕ» pourrait bien sûr déjà être exprimé par (∃x) ϕx; «Au moins deux choses distinctes (non identiques) sont ϕ» peuvent maintenant être exprimées par (∃x) (∃y) (ϕx · ϕy · x ≠ y); et la séquence peut être poursuivie de manière évidente. «Au plus une chose est ϕ» (c.-à-d. «Il n'y a pas deux choses distinctes toutes les deux ϕ») peut être exprimée par la négation du dernier wff mentionné ou par son équivalent, (∀x) (∀y) [(ϕx · ϕy) ⊃ x = y], et la séquence peut de nouveau être facilement poursuivie. Une formule pour «exactement une chose est is» peut être obtenue en joignant les formules pour «au moins une chose est ϕ» et «au plus une chose est ϕ», mais un wff plus simple équivalent à cette conjonction est (∃x) [ϕx · (∀y) (ϕy ⊃ x = y)], ce qui signifie "Il y a quelque chose qui est ϕ, et tout ce qui est ϕ est cette chose." La proposition «Exactement deux choses sont ϕ» peut être représentée par (∃x) (∃y) {ϕx · ϕy · x ≠ y · (∀z) [ϕz ⊃ (z = x ∨ z = y)]}; c'est-à-dire, "Il y a deux choses non identiques dont chacune est ϕ, et tout ce qui est ϕ est l'une ou l'autre de celles-ci." De toute évidence, cette séquence peut également être étendue pour donner une formule pour «Exactement n choses sont ϕ» pour chaque nombre naturel n. Il est pratique d'abréger le wff pour «Exactly one thing is ϕ» to (∃! X) ϕx. Ce quantificateur spécial est fréquemment lu à haute voix comme «E-Shriek x».

Descriptions précises

Lorsqu'une certaine propriété ϕ appartient à un et un seul objet, il est pratique d'avoir une expression qui nomme cet objet. Une notation courante à cet effet est (ιx) ϕx, qui peut être lue comme «la chose qui est ϕ» ou plus brièvement comme «le ϕ». En général, où a est une variable individuelle et α est un wff, (ιa) α représente alors la valeur unique de a qui rend α vrai. Une expression de la forme «tel ou tel» est appelée une description définie; et (ιx), connu sous le nom d'opérateur de description, peut être considéré comme formant le nom d'un individu à partir d'une forme de proposition. (ιx) est analogue à un quantificateur en ce que, lorsqu'il est préfixé à un wff α, il lie chaque occurrence libre de x dans α. Le recalibrage des variables liées est également autorisé; dans le cas le plus simple, (ιx) ϕx et (ιy) ϕy peuvent chacun être lus simplement comme «le ϕ».

En ce qui concerne les règles de formation, des descriptions définitives peuvent être incorporées dans le LPC en laissant les expressions de la forme (ιa) α compter comme des termes; la règle 1 'ci-dessus, dans "Extensions de LPC", leur permettra alors de se produire dans les formules atomiques (y compris les formules d'identité). «Le ϕ est (c'est-à-dire qu'il a la propriété) ψ» peut alors être exprimé par ψ (ιx) ϕx; «Y est (le même individu que) le ϕ» comme y = (ιx) ϕx; «Le ϕ est (le même individu que) le ψ» comme (ιx) ϕx = (ιy) ψy; et ainsi de suite.

L'analyse correcte des propositions contenant des descriptions précises a fait l'objet d'une controverse philosophique considérable. Cependant, un récit largement accepté - essentiellement celui présenté dans Principia Mathematica et connu sous le nom de théorie des descriptions de Russell - soutient que «Le ϕ est ψ» doit être compris comme signifiant qu'exactement une chose est ϕ et que cette chose est également ψ. Dans ce cas, il peut être exprimé par un wff de LPC-avec-identité qui ne contient aucun opérateur de description, à savoir, (1) (∃x) [ϕx · (∀y) (ϕy ⊃ x = y) · ψx]. De façon analogue, «y est le ϕ» est analysé comme «y est ϕ et rien d'autre n'est ϕ» et donc comme exprimable par (2) ϕy · (∀x) (ϕx ⊃ x = y). "Le ϕ est le ψ" est analysé comme "Exactement une chose est ϕ, exactement une chose est ψ, et tout ce qui est ϕ est ψ" et donc comme exprimable par (3) (∃x) [ϕx · (∀y) (ϕy ⊃ x = y)] · (∃x) [ψx · (∀y) (ψy ⊃ x = y)] · (∀x) (ϕx ⊃ ψx). ψ (ιx) ϕx, y = (ιx) ϕx et (ιx) ϕx = (ιy) ψy peuvent alors être considérés comme des abréviations pour (1), (2) et (3), respectivement; et en généralisant à des cas plus complexes, tous les wff qui contiennent des opérateurs de description peuvent être considérés comme des abréviations pour des wff plus longs qui n'en contiennent pas.

L'analyse qui mène à (1) comme formule pour «Le ϕ est ψ» conduit à ce qui suit pour «Le ϕ n'est pas ψ»: (4) (∃x) [ϕx · (∀y) (ϕy ⊃ x = y) · ∼ψx]. Il est important de noter que (4) n'est pas la négation de (1); cette négation est, au contraire, (5) ∼ (∃x) [ϕx · (∀y) (ϕy ⊃ x = y) · ψx]. La différence de signification entre (4) et (5) réside dans le fait que (4) n'est vrai que lorsqu'il y a exactement une chose qui est ϕ et que cette chose n'est pas ψ, mais (5) est vrai à la fois dans ce cas et aussi quand rien n'est ϕ du tout et quand plus d'une chose est ϕ. La négligence de la distinction entre (4) et (5) peut entraîner une grave confusion de pensée; dans le langage ordinaire, il est souvent difficile de savoir si quelqu'un qui nie que le ϕ est ψ concède que exactement une chose est ϕ mais nie que c'est ψ, ou nie que exactement une chose est ϕ.

La thèse fondamentale de la théorie des descriptions de Russell est qu'une proposition contenant une description définie ne doit pas être considérée comme une assertion sur un objet dont cette description est un nom, mais plutôt comme une affirmation quantifiée existentiellement qu'une certaine propriété (plutôt complexe) a une instance. Formellement, cela se reflète dans les règles d'élimination des opérateurs de description décrites ci-dessus.