Est-ce que ce compte pour toutes les combinaisons entre A, B et C en utilisant les opérateurs?
Cela dépend de quelles sont vos règles, mais étant donné les règles raisonnables, je ne pense pas. Je ne vois pas A & (!B & !C), par exemple. Y at-il un moyen de calculer cette quantité de combinaisons au lieu de devoir le faire à la main? Ecrivez les règles d'une expression de votre formulaire.
Être spécifique. Est-ce que A, B et C n'apparaissent qu'une seule fois? Est-ce qu'un nombre quelconque - 0, 1, 2 ou 3 - peut être annulé dans une expression? Les parenthèses sont-elles toujours autour de l'opération la plus à droite et jamais la plus à gauche? L'expression entre parenthèses peut-elle être annulée? Confirmer que des choses comme la négation multiple sont interdites montrerait également que vous avez considéré cette possibilité. Une fois que vous avez les règles, vous pouvez passer en revue les composants requis et les limitations sur vos expressions et dire combien d'options vous avez pour satisfaire chaque exigence soumise à chaque contrainte. Par exemple, en supposant A, B, C montrent exactement une fois dans cet ordre, que chaque variable peut être niée ou non, et que les opérateurs binaires peuvent être choisis librement et indépendamment, je reçois:
- 1 façon de choisir et d'organiser les variables
A, B, C
- une façon de parenthèses dans l'expression
- 2^3 = 8 façons de placer négations (3 variables, une sous-expression entre parenthèses, tous soit niée ou non)
- 3^2 = 9 façons de choisir les opérateurs binaires (3 opérateurs, deux endroits pour les mettre, chacun choisi librement)
- Total: 1 x 1 x 8 x 9 = 72 expressions
Certaines de ces 72 expressions seront équivalentes; en particulier, !X^!Y = X^Y, !X^Y = X^!Y, et X^!Y = !X^Y, donc nous avons compté deux fois dans 1/2 cas où ^ a été sélectionné comme le deuxième opérateur - 1/3 de tous les cas. 72 x 1/2 x 1/3 = 72/6 = 12 aurait vraiment dû être 6. Donc 72-6 = 66 de nos expressions restent. Mais attendez, rappelez-vous De Morgan: (X & Y) = !(!X | !Y) et (X | Y) = !(!X & !Y). Donc, nos expressions !A^(B & C) et A^(!B | !C) sont équivalentes par le même raisonnement ci-dessus. Autrement dit, lorsque l'opération la plus à gauche est ^ et que A est annulée (1/3 des cas et 1/2 des cas, respectivement), nous avons de nouveau compté deux fois.72 x 1/3 x 1/2 = 72/6 = 12 aurait vraiment dû être 6. Donc 66 - 6 = 60 expressions restent.
Bien sûr, les deux conditions peuvent se produire ensemble. Nous devons ajouter cela ou nous aurons surcompensé. Dans 72 x 1/2 x 1/3 x 1/3 x 1/2 = 72/36 = 2 cas, nous devons ajouter. Nous avons donc 62 expressions distinctes logiquement, 10 expressions équivalentes à certaines des 62 autres, pour un total de 72 expressions.
On s'attendrait à ce qu'il y ait 256 expressions logiquement uniques sur trois variables (2^3 affectations à 3 variables, et 2 valeurs de fonction pour chaque affectation, signifie 2^(2^3) = 2^8 = 256 fonctions) . De même, il y a 2^(2^2) = 2^4 = 16 fonctions sur deux variables, 2^(2^1) = 2^2 = 4 sur une variable, et 2^(2^0) = 2^1 = 2 sans variables. Avec cela, nous pouvons combien de fonctions uniques que nous avons plus exactement trois variables:
exactly 0: 2
0 f = T ***
1 f = F ***
exactly 1: 4 - (1 choose 0) * 2 = 2
00 f(X) = F
01 f(X) = !X ***
10 f(X) = X ***
11 f(X) = T
exactly 2: 16 - (2 choose 1) * 2 - (1 choose 0) * 2 = 10
0000 f(X,Y) = T
0001 f(X,Y) = !X & !Y ***
0010 f(X,Y) = !X & Y ***
0011 f(X,Y) = !X
0100 f(X,Y) = X & !Y ***
0101 f(X,Y) = !Y
0110 f(X,Y) = X^Y ***
0111 f(X,Y) = !X | !Y ***
1000 f(X,Y) = X & Y ***
1001 f(X,Y) = !(X^Y) ***
1010 f(X,Y) = Y
1011 f(X,Y) = !X | Y ***
1100 f(X,Y) = X
1101 f(X,Y) = X | !Y ***
1110 f(X,Y) = X | Y ***
1111 f(X,Y) = T
exactly 3: 256 - (3 choose 2) * 10 - (3 choose 1) * 4 - (3 choose 0) * 2 = 212
...
Cela implique qu'il ya environ 184 fonctions de trois variables qui ne peuvent pas être codées dans cette représentation, soit environ 150 fonctions qui nécessitent au moins trois variables. Une fonction qui ne peut être calculée par aucune de nos expressions est: au moins deux de A, B et C sont vrais. La table de vérité est:
A B C f(A,B,C)
T T T T
T T F T
T F T T
T F F F
F T T T
F T F F
F F T F
F F F F
Pour voir il n'y a pas d'expression pour cela, commencer à construire un:
A est suivi par &, | ou ^. Si &, nous ne pourrions avoir que T s dans une moitié mais pas les deux, mais nous avons T dans les deux. Si |, une moitié devrait être tous T s, mais aucune de nos moitiés est tous T s. Donc ^ est notre seule option.
A est annulé ou non. Si elle est niée, nous avons besoin d'une table de vérité comme ce qui suit pour B et C:
B C g(B,C)
T T F
T F F for A=T, T for A=F
F T F for A=T, T for A=F
F F T for A=T, F for A=F
C'est, pour la sous-expression B et C dépendrait de A, une contradiction. Donc, il n'y a aucune expression dans notre schéma qui a cette table de vérité. Voici une expression sur trois variables avec la table de vérité: (A & B) | (B & C) | (A & C)