Expression booléenne

Question

Comment pouvez-vous exprimer X de Y sont vrais, dans la logique booléenne? une règle comme 2 des suivantes doit être vraie (A, B, C, D, E, F) est-ce une forme de multiplication ou d'opérations d'ensemble?
le résultat final est toutes les permutations comme AB ou AC ou AD, si vous avez dit 3 de la suite, c'est comme ABC, ABD, ABE, etc., donc c'est comme (A, B, C)^2?

merci!

Answer 1

En logique booléenne (v est OR, ' suivant le prédicat est pas):

A B C'D'E'F' v 
A B'C'D'E'F v 
A'B C'D'E'F' v 
: : : : : : 
<absolute bucketload of boolean expressions> 
: : : : : : 
A'B'C'D'E F 

Avec permutations, il y a un grand nombre de sous-expressions dont vous avez besoin d'écrire.

Bien sûr, si cela est une question de programmation, vous pouvez simplement convertir les booléens à 0 ou 1, les ajouter tous et assurer le résultat est 2.

Answer 2

Vous avez l'idée là-bas. Pour exprimer "k of n hold", vous devrez énumérer tous les cas pour lesquels k est valable. Donc, si nous avons des variables A B C D E, et que vous voulez 3 5, vous aurez besoin

(A & B & C & ~D & ~E) | 
(A & B & ~C & D & ~E) | 
(A & B & ~C & ~D & E) | ... 
(~A & ~B & C & D & E) 

où & est "et" | est "ou" et ~ est "pas".

Answer 3

En supposant "Un ou plusieurs"

vous pouvez faire un peu mieux en construisant un arbre

2 : a&(b|c|d|e|f) | b&(c|d|e|f) | c&(d|e|f) | d&(e|f) | e*f 
3 : a&(b&(c|d|e|f) | c&(d|e|f) | d&(e|f) | e*f) | b&(c&(d|e|f) | d&(e|f) | e*f) | c&(d&(e|f) | e*f) | d&e&f 

ou code

bool AofB(int n, bool[] bs) 
{ 
    if(bs.length == 0) return false; 
    if(n == 0) return true; 

    foreach(int i, bool b; b[0..$-n]) 
     if(b && AofB(n-1,b[i+1..$]) return true; 

    return false; 
} 

mieux encore

bool AofB(int n, bool[] bs) 
{ 
    foreach(bool b; bs) if(b && --n == 0) return true; 
    return false; 
} 

Answer 4

En supposant C# ou une autre langue où bool! = int:

bool nOf(int n, bool[] bs) 
{ 
    foreach(bool b in bs) 
    { 
     if((n -= b ? 1 : 0) <= 0) break; 
    } 
    return n == 0; 
} 

Answer 5

Python:

expressions = [A, B, C, D, E, F, G ] 
numTrue = len(filter(None, expressions) 

PHP:

$expressions = array(A, B, C, D, E, F, G); 
$numTrue = count(array_filter($expressions)); 

Answer 6

Je les compterais. Toutefois, si vous devez produire un prédicat en utilisant uniquement des opérations booléennes, vous pouvez traiter les entrées comme des bits dans un système d'additionneurs.

Basic Half-Adder 

A, B : 1st 2nd bits 
O, C : unit output and carry to next unit 

O := A xor B; 
C := A and B; 

Vous pouvez trouver plus d'exemples et des liens à [Wikipédia] [http://en.wikipedia.org/wiki/Half_adder (demi-Adder)]

Ensuite, vous pouvez regrouper les six variables en 3 paires, ensuite déterminer comment utiliser ces sorties pour se rapprocher de la réponse et résoudre le reste vous-même.

Une autre option serait d'utiliser un circuit pour trouver le nombre de pop (ajouter le côté) et vérifier si le seul bit correspond à 2. exemple célèbre dans l'assemblage non des portes logiques est [Hakmem 169] [http://home.pipeline.com/~hbaker1/hakmem/hacks.html#item169 (PopCount) ]

Answer 7

Cela fait une différence si vous voulez dire "exactement deux doivent être vraies" contre "au moins deux doivent être vraies". Pour l'ensemble des variables {A..F}, les réponses de Pax et de Charlie Martin ont couvert la situation "exactement deux" (deux sont vraies et les autres sont fausses), tandis que l'expression dans votre question semblait traiter avec le « au moins deux » cas:

(A && B) || (A && C) || ... || (D && E) || (D && F) || (E && F) 

est une expression qui est vrai lorsque, par exemple, A et B sont vrais et les variables restantes sont quelque chose (vrai ou faux).

Si ce que vous demandez est une expression théorie comme jeu pour décrire la situation (s) ci-dessus, vous pouvez l'exprimer quelque chose comme ceci:

#{x | x <- {A, B, C, D, E, F} | x} = 2 

où travaille la notation de cette ainsi:

#{...} 

représente la taille de l'ensemble fermé, et le jeu lui-même:

{x | x <- {A, B, C, D, E, F} | x} 

lit "l'ensemble de x, où x est l'un des A à F, et est vrai". En d'autres termes, étant donné l'ensemble des variables A à F, le sous-ensemble composé des variables avec des valeurs vraies a exactement deux éléments. (Utilisez <= au lieu de '=' pour exprimer l'autre interprétation de votre question.)