Expressão booleana [fechado]

Question

Como você pode expressar X de Y forem verdadeiras, na lógica booleana?uma regra como 2 o seguinte deve ser verdadeiro (A, B, C, D, E, F) é uma forma de multiplicação ou conjunto de operações?
o resultado final é que todas as permutações como AB OU AC OU AD, se você disse que 3 dos seguintes é como a ABC, ABD, ABE, etc..assim é como (A,B,C)^2?

obrigado!

Answer 1

Na lógica booleana (v é ou, ' Seguir o predicado não é):

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

Com permutações, há muitas subexpressões que você precisa escrever.

Obviamente, se essa é uma pergunta de programação, você pode apenas converter os booleanos em 0 ou 1, adicione todos eles e garantir que o resultado seja 2.

Answer 2

Assumindo C# ou algum outro idioma em que bool! = Int:

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

Answer 3

Pitão:

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 4

Você tem a idéia lá.Para expressar "k de n possui" o que você vai precisar para enumerar todos os casos para os quais k detém.Assim, se temos variáveis A B C D E e você deseja 3 de 5, você precisará de

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

onde & "e" | e "ou" e ~ é "não".

Answer 5

Assumindo "um ou mais"

você pode fazer um pouco melhor construindo uma árvore

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 como código

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;
}

melhor ainda

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

Answer 6

Gostaria de contar-lhes.No entanto, se você deve produzir um predicado utilizar operações booleanas só então você pode tratar as entradas como bits em um sistema de somadores.

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;

Você pode encontrar mais exemplos e links em [Wikipédia][http://en.wikipedia.org/wiki/Half_adder (Half-Adder)]

Em seguida, você pode agrupar até seis variáveis em 3 pares, em seguida, descobrir como utilizar essas saídas para chegar mais perto da resposta e resolver o resto de si mesmo.

Outra opção seria a utilização de um circuito para encontrar pop contagem (para os lados adicionar) e verifique para ver se o bit somente jogos para 2.Famoso exemplo do conjunto de portas lógicas não é [Hakmem 169][http://home.pipeline.com/~hbaker1/hakmem/hacks.html#item169 (popcount)].

Answer 7

Faz diferença se você quer dizer "exatamente dois deve ser true" versus", pelo menos, dois devem ser verdadeiras".

Para o conjunto de variáveis {A..F}, as respostas por Pax e Charlie Martin cobriu o "exatamente dois" situação (duas são verdadeiras e o resto são falsas), enquanto a expressão na sua pergunta parecia lidar com a "pelo menos dois" case":

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

é uma expressão que é verdadeira quando, por exemplo, A e B são verdadeiras e as demais variáveis são algo (verdadeiro ou falso).

Se o que você está pedindo é um conjunto de-teoria-como expressão de descrever a situação(s) acima, você pode expressar algo como isto:

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

onde a notação funciona desta forma:

#{...}

representa o tamanho do fechado, e o conjunto em si:

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

lê-se "o conjunto de x, onde x é um dos A através de F, e x é verdade".Em outras palavras, dado o conjunto de variáveis A através de F, o subconjunto constituído das variáveis com valores verdadeiros possui exatamente dois elementos.(Use <= em vez de '=' para expressar a outro a interpretação de sua pergunta.)