Exercice systeme complet

[Glori18]

Bonjour,

J'aurai besoin de vos conseils pour résoudre cet exercice, je n'ai aucune idée de comment démarrer ...

1. Soit M un systeme de 13 connecteurs binaires 2 a 2 distincts. Montrer que M est complet.
2. Soit M un systeme de 11 connecteurs binaires 2 a 2 distincts. Montrer que M est complet.
3. Determiner la cardinalite maximum d'un systeme incomplet de connecteurs binaires.

Merci

[Glori18]

Up, je n'ai toujours pas trouver de solution a ce probleme , pouvez vous m'aider svp ?

[zygomatique]

salut

peut-être nous dire ce qu'est un système complet ....

[Glori18]

Voici la définition de mon cours ...
On appelle système complet de connecteurs tout sous ensemble C' de C tel que pour toute formule P il
existe une formule P' équivalente à P n’utilisant que les connecteurs de C'

[Doraki]

Combien y a-t-il de connecteurs binaires ?
Est-ce que par pur hasard tu ne connaitrais pas un petit système de connecteurs (2 ou 3 connecteurs) qui est complet ?

[Glori18]

Les connecteur que je connais sont l'implication, l’équivalence, la négation, la conjonction et la disjonction

Il y'a quelques exemples d'ensemble de connecteurs complet dans mon cours, comme l'ensemble de connecteurs ( negation, conjonction , disjonction )

[Monsieur23]

Je pense que Doraki te suggère de montrer qu'il n'y a que 16 connecteurs binaires possibles. Si parmi ces 16, tu en enlèves trois, tu peux montrer que les 13 restants forment un système complet ?

[Glori18]

Genre j'essaye toute les combinaisons possible entre l'implication, l’équivalence, la négation, la conjonction et la disjonction ?

pour des connecteurs 2 a 2 distincts cela voudrai dire qu'il faut montrer que chaqu'un des ensemble ci dessous est complet :

la negation et l'implication
la negation et l'equivalence
la negation et la conjonction
la negation et la disjonction
l'implication et l'equivalence
l'implication et la conjonction
l'implication et la disjonction
l'equivalence et la conjonction
l'equivalence et la disjonction
la conjonction et la disjonction

Cela m'en donne 10, on aurai je oublier certain ?

[Doraki]

On appelle système complet de connecteurs tout sous ensemble C' de C ...

Peux-tu donner la définition de C et de "connecteur binaire" ?

Pour l'instant tu en as donné 4 (équivalence, implication, conjonction, disjonction)
(la négation est connecteur unaire, pas binaire)
Il y en a 12 autres (qui n'ont pas forcément de nom)

D'ailleurs, il y a des systèmes complets qui ne contiennent qu'un seul connecteur.

[Glori18]

Ah ?

Dans mon cours l'ensemble C = { negation, implication ,equivalence, conjonction, disjonction }

Je ne connais pas les autres connecteurs

[zygomatique]

n'en voila un autre :

A B A xor B
1 1 1
1 0 0
0 1 0
0 0 0

(le ou exclusif)

tu vois bien que pour remplir cette troisième colonne tu as 2^4 possibilités donc 16 connecteurs ...

[Doraki]

ça c'est pas xor mais c'est la conjonction.

[Glori18]

Du coup avec le xor cela fais 5 connecteur, mais quel sont les autres ?

Parcontre je ne comprend pas ce que tu veux dire par "pour remplir cette troisième colonne tu as 2^4 possibilités donc 16 connecteurs ... "

il y'a 2^4 possibilité si on considère tout les cas mais comme il s'agit d'un xor on sait deja que les valeur qu'on va mettre vont dependre des valeurs de A et B

De plus pourquoi le fait qu'il y est 2^4 possibilité si on considère tout les cas implique qu'il existe 16 connecteurs ?

[zygomatique]

ça c'est pas xor mais c'est la conjonction.

oui pardon je corrige ::

n'en voila un autre :

A B A xor B
1 1 0
1 0 1
0 1 1
0 0 0

(le ou exclusif)

tu vois bien que pour remplir cette troisième colonne tu as 2^4 possibilités donc 16 connecteurs ...

[zygomatique]

Du coup avec le xor cela fais 5 connecteur, mais quel sont les autres ?

Parcontre je ne comprend pas ce que tu veux dire par "pour remplir cette troisième colonne tu as 2^4 possibilités donc 16 connecteurs ... "

il y'a 2^4 possibilité si on considère tout les cas mais comme il s'agit d'un xor on sait deja que les valeur qu'on va mettre vont dependre des valeurs de A et B

De plus pourquoi le fait qu'il y est 2^4 possibilité si on considère tout les cas implique qu'il existe 16 connecteurs ?

ben tu as une proposition A qui prend deux valeurs 0 ou 1 (vrai ou faux) et de même pour une proposition B

alors voila un autre connecteur : je le note #

A B A # B
1 1 0
1 0 0
0 1 0
0 0 1

il dit simplement que A # B est vrai uniquement lorsque A et B sont fausses

il fait partie des 16 connecteurs possibles

et on reconnaît non (A ou B) qui est équivalent bien sur à (non A) et (non B)

....

[Glori18]

Donc si je comprend bien, pour la 1ere et 2eme question je dois prendre un des 16 connecteurs mentionner ici https://fr.wikipedia.org/wiki/Connecteur_logique

Puis je dois montrer qu'il sont tous 2 a 2 complet ?

Genre si je suis la liste des connecteurs proposer dans la liste sur wikipedia je dois montrer que tout les ensembles du type contradiction + tout ceux qui suis est complet, ensuite conjonction + tout ceux qui suis complet ... etc ? ( je ne sais pas si je suis clair, ce que je veux dire par la c'est qu'il faut montrer contradiction avec conjonction complet, puis contradiction avec non implication complet ... etc )

M sera complet si tout ces connecteurs 2 a 2 distincts sont complet ?

[Doraki]

Sûrement pas.

Ta question c'était "montrer qu'un ensemble de 13 connecteurs distincts est complet", pas "montrer qu'un ensemble de 2 connecteurs distincts est complet".

[Glori18]

Comment puis je faire sa du coup ? mon cours ne contient que des exemples simple avec 2-3 connecteurs

[zygomatique]

ben il suffit de montrer que parmi les 16 tu en as toujours trois qui s'exprime en fonction des autres ... donc sont "inutiles" et qu'en prendre 13 suffit ....

[Glori18]

Pourrai tu me donner un exemple avec un système contenant beaucoup de connecteurs stp ?

Je n'ai que des exemples simple dans ma fiche de TD comme

Et honnêtement déjà avec 2-3 connecteurs j'ai du mal alors avec 13 ... je me sens perdu ^^