Dans une première approche très manichéenne de la logique, toute proposition est vraie ou bien fausse. On lui attribue soit la valeur \(0\) si elle est fausse, soit la valeur \(1\) si elle est vraie. Désignons par \(p\), \(q\),... la valeur des propositions \(P\), \(Q\),...

La négation

La négation d'une proposition \(P\) est notée \(\lnot P\); cette proposition est évidemment fausse si \(P\) est vraie et vraie si \(P\) est fausse. Si \(p\) est la valeur de \(P\), alors la valeur de \(\lnot P\) est \(1-p\).

La conjonction

Soit \(P\) et \(Q\) deux propositions; la conjonction est la proposition \(P\) et \(Q\), où le "et" signifie qu'on affirme simultanément la proposition \(P\) et la proposition \(Q\); elle est notée \(P\land Q\). Attention! Le "et" utilisé n'est toutefois pas le "et " du langage courant. Au cinéma on offre des réductions pour étudiants "et " troisième âge! La proposition \(P\land Q\) n'est évidemment vraie que si \(P\) et \(Q\) le sont simultanément. Autrement dit, elle est fausse dès que l'une des deux propositions l'est, c'est-à-dire si la valeur d'une des deux propositions vaut \(0\). Cette situation conduit à attribuer la valeur \(pq\) à \(P\land Q\) C'est pourquoi la conjonction est également appelée produit logique. Remarquons que comme les variables \(p\), \(q\),... ne prennent que les valeurs \(0\) ou \(1\), on a toujours \(p\)² = \(p\)

La disjonction

Soit \(P\) et \(Q\) deux propositions; la disjonction est la proposition \(P\) ou \(Q\), où le "ou " signifie qu'on affirme l'une des deux propositions \(P\) ou \(Q\); elle est notée \(P\lor Q\). Attention! A nouveau, le "ou " utilisé n'est pas toujours le "ou " du langage courant. Dans la langue française le terme ou possède deux sens différents; il peut signifier soit l'un, soit l'autre (c'est le "ou " inclusif) mais aussi soit l'un, soit l'autre, mais pas les deux simultanément (c'est le "ou " exclusif). En logique le "ou " est le ou inclusif. La proposition \(P\lor Q\) est vraie dès que l'une des deux propositions \(P\) ou \(Q\) l'est. Autrement dit, la valeur de \(P\lor Q\) n'est \(0\) que si la valeur de \(P\) et de \(Q\) est 0. On est tenté d'attribuer la valeur \(p+q\), mais si \(P\) et \(Q\) sont toutes deux vraies (si \(p\) = \(q\) = \(1\)) alors on aurait pour valeur 2 ! On attribue donc à la proposition \(P\lor Q\) la valeur \(p+q-pq\); la disjonction est appelée somme logique.

L'implication

On note \(P\implies Q\), l'implication de \(Q\) par la proposition \(P\). Il n'est pas possible qu'une proposition vraie implique une proposition fausse; la valeur d'une implication n'est \(0\) que si \(p=1\) et \(q=0\). Une autre manière de voir les choses et de dire que la proposition \(P\implies Q\) est équivalente à \(\lnot(P\land \lnot Q)\). On peut facilement calculer la valeur de \(P \implies Q\); elle vaut 1 - (\(p\)(1 - \(q\))) = 1 - \(p\) + pq .

L'équivalence

On note \(P\iff Q\), l'équivalence des propositions \(P\) et \(Q\). L'équivalence est vraie si les deux propositions sont simultanément vraies ou simultanément fausses. On doit avoir \((P\implies Q)\land (Q\implies P)\). Cette remarque permet de calculer la valeur d'une équivalence:

\[(1-p+pq)(1-q+qp)=1-q+qp-p+pq-p^2q+pq-pq^2+p^2q^2 \]

Mais il faut remarquer que \(p^2=p\) (la valeur de \(p\) est soit \(0\) soit \(1\)) ! On peut donc simplifier l'expression et on obtient: \(1-p-q+2pq\) On peut ainsi remarquer qu'une équivalence est vraie si \(1-p-q+2pq=1\), ce qui revient à écrire \(pq=p+q-pq\) (c'est-à-dire que la conjonction et la disjonction de \(P\) et \(Q\) sont simultanément vraies ou fausses) ou encore en multipliant soit par \(p\), soit par \(q\) et en effectuant les calculs que \(P\) et \(Q\) sont simultanément vraies ou fausses.

Les tautologies

Il s'agit de propositions qui sont toujours vraies. Un exemple simple est \(P\lor \lnot P\); en effet ou bien \(P\) est vraie sinon \(\lnot P\) est vraie. La valeur d'une tautologie est 1. Dans l'exemple on a \(p+(1-p)-p(1-p)=p+1-p-p+p^2=1\) (n'oublions pas que \(p^2=p\)).

Un autre exemple classique est celui du syllogisme:

\[ ((P\implies Q)\land (Q\implies R))\implies (P\implies R) \]

Calculons:

La valeur de \(P\implies Q\) vaut \((1-p+pq)\); celle de \(Q\implies R\) est égale à \((1-q+qr)\). On en déduit que la première parenthèse vaut le produit \((1-p+pq)(1-q+qr)\) \(=1-p-q+pq+qr\). La valeur de la deuxième parenthèse vaut \(1-p+pr\) La valeur de l'expression vaut donc: \(1-(1-p-q+pq+qr)+(1-p-q+pq+qr)(1-p+pr)\), ce qui après calcul donne 1. Remarquons qu'un peu de "bon sens" nous aurait évité de fastidieux calculs.

En effet l'expression ne peut être fausse que si la prémisse est vraie et la conclusion fausse; cette conclusion ne peut être fausse que si \(P\) est vrai et \(R\) faux. Or si \(Q\) est vrai, (et \(R\) faux) le premier membre est faux car \(Q\implies R\) est faux, et si \(Q\) est faux il l'est également car c'est alors \(P\implies Q\) qui est faux.

Parmi toutes ces opérations sur les propositions, il est naturel de se poser la question de savoir si certaines d'entre elles ne peuvent pas s'exprimer à l'aide d'autres. Par exemple il est évident qu'avec la négation ("non ") et la disjonction ("ou"), on est à même de définir la conjonction ("et"). En effet \(P\land Q=\lnot (\lnot P\lor \lnot Q)\).

Mais il y a mieux : l'opération correspondant à la "barre de Scheffer". Aux propositions \(P\) et \(Q\) on associe l'opération "incompatibilité" de \(P\) et \(Q\) : \(P\)|\(Q\) qui n'est fausse que si \(P\) et \(Q\) sont toutes deux vraies (c'est le NAND des électroniciens). La valeur de l'incompatibilité de \(P\) et de \(Q\) vaut \(1 -pq\)

Une simple observation : \(P|P=\lnot P\) (en effet \(1-pp=1-p\)) montre que la barre de Scheffer permet de définir la négation et, en poursuivant, on voit ainsi comment définir toutes les opérations sur les propositions.

Dans la réalité tout n'est pas nécessairement blanc ou noir; les choses sont plus nuancées. Une proposition \(P\) peut être fort probablement vraie, ou peut-être vraie, ou très peu vraisemblablement vraie... On doit donc lui accorder une valeur de vérité \(p\) qui est comprise entre 0 et 1. On peut parler de la probabilité de véracité de la proposition \(P\). De plus dans un ensemble, les éléments d'un sous-ensemble peuvent rendre une proposition vraie (dans l'ensemble des réels \(x^2 \lt 1\) est vraie pour le sous-ensemble \(-1 \lt x \lt 1\)).

On voit le lien étroit qui existe entre logique, probabilités et ensembles .