Warum ist F + F '= 1?

15

Ich habe die Funktion: $f(x,y,z,w) = wx + yz$

Ich fand seine Komplementfunktion: $f '(x,y,z,w) = w'y' + w'z' + x'y' + x'z'$

Ich muss zeigen, dass: aber ich kann nicht sehen, wie es geht. $f + f '=1$

Es scheint, als gäbe es nichts, was sich gegenseitig aufhebt.

Bearbeiten

Wie vorgeschlagen, habe ich jetzt den Satz von DeMorgan verwendet und Folgendes gefunden:

$f + f' = wx+yz+(w+y)'+(w+z)'+(x+y)'+(y+z)'$

Aber es scheint mir immer noch, dass nichts mich der Verwirklichung von näher bringt $f+f' = 1$

boolean-algebra Carl
quelle

6

Hinweis: Verwenden Sie DeMorgans Gesetz

Spehro Pefhany

11

Entweder f oder f 'muss 1

Chu

4

Sie haben nur 4 Eingänge. Wenn nichts anderes, können Sie einfach eine Wahrheitstabelle ausschreiben.

Das Photon

2

Spehro hat Recht, aber es hilft nicht, DeMorgan als ersten Schritt anzuwenden. Um den Hinweis von Spehro ein wenig zu erweitern: Die Lösung beinhaltet eine grundlegende Algebra, die DeMorgan als Schritt einschließt. Mit einfacher Algebra + DeMorgan können Sie die f'-Funktion in eine deutlich sichtbare Negation von f umwandeln. Ich kritzelte es auf ein Stück Papier und benötigte dafür nur 4 Schritte.

Mr. Snrub

1

@ Mr.Snrub der erste Schritt von "Ich fand seine Komplementfunktion" sollte sein (wx + yz) '

OrangeDog

4

Da hat Carl nett gefragt. Ausgangspunkt:

f (x, y, z, w) = w x + y z

$f(x,y,z,w)=wx+yz$ und

f' (x, y, z, w) = w' y' + w' z' + x' y' + x' z'

$f′(x,y,z,w)=w′y′+w′z′+x′y′+x′z′$

Führe die folgenden Schritte mit $f'$ : DeMorgan: DeMorgan, wiederum: Die rechte Seite von ist also nur die einfache Negation der rechten Seite von . Was ein wenig antiklimaktisch ist, da wir uns jetzt nur auf die Tatsache verlassen, dass jeder Ausdruck ist, was die Leute die ganze Zeit über gesagt haben , aber zumindest ein wenig liefert Boolesche Algebra Erklärung, warum das wahr ist.

f' (x, y, z, w) = w' (y' + z') + x' (y' + z')

$f′(x,y,z,w)=w′(y′+z′)+x′(y′+z′)$

f' (x, y, z, w) = (w' + x^{'}) (y' + z')

$f′(x,y,z,w)=(w′+x')(y′+z′)$

f' (x, y, z, w) = (w x)' (y z)^{'}

$f′(x,y,z,w)=(wx)′(yz)'$

f' (x, y, z, w) = (w x + y z)^{'}

$f′(x,y,z,w)=(wx + yz)'$

f^{'}

$f'$

f

$f$

x + x^{'} = 1

$x + x' = 1$

f + f^{'} = 1

$f+f'=1$

Mr. Snrub
quelle

Ich verstehe nicht, wie Sie zur zweiten Zeile gekommen sind, ohne Ihre endgültige Antwort zu übergeben. Ihre endgültige Antwort war mein erster Schritt: Es ist nur die Verneinung beider Seiten.

C. Lange

Die ersten beiden Zeilen sind die von OP gegebenen Formeln. Sie sind per Definition der Ausgangspunkt. Ich stimme voll und ganz zu, dass das Zeug später Teil der Ableitung der ersten beiden Formeln von OP gewesen sein könnte. Aber wir haben diese Informationen nicht; wir können es einfach nicht bestätigen.

Mr. Snrub

Verstanden - unter der Annahme, dass

und

in der Frage wie OP angegeben wurden, hat sie ausgeschrieben. Mein Verständnis war, dass OP bereits versucht hatte,

zu erweitern und nicht wusste, wohin es gehen sollte.

f

$f$

f^{'}

$f'$

f^{'}

$f'$

C. Lange

41

Der Punkt ist, es ist wirklich egal, welche Funktion $f()$ tatsächlich ist. Die wichtigste Tatsache ist, dass die Ausgabe ein einzelner Binärwert ist.

Es ist eine grundlegende Tatsache in der Booleschen Algebra, dass das Komplement eines Binärwerts immer dann wahr ist, wenn der Wert selbst falsch ist. Dies wird als Gesetz der ausgeschlossenen Mitte bezeichnet . Die ODER-Verknüpfung eines Wertes mit seinem Komplement ist also immer wahr, und die UND-Verknüpfung eines Wertes mit seinem Komplement ist immer falsch.

Es ist schön, dass Sie die spezifische Funktion $f'()$ ableiten konnten , aber das ist für die eigentliche Frage eigentlich irrelevant!

Dave Tweed
quelle

1

Dies wird als Gesetz der ausgeschlossenen Mitte bezeichnet .

BallpointBen

@BallpointBen: Danke! Ich habe es zu meiner Antwort hinzugefügt.

Dave Tweed

13

Alle vorherigen Antworten sind richtig und sehr gründlich. Eine einfachere Möglichkeit, dies zu erreichen, besteht darin, sich daran zu erinnern, dass in der Booleschen Algebra alle Werte entweder 0 oder 1 sein müssen.

Also ... entweder ist F 1, dann ist F '0 oder umgekehrt: F ist 0 und F' ist 1. Wenn Sie dann die boolesche ODER-Funktion anwenden: F + F ', haben Sie immer eine von beiden Begriffen 1, so wird das Ergebnis immer 1 sein.

Opifex
quelle

11

Meine Antwort ähnelt der von Dave Tweed, was bedeutet, dass ich sie auf eine formalere Ebene gestellt habe. Natürlich habe ich später geantwortet, aber ich habe beschlossen, es trotzdem zu posten, da jemand diesen Ansatz interessant finden könnte.

Die Beziehung, die Sie zu beweisen versuchen, ist unabhängig von der Struktur der Funktion $f$ da es sich tatsächlich um eine Tautologie handelt . Um zu erklären , was ich meine, schlage ich vor , eine Demonstration für einen allgemeinen, richtig gebildet, Booleschen Ausdruck $P$ in einer beliebigen Anzahl von Booleschen Variablen, sagen $n\in\Bbb N$ , $y_1,\ldots,y_n$ , wobei $y_i\in\{0,1\}$ für alle $i=1,\ldots,n$ .
Wir haben das $P(y_1,\ldots,y_n)\in\{0,1\}$ und betrachten Sie die folgenden zwei Mengen von Booleschen Werten für den $n$ dimensionalen Booleschen Vektor $(y_1,\ldots,y_n)$

\begin{aligned} Y & = {(y_{1}, \dots, y_{n}) \in {0, 1}^{n} | P (y_{1}, \dots, y_{n}) = 1} \\ \bar{Y} & = {(y_{1}, \dots, y_{n}) \in {0, 1}^{n} | P (y_{1}, \dots, y_{n}) = 0} \end{aligned}

$\begin{align} Y&=\{(y_1,\ldots,y_n)\in\{0,1\}^n|P(y_1,\ldots,y_n)=1\}\\ \bar{Y}&= \{(y_1,\ldots,y_n)\in\{0,1\}^n|P(y_1,\ldots,y_n)=0\} \end{align}$ Diese Menge ist eine Partition der gesamten Menge von Werten, die der Boolesche Eingabevektor annehmen kann, dh

Y \cup \bar{Y} = {0, 1}^{n}

$Y\cup\bar{Y}=\{0,1\}^n$ und

Y \cap \bar{Y} = \emptyset

$Y\cap\bar{Y}=\emptyset$ (die leere Menge), also

\begin{aligned} P (y_{1}, \dots, y_{n}) & = {\begin{cases} 0 & if (y_{1}, \dots, y_{n}) \in \bar{Y} \\ 1 & if (y_{1}, \dots, y_{n}) \in Y \end{cases} \\ ⇕ \\ P^{'} (y_{1}, \dots, y_{n}) & = {\begin{cases} 1 & if (y_{1}, \dots, y_{n}) \in \bar{Y} \\ 0 & if (y_{1}, \dots, y_{n}) \in Y \end{cases} \end{aligned}

$\begin{align} P(y_1,\ldots,y_n)&= \begin{cases} 0&\text{if }(y_1,\ldots,y_n)\in \bar{Y}\\ 1&\text{if }(y_1,\ldots,y_n)\in Y\\ \end{cases}\\ &\Updownarrow\\ P'(y_1,\ldots,y_n)&= \begin{cases} 1&\text{if }(y_1,\ldots,y_n)\in \bar{Y}\\ 0&\text{if }(y_1,\ldots,y_n)\in Y\\ \end{cases} \end{align}$ daher haben wir immer

P + P^{'} = 1 \forall (y_{1}, \dots, y_{n}) \in {0, 1}^{n}

$P+P'=1\quad\forall(y_1,\ldots,y_n)\in\{0,1\}^n$

Daniele Tampieri
quelle

11

Alles gute Antworten, die auf die eine oder andere Weise die nötige Rechtfertigung liefern. Da es sich um eine Tautologie handelt, ist es schwierig, einen Beweis zu erstellen, der nicht nur "es ist, was es ist!" Vielleicht hilft diese Methode dabei, das Problem aus einem weiteren, breiteren Blickwinkel anzugehen:

Erweitern Sie beide Anweisungen, um ihre redundanten Fälle einzuschließen, und entfernen Sie die wiederholten Fälle:

$𝑓=𝑤𝑥+𝑦𝑧\\ \ \ =wx\cdot(y'z'+y'z+yz'+yz)\ +\ yz\cdot(x'w'+x'w+xw'+xw)\\ \ \ =wxy'z'+wxy'z+wxyz'+wxyz\ +\ yzx'w'+yzx'w+yzxw'+yzxw\\ \ \ =wxy'z'+wxy'z+wxyz'+wxyz\ +\ yzx'w'+yzx'w+yzxw'$

und

$𝑓′=𝑤′𝑦′+𝑤′𝑧′+𝑥′𝑦′+𝑥′𝑧′\\ \ \ \ = w'y'\cdot(x'z'+x'z+xz'+xz)\ +\ 𝑤′𝑧′\cdot(x'y'+x'y+xy'+xy)\ +\\ \ \ \ \ \ \ \ \ \ x′y′\cdot(w'z'+w'z+wz'+wz)\ +\ x′𝑧′\cdot(w'y'+w'y+wy'+wy)\\ \ \ \ = w'y'x'z'+w'y'x'z+w'y'xz'+w'y'xz\ +\ 𝑤′𝑧′x'y'+𝑤′𝑧′x'y+𝑤′𝑧′xy'+𝑤′𝑧′xy\ +\\ \ \ \ \ \ \ \ \ \ x′y′w'z'+x′y′w'z+x′y′wz'+x′y′wz\ +\ x′𝑧′w'y'+x′𝑧′w'y+x′𝑧′wy'+x′𝑧′wy\\ \ \ \ = w'y'x'z'+w'y'x'z+w'y'xz'+w'y'xz\ +\ 𝑤′𝑧′x'y+𝑤′𝑧′xy\ +\\ \ \ \ \ \ \ \ \ \ x′y′wz'+x′y′wz\ +\ x′𝑧′wy$

Ich habe die Begriffe in einer konsistenten Reihenfolge gehalten, um die Ableitung deutlicher zu machen, aber sie könnten aus Gründen der Klarheit alphabetisch geschrieben werden. In jedem Fall ist der Punkt, dass $f$ OR sieben 4-Bit-Fälle und $f'$ OR neun verschiedene 4-Bit-Fälle sind. Zusammen ODER alle 16 4-Bit-Fälle, also auf $1$ reduzieren .

Heath Raftery
quelle

4

+1 Dies ist die einzige Antwort, die die wahre Absicht der OP-Frage beantwortet, nämlich eine Boolesche Algebra zu machen, anstatt theoretische Argumente zu liefern. Beachten Sie jedoch, dass es nach meinem Kommentar zum OP eine elegantere Lösung gibt. Dieses Problem kann gelöst werden, ohne dass redundante Fälle hinzugefügt werden müssen.

Mr. Snrub

Das würde ich auch sehr gerne sehen. Das heißt, wenn Sie die Zeit und die Großzügigkeit zu tun haben it.t

Carl

8

F + F '= 1 bedeutet, dass Sie zeigen müssen, dass unabhängig vom Zustand der 4 Eingänge ODER das Ergebnis dieser 2 immer 1 ergibt.

Ein paar Minuten in Excel zeigen, dass dies tatsächlich der Fall ist. Sie können "NOT ()" verwenden, um in Excel zwischen 0 und 1 zu invertieren.

F = W * X + Y * Z

F '= W' * Y '+ W' * Z '+ X' * Y '+ X' * Z '

Wenn Sie möchten, dass F falsch ist, z. B. wenn Sie W und Y auf niedrig setzen, haben Sie F 'auf wahr gesetzt. Wenn Sie X und Z niedrig machen, haben Sie auch F "wahr gemacht, das gleiche gilt für den Austausch von Paaren.

Umleiten
quelle

2

"F + F '= 1 bedeutet, dass Sie zeigen müssen, dass unabhängig vom Zustand der 4 Eingänge ODER das Ergebnis dieser 2 immer 1 ergibt." Nein, das tut es nicht. Es bedeutet lediglich, dass Sie zeigen müssen, dass unabhängig von der Ausgabe (die nur zwei Möglichkeiten haben kann) und der entsprechenden Ausgabe ihres Komplements die Beziehung gilt. Die Eingänge sind ebenso wie die Funktion irrelevant. Die einzige Wahrheitstabelle, die benötigt wird, ist die, die die Beziehung zwischen der Ausgabe der Funktion und der Ausgabe von irgendetwas zeigt, das sich als ihre Ergänzung qualifiziert.

Chris Stratton

@ChrisStratton, das hängt davon ab, ob die Frage zeigt, dass das ODER einer Funktion und ihres Komplements immer 1 ist (was per Definition des Komplements trivial ist) oder ob die vorgeschlagene Funktion F 'tatsächlich das Komplement von F ist. From OP Formulierung, ich denke, sie hatten ein 2-teiliges Problem. Teil A: Finde die Komplementfunktion. Teil B: Zeigen Sie, dass es sich tatsächlich um die Ergänzung handelt.

Das Photon

0

$+$ $′$

 A | B | A + B
---------------
 0 | 0 |   0
 1 | 0 |   1
 0 | 1 |   1
 1 | 1 |   1

 A | A′| A + A′
----------------
 0 | 1 |   1
 1 | 0 |   1

$∴ ∀f. f + f′ = 1$

OrangeDog
quelle

Warum ist F + F '= 1?

Antworten: