How to construct XOR gate using only 4 NAND gate?

Assuming we are on the right track, we need two NAND gates to produce X and Y. So that leaves us with only one gate to produce a formula Z that combined with A ... ComputerScienceStackExchangeisaquestionandanswersiteforstudents,researchersandpractitionersofcomputerscience.Itonlytakesaminutetosignup. Signuptojointhiscommunity Anybodycanaskaquestion Anybodycananswer Thebestanswersarevotedupandrisetothetop Home Public Questions Tags Users Companies Unanswered Teams StackOverflowforTeams –Startcollaboratingandsharingorganizationalknowledge. CreateafreeTeam WhyTeams? Teams CreatefreeTeam Teams Q&Aforwork Connectandshareknowledgewithinasinglelocationthatisstructuredandeasytosearch. Learnmore HowtoconstructXORgateusingonly4NANDgate? AskQuestion Asked 7years,1monthago Modified 3years,10monthsago Viewed 226ktimes 21 12 $\begingroup$ xorgate,nowIneedtoconstructthisgateusingonly4nandgate about 000 011 101 110 thexor=(aandnotb)or(notaandb),whichis \begin{split}\overline{A}{B}+{A}\overline{B}\end{split} Iknowtheanswerbuthowtogetthegatediagramfromtheformula? EDIT Imeanintuitively,tome,IshouldgetthisoneifIdoitstepbystepfollowedbythedefinitionxor=(aandnotb)or(notaandb). \begin{split}\overline{\overline{\overline{A}{B}}\cdot\overline{{A}\overline{B}}}\end{split} andxorwillbeconstructedwith5nandgates(first#1imagebelow) myquestionismorelike:imaginethefirstpersoninhistoryfigureoutthisformula,howcanheorshe(thethinkingprocess)getthe4nandsoltuionfromthisformula,stepbystep. \begin{split}\overline{A}{B}+{A}\overline{B}\end{split} logicboolean-algebra Share Cite Improvethisquestion Follow editedAug24,2018at6:13 Timeless askedJun7,2015at8:05 TimelessTimeless 75511goldbadge88silverbadges1515bronzebadges $\endgroup$ 5 $\begingroup$ I'msureyouknowhowtotakeaXOR(oranyotherfunction)andconvertittoanequivalentcircuitthatonlyusesNAND(whichisalwayspossible,sinceNANDiscomplete).Howeverifyouaskhowtoreducethisformulatousingonly4NANDs,oringeneral,lessthan$k$NANDs,andwhetheritisevenpossibletoobtainanequivalentcircuitwith$\lek$NANDs--I'mnotsurethereisaneasyanswerforthat. $\endgroup$ – RanG. Jun7,2015at16:05 $\begingroup$ Belowaretwoanswerstotheproblem.Mineisquitecandidaboutthefactthatyoucandesign(aposteriori)awaytofindthedesiredconstructionfromknowingthefinalresultinadvance,whichwasgiveninthequestionandisavailableontheInternet.Itisclearlythesimplerwayofdoingthing,absurdasitmayseem,shortofgivingageneralprocedure,whichnoanswerisdoing.Hence,Iaminterestedinknowingwhyvoterspreferoneanswerovertheother,whentheydo...ifyouwilltakethetimeforashortcomment.Thanksinadvance. $\endgroup$ – babou Jun8,2015at9:43 $\begingroup$ Thisquestionisupforbeingclosedasunclear.IthinkitmightbefairlyclearwhattheOPisasking,andmorei8nteresting,iftheOPbotheredtoreacttothevarioususerswhotrytoanswerhim, $\endgroup$ – babou Jun14,2015at11:21 $\begingroup$ electronics.stackexchange.com/questions/84714/…--thisquestionismoregeneral,theanswersgivemoreinformationonageneralapproachtosolvingthisproblem,andthisanswerelectronics.stackexchange.com/a/84803showshowtoderiveNANDrepresentationfortheXORoperator $\endgroup$ – AntonTrunov Nov12,2015at13:46 $\begingroup$ Iplayedaroundwithsomesimilarproblemsandjustwroteaprogramthattriedeverythingsystematically...Fineforuptofourinputs,wherethereareonly65,536possiblefunctions.Forslightlymorecomplicatedcircuitsthisalsoallowedmetooptimisedelays,andtofindoptimalcircuitsifoneortwoinputswereavailablelaterthanothers.Circuitswith5inputs=2^32possiblefunctionswouldprobablybedoableusingbruteforce. $\endgroup$ – gnasher729 Aug11,2016at16:20 Addacomment  |  7Answers 7 Sortedby: Resettodefault Highestscore(default) Datemodified(newestfirst) Datecreated(oldestfirst) 17 $\begingroup$ Fromthatformula?Itcanbedone.Butit'seasiertostartwiththisone:(usingadifferentnotationhere) a^b=~(a&b)&(a|b) Ok,nowwhat?Eventuallyweshouldderive~(~(~(a&b)&a)&~(~(a&b)&b))(whichlookslikeithas5NANDs,butjustlikethecircuitdiagramithasasub-expressionwhichisusedtwice). Somakesomethingthatlookslike~(a&b)&a(andthesamethingbutwithabattheend)andhopethatit'llstickaround:(anddistributesoveror) (~(a&b)&a)|(~(a&b)&b) Prettyclosenow,justapplyDeMorgantoturnthatmiddleorintoanand: ~(~(~(a&b)&a)&~(~(a&b)&b)) Andthat'sit. Share Cite Improvethisanswer Follow answeredJun7,2015at9:01 haroldharold 1,8131111silverbadges1111bronzebadges $\endgroup$ Addacomment  |  9 $\begingroup$ Ithinkyouareaskingforthisproof: A^B=(!A)B+A(!B) =!!((!A)B)+!!(A(!B)) =!(!!A+!B)+!(!A+!!B) =!(A+!B)+!(!A+B) =!((A+!B)(!A+B)) =!(A(!A)+AB+(!A)(!B)+B(!B)) =!(AB+(!A)(!B)) =!(AB)(!(!A)(!B)) =!(AB)(!!A+!!B) =!(AB)(A+B) =!(AB)A+!(AB)B =!!(!(AB)A+!(AB)B) =!((!(!(AB)A))(!(!(AB)B))) Althoughapparentlythereare5NANDsusedintheresultantequation,buttheduplicate!(AB)willbeusedonlyoncewhenyouaredesigningitscircuit. Share Cite Improvethisanswer Follow answeredMay12,2016at20:51 MuntasirMuntasir 20622silverbadges44bronzebadges $\endgroup$ 2 $\begingroup$ Iamsorry,butisn'tA^BmeansAANDB?ItseemsyourintentionwastoproofXORwhichsymbolshouldbe⊕or⊻.HoweverthisproofwaswhatIreallylookedfor,thankyou! $\endgroup$ – osiixy Feb15,2019at9:53 1 $\begingroup$ @oslixy:^isusedforbitwiseXORintheClanguage.Herehe'susingmultiplication(writtenasjuxtaposition)forAND,whichisquitecommon. $\endgroup$ – wnoise Dec6,2020at19:14 Addacomment  |  6 $\begingroup$ Sinceyoualreadyhavethediagramanswer,easilyawailablefrom wikipediabytypingyouquestiontitleinGoogle,asa.pngdiagram identicaltoyours,itshouldbeeasyforyoutofindtheformulaby extractingitfromthatdiagram.GiventhedefinitionNANDas $\text{NAND}(A,B)=\overline{AB}\;$: Theleftmostgategives$C=\overline{AB}$; Thetopgategives$D_1=\overline{AC}$; Thetopgategives$D_2=\overline{BC}$,astheNANDis commutatveliketheAND; Therightmostgategives$E=\overline{D_1D_2}$. Puttingitalltogetherwefirstnotethat $C=\overline{AB}=\overlineA+\overlineB$ $\begin{align} \overline{D_1}&=AC\\ &=A(\overlineA+\overlineB)\\ &=A\overlineA+A\overlineB\\ &=0+A\overlineB\\ &=A\overlineB\\ \end{align}$ Similarly:$\overline{D_2}=B\overlineA$ Thus $\begin{align} E&=\overline{D_1D_2}\\ &=\overline{D_1}+\overline{D_2}\\ &=A\overlineB+B\overlineA \end{align}$ WhichispreciselythedefinitionofXOR.Youmayjustreverseallthisifyouwanttostartfromyourinitialdata,ratherthanjustchecktheanswer. Findingtheanswerwithnopriorknowledge Thisisintendedtoanswertheexplicitrequest,addedasanedittothequestion,forawayoffindingthesolutionfromscratch.Giventhatthequestionisaboutathoughtprocess,Iamgivingalldetails. Iwouldtrytorelyontheconstraintsoftheproblem(only4NANDgates)andonitssymmetrybetween$A$and$B$whichmaybepreservedinthesolution. OnethingIknow(assuminginformationflowsfromlefttorightasinthequestiondiagrams)isthattheremustbearightmostNANDgatethatproducesthedesiredanswer$\text{XOR}(A,B)=A\overlineB+B\overlineA\;$. Sowecantrytoguesswhatkindofinputtothisgatewouldproducethedesiredoutput. Weknowthat$\text{NAND}(X,Y)=\overline{XY}=\overlineX+\overline Y\;$ Unifyingthislastformulawiththeresult wehavetoget,weobtain: $\overlineX=A\overlineB\;$,thus$X=\overline{A\overlineB}=\overlineA+B\;$. andsymetrically$Y=\overline{\overlineAB}=A+\overlineB\;$. Notethatthisisonlythesimplestpossibility.Thereareotherpairsofinputsthatwouldgivethedesiredresult,becausewearenotunifyinginafreealgebra,sinceNANDhasequationalproperties.Butwetrythatforastart. Theproblemisnowwhetherwecanobtainboth$X$and$Y$from$A$and $B$with3NANDgates. Wecouldtrytorepeattheunificationprocedure(Idid),butthiswill naturallyleadustousingfourmoregates,hencetoa5gatessolution. Assumingweareontherighttrack,weneedtwoNANDgatestoproduce $X$and$Y$.Sothatleavesuswithonlyonegatetoproduceaformula $Z$thatcombinedwith$A$or$B$willprovidetheinputforthesetwo intermediategates. Giventhatwehavetoprovidesymetricallyfor$X$and$Y$,wecan expectthat$Z$shouldbesymmetricin$A$and$B$.Hencethis leftmostNANDgateshouldtakeboth$A$and$B$asinput. ThisfirstNANDgate,with$A$and$B$asinput,producesasoutput: $Z=\text{NAND}(A,B)=\overline{AB}=\overlineA+\overlineB\;$ Now,wehavetocheckwhethercombining$Z$withitself,$A$,$B$,0, or1throughaNANDgatecanproduce$X$,andalso$Y$. Weknowthatcombiningavaluewithitself,0or1throughaNANDgate iseithertheidentityfunctionorthenegation.Sotheonlyremaining candidatesare$A$and$B$. Itiseasytocheckthat $\begin{align} \text{NAND}(Z,A)&=\overline{ZA}\\ &=\overline{\overline{AB}\;A}\\ &=\overline{(\overlineA+\overlineB)\;A}\\ &=\overline{\overlineAA+\overlineBA}\\ &=\overline{0+\overlineBA}\\ &=\overline{\overlineBA}\\ &=\overline{A\overlineB}\\ &=X \end{align}$ Similarly$\text{NAND}(Z,B)=Y$ Hencewecancomposethesefourgatestogetthedesiredresult,i.e., theXORfunction. Share Cite Improvethisanswer Follow editedJun10,2015at23:48 answeredJun7,2015at12:15 baboubabou 19.1k3737silverbadges7373bronzebadges $\endgroup$ 5 $\begingroup$ Notinareversewaytoprovethattheyareequal.Butimagethatyoudon'tknowthediagrambuttoconstructthegateusingminimumnandgate. $\endgroup$ – Timeless Jun7,2015at13:05 1 $\begingroup$ Whatdoyouexpectasananswer?Asystematictechniquefordoingthat.Idonotknowthatthereisanythatistractableenoughtobeworthusingincomplexcases.GiventhatIknowtheanswerIcanjustlietoyouandpretendtohavefoundbyreasonningwhatIdiscoveredbycheckingtheanswer.Thissaid,lookingatwhatIgetwithNAND(A,B)isallthatseemsusefulforastart.ThenNANDingtheresultwithoneargumentAorB,isalsoonethingtolookat,togetaviewofwhereIam.Fromthere,oneisprettyclosetothefinalanswer. $\endgroup$ – babou Jun7,2015at13:27 1 $\begingroup$ @TimelessAnotherwaytogoaboutitisbackwardfromtheanswer,knowingthattheanswerisfronaNANDgate.IfyouassumethatthesolutionissymmetricalinAandB,itgivesyoualikelyformoftheinputstothelastNANDgate.Therearemanywaytogoaboutit,eithertofindtheanswer,ortojustifyfindingitaposteriory.Butaproofisaproof,whetherfoundbyyouringenuity,orgivenbysomeoracleoragoodfriend.Andatsomepointnoonecantellthedifference.Actually,thebackwardproofIgivecouldbethebestproof,evenifthesolutionwasfoundsomeotherway. $\endgroup$ – babou Jun7,2015at13:41 $\begingroup$ Actually,itisquitecommoninmathtohaveananalysisparttofindasolution,thenasynthesispartwhereyouproveitisthesolution.Oneusuallygivesboth,butonlythesecondpartisreallynecessary. $\endgroup$ – babou Jun7,2015at13:43 $\begingroup$ @TimelessBothanswerswerebasedontheknowledgeofaformulatoobtain,deducedfromthediagramtobeobtained.Youreditaskedforaplausibleintuitivescenariotofindtheanswerwithoutanypriorknowledgeoftheresult.Ididaddthattomyanswer,butitwouldbenicetoknowwhetheritfitswhatyouexpected. $\endgroup$ – babou Jun10,2015at23:33 Addacomment  |  0 $\begingroup$ Itaketheinput$(0,0)$asanexample. For$\text{XOR}$,thedesiredoutputis0.However,$\text{NAND}(0,0)=1$. Becausetheonlywaytogeta0using$\text{NAND}$is(atthelastlayer)$\text{NAND}(1,1)=0$,youshouldfirstproducetwo1's. Accordingto$\text{NAND}(0,1)=1$or$\text{NAND}(1,0)=1$,youproducea1usingone$\text{NAND}(0,0)$atthefirstlayerandfeedit,alongwithoneinput0,intoasecondlayer$\text{NAND}$. Onlyfour$\text{NAND}$sareinvolved.Butitisonlycorrectfortheinput$(0,0)$sofar.Soyouneedtocheckotherinputs$(0,1),(1,0),$and$(1,1)$againstthesolutionandfindthatitjustworks.Lucky. Share Cite Improvethisanswer Follow editedJun13,2015at3:49 answeredJun7,2015at9:04 hengxinhengxin 9,20922goldbadges2828silverbadges6363bronzebadges $\endgroup$ Addacomment  |  0 $\begingroup$ Itriedmybesttogivetheanswerusingformulaasasked.Hopeyouappreciateit. Z=AB'+A'B Z=AA'+AB'+BB'+A'B--->BB'=AA'=0 Z=A(A'+B')+B(B'+A') Z=A(AB)'+B(AB)'-->Hint sonow(AB)'cangetthrough1stNANDgate,thenin2ndandthirdNANDgatetheoutputof1stNANDgatepassthroughwithoneoftheinputasAandB.AfterthisweneedonemorecomplementsousefourthNANDgate. NAND(1st)=(AB)'=A'+B' NAND(2nd)=(A(AB)')'=(A(A'+B'))'=(AB')'=A'+B NAND(3rd)=(B(AB)')'=(B(A'+B'))'=(A'B)'=A+B' NAND(4th)=[(A'+B)(A+B')]'=[A'B'+AB]'=(A+B)(A'+B')=AB'+A'B Happy! Share Cite Improvethisanswer Follow answeredAug11,2016at16:11 MANVENDRASINGHMANOHARMANVENDRASINGHMANOHAR 1 $\endgroup$ Addacomment  |  0 $\begingroup$ Theformula:XOR=(aandnotb)or(notaandb). Thats'notwhatyouwant,youwantaformulathatisaNAND.Rememberthatnot(aorb)=notaandnotb,andtherefore(aorb)=not(notaandnotb).Therefore (aandnotb)or(notaandb)= not(not(aandnotb)andnot(notaandb))= not((notaorb)and(aornotb))= NAND(notaorb,aornotb). SoweusedoneNANDgate,andhavetocalculate(notaorb)and(aornotb)usingthreeNANDs.WeturneachexpressionintoaNAND: notaorb=not(aandnotb)=NAND(a,notb) aornotb=not(notaandb)=NAND(nota,b) Nowweobservethat(xandy)=xand(notxory):Ifxisfalsethenbothsidesarefalse.Ifxistruethen(notxory)=(falseory)=y.ThisistrueforNANDjustasit'strueforAND.Therefore NAND(a,notb)=NAND(a,notaornotb)=NAND(a,NAND(a,b)) NAND(b,nota)=NAND(b,notbornota)=NAND(b,NAND(a,b)). Sowefirstfindmid=NAND(a,b),left=NAND(a,mid)andright=NAND(b,mid),finallyXOR=NAND(left,right). Share Cite Improvethisanswer Follow answeredAug11,2016at16:39 gnasher729gnasher729 25.2k2929silverbadges3939bronzebadges $\endgroup$ Addacomment  |  -2 $\begingroup$ *Fromlefttoright--D1,D2,D3,D4 ** D1=(A.B)'OR(A'+B') suppose (A.B)'=C D2=(A.C)'=A'+C' D3=(B.C)'=B'+C' then D4=(D2.D3)' D4=((A.C)'.(B.C)')' D4=(A.C)''+(B.C)'' D4=(A.C)+(B.C) D4=A.(A'+B')+B.(A'+B') D4=AB'+BA'{A.A'=B.B'=0}** Share Cite Improvethisanswer Follow answeredNov12,2015at3:34 BivashBivash 1 $\endgroup$ 1 2 $\begingroup$ Ifindithardtofollowthisanswerorunderstandwhatprocessyouareusing.Canyouaddsometextsentencestoexplaintheapproach,sothisisn'tjustasequenceofequations? $\endgroup$ – D.W. ♦ Nov12,2015at7:37 Addacomment  |  Highlyactivequestion.Earn10reputation(notcountingtheassociationbonus)inordertoanswerthisquestion.Thereputationrequirementhelpsprotectthisquestionfromspamandnon-answeractivity. Nottheansweryou'relookingfor?Browseotherquestionstaggedlogicboolean-algebraoraskyourownquestion. TheOverflowBlog StackExchangesitesaregettingprettierfaster:IntroducingThemes FeaturedonMeta Testingnewtrafficmanagementtool Duplicatedvotesarebeingcleanedup Related 4 Simplestcombinationoflogicgatestoproduceagivensetofoutputs 0 ConvertingBooleanExpressionforNANDGateImplementation-DeMorgan'sLaw 0 HowcanidesignthisfunctionusingonlyNANDandXORgates? 1 DoesXNORofthreevariableequalsXORofsamethreevariables 0 Howto"logically"solvebooleanlogic 0 SimplifyingSOP:implementingORwithNAND 0 Foralogicgatetobeuniversal,mustitnecessarilybeabletoperformduplication? 3 Howexpensiveisittoverifythatagateisuniversal? 3 IsanANDgatewhichisnoisy1/3ofthetimeononlyoneofitsinputsuniversal? HotNetworkQuestions Howwouldyoumakeadoorthatcouldstillbeopenedamillionyearslater? Howdoestheearthcaststraightandreversedshadowsonthemoon? Whyispressureindependentofthemassoftheparticlesofthegas? MySQL:HowtooptimizeacertainSELECTstatementwhichcausesveryhighload? WhowasRichardThompson?(Mathematics/Logic) Meaningofthequestion'areyoufeelingunwellbecauseyouatetoomuch?' DoPCboardsinACunitswearout? WhydomybossesaskifIamokay? Wordmeaningtotakeawaythesophisticationofsomething WillithurtmychancesifIstateIwanttostudyTheoreticalComputerScienceinsteadofsthlikeAI/MLforPhD? Arequantifiersredundantbytreatingfreevariablesasimplicitlyuniversallyquantified? Howtocreatethisrhombusshape HowcanItestaprocmailrulewithoutsendingmyselfanemail? Purposeof的in谁说的？ IsitOKtousethetransposefunctionofapianolikeguitarplayersuseacapo? Ismultiplicationimplicitlydefinablefromsuccessor? Whydoesschoolbullyingkeepshowingupinmanga? RadiowaveseffectinBlender Buttonwithoutdirectaction Whatisthiswhitebaronmydoor? Whatsortsofpeoplewerepopularcelebritiesin17thto19thcenturyEurope? Whatisthelargestanimalthatapersoncouldkillwithstoneageweaponry66MYA?Whatisthebiggestonetheycankillinselfdefense? Cansomethingbenoumenalformeandnotforyou? Isthemagneticfieldreallyarelativisticeffectoftheelectricfield? morehotquestions Questionfeed SubscribetoRSS Questionfeed TosubscribetothisRSSfeed,copyandpastethisURLintoyourRSSreader. Yourprivacy Byclicking“Acceptallcookies”,youagreeStackExchangecanstorecookiesonyourdeviceanddiscloseinformationinaccordancewithourCookiePolicy. Acceptallcookies Customizesettings