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


163

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ć?


10
Hmm, jedyny sposób, w jaki przychodzi mi do głowy bez wzoru matematycznego, to użycie licznika. Dobre pytanie! :)
Jestem Cavic

10
Twój pomysł nie jest zły, ale musisz wziąć negacje: not a ^ not b ^ not c ^ not djest prawdziwy, gdy dokładnie jedna z zanegowanych wartości jest prawdziwa. Oznacza to, że z oryginalnych wartości dokładnie jeden był fałszywy.
Ingo

23
Jaki jest twój rzeczywisty problem związany z tymi szczegółami?
Wolf

5
@Ingo not a ^ not b ^ not c ^ not d return true gdzie tylko jeden jest fałszywy AND gdzie 3 to fałsz.
NameSpace

9
Oczywistym rozwiązaniem nie liczącym jest (!a&&b&&c&&d) || (a&&!b&&c&&d) || (a&&b&&!c&&d) || (a&&b&&c&&!d).
Jason C

Odpowiedzi:


248

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)
    ...

23
To jest dobra odpowiedź. To wygląda na przypadek X / Y. "Chce zrobić X używając Y, ale nie wie jak zrobić Y. Zamiast pytać X, pyta Y." O ile nie projektuje obwodu logicznego lub czegoś w tym rodzaju (a wtedy znalazłby się w złym miejscu), najlepszym sposobem na zrobienie tego jest sposób, który jest czytelny .
NothingsImpossible

2
@NothingsImpossible W pytaniu nie ma nic XY. To jasne i proste pytanie dotyczące rozwiązania dość powszechnego problemu w programowaniu. Y nie ma znaczenia.
Ярослав Рахматуллин

Dzięki! To jest naprawdę to, co mam na myśli to zrobić, ale mój pomysł był tak niezdarny, że dotarłem dla operacji logicznych.
Simon Kuang,

3
if (!!a + !!b + !!c + !!d == 3)łatwiej jest pisać, chociaż nie wiem, czy kompilatory optymalizują to, czy nie
phuclv

2
Zauważ, że w C ++ rzutowanie z bool na int nie jest konieczne.
PlasmaHH

90

# 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.


18
+1 - podczas gdy inne odpowiedzi są lepsze dla większości języków programowania, twoja nr 2 jest najlepszą odpowiedzią w czystej logice boolowskiej.
Brilliand


68

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):

17
+1 To rozwiązuje problem poprzez poprawne przetłumaczenie go na język Python.
Wolf

Jest to nieco niebezpieczne, ponieważ ludzie mogą zwracać dowolną niezerową liczbę całkowitą w kontekście logicznym w Pythonie. Stara sztuczka C działa w Pythonie za: a=5;not not a == 1. Wadą jest brak prawdziwego typu boolowskiego.
Voo

@Voo Mamy też bool:)
thefourtheye

@thefourtheye Ach tak, prawda, o wiele ładniejsza niż sztuczka / hack z podwójną negacją.
Voo

1
Albo ... albo ... albo ... Powinien być jeden - a najlepiej tylko jeden - oczywisty sposób na zrobienie tego. : - / :-)
rz.

53

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


2
@Ben to po prostu daje różne jej normalne formy, które to już jest w (DNF).
Riking

8
A co powiesz (a & b & (c ^ d)) | ((a ^ b) & c & d)?
user253751

2
Tak, @immibis, według Wolframa Alpha jego DNF to formuła, którą napisałem, więc jest to ta sama funkcja boolowska.
Gastón Bengolea

2
+1, ponieważ myślę, że ktoś czytający kod szybciej zrozumie, o co próbowano, niż w przypadku innych odpowiedzi.
Boluc Papuccuoglu,


22

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

12
Pokonaj mnie. Czytelność za każdym razem przewyższa spryt. +1
MikeTheLiar

20

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ę.


18

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.


2
To jest odpowiedź, którą zamierzałem opublikować. Jedną rzeczą do dodania, w zależności od używanego języka programowania, byłaby odpowiedź -3. W VB True = -1.
Tom Collins,


11
((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.


11

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.


11

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 )


OP chce dokładnie n, a nie przynajmniej n. Ale to łatwa zmiana w porównaniu z tym rozwiązaniem
Cruncher

2
@Wolf to pytanie należy do StackUnderflow.com: p
To nie jest błąd

10

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;

10

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.


9
(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


Jest to odpowiednik drugiego rozwiązania NameSpace.
Brilliand

@Brilliand Wydaje mi się inny. Jego xory wszystkie razem, aby uzyskać wszystkie 3 lub 1, a następnie wyklucza te z 1, wymagając co najmniej jednej z 2 różnych grup. (podsumowane jako 1 lub 3 i co najmniej 2). Mój wymaga zarówno jednej z odrębnych grup, jak i dokładnie jednej z drugiej.
Cruncher

Jeśli miałeś na myśli odpowiednik w tym sensie, że mine <=> hisnie wiem, co powiedzieć, ponieważ można by się tego spodziewać.
Cruncher

Myślę, że chodziło mi o to, że ta odpowiedź jest dobra w dokładnie taki sam sposób, w jaki drugie rozwiązanie NameSpace jest dobre, bez dodawania niczego nowego, czego nie obejmowała (wcześniejsza) odpowiedź NameSpace. Cóż, i tak zagłosuję za.
Brilliand

8

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 :)


8

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)

Dziękuję za odpowiedź, ale czy możesz dodać komentarz, jak to działa? Dzięki.
Deanna

(Przepraszam, że cię czepiam, dostałem to jako audyt przeglądowy. Przynajmniej zdałem .. :))
Deanna

7

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.


7

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

5

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.


1
Co oznacza wysokość paska? Zauważam, że przesuwa się w dół listy.
NameSpace

3
@NameSpace Jest to jeden ze zbyt wielu zapisów IMO, których ludzie używają do wyrażenia „nie”.

5

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;

1
Niezła pułapka. Zakłada się, że truerówna się 1. To nie jest prawda (gra słów nie zamierzona) we wszystkich językach / przypadkach. blogs.msdn.com/b/oldnewthing/archive/2004/12/22/329884.aspx
JensG

@JensG Masz rację: stawiam to założenie jasno. Dzięki :)
Wolf

4
((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.


4

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.


@ FélixSaparelli: Nie mam pewności, czy „prawda” ma tutaj zastosowanie… wydawałoby się, że jesteś zadowolony tylko z jednego true. Może coś takiego containsNumberOfTrueValues(). Tak na marginesie: nazewnictwo Smalltalk byłby znacznie bardziej nadaje się do tego, iż: doesArray: someBooleans startingAt: anIndex containNumberOfTrueValues: anExpectedNumber foundSofar: aNumberFoundSoFar. Prawdopodobnie za długo jak na gust niektórych deweloperów Javy, ale Smalltalkers nigdy nie boją się odpowiedniego nazewnictwa ;-)
Amos M. Carpenter

To było głównie zabawne. I containsTruthdosłownie oznacza „zawiera pewną nieujawnioną ilość prawdy”, więc uważam, że jest w porządku.
Félix Saparelli

3

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)
{
    //...
}

3

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

2
(((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.


1

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.

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.