Fonctionnalité (logique)

Cet article est une ébauche concernant la logique.

La fonctionnalité est la propriété d'une sémantique formelle polyvalente selon laquelle la valeur d'une formule logique dépend exclusivement de la valeur de vérité des formules qui la composent et de la façon dont elles sont composées^[1]. Lorsque cette propriété est vérifiée, on appelle une telle sémantique fonctionnelle ou truth-functional (« vérifonctionnelle^[1] »).

En d'autres termes, dans une sémantique polyvalente avec V pour ensemble de valeurs, la fonctionnalité permet de traiter chaque opération logique n-aire comme une fonction de Vⁿ dans V. Ces fonctions sont parfois appelées tables de vérité ou fonctions de vérité.

Conséquence sémantique et valeurs désignées

Une propriété de désignation est une propriété qui s'hérite des prémisses vers le conséquent : si toutes les prémisses sont désignées, alors le conséquent est désigné à son tour. Ce critère de désignation peut être celui de la vérité^[2].

Dans une sémantique fonctionnelle 𝒮, avec V_𝒮 pour ensemble de valeurs, on définit alors V_𝒮⁺ un sous-ensemble de valeurs désignées, on peut ainsi définir la conséquence sémantique comme suit : pour toutes formules logiques p₁, ..., p_n et q, les deux affirmations suivantes sont équivalentes^[3] : - que pour toute assignation de valeurs dans V_𝒮 à chaque variable propositionnelle, soit q a une valeur désignée, c'est-à-dire dans V_𝒮⁺, soit il y a une des prémisses de p₁ à p_n qui n'est pas désignée, c'est-à-dire dans V\V_𝒮⁺, soit les deux ;

- que p₁, ..., p_n ⊨_𝒮 q, c'est-à-dire que q est une conséquence de p₁, ..., p_n dans la sémantique 𝒮.

Par exemple, la logique classique est équivalente à une sémantique fonctionnelle bivalente B2, telle que V_B2={0;1} et V_B2⁺={1}. Les seules opérations logiques dans B2 sont la conjonction (∧), la disjonction (∨) et la négation (¬).

$\land$	0	1
0	0	0
1	0	1

$\lor$	0	1
0	0	1
1	1	1

$p$	$\neg p$
0	1
1	0

Nous pouvons ainsi vérifier que $\{p\lor q,\neg q\}\vDash _{\rm {B2}}p$ en vérifiant chaque assignation possible des variables propositionnelles p et q :

Variables		Prémisses		Conséquent	Contre-modèle ?
p	q	$p\lor q$	$\neg q$	$p$	Contre-modèle ?
0	0	0	1	1	Non : la prémisse $p\lor q$ n'est pas désignée.
0	1	1	0	0	Non : la prémisse $\neg q$ n'est pas désignée.
1	0	1	1	1	Non : le conséquent est désigné.
1	1	1	0	1	Non : le conséquent est désignée et la prémisse $\neg q$ n'est pas désignée.
Conclusion					Pas de contre-modèle, la conséquence est donc valide.

De fait, la conséquence sémantique est l'analogue pour la sémantique fonctionnelle des tests d'hypothèses statistiques pour la méthode hypothético-déductive, en cela que l'on montre que rien ne permet de rejeter la règle, plutôt qu'une forme plus directe, positive ou langagière de conséquence qui consisterait à chercher ce qui permettrait de prouver la règle à l'instar de la conséquence syntaxique.

Correction et complétude

En s'assurant qu'une sémantique fonctionnelle 𝒮 est soumise aux mêmes règles qu'une théorie démonstrative 𝒯 donnée, 𝒮 devient une sémantique dite saine ou correcte pour 𝒯, ce qui signifie que $p_{1},\ldots ,p_{n}\vdash _{\mathcal {T}}p$ implique $\{p_{1},\ldots ,p_{n}\}\vDash _{\mathcal {S}},$ à traduction près. Celles-ci peuvent être trouvées en soumettant un nombre fini de valeurs et d'opérations internes sur ces valeurs aux mêmes règles logiques que le système dont on cherche à trouver une sémantique saine, que ce soit à la main, par le biais d'un solveur de problème SAT automatique ou autre assistant de preuve.

Si la réciproque est vraie, à savoir que $\{p_{1},\ldots ,p_{n}\}\vDash _{\mathcal {S}}$ implique $p_{1},\ldots ,p_{n}\vdash _{\mathcal {T}}p,$ à traduction près, on dit alors que 𝒮 est une sémantique complète pour 𝒯. Une sémantique 𝒮 complète et saine pour 𝒯 fait qu'à traduction près, $\vDash _{\mathcal {S}}$ et $\vdash _{\mathcal {T}}$ décrivent la même relation de conséquence, ce sont des logiques équivalentes.

Intérêts

Beaucoup de propriétés du métalangage sont difficilement obtenables par la seule théorie de la démonstration d'une logique donnée. Dans les sémantiques fonctionnelles, cependant, chaque interprétation des variables propositionnelles conduit chaque valeur à agir comme une classe d'équivalence sur les formules construites à partir desdites variables. Ainsi, lorsqu'une sémantique fonctionnelle a un nombre fini de valeurs, la plupart des propriétés de sa relation de conséquence peuvent être vérifiées en explorant un nombre fini de cas.

Sémantiques correctes

Non-trivialité, non-théorèmes, non-règles

Une théorie démonstrative permet de déterminer quelles règles sont dérivables à partir des règles de base, mais plus difficilement ce qui n'est pas dérivable, c'est-à-dire les non-règles. Pour cela, on passe par des modèles sémantiques sains pour cette logique.

Une sémantique fonctionnelle 𝒮 est triviale si V=V⁺, c'est-à-dire qui n'a aucune valeur non-désignée, sinon elle est non-triviale.

S'il existe une sémantique fonctionnelle non-triviale 𝒮 saine pour 𝒯, alors $\{\}\not \vDash _{\mathcal {S}}p$ puisqu'on peut assigner à p une valeur non-désignée grâce à la non-trivialité de 𝒮.

Plus généralement, pour toute sémantique fonctionnelle 𝒮, si $\{p_{1},\ldots ,p_{n}\}\not \vDash _{\mathcal {S}}q$ et 𝒮 est saine pour 𝒯, alors $p_{1},\ldots ,p_{n}\not \vdash _{\mathcal {T}}q$ à traduction près. Cela permet en particulier de déceler des non-théorèmes et des non-règles de 𝒯 à partir d'une sémantique fonctionnelle qui lui est saine.

Pour reprendre notre sémantique B2 pour la logique classique, nous pouvons montrer $\{p\lor q\}\not \vDash _{\rm {B2}}\neg (p\lor \neg q),$ ce qui conduit à la non-règle $p\lor q\not \vdash \neg (p\lor \neg q)$ en logique classique.

Variables		Prémisse	Conséquent	Contre-modèle ?
p	q	$p\lor q$	$\neg (p\lor \neg q)$	Contre-modèle ?
0	0	0	0	Non : la prémisse n'est pas désignée.
0	1	1	1	Non : le conséquent est désigné.
1	0	1	0	Oui : la prémisse est désignée tandis que le conséquent n'est pas désigné.
Conclusion				Il existe un contre-modèle, la conséquence n'est pas valide.

Inexistence de théorèmes

Il est également possible de déterminer si une théorie démonstrative 𝒯 n'admet aucun théorème à partir d'une sémantique fonctionnelle 𝒮 saine pour 𝒯. Pour cela, il suffit de trouver un ensemble α qui vérifient les propriétés suivantes : - α est un sous-ensemble non-vide de V\V⁺, étant donc composé uniquement de valeurs non-désignées.

- α est un ensemble stable par toutes les opérations logiques.

- S'il existe des constantes logiques dans 𝒮, par exemple ⊥, celles-ci ont toute une valeur dans α.

Prenons le cas de la logique FDE^[4]^,^[5]. En tant que sémantique fonctionnelle, ses seules opérations logiques sont la conjonction, la disjonction et la négation, tandis que $V_{\rm {FDE}}=\{{\textsf {true,both,neither,false}}\}$ et $V_{\rm {FDE}}^{+}=\{{\textsf {true,both}}\}.$

$\land$	true	both	neither	false
true	true	both	neither	false
both	both	both	false	false
neither	neither	false	neither	false
false	false	false	false	false

$\lor$	true	both	neither	false
true	true	true	true	true
both	true	both	true	both
neither	true	true	neither	neither
false	true	both	neither	false

$p$	$\neg p$
true	false
both	both
neither	neither
false	true

Ici, notre ensemble α témoin n'est autre que le singleton {neither}. En effet, neither est une valeur non-désignée, fixe par toutes les opérations logiques :

${\begin{array}{rcl}{\textsf {neither}}&=&{\textsf {neither}}\land {\textsf {neither}}\\&=&{\textsf {neither}}\lor {\textsf {neither}}\\&=&\neg {\textsf {neither}}\end{array}}$

Cela permet de démontrer que la logique FDE n'admet aucun théorème.

Paracohérence

Soit 𝒯 une théorie démonstrative. On dit que 𝒯 est une logique paracohérente si elle n'admet pas le principe d'explosion, c'est-à-dire que $p,\neg p\not \vdash _{\mathcal {T}}q.$

Pour démontrer que 𝒯 est paracohérente, il suffit de trouver une sémantique 𝒮 saine pour 𝒯 qui vérifie ces deux propriétés : - 𝒮 est une sémantique non-triviale, c'est-à-dire que V_𝒮\V_𝒮⁺ est non-vide.

- 𝒮 admet au moins une valeur glut (« surplus »), c'est-à-dire qu'il existe une valeur $v\in V$ telle que v est désignée et que ¬v est désignée aussi.

En effet, $\{p,\neg p\}\not \vdash _{\mathcal {S}}q$ car on obtient un contre-modèle en donnant à p une valeur surplus, de sorte que les deux prémisses soient désignées, et à q une valeur non-désignée, de sorte que le conséquent ne soit pas désigné.

Là aussi, nous pouvons vérifier la paracohérence de FDE à partir de ce seul critère. D'une part, cette sémantique est non-triviale, puisqu'elle admet pour valeurs non-désignées les valeurs neither et false. D'autre part, la valeur both est une valeur surplus égale à sa propre négation logique, ce qui fait que both est une valeur surplus. Les critères étant réunis, nous avons donc $\{p,\neg p\}\not \vDash _{\rm {FDE}}q,$ avec pour contre-modèles ceux qui assignent à p la valeur both et à q soit la valeur neither, soit la valeur false.

Propriété de partage des variables

Article détaillé : Logique pertinente.

Une logique propositionnelle pertinente 𝒯 doit, en plus de rejeter le syllogisme disjonctif, satisfaire la propriété de partage de variables : si $\vdash _{\mathcal {T}}p\to q$ , alors p et q partagent au moins une variable propositionnelle commune.

Le critère de vérification de cette propriété, à partir d'une sémantique fonctionnelle saine pour 𝒯, est détaillé dans l'article sur la logique pertinente.

Sémantiques complètes

Dans une théorie démonstrative 𝒯, démontrer un séquent $\Gamma \vdash _{\mathcal {T}}p$ peut s'avérer complexe. Dans certains cas, les règles d'introduction et d'élimination permettent d'abduire les raisonnements à mobiliser au vu de la forme des formules.

Prenons l'exemple du séquent $\vdash ((p\to q)\land \neg q)\to \neg p$ en logique intuitionniste, avec les règles d'introduction et d'élimination pour la conjonction, pour la disjonction, pour la négation (avec le syllogisme disjonctif comme règle d'élimination) et pour l'implication, ainsi que toutes les règles d'identité et règles structurelles usuelles.

Démonstration

L'opération principal est l'implication, ce qui pousse à se dire qu'on va utiliser la règle d'introduction de l'implication pour conclure la preuve.

${\begin{array}{llr}\vdots &\vdots &\vdots \\n&(p\to q)\land \neg q\vdash \neg p&\cdots \\\blacksquare &\vdash ((p\to q)\land \neg q)\to \neg p&{\to }_{i}(n)\end{array}}$

À l'étape n, nous aurons donc à prouver une négation, ce qui signifie qu'il faudra utiliser la règle d'introduction de la négation. Ainsi, il faudra trouver une formule $\varphi$ qui permette d'avoir une preuve de la sorte :

${\begin{array}{llr}\vdots &\vdots &\vdots \\l&(p\to q)\land \neg q,p\vdash \varphi &\cdots \\\vdots &\vdots &\vdots \\m&(p\to q)\land \neg q,p\vdash \neg \varphi &\cdots \\\vdots &\vdots &\vdots \\n&(p\to q)\land \neg q\vdash \neg p&{\neg }_{i}(l,m)\\\vdots &\vdots &\vdots \\\blacksquare &\vdash ((p\to q)\land \neg q)\to \neg p&{\to }_{i}(n)\end{array}}$

Intéressons-nous aux prémisses de l et m. Nous pouvons abduire qu'il faudra utiliser les deux prémisses. Pour ce faire, nous aurons d'abord besoin d'appliquer la règle d'axiome avec ces deux formules au début de la preuve.

${\begin{array}{llr}1&(p\to q)\land \neg q\vdash (p\to q)\land \neg q&ax\\2&p\vdash p&ax\\\vdots &\vdots &\vdots \\l&(p\to q)\land \neg q,p\vdash \varphi &\cdots \\\vdots &\vdots &\vdots \\m&(p\to q)\land \neg q,p\vdash \neg \varphi &\cdots \\\vdots &\vdots &\vdots \\n&(p\to q)\land \neg q\vdash \neg p&{\neg }_{i}(l,m)\\\vdots &\vdots &\vdots \\\blacksquare &\vdash ((p\to q)\land \neg q)\to \neg p&{\to }_{i}(n)\end{array}}$

Dans la ligne 1, l'opération principale est celle de la conjonction. Nous allons appliquer les règles d'élimination de la conjonction, pour pouvoir l'utiliser dans la preuve.

${\begin{array}{llr}1&(p\to q)\land \neg q\vdash (p\to q)\land \neg q&ax\\2&p\vdash p&ax\\3&(p\to q)\land \neg q\vdash p\to q&{\land }_{e}^{g}(1)\\4&(p\to q)\land \neg q\vdash \neg q&{\land }_{e}^{d}(1)\\\vdots &\vdots &\vdots \\l&(p\to q)\land \neg q,p\vdash \varphi &\cdots \\\vdots &\vdots &\vdots \\m&(p\to q)\land \neg q,p\vdash \neg \varphi &\cdots \\\vdots &\vdots &\vdots \\n&(p\to q)\land \neg q\vdash \neg p&{\neg }_{i}(l,m)\\\vdots &\vdots &\vdots \\\blacksquare &\vdash ((p\to q)\land \neg q)\to \neg p&{\to }_{i}(n)\end{array}}$

Pour utiliser l'implication dans le conséquent de la ligne 3, il nous faut utiliser un modus ponens avec un autre séquent qui prouve p. La ligne 2 permet cela.

${\begin{array}{llr}1&(p\to q)\land \neg q\vdash (p\to q)\land \neg q&ax\\2&p\vdash p&ax\\3&(p\to q)\land \neg q\vdash p\to q&{\land }_{e}^{g}(1)\\4&(p\to q)\land \neg q\vdash \neg q&{\land }_{e}^{d}(1)\\5&(p\to q)\land \neg q,p\vdash q&{\to }_{e}(3,2)\\\vdots &\vdots &\vdots \\l&(p\to q)\land \neg q,p\vdash \varphi &\cdots \\\vdots &\vdots &\vdots \\m&(p\to q)\land \neg q,p\vdash \neg \varphi &\cdots \\\vdots &\vdots &\vdots \\n&(p\to q)\land \neg q\vdash \neg p&{\neg }_{i}(l,m)\\\vdots &\vdots &\vdots \\\blacksquare &\vdash ((p\to q)\land \neg q)\to \neg p&{\to }_{i}(n)\end{array}}$

Nous retrouvons, ligne 5, les deux prémisses de la ligne l. Nous pouvons également utiliser la règle d'affaiblissement sur la ligne 4 pour obtenir les mêmes prémisses, mais dont le conséquent est la négation-même de celui de la ligne 5, ce qui permet de conclure la preuve avec ${\displaystyle \phi$

${\begin{array}{llr}1&(p\to q)\land \neg q\vdash (p\to q)\land \neg q&ax\\2&p\vdash p&ax\\3&(p\to q)\land \neg q\vdash p\to q&{\land }_{e}^{g}(1)\\4&(p\to q)\land \neg q\vdash \neg q&{\land }_{e}^{d}(1)\\5&(p\to q)\land \neg q,p\vdash q&{\to }_{e}(3,2)\\6&(p\to q)\land \neg q,p\vdash \neg q&{\textit {aff}}(4)\\7&(p\to q)\land \neg q\vdash \neg p&{\neg }_{i}(5,6)\\\blacksquare &\vdash ((p\to q)\land \neg q)\to \neg p&{\to }_{i}(7)\end{array}}$

Cependant, une logique n'ayant pas de telles règles rend la démonstration de séquents potentiellement plus complexe.

L'intérêt majeur d'une sémantique fonctionnelle complète pour 𝒮 est donc la réduction drastique de la complexité algorithmique et la non-nécessité de trouver une preuve syntaxique d'un séquent pour s'assurer de sa démontrabilité.

Au-delà de la fonctionnalité

Tables non-déterministes

Certaines sémantiques polyvalentes non-fonctionnelles ont été développées. Nous pouvons notamment citer le cas des sémantiques à tables non-déterministes, ce qui fait que les opérations logiques ne sont plus tant des fonctions que des relations. La conséquence sémantique dans ces sémantiques non-déterministes consiste à vérifier toutes les assignations de formules possibles à partir de ces lois d'assignations, en procédant par disjonction de cas. Une telle sémantique pourrait ressembler à ça :

$\land$	T	F
T	T	F
F	F	F

$\lor$	T	F
T	T	T
F	T	F

$\to$	T	F
T	T ou F	F
F	T ou F	T ou F

$p$	$\neg p$
T	F
F	T ou F

On peut par exemple tester le modus ponens dans cette sémantique.

Variables		Prémisses		Conséquent	Contre-modèle ?
p	q	p→q	p	q	Contre-modèle ?
T	T	T	T	T	Non : le conséquent q est désigné.
	T	F	T	T	Non : la prémisse p→q n'est pas désignée, le conséquent q est désigné.
	F	F	T	F	Non : la prémisse p→q n'est pas désignée.
F	T	T	F	T	Non : la prémisse p n'est pas désignée, le conséquent q est désigné.
	T	F	F	T	Non : les prémisses p→q et p ne sont pas désignées, le conséquent q est désigné.
	F	T	F	F	Non : la prémisse p n'est pas désignée.
	F	F	F	F	Non : les prémisses p→q et p ne sont pas désignées.
Conclusion					Pas de contre-modèle, la conséquence est donc valide.

Non-déterminisme restreint

Dans certains cas, ces sémantiques non-déterministes utilisent des restrictions. Un exemple majeur est la sémantique trivalente non-déterministe saine et complète pour la logique intuitionniste, donné par l'ensemble de valeurs $V=\{{\textsf {T,U,F}}\},$ l'ensemble de valeurs désignées $V^{+}=\{{\textsf {T}}\}$ et pour tables non-déterministes les suivantes, puis en imposant diverses restrictions développés dans le papier dans Leme et al. (2025)^[6] :

$\land$	T	U	F
T	T	F	F
U	F	F	F
F	F	F	F

$\lor$	T	U	F
T	T	T	T
U	T	F	F
F	T	F	F

$\to$	T	U	F
T	T	F	F
U	T	U ou T	U ou T
F	T	U ou T	U ou T

$p$	$\neg p$
T	F
U	U ou T
F	U ou T

Modèles structurels et algébriques

Différents systèmes logiques peuvent être modélisés en tant que structures algébriques ou au moins structurels. C'est notamment le cas de la logique classique avec les algèbres de Boole, de la logique intuitionniste avec les algèbres de Heyting, de la logique pertinente R avec les monoïdes de De Morgan ou encore en logique quasi-pertinente R-mingle (ou RM) avec les modèles de Sugihara.

Toutefois, bien que ces structures ne sont pas des sémantiques fonctionnelles à elles seules, celles-ci le deviennent généralement lorsqu'on définit ce qu'est une interprétation sémantique de formules dans ces modèles.

Logique du premier ordre et théorie des modèles

Article détaillé : Théorie des modèles.

La sémantique des logiques du premier ordre ne sont pas fonctionnelles à proprement parler, principalement à cause des quantificateurs, des prédicats et des variables algébriques. Les sémantiques de telles logiques sont étudiées en théorie des modèles.

Modèles de Kripke

Article détaillé : Sémantique de Kripke.

En logique modale, en logique intuitionniste et dans quelques autres logiques (e.g. logique de Gödel-Dummett (en)), les sémantiques peuvent se faire à l'aide de mondes possibles à partir de modèles de Kripke.

Modèles de Routley-Meyer

Article détaillé : Logique pertinente.

Les modèles de Routley-Meyer sont principalement utilisés pour donner des sémantiques à diverses logiques pertinentes. Contrairement aux sémantiques non-fonctionnelles mentionnées jusqu'ici, les modèles de Routley-Meyer tournent autour d'une relation ternaire plutôt qu'une relation binaire.

Articles connexes

- Logique polyvalente

- Table de vérité

- Déduction naturelle

Notes et références

1 2 Mikael Cozic, « Logique propositionnelle, 1 (Logique séance 2) », 2009-2010.
↑ (en) Siegfried Gottwald, « Many-Valued Logic », sur Stanford Encyclopedia of Philosophy, 2000.
↑ (en) Yaroslav Shramko et Heinrich Wansing, « Truth Values », sur Stanford Encyclopedia of Philosophy, 2010.
↑ (en) J. Michael Dunn, « Intuitive semantics for first-degree entailments and ‘coupled trees’ », Philosophical Studies, vol. 29,‎ 1976, p. 149-168 (DOI 10.1007/BF00373152)
↑ (en) Nuel D. Belnap Jr., « A Useful Four-Valued Logic », Modern Uses of Multiple-Valued Logic, éds. J. Michael Dunn & George Epstein, Episteme, vol. 2,‎ 1977, p. 5-37 (DOI 10.1007/978-94-010-1161-7_2)
↑ (en) Renato R. Leme, Marcelo E. Coniglio et Bruno Lopes, « A new decision method for Intuitionistic Logic by 3-valued non-deterministic truth-tables », Journal of Symbolic Logic,‎ 17 décembre 2025 (DOI 10.1017/jsl.2025.10174).

Portail de la logique

[cozic0910-1] 1 2 Mikael Cozic, « Logique propositionnelle, 1 (Logique séance 2) », 2009-2010.

[2] (en) Siegfried Gottwald, « Many-Valued Logic », sur Stanford Encyclopedia of Philosophy, 2000.

[3] (en) Yaroslav Shramko et Heinrich Wansing, « Truth Values », sur Stanford Encyclopedia of Philosophy, 2010.

[4] (en) J. Michael Dunn, « Intuitive semantics for first-degree entailments and ‘coupled trees’ », Philosophical Studies, vol. 29,‎ 1976, p. 149-168 (DOI 10.1007/BF00373152)

[5] (en) Nuel D. Belnap Jr., « A Useful Four-Valued Logic », Modern Uses of Multiple-Valued Logic, éds. J. Michael Dunn & George Epstein, Episteme, vol. 2,‎ 1977, p. 5-37 (DOI 10.1007/978-94-010-1161-7_2)

[6] (en) Renato R. Leme, Marcelo E. Coniglio et Bruno Lopes, « A new decision method for Intuitionistic Logic by 3-valued non-deterministic truth-tables », Journal of Symbolic Logic,‎ 17 décembre 2025 (DOI 10.1017/jsl.2025.10174).

[1]

[2]

[3]

[4]

[5]

[6]