IF-Abfrage

tech-house

Hi, wie lässt sich überprüfen, ob von vier Bool-Variablen eine ungerade Anzahl wahr ist? Es dürfen nur drei Operatoren verwendet werden.

Beispiel: falsch wahr falsch falsch => wahr

Finnegan

@tech-house du könntest die bools zu int casten und dann aufsummieren. static_cast<int>(true) == 1 und static_cast<int>(false) == 0.

tech-house

Ne, sind ja mehr als 3 Operatoren ...

Alleine die Addition 3 und dann noch der Vergleichsoperator (4). Und dazu habe ich noch nicht mal die Cast-Operatoren gezählt.

tech-house

Zumindest eine Möglichkeit hab ich schon herausgefunden:

((a != b) != c) != d

#include <iostream>
using namespace std;

int main() {
  bool a = false;
  bool b = true;
  bool c = false;
  bool d = false;
  cout << (((a != b) != c) != d) << endl;
  d = true;
  cout << (((a != b) != c) != d) << endl;
  return 0;
}

Es gibt aber noch eine.

DocShoe

Mir fallen zwei Lösungen ein:

int main()
{
   bool const b1 = false;
   bool const b2 = false;
   bool const b3 = true;
   bool const b4 = false;

   // true konvertiert implizit zu 1
   unsigned int const result = b1 + b2 + b3 +b4;
   bool const odd1 = result % 2 != 0; // bei Divisionsrest 1 ungerade

   // XOR Verknüpfung
   bool const odd2 = b1 ^ b2 ^ b3 ^ b4;
}

hustbaer

Du kannst in diesem Fall ^ und != beliebig gegeneinander vertauschen. Und wie du die Klammern setzt ist auch egal.

Es gehen also z.B. auch:

if (a ^ b ^ c ^ d) {
    ...
}
if ((a ^ b) ^ (c ^ d)) {
    ...
}
if ((a ^ b) != (c ^ d)) {
    ...
}
if ((a != b) ^ (c != d)) {
    ...
}

tech-house

Ich dachte, das logische XOR wäre in C++ !=, und das ^ gäbe es gar nicht...

   // true konvertiert implizit zu 1
   unsigned int const result = b1 + b2 + b3 + b4;
----------------------------------1.---2.---3.---
   bool const odd1 = result % 2 != 0; // bei Divisionsrest 1 ungerade
----------------------------4.--5.--------------- ...

5 Operatoren!

tech-house

Außerdem ... wäre eine Addition auf der untersten Ebene sehr langsam.

DocShoe

@tech-house sagte in IF-Abfrage:

Außerdem ... wäre eine Addition auf der untersten Ebene sehr langsam.

Das ist eine bloße Vermutung, die ich so nicht unterschreiben würde. Compiler optimieren sehr gut und erkennen teilweise schon die Absicht des Programms. Es würde mich nicht wundern, wenn aktuelle Compiler für die XORund Addition sehr ähnlichen Code mit minimalen Laufzeitunterschieden produzieren. Sehr langsam ist das mit Sicherheit nicht.

wob

@DocShoe Genau. Clang 17.0.1 mit -O3 produziert sogar identischen Code!

Siehe https://gcc.godbolt.org/z/P89Gj5Mox

*john 0

Das ist doch eine typische Übungsaufgabe bei dem man mit Hilfe einer Wahrheitstabelle, und Nutzung der disjunktiven bzw. konjunktiven Normalform die entsprechende Logik ausrechen kann bzw. soll. Dazu sollte man die De-morganschen Gesetze kennen.

Die disjunktive Normalform erhält man, in dem man die für jedes wahre Ergebnis die Eingänge „und“ verknüpft, die konjuktive Normalform erhält für jedes „falsche“ Ergebnis die Eingänge oder verknüpft. Die einzelnen Terme werden bei der disjunktiven Normalform „oder“ verknüpft, und für die konjunktive Normalform „und“ verknüpft.

Ich habe das jetzt für die disjunktive Normalform einmal ausgeführt (englische Schreibweise).

A	B	C	D	Ergebnis	Min Term
0	0	0	0	0
0	0	0	1	1	$\bar{\mathrm{A}}\bar{\mathrm{B}}\bar{\mathrm{C}}\mathrm{D}$
0	0	1	0	1	$\bar{\mathrm{A}}\bar{\mathrm{B}}\mathrm{C}\bar{\mathrm{D}}$
0	0	1	1	0
0	1	0	0	1	$\bar{\mathrm{A}}\mathrm{B}\bar{\mathrm{C}}\bar{\mathrm{D}}$
0	1	0	1	0
0	1	1	0	0
0	1	1	1	1	$\bar{\mathrm{A}}\mathrm{B}\mathrm{C}\mathrm{D}$
1	0	0	0	1	$\mathrm{A}\bar{\mathrm{B}}\bar{\mathrm{C}}\bar{\mathrm{D}}$
1	0	0	1	0
1	0	1	0	0
1	0	1	1	1	$\mathrm{A}\bar{\mathrm{B}}\mathrm{C}\mathrm{D}$
1	1	0	0	0
1	1	0	1	1	$\mathrm{A}\mathrm{B}\bar{\mathrm{C}}\mathrm{D}$
1	1	1	0	1	$\mathrm{A}\mathrm{B}\mathrm{C}\bar{\mathrm{D}}$
1	1	1	1	0

Das ergibt dann für die disjunktive Normalform
$X=\bar{\mathrm{A}}\bar{\mathrm{B}}\bar{\mathrm{C}}\mathrm{D}+\bar{\mathrm{A}}\bar{\mathrm{B}}\mathrm{C}\bar{\mathrm{D}}+\bar{\mathrm{A}}\mathrm{B}\bar{\mathrm{C}}\bar{\mathrm{D}}+\bar{\mathrm{A}}\mathrm{B}\mathrm{C}\mathrm{D}+\mathrm{A}\bar{\mathrm{B}}\bar{\mathrm{C}}\bar{\mathrm{D}}+\mathrm{A}\bar{\mathrm{B}}\mathrm{C}\mathrm{D}+\mathrm{A}\mathrm{B}\bar{\mathrm{C}}\mathrm{D}+\mathrm{A}\mathrm{B}\mathrm{C}\bar{\mathrm{D}}$
Das ist nun mit Hilfe der Rechenregeln zu vereinfachen.

Quiche Lorraine

@john-0 sagte in IF-Abfrage:

Das ist nun mit Hilfe der Rechenregeln zu vereinfachen.

@tech-house schrieb:

Es dürfen nur drei Operatoren verwendet werden.

Quiche Lorraine

@john-0
BTW, warum denn eine Wahrheitstabelle nicht fest eincodieren? Ist ja relativ klein.

#include <iostream>

int main()
{
    static constexpr bool Table[2][2][2][2] = { 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0 };
    bool a = true;
    bool b = false;
    bool c = true;
    bool d = true;

    std::cout << Table[a][b][c][d] << std::endl;
    return 0;
}

*john 0

@Quiche-Lorraine sagte in IF-Abfrage:

@john-0
BTW, warum denn eine Wahrheitstabelle nicht fest eincodieren? Ist ja relativ klein.

Der Ansatz kommt aus der Digitalelektronik, d.h. man will die Schaltung mit NANDs oder NORs aufbauen bzw. mit VHDL o.ä. in einem FPGA umsetzen, weil man da nur Gatterlaufzeiten hat. Mit denselben Methoden kann man aber auch die Abfragen vereinfachen. Wenn man das nun nicht ausrechnen will, kann man das natürlich mit einer Tabelle umsetzen.

Quiche Lorraine

@john-0 sagte in IF-Abfrage:

Mit denselben Methoden kann man aber auch die Abfragen vereinfachen.

Und ich erinnere mich noch düster an die KV Diagramme

tech-house

Ihr habt alle recht. Ich möchte mir einen kleinen Computer selber basteln, und dafür brauche ich das.

Das XOR war schon ganz schön anstrengend (https://de.wikipedia.org/wiki/Exklusiv-Oder-Gatter#Synthese).

PS. Den KV-Würfel verstehe ich nicht.

*john 0

@Quiche-Lorraine sagte in IF-Abfrage:

Und ich erinnere mich noch düster an die KV Diagramme

Darauf bin ich vorhin als ich das alte Uni-Skript aus dem Regal holte auch gestoßen. Die disjunktive Normalform war mir noch im Gedächtnis, die KV-Diagramme nicht mehr.

Finnegan

@john-0 sagte in IF-Abfrage:

$X=\bar{\mathrm{A}}\bar{\mathrm{B}}\bar{\mathrm{C}}\mathrm{D}+\bar{\mathrm{A}}\bar{\mathrm{B}}\mathrm{C}\bar{\mathrm{D}}+\bar{\mathrm{A}}\mathrm{B}\bar{\mathrm{C}}\bar{\mathrm{D}}+\bar{\mathrm{A}}\mathrm{B}\mathrm{C}\mathrm{D}+\mathrm{A}\bar{\mathrm{B}}\bar{\mathrm{C}}\bar{\mathrm{D}}+\mathrm{A}\bar{\mathrm{B}}\mathrm{C}\mathrm{D}+\mathrm{A}\mathrm{B}\bar{\mathrm{C}}\mathrm{D}+\mathrm{A}\mathrm{B}\mathrm{C}\bar{\mathrm{D}}$

Danke, dass du die Notation verwendet hast, ich finde die immer extrem gut lesbar. Die ist irgendwie bei den Elektrotechnikern beliebt, aber die Mathematiker wollten damals nix davon wissen und haben auf dieses unsägliche $\land$ / $\lor$ -Hütchenspiel bestanden, bei dem man Flimmern vor den Augen bekommt (ich zumindest).... aber ich kann das schon verstehen - man muss schliesslich mit beidem klar kommen. Ich war aber bei viele Zeilen langen Ausdrücken nie so schnell und hab so wenig Fehler gemacht, wie mit dieser Digitaltechnik-Notation

Edit: Dein Audruck da oben könnte auch so aussehen, wenn ich mich nicht vertippt hab (grusel!):

$X=\lnot A \land \lnot B \land \lnot C \land D \lor \lnot A \land \lnot B \land C \land \lnot D \lor \lnot A \land B \land \lnot C \land \lnot D \lor \lnot A \land B \land C \land D$
$\lor A \land \lnot B \land \lnot C \land \lnot D \lor A \land \lnot B \land C \land D \lor A \land B \land \lnot C \land D \lor A \land B \land C \land \lnot D$

tech-house

@Finnegan sagte in IF-Abfrage:

Dein Audruck da oben könnte auch so aussehen, wenn ich mich nicht vertippt hab (grusel!)

Eii, das Forum/der Browser scheint damit Darstellungsprobleme zu haben.^^

Edit: Man darf aber auch Klammern setzen, falls es sonst zu unübersichtlich wird ...

Finnegan

@tech-house sagte in IF-Abfrage:

@Finnegan sagte in IF-Abfrage:

Dein Audruck da oben könnte auch so aussehen, wenn ich mich nicht vertippt hab (grusel!)

Eii, das Forum/der Browser scheint damit Darstellungsprobleme zu haben.^^

Ja, ich habs grad noch auf 2 Zeilen aufgesplittet, der Latex-Renderer scheint einfach abzuschneiden, wenns zu lang wird (zumindest mit $latex$). Bei mir siehts jetzt richtig aus ... und es ist schon ein Zeichen für eine bessere Notation, wenn man es auch ohne die eigentlich nicht notwendigen Klammern gut lesen kann.