Toute logique formelle admet un langage formel et un ensemble de règles de déduction basée sur la syntaxe du langage que l'on appelle système de démonstration. Il existe plusieurs systèmes de démonstration possibles. Chaque système de démonstration correspond à une interprétation du langage. Syntaxe et sémantique sont ainsi liés.
Cependant il y a des choix rudimentaires sur l'interprétation que l'on peut faire en premier et qui se traduisent par les premières règles de déduction. Le premier choix qui est fait, est la définition des connecteurs logiques appliqués à des booléens, correspondant aux opérations booléennes. Cela permet de définir un ensemble de règles de déduction déterminant le calcul des équations booléennes, c'est à dire le calcul propositionnel.
La définition d'un langage commence par sa syntaxe, sans donner aucune interprétation sur les symbôles qu'elle utilise, et sans utiliser de variable. Le langage propositionnel est d'abord un langage d'opérateurs, c'est à dire une structure libre engendrée par des opérateurs dits générateurs que l'on regroupe dans sa présentation. Et on choisie comme présentation `L`, des opérateurs générateurs correspondant aux connecteurs logiques habiuels :
`L = {0,1,"¬(.)", "⇒(.,.)","⇔(.,.)","⇎(.,.)","et(.,.)","ou(.,.)"}`
L'ensemble de toutes les combinaisons closes de ces opérateurs, en excluant les compositions de taille infinie ou récurcives, forme le langage `ccL`
`ccL = "<"L">"`
Les crochets `"<"...">"` désigne la clôture par composition close des opérateurs ou ensemble d'opérateurs s'y trouvant. Sont exlcus les compositions de taille infinie ou récurcives. Les compositions ainsi produite constitue les termes du langage d'opérateurs `ccL`. Et cet ensemble constitue une structure libre.
`ccL = {0, 1, "¬"0, 0 "et" 1, 1"⇒"0, (0 "ou" "¬"1) "⇒" 1,...}`
Chaque terme possède une taille qui est définie égale au nombre d'opérateurs qu'il contient.
La constante `0` représente le faux. La constante `1` représente le vrai. L'opérateur `"¬(.)"` représente le connecteur de négation. L'opérateur `"⇒(.,.)"` représente le connecteur d'implication. L'opérateur `"⇔(.,.)"` représente le connecteur d'équivalence. L'opérateur `"⇎(.,.)"` représente le connecteur disjonction exclusive, L'opérateur `"et(.,.)"` représente le connecteur de conjonction, L'opérateur `"ou(.,.)"` représente le connecteur de disjonction :
`x` `y` `x "et" y` `x "ou" y` `x"⇒"y` `x"⇔"y` `x"⇎"y` 0 0 0 0 1 1 0 0 1 0 1 1 0 1 1 0 0 1 0 0 1 1 1 1 1 1 1 0
Avec cette interprétation, chaque terme du langage `ccL` s'évalue en une valeur booléenne. Les termes s'appellent des propositions sans inconnu. Le langage s'appelle le langage propositionel sans inconnu.
On ajoute au langage d'opérateur des opérateurs zéro-air supplémentaires `a,b,c` pour former le langage d'opérateurs `ccL[a,b,c] = "<"a,b,c,L">"`. Le langage d'opérateurs qui est une structure libre s'enrichie ainsi de nouveaux élémentd par le procédé d'extension élémentaire.
Puis on donne comme interprétation à ces éléments le rôle d'inconnu booléen, et on les appelles de variables. On obtient alors le langage propositionnel à trois inconnus `a,b,c`. Les termes sont appelés des propositions.
Considérons la proposition suivante :
`(a "ou" "¬"b) "⇒" b`
Les inconnues `a,b` sont booléens et donc possèdent `2` valeurs possibles, `0` ou `1`. La proposition peut être vérifiée en écrivant sa table de vérité c'est à dire en passant en revue toutes les valeurs possibles des variables `a,b`, et pour chacune d'elles, en évaluant la proposition :
Si la proposition est toujours vrai, alors elle est vérifiée et constitue une tautologie. Si la proposition est toujours fausse alors sa négation est vérifiée et elle constitue une antilogie. Si la proposition est vrai dans certain cas et est fausse dans certain autre cas, alors la proposition constitue une indécidée. Cela constitue les trois états possibles d'une proposition. Dans l'exemple, la proposition `(a "ou" "¬"b) "⇒" b` est une tautologie.
Une proposition `P` a donc trois valeurs possibles d'état que l'on note comme suit :
Les deux premières valeurs d'état coïncident aux valeurs booléennes. La troisième valeur d'état représentée par le symbole `?` n'est pas une valeur booléenne, mais désigne toujours une inconnue booléenne avec une information supplémentaire qui est que dans l'univers, il existe au moins un monde ou la variable vaut`1` et il existe au moins un monde où la vatiable vaut `0`.
On veut étendre le calcul booléen à cette valeur d'état. Que signifie une variable possédant cette valeur d'état ? Qu'est-ce qu'une variable indécidée ? Cela signifie que la variable doit être remplacée par une proposition indécidée. Or deux propositions indécidées peuvent être liées entres elles. Autrement dit, deux variables indécidés peuvent être liées entres elles. Et cela rend caduc nos efforts pour produire des règles logiques pertinentes que nous pourrions élaborer entre propositions possèdant des variables indécidées. Sauf si nous ajoutons une propriété déterminant le lien exacte entre ces variables indécidées. Et le premier lien qu'il convient de mettre en exergue et celui de ne pas en avoir, c'est à dire celui d'indépendance. Pour des variables inconnues mais indépendantes, des règles générales de calcul dit triléen peuvent être édictées.
Tout d'abord, deux propositions indécidées `P,Q` sont dites indépendantes si et seulement si pour chacune des alternatives `P "et" Q, P "et" "¬"Q, "¬"P "et" Q, "¬"P "et" "¬"Q`, il existe des mondes où elle se réalise. De même, `n` propositions indécidées `P_1,P_2,P_3,...P_n` sont dites indépendantes si et seulement si pour chacune des alternatives `sigma_1P_1 "et" sigma_2P_2 "et" ...sigma_nP_n` où `sigma_i` désigne soit l'identité ou soit la négation, il existe des mondes où elle se réalise.
On peut alors définir une troisième valeur logique désignée par le symbole `?` et dont les occurences correspondent par définition à autant de valeurs d'état indécidés indépendantes :
`x"⇔"y` `x"⇎"y`
Le choix de l'indépendance entre les valeurs indécidées se justifit par la liberté de construction. En effet une variable libre peut s'unifier à n'importe quelle proposition, et donc peut s'unifier à une nouvelle variable qui ouvre la constrution de nouvelles alternatives possibles indépendament des autres variables.
Les variables deviennent triléennes, le langage s'augmente de la constante `?`. Nous avons `(a"⇔"1)"⇔"a`, et il est impossible d'exprimer dans le langage la propostion `a"="1`. Pour cela il faut ajouter le connecteur d'égalité logique `"="` au langage. On ajoute par commodité également le connecteur unaire `?"(.)"` défini comme suit `?a"⇔"(a"="?)`.
Chaque situation possible constitue un monde. Considérons la table de vérité vue précédement :
Cette table de vérité évoque l'alternative de `4` mondes possibles. Et le nombre de possibilités double à chaque introduction d'un nouvel inconnu booléen. Si nous déclarons `n` inconnus booléens, c'est à dire `n` variables `(a_1,a_2,a_3,...,a_n)`, alors il y aura `2^n` mondes possibles. La table de vérité comprendra `2^n` lignes. L'ensemble des `2^n` mondes forment l'univers, et l'on parlera d'univers booléen de dimension `n`. Le langage de cet univers est le langage propositionnel étendu `ccL[a_1,a_2,a_3,...,a_n]`.
Un tel univers `Omega` est défini par une liste de `n` inconnus booléens. Ce qui se note :
`Omega = "Univers"(Omega_1,Omega_2,Omega_3,...,Omega_n)`
Un monde `m` est défini par une liste de `n` booléens :
`m=(m_1,m_2,m_3,...,m_n)`
Le monde est une instanciation de l'univers. Notez alors la différence de type entre booléen et inconnu booléen, entre valeur et variable. L'une est une valeur booléenne, l'autre est une mémoire contenant une valeur booléenne. Il conviendrait d'avoir une écriture distincte pour préciser ce type et éviter les ambiguitées.
Un monde `m` est une application de l'ensemble des variables vers les booléens, ce qui se note :
`m ∈ ({Omega_1,Omega_2,Omega_3,...,Omega_n}"→"{0,1})`
L'univers est l'ensemble des mondes :
`Omega = ({Omega_1,Omega_2,Omega_3,...,Omega_n}"→"{0,1})`
Et d'un autre point de vue, il constitue l'ensemble des variables. Car les variables possèdent par principe un nom les identifiant et ce nom admet un ordre canonique qui est l'ordre lexicographique :
`ccV(Omega) = {Omega_1,Omega_2,Omega_3,...,Omega_n}`
Dans chaque monde `m`, toutes des variables de l'univers étant de valeur logique connue, toute proposition `P` écrite dans le langage de l'univers s'évalue en un booléen. Et donc seulement deux cas peuvent se produire :
Soit `P` vaut `1` dans le monde `m`. Et on dit que `P` est vrai dans le monde `m`, ou encore, que `m` satisfait `P`, ou encore, que le monde `m` réalise `P`, ce qui se note :
`m"⊨"P`
`m"⊨"(P"="1)`
Soit `P` vaut `0` dans le monde `m`. Et on dit que `P` est faux dans le monde `m`, ou encore, que `m` satisfait `"¬"P`, ou encore, que le monde `m` réalise `"¬"P`, ce qui se note :
`m"⊨¬"P`
`m"⊨"(P"="0)`
Il est toujours possible d'ajouter une variable booléenne, doublant le nombre de mondes possibles, augmentant ainsi l'univers, faisant que les mondes évoqués antérieurement sont incomplets, ignore la valeur de cette variable. Il est donc judicieux de créer dés le départ, le concept de monde incomplet.
Un monde `m` est incomplet s'il ne connait pas les valeurs de toutes les variables de l'univers.
L'univers `Omega` peut être vue comme un ensemble de variable `ccV(Omega)`.
Un monde complet est décrit par un couple d'ensembles de variables `(A,B)` formant une partition de l'univers `ccV(Omega)`. Le premier ensemble `A` regroupe les variables vrais dans le monde, le second ensemble `B` regroupe les variables fausses dans le monde. Et comme `B` s'obtient par complément de `A` dans l'univers, on en déduit qu'un monde est déterminé par un sous-ensemble `A` de `ccV(Omega)`.
Un monde incomplet est décrit par un triplet d'ensembles de variables `(A,B,C)` formant une partition de l'univers `Omega`. Le premier ensemble `A` regroupe les variables vrais dans le monde, le second ensemble `B` regroupe les variables fausses dans le monde, et le troisime ensemble `C` regroupe les variables ignorées dans le monde. Et comme `C` s'obtient par complément de `AuuB` dans l'univers, on en déduit qu'un monde est déterminé par un couple `(A,B)` de sous-ensembles disjoints de `Omega`.
Considérons une variable booléenne `a` de l'univers, celle-ci constitue une proposition. On va agrandire le langage propositionnel pour incorporer une nouvelle proposition `a"="?` qui signifie que le monde, où la proposition est testé, ne connait pas la valeur de `a`. Et pour un monde quelconque complet ou incomplet `m`, nous aurons seulement trois cas possibles :
`m"⊨"(a"="1)`
`m"⊨"(a"="0)`
`m"⊨"(a"="?)`
Et nous avons :
`m"⊨"(a"="1)<=> m"⊨"a`
`m"⊨"(a"="0)<=> m"⊨¬"a`
`m"⊨"(a"="?)<=> (m"⊭"a) "et" (m"⊭¬"a)`
Avec une règle syntaxique de bas niveau qui nous indique que `m"⊭"a` signifie exactement `"¬"(m"⊨"a)`.
En procédant ainsi on introduit une troisième valeur logique `?` sans porter atteinte au système logique booléen initial et qui coïncide avec celle défini dans le chapitre précédent, puisque les variables dans les univers ainsi décrits sont indépendantes entre-elles. On ajoute aussi un nouveau connecteur logique qu'est l'égalité logique `"=(.,.)"`
Un monde `m` devient une application de l'ensemble des variables vers les triléens, ce qui se note :
`m ∈ ({Omega_1,Omega_2,Omega_3,...,Omega_n}"→"{0,1,?})`
Un monde `m` constitue un couple de sous-ensembles disjoints de `ccV(Omega)` qui peut se noter : `(m^-1(0), m^-1(1))`
L'univers est maintenant identifié à l'ensemble des mondes complets et incomplets :
`Omega = ({Omega_1,Omega_2,Omega_3,...,Omega_n}"→"{0,1,?})`
On sépare le symbole de l'objet, le signifiant du signifié. L'un fait partie de la syntaxe, l'autre fait partie de la sémantique. Une proposition `P` désigne l'ensemble des mondes ou elle se réalise `{m"∈"Omega "/" m"⊨"P}`. C'est la définition formelle de la sémantique dans le cas des mondes complets :
`P` est une tautologie `AA m"∈"Omega, m"⊨"P` `P` est une antilogie `AA m"∈"Omega, m"⊨¬"P` `P` est un indécidé `EE(m,m"'")"∈"Omega^2, (m"⊨"P) "et" (m"'""⊨¬"P)`
On étend l'usage du symbole `"⊨"` aux ensembles de mondes comme premier argument. Un ensemble de mondes `E"∈"ccP(Omega)` satisfait une proposition `P` si et seulement si chacun des mondes de l'ensemble `E` satisfait `P` :
Avec cette définition, l'ensemble vide `Ø`, ne contenant aucun monde, satisfait toutes les propositions même la proposition antilogique `0` :
Puis on étend l'usage du symbole `"⊨"` aux propositions comme premier argument. Une proposition `Q"∈"ccL_0` satisfait une proposition `P` si et seulement si chaque monde satisfaisant `Q` satisfait `P` :
Ainsi le symbole `⊨` définit l'implication sémantique. Et cela correspond à la relation `"⊇"` d'inclusion inverse dans `ccP(Omega)`. Et donc l'équivalence sémantique correspond à l'égalité sémantique. On utilise le symbôle d'égalité `P"="Q` pour signifier l'égalité sémantique, c'est à dire que `{m"∈"Omega "/" m"⊨"P}` `=` `{m"∈"Omega "/" m"⊨"Q}`.
Maintenant ajoutons dans notre univers les mondes incomplets tels que définis au chapitre 4. La sémantique se perfectionne, car maintenant étant donné une proposition `P`, il existe `3` ensembles de mondes ; ceux qui satisfont `P`, ceux qui satisfont `"¬"P` et ceux qui satisfont `P"="?`. Et il faut connaitre au moins deux d'entre-eux, le troisième se déduisant des deux autres par complément, pour connaitre toutes la sémantique de `P`, c'est à dire toute la signification de `P`.
En introduisant dans le langage propositionnel les connecteurs `"=", ?`, cela produit `7` états possibles :
`P` est une tautologie triviale `AA m"∈"Omega, (m"⊨"P)` `P` est une antilogie triviale `AA m"∈"Omega, (m"⊨¬"P)` `P` est ignoré `AAm"∈"Omega, m"⊨"(P"="?)` `P` est une tautologie `((AA m"∈"Omega"," (m"⊭¬"P)),(EE m"∈"Omega","(m"⊨"P)),(EE m"∈"Omega"," (m"⊨"(P"="?))))` `P` est une antilogie `((AA m"∈"Omega"," (m"⊭"P)),(EE m"∈"Omega","(m"⊨¬"P)),(EE m"∈"Omega"," (m"⊨"(P"="?))))` `P` est un indécidé `((EE m"∈"Omega"," (m"="?)),(EE m"∈"Omega","(m"⊨"P)),(EE m"∈"Omega"," (m"⊨¬"P)))` `P` est un indécidé forcé `((AA m"∈"Omega"," (m"⊭"(P"≠"?))),(EE m"∈"Omega","(m"⊨"P)),(EE m"∈"Omega","(m"⊨¬"P)))`
Sans introduire dans le langage propositionnel les connecteur `"=", ?`, seulement 5 états sont possibles (tautologie triviale, antilogie triviale, tautologie, antilogie, indécidé).