Logik zum Testen, dass 3 von 4 wahr sind

163

Ich möchte Truegenau dann zurückkehren, wenn 3 von 4 booleschen Werten wahr sind.

Das nächste, was ich bekommen habe, ist (x ^ y) ^ (a ^ b):

Was soll ich machen?

Simon Kuang
quelle
10
Hmm, der einzige Weg, den ich mir ohne mathematische Formel vorstellen kann, ist die Verwendung von count. Gute Frage! :)
Ich bin Cavic
10
Ihre Idee ist nicht schlecht, aber Sie müssen die Negationen nehmen: not a ^ not b ^ not c ^ not dist wahr, wenn genau einer der negierten Werte wahr ist. Dies bedeutet, dass von den ursprünglichen Werten genau einer falsch war.
Ingo
23
Was ist Ihr eigentliches Problem hinter diesen Details?
Wolf
5
@Ingo nicht a ^ nicht b ^ nicht c ^ nicht d return true, wo nur einer falsch ist UND wo 3 falsch sind.
NameSpace
9
Die offensichtliche Non-Count-Lösung ist (!a&&b&&c&&d) || (a&&!b&&c&&d) || (a&&b&&!c&&d) || (a&&b&&c&&!d).
Jason C

Antworten:

248

Ich schlage vor, den Code so zu schreiben, dass er angibt, was Sie meinen. Wenn Sie möchten, dass 3 Werte wahr sind, erscheint es mir natürlich, dass der Wert 3 irgendwo erscheint.

Zum Beispiel in C++:

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

Dies ist gut definiert in C++: Das standard (§4.7/4)gibt an, dass die Konvertierung boolin intdie erwarteten Werte 0 oder 1 ergibt.

In Java und C # können Sie das folgende Konstrukt verwenden:

if ((a?1:0) + (b?1:0) + (c?1:0) + (d?1:0) == 3)
    ...
Sam Hocevar
quelle
23
Das ist eine gute Antwort. Dies sieht aus wie ein Fall von dieser X / Y-Sache. "Er möchte X mit Y machen, weiß aber nicht, wie man Y macht. Anstatt X zu fragen, fragt er Y." Wenn er keine Logikschaltung oder ähnliches entwirft (und sich dann an der falschen Stelle befindet), ist dies am besten lesbar .
Nichts
2
@NothingsImpossible Die Frage enthält nichts XY. Es ist eine klare und unkomplizierte Frage zur Lösung eines einigermaßen häufigen Problems bei der Programmierung. Das Y ist irrelevant.
Ярослав Рахматуллин
Vielen Dank! Das ist wirklich das, was ich meinte zu tun, aber meine Idee war so ungeschickt , dass ich für Boolesche Logik erreicht.
Simon Kuang
3
if (!!a + !!b + !!c + !!d == 3)ist einfacher zu schreiben, obwohl ich nicht weiß, ob Compiler dies optimieren oder nicht
phuclv
2
Beachten Sie, dass in c ++ die Umwandlung von bool nach int nicht erforderlich ist.
PlasmaHH
90

# 1: Verwenden einer Verzweigung ?: 3 oder 4 Operationen

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

# 2 Nicht verzweigt, 7 Operationen

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

Als ich früher alles profilierte, stellte ich fest, dass nicht verzweigte Lösungen von Operation zu Operation viel schneller waren, da die CPU den Codepfad besser vorhersagen und mehr Operationen gleichzeitig ausführen konnte. Die Verzweigungsanweisung enthält hier jedoch etwa 50% weniger Arbeit.

NameSpace
quelle
18
+1 - während die anderen Antworten für die meisten Programmiersprachen besser sind, ist Ihre Nummer 2 die beste Antwort in reiner boolescher Logik.
Brilliand
68

Wenn dies Python gewesen wäre, hätte ich geschrieben

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

Oder

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

Oder

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

Oder

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

Oder

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

Oder

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

Oder

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

All dies funktioniert, da Boolesche Werte in Python Unterklassen von Ganzzahlen sind.

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

Oder, inspiriert von diesem tollen Trick ,

data = iter([a, b, c, d])
if not all(data) and all(data):
thefourtheye
quelle
17
+1 Dies löst das Problem, indem es korrekt in Python übersetzt wird.
Wolf
Dies ist etwas gefährlich, da Benutzer in einem booleschen Kontext in Python möglicherweise eine Ganzzahl ungleich Null zurückgeben. Der alte C-Trick funktioniert auch in Python : a=5;not not a == 1. Der Nachteil, keinen echten Booleschen Typ zu haben.
Voo
@ Voo Wir haben auch bool:)
thefourtheye
@thefourtheye Ah ja wahr, viel schöner als der Double Negation Trick / Hack.
Voo
1
Oder ... oder ... oder ... Es sollte einen - und vorzugsweise nur einen - offensichtlichen Weg geben, dies zu tun. : - / :-)
rz.
53

Lange aber sehr einfache, (disjuntive) Normalform:

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

Es mag vereinfacht sein, aber das erfordert mehr Nachdenken: P.

Gastón Bengolea
quelle
2
@Ben, das gibt Ihnen nur verschiedene normale Formen davon, in denen dies bereits ist (DNF).
Riking
8
Wie wäre es (a & b & (c ^ d)) | ((a ^ b) & c & d)?
user253751
2
Ja, @immibis, laut Wolfram Alpha ist die DNF die Formel, die ich geschrieben habe, also die gleiche boolesche Funktion.
Gastón Bengolea
2
+1, weil ich denke, dass jemand, der den Code liest, schneller versteht, was versucht wird, als mit anderen Antworten.
Boluc Papuccuoglu
34

Ich bin mir nicht sicher, ob es einfacher ist, aber vielleicht.

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

Karl Kieninger
quelle
1
Verdammt! Sie hätten Option Multi Up-Vote eine Antwort geben sollen! Besonders die Verwendung von Wolfram Alpha, um zu beweisen, dass Ihre Antwort richtig ist, ist eine sehr gute Sache!
Durai Amuthan.H
22

Wenn Sie diese Logik in einer Programmiersprache verwenden möchten, ist mein Vorschlag

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

Oder wenn Sie möchten, können Sie all dies in eine einzige Zeile setzen:

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

Sie können dieses Problem auch auf Folgendes verallgemeinern 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;
}
Frogatto
quelle
12
Schlage mich dazu. Die Lesbarkeit übertrifft jedes Mal die Klugheit. +1
MikeTheLiar
20

Diese Antwort hängt vom Repräsentationssystem ab. Wenn jedoch 0 der einzige Wert ist, der als falsch interpretiert wird, und not(false)immer den gleichen numerischen Wert zurückgibt, not(a) + not(b) + not(c) + not(d) = not(0)sollte dies der Trick sein.

MattClarke
quelle
18

Denken Sie daran, dass die Antwort für Programmierfragen und nicht nur für logische Probleme offensichtlich von der Wahl einer Programmiersprache abhängt. Einige Sprachen unterstützen Funktionen, die für andere ungewöhnlich sind.

In C ++ können Sie beispielsweise Ihre Bedingungen testen mit:

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

Dies sollte der schnellste Weg sein, um Sprachen einzuchecken, die die automatische Konvertierung (auf niedriger Ebene) von booleschen zu ganzzahligen Typen unterstützen. Aber auch hier gibt es keine allgemeine Antwort auf dieses Problem.

GOTO 0
quelle
2
Dies ist die Antwort, die ich posten wollte. Abhängig von der verwendeten Programmiersprache sollte die gewünschte Antwort -3 sein. In VB ist True = -1.
Tom Collins
11
((a xor b) xor (c xor d)) and ((a or b) and (c or d))

Der Faustausdruck sucht nach 1 oder 3 truevon 4. Der zweite eliminiert 0 oder 1 (und manchmal 2) truevon 4.

Durum
quelle
11

Java 8, filtern Sie die falschen Werte heraus und zählen Sie die verbleibenden wahren Werte:

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

Dann können Sie es wie folgt verwenden:

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

Leicht verallgemeinert zu Überprüfung nvon mArtikeln wahr.

David Conrad
quelle
11

Um zumindest zu überprüfen, ob nalle Booleanwahr sind (n muss kleiner oder gleich der Gesamtzahl von Boolean: p sein)

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

Bearbeiten : Nach dem Kommentar von @ Cruncher

Um 3 booleanvon 4 zu überprüfen

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

Noch einer :

((c & d) & (a ^ b)) | ((a & b) & (c ^ d))( Details )

Kein Fehler
quelle
OP will genau n, nicht mindestens n. Aber das ist eine einfache Änderung von dieser Lösung
Cruncher
2
@ Wolf diese Frage gehört zu StackUnderflow.com: p
Kein Fehler
10

Hier ist eine Möglichkeit, wie Sie es in C # mit LINQ lösen können:

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

Das ist die symmetrische Boolesche Funktion S₃(4). Eine symmetrische Boolesche Funktion ist eine Boolesche Funktion, die nur von der Anzahl der eingestellten Eingaben abhängt, nicht jedoch von den Eingaben. Knuth erwähnt Funktionen dieses Typs in Abschnitt 7.1.2 in Band 4 der Kunst der Computerprogrammierung.

S₃(4) kann mit 7 Operationen wie folgt berechnet werden:

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

Knuth zeigt, dass dies optimal ist, was bedeutet, dass Sie dies nicht in weniger als 7 Operationen mit den normalen Operatoren tun können: &&, || , ^, <,und >.

Wenn Sie dies jedoch in einer Sprache verwenden möchten, die 1für wahr und 0für falsch verwendet wird, können Sie Addition auch einfach verwenden:

x + y + a + b == 3

das macht deine Absicht ganz klar.

Paul
quelle
9
(a && b && (c xor d)) || (c && d && (a xor b))

Aus rein logischer Sicht habe ich mir das ausgedacht.

Wenn nach dem Taubenlochprinzip genau 3 wahr sind, dann sind entweder a und b wahr oder c und d sind wahr. Dann geht es nur noch darum, jeden dieser Fälle mit genau einem der anderen zu verbinden 2.

Wolfram Wahrheitstabelle

Cruncher
quelle
Dies entspricht der zweiten Lösung von NameSpace.
Brilliand
@ Brilliand Scheint anders als ich. Seine xors alle zusammen, um alle 3er oder 1er zu erhalten, schließt dann diejenigen mit 1 aus, indem mindestens eine von 2 verschiedenen Gruppen benötigt wird. (zusammengefasst als 1 oder 3 und mindestens 2). Meins erfordert beide von einer der verschiedenen Gruppen und dann genau eine von der anderen Gruppe.
Cruncher
Wenn Sie gleichwertig in dem Sinne meinten, mine <=> hisdann weiß ich nicht, was ich sagen soll, da dies zu erwarten wäre.
Cruncher
Ich denke, ich meinte, dass diese Antwort genauso gut ist wie die zweite Lösung von NameSpace, ohne etwas Neues hinzuzufügen, das in der (früheren) Antwort von NameSpace nicht behandelt wurde. Nun, ich werde trotzdem upvoten.
Brilliand
8

Wenn Sie ein Logikvisualisierungstool wie Karnaugh Maps verwenden, sehen Sie, dass dies ein Problem ist, bei dem Sie einen vollständigen Logikbegriff nicht vermeiden können, wenn Sie ihn in eine if (...) -Zeile schreiben möchten. Lopina hat es bereits gezeigt, es ist nicht möglich, es einfacher zu schreiben. Sie können ein wenig herausrechnen, aber es bleibt für Sie UND die Maschine schwer zu lesen.

Zähllösungen sind nicht schlecht und zeigen, wonach Sie wirklich suchen. Wie Sie effizient zählen, hängt von Ihrer Programmiersprache ab. Die Array-Lösungen mit Python oder LinQ sind schön anzusehen, aber Vorsicht, das ist LANGSAM. Wolfs (a + b + x + y) == 3 funktioniert gut und schnell, aber nur, wenn Ihre Sprache "wahr" mit 1 gleichsetzt. Wenn "wahr" durch -1 dargestellt wird, müssen Sie auf -3 testen: )

Wenn Ihre Sprache echte Boolesche Werte verwendet, können Sie versuchen, sie explizit zu programmieren (ich verwende! = Als XOR-Test):

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" funktioniert nur, wenn x, y vom booleschen Typ sind. Wenn es sich um einen anderen Typ handelt, bei dem 0 falsch und alles andere wahr ist, kann dies fehlschlagen. Verwenden Sie dann ein boolesches XOR oder ((bool) x! = (Bool) y) oder schreiben Sie "if (x) return (y == false) else return (y == true);", was etwas mehr ist Arbeit für den Computer.

Wenn Ihre Programmiersprache den Operator ternary ?: Bereitstellt, können Sie ihn auf kürzen

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

das hält ein bisschen Lesbarkeit, oder schneiden Sie es aggressiv auf

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

Dieser Code führt genau drei Logiktests durch (Zustand von a, Zustand von b, Vergleich von x und y) und sollte schneller sein als die meisten anderen Antworten hier. Aber du musst es kommentieren, sonst wirst du es nach 3 Monaten nicht verstehen :)

Rolf
quelle
8

Hier gibt es viele gute Antworten; Hier ist eine alternative Formulierung, die noch niemand veröffentlicht hat:

 a ? (b ? (c ^ d) : (c && d)) : (b && c && d)
Alex D.
quelle
Vielen Dank für Ihre Antwort, aber können Sie bitte einen Kommentar dazu hinzufügen, wie es funktioniert? Vielen Dank.
Deanna
(Tut mir leid, Sie ausgewählt zu haben, ich habe es als Prüfungsaudit erhalten. Zumindest habe ich bestanden .. :))
Deanna
7

Ähnlich wie bei der ersten Antwort, aber reines Java:

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

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

Ich ziehe es vor, sie als Ganzzahlen zu zählen, da dies zu besser lesbarem Code führt.

La-comadreja
quelle
7

Verwenden Sie in Python Folgendes , um zu sehen, wie viele iterierbare Elemente True sind sum(ganz einfach):

Konfiguration

import itertools

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

Aktueller Test

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

Ausgabe

(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
Aaron Hall
quelle
5

Wenn Sie nach der Lösung auf dem Papier (ohne Programmierung) suchen, sind K-Maps und Quine-McCluskey-Algorithmen genau das, wonach Sie suchen. Sie helfen Ihnen dabei, Ihre Boolesche Funktion zu minimieren.

In Ihrem Fall ist das Ergebnis

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

Wenn Sie dies programmgesteuert, mit einer nicht festgelegten Anzahl von Variablen und einem benutzerdefinierten "Schwellenwert" tun möchten, ist es ziemlich einfach und unkompliziert, einfach eine Liste von Booleschen Werten zu durchlaufen und das Auftreten von "true" zu zählen.

ioreskovic
quelle
1
Was bedeutet der Bar-Overhead? Ich bemerke, dass es die Liste runtergeht.
NameSpace
3
@NameSpace Es ist eine der IMO-Notationen, mit denen zu viele "nicht" ausgedrückt werden.
5

Ich möchte genau dann true zurückgeben, wenn 3 von 4 booleschen Werten true sind.

Angesichts der 4 booleschen Werte a, b, x, y wird diese Aufgabe in die folgende C-Anweisung übersetzt:

return (a+b+x+y) == 3;
Wolf
quelle
1
Schöne Falle. Dies setzt truegleich 1 voraus . Dies ist nicht in allen Sprachen / Fällen wahr (kein Wortspiel beabsichtigt). blogs.msdn.com/b/oldnewthing/archive/2004/12/22/329884.aspx
JensG
@JensG Du hast recht: Ich mache diese Annahme explizit. Thx :)
Wolf
4
((a^b)^(x^y))&((a|b)&(x|y))

ist was du willst. Grundsätzlich habe ich Ihren Code genommen und hinzugefügt, um zu überprüfen, ob tatsächlich 3 wahr und nicht 3 falsch sind.

Shujal
quelle
4

Eine Programmierfrage ohne Antwort mit Rekursion? Undenkbar!

Es gibt genug "genau 3 von 4 Wahrheiten" -Antworten, aber hier ist eine verallgemeinerte (Java) Version für "genau m von n Wahrheiten" (sonst lohnt sich eine Rekursion nicht wirklich), nur weil Sie können:

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

Dies könnte mit so etwas wie bezeichnet werden:

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

was zurückkehren sollte true(weil 5 von 8 Werten wie erwartet wahr waren). Nicht ganz zufrieden mit den Wörtern "wahr" und "falsch", aber ich kann mir momentan keinen besseren Namen vorstellen ... Beachten Sie, dass die Rekursion stoppt, wenn zu viele true oder zu viele falseWerte gefunden wurden.

Amos M. Carpenter
quelle
@ FélixSaparelli: Ich bin mir nicht sicher, ob "Wahrheit" hier zutrifft ... es würde so klingen, als wären Sie mit nur einer zufrieden true. Vielleicht so etwas wie containsNumberOfTrueValues(). Nebenbei: Smalltalks Benennung wäre dafür allerdings viel besser geeignet : doesArray: someBooleans startingAt: anIndex containNumberOfTrueValues: anExpectedNumber foundSofar: aNumberFoundSoFar. Wahrscheinlich zu lang für den Geschmack einiger Java-Entwickler, aber Smalltalker haben nie Angst vor der richtigen Benennung ;-)
Amos M. Carpenter
Das war meistens humorvoll. Und containsTruthbedeutet wörtlich "enthält eine unbekannte Menge an Wahrheit", also glaube ich, dass es ganz in Ordnung ist.
Félix Saparelli
3

Da die Lesbarkeit ein großes Problem darstellt, können Sie einen beschreibenden Funktionsaufruf verwenden (um eine der vorgeschlagenen Implementierungen einzuschließen). Wenn diese Berechnung an mehreren Stellen durchgeführt werden muss, ist ein Funktionsaufruf der beste Weg, um eine Wiederverwendung zu erreichen, und macht deutlich, was Sie genau tun.

bool exactly_three_true_from(bool cond1, bool cond2, bool cond3, bool cond4)
{
    //...
}
Graham Griffiths
quelle
3

In PHP wird es dynamischer (nur für den Fall, dass Sie die Anzahl der Bedingungen usw. ändern):

$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";
Bill Ortell
quelle
2
(((a AND b) OR (x AND y)) AND ((a XOR b) OR (x XOR y)))

Obwohl ich zeigen konnte, dass dies eine gute Lösung ist, ist Sam Hocevars Antwort später leicht zu schreiben und zu verstehen. In meinem Buch macht es das besser.

Jack Stout
quelle
1

Hier ist ein C # -Code, den ich gerade geschrieben habe, weil Sie mich inspiriert haben:

Es braucht eine beliebige Anzahl von Argumenten und wird Ihnen sagen, ob n von ihnen wahr sind.

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

und du nennst es so:

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

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

So können Sie jetzt 7/9 oder 15/100 testen, wie Sie möchten.

JPK
quelle