boolean-logic - boolean algebra calculator
Lógica para probar que 3 de 4 son Verdaderos (27)
Quiero devolver True si y solo si 3 de 4 valores booleanos son verdaderos.
Lo más cercano que he obtenido es (x ^ y) ^ (a ^ b) :
¿Que debería hacer?
Quiero devolver verdadero si y solo si 3 de 4 valores booleanos son verdaderos.
Dados los 4 valores booleanos, a, b, x, y, esta tarea se traduce en la siguiente declaración C:
return (a+b+x+y) == 3;
# 1: ¿Usando una ramificación?: 3 o 4 operaciones
A ^ B ? C & D : ( C ^ D ) & A
# 2 Sin ramificación, 7 operaciones
(A ^ B ^ C ^ D) & ((A & B) | (C & D))
Cuando utilicé para hacer un perfil de todo, encontré que non-branching soluciones non-branching eran bastante más rápidas de operación para la operación, ya que la CPU podía predecir mejor la ruta del código y ejecutar más operaciones en tándem. Sin embargo, aquí hay un 50% menos de trabajo en la declaración de ramificación.
¿Una pregunta de programación sin una respuesta que implique recursión? ¡Inconcebible!
Hay suficientes respuestas "exactamente 3 de 4 trues", pero aquí hay una versión generalizada (Java) para "exactamente m de n trues" (de lo contrario, la recursión no vale la pena) simplemente porque puedes:
public static boolean containsTrues(boolean[] someBooleans,
int anIndex, int truesExpected, int truesFoundSoFar) {
if (anIndex >= someBooleans.length) {
return truesExpected == truesFoundSoFar; // reached end
}
int falsesExpected = someBooleans.length - truesExpected;
boolean currentBoolean = someBooleans[anIndex];
int truesFound = truesFoundSoFar + (currentBoolean ? 1 : 0);
if (truesFound > truesExpected) {
return false;
}
if (anIndex - truesFound > falsesExpected) {
return false; // too many falses
}
return containsTrues(someBooleans, anIndex + 1, truesExpected,
truesFound);
}
Esto podría llamarse con algo como:
boolean[] booleans = { true, false, true, true, false, true, true, false };
containsTrues(booleans, 0, 5, 0);
que debería devolver true (porque 5 de 8 valores eran verdaderos, como se esperaba). No del todo feliz con las palabras "trues" y "falsos", pero no puedo pensar en un nombre mejor en este momento ... Tenga en cuenta que la recursión se detiene cuando se han encontrado demasiados valores true o demasiados false .
Aquí hay muchas buenas respuestas; aquí hay una formulación alternativa que nadie más ha publicado aún:
a ? (b ? (c ^ d) : (c && d)) : (b && c && d)
Aquí hay un código c # que acabo de escribir porque me has inspirado:
Toma cualquier cantidad de argumentos y le dirá si n de ellos son verdaderos.
static bool boolTester(int n, params bool[] values)
{
int sum = 0;
for (int i = 0; i < values.Length; i++)
{
if (values[i] == true)
{
sum += 1;
}
}
if( sum == n)
{
return true;
}
return false;
}
y lo llamas así:
bool a = true;
bool b = true;
bool c = true;
bool d = false;
bool test = false;
test = boolTester(3, a, b, c, d);
Entonces ahora puedes probar 7/9 o 15/100 como quieras.
Aquí hay una manera de resolverlo en C # con LINQ:
bool threeTrue = new[] { a, b, x, y }.Count(x => x) == 3;
Debido a que la legibilidad es una gran preocupación, puede usar una función de llamada descriptiva (envolviendo cualquiera de las implementaciones sugeridas). Si este cálculo debe realizarse en varios lugares, una llamada a la función es la mejor manera de lograr la reutilización, y deja en claro exactamente lo que está haciendo.
bool exactly_three_true_from(bool cond1, bool cond2, bool cond3, bool cond4)
{
//...
}
En Python , para ver cuántos de los elementos iterables son True, use sum (es bastante sencillo):
Preparar
import itertools
arrays = list(itertools.product(*[[True, False]]*4))
Prueba real
for array in arrays:
print(array, sum(array)==3)
Salida
(True, True, True, True) False
(True, True, True, False) True
(True, True, False, True) True
(True, True, False, False) False
(True, False, True, True) True
(True, False, True, False) False
(True, False, False, True) False
(True, False, False, False) False
(False, True, True, True) True
(False, True, True, False) False
(False, True, False, True) False
(False, True, False, False) False
(False, False, True, True) False
(False, False, True, False) False
(False, False, False, True) False
(False, False, False, False) False
En PHP, haciéndolo más dinámico (en caso de que cambie el número de condiciones, etc.):
$min = 6;
$total = 10;
// create our boolean array values
$arr = array_map(function($a){return mt_rand(0,1)>0;},range(1,$total));
// the ''check''
$arrbools = array_map(function($a){return (int)$a;},$arr);
$conditionMet = array_sum($arrbools)>=$min;
echo $conditionMet ? "Passed" : "Failed";
Esa es la función booleana simétrica S₃(4) . Una función booleana simétrica es una función booleana que solo depende de la cantidad de entradas configuradas, pero no depende de qué entradas sean. Knuth menciona funciones de este tipo en la sección 7.1.2 en el Volumen 4 de El arte de la programación de computadoras.
S₃(4) se puede calcular con 7 operaciones de la siguiente manera:
(x && y && (a || b)) ^ ((x || y) && a && b)
Knuth muestra que esto es óptimo, lo que significa que no puede hacer esto en menos de 7 operaciones con los operadores normales: &&, || , ^, <, &&, || , ^, <, y > .
Sin embargo, si desea usar esto en un idioma que usa 1 para verdadero y 0 para falso, también puede usar la adición fácilmente:
x + y + a + b == 3
lo cual hace que tu intención sea bastante clara.
Esta respuesta depende del sistema de representación, pero si 0 es el único valor interpretado como falso, y not(false) siempre devuelve el mismo valor numérico, entonces not(a) + not(b) + not(c) + not(d) = not(0) debería hacer el truco.
Forma normal larga pero muy simple (disyuntiva):
(~a & b & c & d) | (a & ~b & c & d) | (a & b & ~c & d) | (a & b & c & ~d)
Se puede simplificar, pero eso requiere más reflexión: P
Java 8, filtra los valores falsos y cuenta los valores verdaderos restantes:
public static long count(Boolean... values) {
return Arrays.stream(values).filter(t -> t).count();
}
Entonces puedes usarlo de la siguiente manera:
if (3 == count(a, b, c, d)) {
System.out.println("There... are... THREE... lights!");
}
Se generaliza fácilmente para verificar que n de m elementos sea verdadero.
Lo mejor que puedo hacer es ((x ^ y) ^ (a ^ b)) && ((a || x) && (b || y))
No estoy seguro de que sea más simple, pero tal vez.
Para verificar al menos n de todos los Boolean son verdaderos, (n debe ser menor o igual que el número total de Boolean : p)
if (((a ? 1:0) + (b ? 1:0 ) + (c ? 1:0) + (d ? 1:0 )) >= n) {
// do the rest
}
Editar : después del comentario de @ Cruncher
Para verificar 3 boolean de 4
if (((a ? 1:0) + (b ? 1:0 ) + (c ? 1:0) + (d ? 1:0 )) == 3) {
// do the rest
}
Otro :
((c & d) & (a ^ b)) | ((a & b) & (c ^ d)) ((c & d) & (a ^ b)) | ((a & b) & (c ^ d)) ( Details )
Si buscas la solución en el papel (sin programación), los algoritmos K-maps y Quine-McCluskey son lo que buscas, te ayudan a minimizar tu función booleana.
En tu caso, el resultado es
y = (x̄3 ^ x2 ^ x1 ^ x0) ∨ (x3 ^ x̄2 ^ x1 ^ x0) ∨ (x3 ^ x2 ^ x̄1 ^ x0) ∨ (x3 ^ x2 ^ x1 ^ x̄0)
Si desea hacer esto programáticamente, la cantidad no fija de variables y un "umbral" personalizado, simplemente iterar a través de una lista de valores booleanos y contar las ocurrencias de "verdadero" es bastante simple y directo.
Si desea utilizar esta lógica en un lenguaje de programación, mi sugerencia es
bool test(bool a, bool b, bool c, bool d){
int n1 = a ? 1 : 0;
int n2 = b ? 1 : 0;
int n3 = c ? 1 : 0;
int n4 = d ? 1 : 0;
return n1 + n2 + n3 + n4 == 3;
}
O si lo desea, puede poner todos estos en una sola línea:
return (a ? 1 : 0) + (b ? 1 : 0) + (C ? 1 : 0) + (d ? 1 : 0) == 3;
También puedes generalizar este problema a n of m :
bool test(bool *values, int n, int m){
int sum = 0;
for(int i = 0; i < m; i += 1){
sum += values[i] ? 1 : 0;
}
return sum == n;
}
Si esto hubiera sido Python, habría escrito
if [a, b, c, d].count(True) == 3:
O
if [a, b, c, d].count(False) == 1:
O
if [a, b, c, d].count(False) == True:
# In Python True == 1 and False == 0
O
print [a, b, c, d].count(0) == 1
O
print [a, b, c, d].count(1) == 3
O
if a + b + c + d == 3:
O
if sum([a, b, c, d]) == 3:
Todo esto funciona, ya que los booleanos son subclases de enteros en Python.
if len(filter(bool, [a, b, c, d])) == 3:
O, inspirado en este bonito truco ,
data = iter([a, b, c, d])
if not all(data) and all(data):
Si utiliza una herramienta de visualización lógica como Karnaugh Maps, verá que este es un problema en el que no puede evitar un término lógico completo si desea escribirlo en una línea (...). Lopina ya lo mostró, no es posible escribirlo más simple. Puede factorizar un poco, pero será difícil de leer para usted Y para la máquina.
Las soluciones de conteo no son malas y muestran lo que realmente buscas. Cómo se hace el recuento de manera eficiente depende de su lenguaje de programación. Las soluciones de matriz con Python oder LinQ son agradables de observar, pero cuidado, esto es LENTO. Wolf''s (a + b + x + y) == 3 funcionará bien y rápido, pero solo si tu lenguaje iguala "verdadero" con 1. Si "verdadero" está representado por -1, tendrás que probar por -3: )
Si su lenguaje usa booleanos verdaderos, puede tratar de programarlo explícitamente (yo uso! = Como prueba XOR):
if (a)
{
if (b)
return (x != y); // a,b=true, so either x or y must be true
else
return (x && y); // a=true, b=false, so x AND y must be true
}
else
{
if (b)
return (x && y); // a=false, b=true, so x and y must be true
else
return false; // a,b false, can''t get 3 of 4
}
"x! = y" solo funciona si x, y son de tipo booleano. Si son de otro tipo donde 0 es falso y todo lo demás es verdadero, esto puede fallar. Luego use un XOR booleano, o ((bool) x! = (Bool) y), o escriba "if (x) return (y == false) else return (y == true);", que es un poco más trabajar para la computadora.
Si su lenguaje de programación proporciona el operador ternario?: Puede acortarlo a
if (a)
return b ? (x != y) : (x && y);
else
return b ? (x && y) : false;
que mantiene un poco de legibilidad, o cortarlo agresivamente a
return a ? (b ? (x != y) : (x && y)) : (b ? (x && y) : false);
Este código hace exactamente tres pruebas lógicas (estado de a, estado de b, comparación de xey) y debería ser más rápido que la mayoría de las otras respuestas aquí. Pero necesita comentarlo, o no lo entenderá después de 3 meses :)
Similar a la primera respuesta, pero pura Java:
int t(boolean b) {
return (b) ? 1 : 0;
}
if (t(x) + t(y) + t(a) + t(b) == 3) return true;
return false;
Prefiero contarlos como enteros porque hace que el código sea más legible.
Sugiero escribir el código de una manera que indique a qué te refieres. Si quiere que 3 valores sean verdaderos, me parece natural que el valor 3 aparezca en alguna parte.
Por ejemplo, en C++ :
if ((int)a + (int)b + (int)c + (int)d == 3)
...
Esto está bien definido en C++ : el standard (§4.7/4) indica que la conversión de bool a int da los valores esperados 0 o 1.
En Java y C #, puede usar la siguiente construcción:
if ((a?1:0) + (b?1:0) + (c?1:0) + (d?1:0) == 3)
...
Teniendo en cuenta que SO, si se trata de preguntas de programación, en lugar de simples problemas lógicos, la respuesta obviamente depende de la elección de un lenguaje de programación. Algunos idiomas admiten características que son poco comunes para otros.
Por ejemplo, en C ++ puedes probar tus condiciones con:
(a + b + c + d) == 3
Esta debería ser la forma más rápida de hacer el chequeo en idiomas que soportan la conversión automática (bajo nivel) de tipos booleanos a enteros. Pero, de nuevo, no hay una respuesta general para ese problema.
(((a AND b) OR (x AND y)) AND ((a XOR b) OR (x XOR y)))
Si bien podría mostrar que esta es una buena solución, la respuesta de Sam Hocevar es fácil de escribir y comprender más adelante. En mi libro eso lo hace mejor.
((a xor b) xor (c xor d)) and ((a or b) and (c or d))
La primera expresión busca 1 o 3 true de 4. El segundo elimina 0 o 1 (y algunas veces 2) es true de 4.
((a^b)^(x^y))&((a|b)&(x|y))
es lo que quieres Básicamente tomé su código y agregué chequeo si realmente 3 son verdaderos y no 3 son falsos.
(a && b && (c xor d)) || (c && d && (a xor b))
Desde el punto de vista de la lógica pura, esto es lo que se me ocurrió.
Según el principio del casillero, si exactamente 3 son verdaderos, entonces a y b son verdaderos, o c y d son verdaderos. Entonces solo es cuestión de resolver cada uno de esos casos exactamente con uno de los otros 2.