{Et,Ou,Non} complet

[solad]

Bonjour,

Existe-t-il une démonstration de la complétude du système logique {Et, Ou, Non}, ou bien est-ce un axiome ?

En effet, pour montrer la complétude d'un système logique comme {Nand}, on montre que Et, Ou, et Non peuvent s'exprimer à l'aide de Nand.
Mais comment montrer que {Et,Ou,Non} lui-même est complet ?

Merci d'avance !

[Médiat]

Bonjour,

Ce n'est pas un axiome, un connecteur logique binaire est en fait une application de {0, 1}² dans {0, 1}, il en existe donc 16 en tout et pour tout et on peut montrer que ces 16 applications sont expressibles à l'aide de 3 d'entre elles {Et, Ou, Non}, c'est en ce sens que ce système est complet.

En fait comme on peut montrer, facilement, que "Et" peut s'exprimer à l'aide de {Ou, Non} et que "Ou" peut s'exprimer à l'aide de {Et, Non}, on a que les systèmes complets les plus simples sont :
{Nand}
{Et, Non}
{Ou, Non}

D'ailleurs pour démontrer que {Nand} est complet, on peut soit démontrer que les 16 connecteurs possibles sont expressibles avec {Nand} (long et pénible), soit montrer que {Nand} permet d'exprimer {Et, Non} ou {Ou, Non} (montrer que {Nand} permet d'exprimer les 3 est superflu).

[polo974]

de {0, 1}² dans {0, 1}, c'est 8 connecteurs possibles, non? (et encore en ignorant la commutativité)

(ou bien j'ai encore glissé sur une définition...)

[solad]

D'accord... Donc initialement, on est obligé de tout vérifier "à la main" avec un des systèmes complets. Mais ça suppose qu'on n'a que 2 entrées et 1 sortie ?
Quand un système est complet, il permet de réaliser n'importe quel circuit logique, donc on n'a pas forcément deux entrées et une sortie ? A moins qu'on ne considère que tout circuit logique est composé de ces 16 connecteurs logiques binaires ?

[solad]

Par exemple un demi-additionneur a 2 entrées et 2 sorties.

[ProgVal]

Tout circuit logique est équivalent à un circuit logique composé uniquement de fonctions de {0, 1}² dans {0, 1}.
La démonstration peut se faire en considérant qu'il y a une unique sortie (sinon on met deux circuits ensemble, et c'est réglé), puis en faisant une récurrence sur le nombre d'entrées.