Poängen är att det verkligen spelar ingen roll vilken funktion \ $ f () \ $ faktiskt är.Det viktigaste faktum är att dess produktion är ett enda binärt värde.

Det är ett grundläggande faktum i boolesk algebra att komplementet till ett binärt värde är sant när värdet i sig är falskt.Detta är känt som lagen om utesluten mitt.Så att ORing ett värde med dess komplement är alltid sant, och ANDing ett värde med dess komplement är alltid falskt.

Det är trevligt att du kunde härleda den specifika funktionen \ $ f '() \ $ , men det är faktiskt irrelevant för själva frågan!

Alla tidigare svar är korrekta och mycket djupgående. Men ett enklare sätt att närma sig detta kan vara att komma ihåg att i boolesk algebra måste alla värden vara antingen 0 eller 1.

Så ... antingen F är 1, då är F '0 eller tvärtom: F är 0 och F' är 1. Om du sedan tillämpar den booleska OR-funktionen: F + F ', kommer du alltid att ha en av båda termerna 1, så resultatet blir alltid 1.

Mitt svar liknar svaret från Dave Tweed, vilket innebär att jag lägger det på en mer formell nivå. Jag svarade uppenbarligen senare, men jag bestämde mig för att ändå lägga upp det eftersom någon kan tycka att den här metoden är intressant.

Förhållandet du försöker bevisa är oberoende av strukturen för funktionen \ $ f \ $ eftersom det faktiskt är en tautologi . För att förklara vad jag menar föreslår jag en demonstration för ett allmänt, korrekt utformat, booleskt uttryck \ $ P \ $ i ett godtyckligt antal booleska variabler, säg \ $ n \ i \ Bbb N \ $ , \ $ y_1, \ ldots, y_n \ $ , där \ $ y_i \ i \ {0,1 \} \ $ för alla \ $ i = 1, \ ldots, n \ $ .
Vi har den \ $ P (y_1, \ ldots, y_n) \ i \ {0,1 \} \ $ och överväger följande två uppsättningar booleska värden för \ $ n \ $ -dimensionell boolesk vektor \ $ (y_1, \ ldots, y_n) \ $ $$ \ 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} $$ Dessa uppsättningar är en partition av hela uppsättningen värden som den booleska vektorn kan anta, dvs. \ $ Y \ cup \ bar {Y} = \ {0,1 \} ^ n \ $ och \ $ Y \ cap \ bar {Y} = \ emptyset \ $ (den tomma uppsättningen), alltså $$ \ begin {align} P (y_1, \ ldots, y_n) & = \ begin {cases} 0& \ text {if} (y_1, \ ldots, y_n) \ i \ bar {Y} \\ 1& \ text {if} (y_1, \ ldots, y_n) \ i Y \\ \ end {cases} \\ & \ Updownarrow \\ P '(y_1, \ ldots, y_n) & = \ begin {cases} 1& \ text {if} (y_1, \ ldots, y_n) \ i \ bar {Y} \\ 0& \ text {if} (y_1, \ ldots, y_n) \ i Y \\ \ end {cases} \ end {align} $$ därför har vi alltid $$ P + P '= 1 \ quad \ forall (y_1, \ ldots, y_n) \ i \ {0,1 \} ^ n $$

Alla bra svar som ger den nödvändiga motiveringen på ett eller annat sätt. Eftersom det är en tautologi är det svårt att skapa ett bevis som inte bara resulterar i "det är vad det är!". Kanske hjälper den här metoden att ta itu med den från ännu en bredare vinkel:

Expandera båda uttalandena för att inkludera deras överflödiga fall och ta bort de upprepade fallen:

\ $ = + \\ \ \ = 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' \ $

och

\ $ ′ = ′ ′ + ′ ′ + ′ ′ + ′ ′ \\ \ \ \ = 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 \ $

Jag har hållit villkoren konsekvent för att göra härledningen mer uppenbar, men de kan skrivas alfabetiskt för att vara tydligare. I vilket fall som helst är poängen att \ $ f \ $ ORs sju 4-bitars fall och \ $ f '\ $ ELLER nio, distinkta 4-bitars fall. Tillsammans ELLER alla sexton 4-bitars fall, så reducera till \ $ 1 \ $ .

F + F '= 1 betyder att du måste visa att oavsett tillståndet för de 4 ingångarna, ELLER att resultatet av dessa 2 alltid resulterar i 1,

Några minuter i excel visar att det verkligen är fallet. Du kan använda "NOT ()" för att invertera mellan 0 och 1 i excel.

F = W * X + Y * Z

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

Varför detta är fallet, Om du vill att F ska vara falsk, t.ex.genom att ställa in W och Y lågt gjorde du precis F 'sant.Om du gör X och Z låg gjorde du också F "sant, samma för att byta där par.

Eftersom Carl frågade snyggt. Utgångspunkt: $$ f (x, y, z, w) = wx + yz $$ och $$ f ′ (x, y, z, w) = w′y ′ + w′z ′ + x′y ′ + x′z ′ $$

Ta följande steg med \ $ f '\ $ : $$ 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, igen: $$ f ′ (x, y, z, w) = (wx + yz) ' $$ Så nu är den högra sidan av \ $ f '\ $ bara den enkla negationen av den högra sidan av \ $ f \ $ . Vilket är lite anti-klimaktiskt, eftersom vi nu bara litar på det faktum att alla uttryck \ $ x + x '= 1 \ $ , vilket är vad människor har varit säger hela tiden om \ $ f + f '= 1 \ $ , men åtminstone ger det en liten boolesk-algebra förklaring till varför det är sant.

Genom enkel definition av \ $ + \ $ (OR) och \ $ ′ \ $ (INTE)

  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 \ $