Logika sprawdzająca, czy 3 z 4 są prawdziwe

Chcę zwrócić Truewtedy i tylko wtedy, gdy 3 z 4 wartości logicznych są prawdziwe.

Najbliższe otrzymałem to (x ^ y) ^ (a ^ b):

Co powinienem zrobić?

Proponuję napisać kod w sposób, który wskazuje, co masz na myśli. Jeśli chcesz, aby 3 wartości były prawdziwe, wydaje mi się naturalne, że wartość 3 gdzieś się pojawia.

Na przykład w C++:

if ((int)a + (int)b + (int)c + (int)d == 3)
    ...

Jest to dobrze zdefiniowane w C++: standard (§4.7/4)oznacza, że ​​konwersja boolna intdaje oczekiwane wartości 0 lub 1.

W Javie i C # możesz użyć następującej konstrukcji:

if ((a?1:0) + (b?1:0) + (c?1:0) + (d?1:0) == 3)
    ...

# 1: Używanie rozgałęzienia?: 3 lub 4 operacje

A ^ B ? C & D : ( C ^ D ) & A

# 2 Bez rozgałęzienia, 7 operacji

(A ^ B ^ C ^ D) & ((A & B) | (C & D))

Kiedy już używałem profilowania wszystkiego, odkryłem, że rozwiązania nierozgałęziające były znacznie szybsze w działaniu, ponieważ procesor mógł lepiej przewidywać ścieżkę kodu i wykonywać więcej operacji w tandemie. Jednak w instrukcji rozgałęzienia jest około 50% mniej pracy.

Gdyby to był Python, napisałbym

if [a, b, c, d].count(True) == 3:

Lub

if [a, b, c, d].count(False) == 1:

Lub

if [a, b, c, d].count(False) == True:
# In Python True == 1 and False == 0

Lub

print [a, b, c, d].count(0) == 1

Lub

print [a, b, c, d].count(1) == 3

Lub

if a + b + c + d == 3:

Lub

if sum([a, b, c, d]) == 3:

Wszystko to działa, ponieważ wartości logiczne są podklasami liczb całkowitych w Pythonie.

if len(filter(bool, [a, b, c, d])) == 3:

Lub zainspirowany tą zgrabną sztuczką ,

data = iter([a, b, c, d])
if not all(data) and all(data):

Długa, ale bardzo prosta (rozłączna) postać normalna:

 (~a & b & c & d) | (a & ~b & c & d) | (a & b & ~c & d) | (a & b & c & ~d)

Można to uprościć, ale wymaga to więcej przemyślenia: P

Nie wiem, czy to prostsze, ale może.

((x xor y) and (a and b)) or ((x and y) and (a xor b))

Jeśli chcesz użyć tej logiki w języku programowania, moja sugestia jest taka

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

Lub jeśli chcesz, możesz umieścić je wszystkie w jednym wierszu:

return (a ? 1 : 0) + (b ? 1 : 0) + (C ? 1 : 0) + (d ? 1 : 0) == 3;

Możesz również uogólnić ten problem, aby 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;
}

Ta odpowiedź zależy od systemu reprezentacji, ale jeśli 0 jest jedyną wartością interpretowaną jako fałsz i not(false)zawsze zwraca tę samą wartość liczbową, to not(a) + not(b) + not(c) + not(d) = not(0)powinno załatwić sprawę.

Mając na uwadze, że SO w przypadku pytań programistycznych, a nie tylko problemów logicznych, odpowiedź oczywiście zależy od wyboru języka programowania. Niektóre języki obsługują funkcje, które są rzadkie w innych.

Na przykład w C ++ możesz przetestować swoje warunki za pomocą:

(a + b + c + d) == 3

Powinien to być najszybszy sposób sprawdzenia w językach, które obsługują automatyczną (niskiego poziomu) konwersję z typów logicznych na całkowite. Ale znowu nie ma ogólnej odpowiedzi na ten problem.

Najlepsze, co mogę zrobić, to ((x ^ y) ^ (a ^ b)) && ((a || x) && (b || y))

((a xor b) xor (c xor d)) and ((a or b) and (c or d))

Pierwsze wyrażenie wyszukuje 1 lub 3 truez 4. Drugi eliminuje 0 lub 1 (a czasem 2) truez 4.

Java 8, odfiltruj wartości fałszywe i policz pozostałe wartości prawdziwe:

public static long count(Boolean... values) {
    return Arrays.stream(values).filter(t -> t).count();
}

Następnie możesz go użyć w następujący sposób:

if (3 == count(a, b, c, d)) {
    System.out.println("There... are... THREE... lights!");
}

Łatwo uogólnia do sprawdzania nz mprzedmiotów jest prawdziwe.

Aby sprawdzić, czy przynajmniej nze wszystkich Booleansą prawdziwe (n musi być mniejsze lub równe całkowitej liczbie Boolean: p)

if (((a ? 1:0) + (b ? 1:0 ) + (c ? 1:0) + (d ? 1:0 )) >= n) {
    // do the rest
}

Edycja : po komentarzu @ Cruncher

Aby sprawdzić 3 booleanz 4

if (((a ? 1:0) + (b ? 1:0 ) + (c ? 1:0) + (d ? 1:0 )) == 3) {
    // do the rest
}

Inny :

((c & d) & (a ^ b)) | ((a & b) & (c ^ d))( Szczegóły )

Oto sposób, w jaki możesz to rozwiązać w C # za pomocą LINQ:

bool threeTrue = new[] { a, b, x, y }.Count(x => x) == 3;

To jest symetryczna funkcja boolowska S₃(4). Symetryczna funkcja boolowska jest funkcją boolowską, która zależy tylko od ilości ustawionych wejść, ale nie zależy od tego, które z nich są. Knuth wspomina o funkcjach tego typu w sekcji 7.1.2 w tomie 4 książki The Art of Computer Programming.

S₃(4) można obliczyć za pomocą 7 operacji w następujący sposób:

(x && y && (a || b)) ^ ((x || y) && a && b)

Knuth pokazuje, że jest to optymalne, co oznacza, że ​​nie można tego zrobić w mniej niż 7 operacjach przy użyciu zwykłych operatorów: &&, || , ^, <,i >.

Jeśli jednak chcesz użyć tego w języku, w którym używa się 1prawdy i 0fałszu, możesz również łatwo użyć dodawania:

x + y + a + b == 3

co sprawia, że ​​twój zamiar jest całkiem jasny.

(a && b && (c xor d)) || (c && d && (a xor b))

Z czysto logicznego punktu widzenia to właśnie wymyśliłem.

Zgodnie z zasadą gołębnika, jeśli dokładnie 3 jest prawdziwe, to albo aib jest prawdą, albo cid jest prawdą. Wtedy wystarczy połączyć każdy z tych przypadków z dokładnie jednym z pozostałych 2.

Tabela prawdy Wolframa

Jeśli używasz narzędzia do wizualizacji logiki, takiego jak Mapy Karnaugha, zobaczysz, że jest to problem, w którym nie możesz uniknąć pełnego wyrażenia logicznego, jeśli chcesz go zapisać w jednym wierszu if (...). Lopina już to pokazała, prościej się nie da napisać. Możesz trochę pomyśleć, ale będzie to trudne do odczytania dla Ciebie ORAZ dla maszyny.

Rozwiązania liczenia nie są złe i pokazują, czego naprawdę szukasz. Skuteczne liczenie zależy od języka programowania. Rozwiązania tablicowe w Pythonie lub LinQ są przyjemne dla oka, ale uwaga, to jest WOLNE. Wolf's (a + b + x + y) == 3 będzie działać dobrze i szybko, ale tylko wtedy, gdy twój język zrównuje „prawda” z 1. Jeśli „prawda” jest reprezentowana przez -1, będziesz musiał przetestować na -3: )

Jeśli twój język używa prawdziwych wartości logicznych, możesz spróbować zaprogramować go jawnie (ja używam! = Jako testu 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” działa tylko wtedy, gdy x, y są typu boolowskiego. Jeśli są innego typu, w których 0 jest fałszywe, a wszystko inne jest prawdą, może się to nie powieść. Następnie użyj logicznego XOR, lub ((bool) x! = (Bool) y), lub napisz „if (x) return (y == false) else return (y == true);”, co jest trochę więcej pracować na komputerze.

Jeśli Twój język programowania udostępnia operator trójskładnikowy?:, Możesz go skrócić do

if (a)
    return b ? (x != y) : (x && y);
else
    return b ? (x && y) : false;

który zachowuje trochę czytelności, lub agresywnie skraca

return a ? (b ? (x != y) : (x && y)) : (b ? (x && y) : false);

Ten kod wykonuje dokładnie trzy testy logiczne (stan a, stan b, porównanie x i y) i powinien być szybszy niż większość innych odpowiedzi tutaj. Ale musisz to skomentować, inaczej nie zrozumiesz po 3 miesiącach :)

Jest tu wiele dobrych odpowiedzi; oto alternatywna formuła, której nikt inny jeszcze nie opublikował:

 a ? (b ? (c ^ d) : (c && d)) : (b && c && d)

Podobna do pierwszej odpowiedzi, ale czysta Java:

int t(boolean b) {
    return (b) ? 1 : 0;
}

if (t(x) + t(y) + t(a) + t(b) == 3) return true;
return false;

Wolę liczyć je jako liczby całkowite, ponieważ dzięki temu kod jest bardziej czytelny.

W Pythonie , aby zobaczyć, ile iterowalnych elementów jest True, użyj sum(jest to dość proste):

Ustawiać

import itertools

arrays = list(itertools.product(*[[True, False]]*4))

Rzeczywisty test

for array in arrays:
    print(array, sum(array)==3)

Wynik

(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

Jeśli szukasz rozwiązania na papierze (nie programistycznego), to mapy K i algorytmy Quine-McCluskey są tym, czego szukasz, pomagają ci zminimalizować funkcję boolowską.

W twoim przypadku wynik jest

y = (x̄3 ^ x2 ^ x1 ^ x0) ∨ (x3 ^ x̄2 ^ x1 ^ x0) ∨ (x3 ^ x2 ^ x̄1 ^ x0) ∨ (x3 ^ x2 ^ x1 ^ x̄0)

Jeśli chcesz to zrobić programowo, z niestałą ilością zmiennych i niestandardowym „progiem”, po prostu iterowanie przez listę wartości logicznych i liczenie wystąpień „prawda” jest całkiem proste i proste.

Chcę zwrócić prawdę wtedy i tylko wtedy, gdy 3 z 4 wartości logicznych są prawdziwe.

Biorąc pod uwagę 4 wartości logiczne, a, b, x, y, zadanie to przekłada się na następującą instrukcję C:

return (a+b+x+y) == 3;

((a^b)^(x^y))&((a|b)&(x|y))

jest tym, czego chcesz. Zasadniczo wziąłem twój kod i dodałem sprawdzanie, czy w rzeczywistości 3 są prawdziwe, a nie 3 są fałszywe.

Pytanie programistyczne bez odpowiedzi z rekurencją? Niepojęty!

Jest wystarczająco dużo odpowiedzi „dokładnie 3 z 4 prawd”, ale tutaj jest uogólniona wersja (w języku Java) wyrażenia „dokładnie m z n praw” (w przeciwnym razie rekursja nie jest tego warta) tylko dlatego, że można:

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

Można to nazwać czymś takim:

 boolean[] booleans = { true, false, true, true, false, true, true, false };
 containsTrues(booleans, 0, 5, 0);

który powinien zwrócić true(ponieważ 5 z 8 wartości było prawdą, zgodnie z oczekiwaniami). Niezupełnie zadowolony ze słów „prawda” i „fałsz”, ale nie mogę teraz wymyślić lepszej nazwy… Zwróć uwagę, że rekursja kończy się, gdy znaleziono zbyt wiele true lub zbyt wiele falsewartości.

Ponieważ czytelność jest dużym problemem, możesz użyć opisowego wywołania funkcji (zawijając dowolną z sugerowanych implementacji). Jeśli to obliczenie trzeba wykonać w wielu miejscach, wywołanie funkcji jest najlepszym sposobem na ponowne użycie i wyjaśnia dokładnie, co robisz.

bool exactly_three_true_from(bool cond1, bool cond2, bool cond3, bool cond4)
{
    //...
}

W PHP, czyniąc go bardziej dynamicznym (na wypadek gdybyś zmienił liczbę warunków itp.):

$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";

(((a AND b) OR (x AND y)) AND ((a XOR b) OR (x XOR y)))

Chociaż mógłbym pokazać, że jest to dobre rozwiązanie, odpowiedź Sama Hocevara jest łatwa zarówno do napisania, jak i do zrozumienia później. W mojej książce to sprawia, że ​​jest lepiej.

Oto kod C #, który właśnie napisałem, ponieważ mnie zainspirowałeś:

Wymaga dowolnej liczby argumentów i powie Ci, czy n z nich jest prawdą.

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

i tak to nazywasz:

        bool a = true;
        bool b = true;
        bool c = true;
        bool d = false;            

        bool test = false;
        test = boolTester(3, a, b, c, d);

Możesz więc teraz przetestować 7/9 lub 15/100, jak chcesz.