Saya memiliki fungsi:
Saya menemukan fungsi komplemennya adalah:
Saya harus menunjukkan bahwa: tetapi saya tidak bisa melihat bagaimana melakukannya.
Sepertinya tidak ada yang membatalkan satu sama lain.
Edit
Seperti yang disarankan, saya sekarang menggunakan teorema DeMorgan dan menemukan ini:
Tapi sepertinya masih ada yang membuat saya lebih dekat dengan realisasi
boolean-algebra
Carl
sumber
sumber
Jawaban:
Karena Carl bertanya dengan baik. Titik awal:f(x,y,z,w)=wx+yz
dan
f'(x,y,z,w)=w'y'+w'z'+x'y'+x'z'
Ambil langkah-langkah berikut denganf′ :
f'(x,y,z,w)=w'(y'+z')+x'(y'+z')
f'(x,y,z,w)=(w'+x′)(y'+z')
DeMorgan:
f'(x,y,z,w)=(wx)'(yz)′
DeMorgan, sekali lagi:
f'(x,y,z,w)=(wx+yz)′
Jadi sekarang sisi kananf′ hanyalah negasi sederhana dari sisi kananf . Yang sedikit anti-klimaks, karena sekarang kita hanya mengandalkan fakta bahwa setiap ekspresi x+x′=1 , yang telah dikatakan orang selama ini tentang f+f′=1 , tapi setidaknya itu memberikan sedikit Penjelasan aljabar Boolean mengapa itu benar.
sumber
The point is, it really doesn't matter what the functionf() actually is. The key fact is that its output is a single binary value.
It is a fundamental fact in Boolean algebra that the complement of a binary value is true whenever the value itself is false. This is known as the law of excluded middle. So ORing a value with its complement is always true, and ANDing a value with its complement is always false.
It's nice that you were able to derive the specific functionf′() , but that's actually irrelevant to the actual question!
sumber
All previous answers are correct, and very much in depth. But a simpler way to approach this might be to remember that in boolean algebra, all values must be either 0 or 1.
So... either F is 1, then F' is 0, or the other way around: F is 0 and F' is 1. If you then apply the boolean OR-function: F + F', you will always have one of both terms 1, so the result will always be 1.
sumber
My answer is similar to the one of Dave Tweed, meaning that I put it on a more formal level. I obviously answered later, but I decided to nevertheless post it since someone may find this approach interesting.
The relation you are trying to prove is independent from the structure of the functionf since it is, as a matter of fact, a tautology. To explain what I mean, I propose a demonstration for a general, correctly formed, Boolean expression P in an arbitrary number of Boolean variables, say n∈N , y1,…,yn , where yi∈{0,1} for all i=1,…,n .P(y1,…,yn)∈{0,1} and consider the following two sets of Boolean values for the n -dimensional Boolean vector (y1,…,yn)
YY¯={(y1,…,yn)∈{0,1}n|P(y1,…,yn)=1}={(y1,…,yn)∈{0,1}n|P(y1,…,yn)=0}
These set are a partition of the full set of values the input Boolean vector can assume, i.e. Y∪Y¯={0,1}n and Y∩Y¯=∅ (the empty set), thus
P(y1,…,yn)P′(y1,…,yn)={01if (y1,…,yn)∈Y¯if (y1,…,yn)∈Y⇕={10if (y1,…,yn)∈Y¯if (y1,…,yn)∈Y
therefore we always have
P+P′=1∀(y1,…,yn)∈{0,1}n
We have that
sumber
All good answers that provide the necessary justification in one way or the other. Since it is a tautology, it's hard to create a proof that doesn't just result in "it is what it is!". Perhaps this method help tackle it from yet another, broader angle:
Expand both statements to include their redundant cases, and the remove the repeated cases:
and
I've kept the terms in consistent order to make the derivation more obvious, but they could be written alphabetically to be clearer. In any case, the point is thatf ORs seven 4-bit cases, and f′ ORs nine, distinct 4-bit cases. Together they OR all sixteen 4-bit cases, so reduce to 1 .
sumber
F + F' = 1 means that you have to show that no matter the state of the 4 inputs, OR'ing the result of those 2 always result in 1,
A few minutes in excel shows it is indeed the case. You can use "NOT()" to invert between 0 and 1 in excel.
F = W * X + Y * Z
F' = W' * Y' + W' * Z' + X' * Y' + X' * Z'
As to why this is the case, If you want F to be false, e.g. setting W and Y low, you just made F' true. If you make X and Z low, you also made F" true, same for swapping there pairs.
sumber
By simple definition of+ (OR) and ' (NOT)
sumber