This page intentionally left blank BooleanFunctions Writtenbyprominentexpertsinthefield,thismonographprovidesthefirstcompre- hensiveandunifiedpresentationofthestructural,algorithmic,andappliedaspectsof thetheoryofBooleanfunctions. ThebookfocusesonalgebraicrepresentationsofBooleanfunctions,especiallydis- junctiveandconjunctivenormalformrepresentations.Itpresentswithinthisframework thefundamentalelementsofthetheory(Booleanequationsandsatisfiabilityproblems, primeimplicantsandassociatedshortrepresentations,dualization),anin-depthstudy ofspecialclassesofBooleanfunctions(quadratic,Horn,shellable,regular,threshold, read-oncefunctionsandtheircharacterizationbyfunctionalequations),andtwofruit- fulgeneralizationsoftheconceptofBooleanfunctions(partiallydefinedfunctionsand pseudo-Booleanfunctions).Severaltopicsarepresentedhereinbookformforthefirst time. Becauseoftheuniquedepthandbreadthoftheunifiedtreatmentthatitprovidesand itsemphasisonalgorithmsandapplications,thismonographwillhavespecialappeal for researchers and graduate students in discrete mathematics, operations research, computerscience,engineering,andeconomics. Dr.YvesCramaisProfessorofOperationsResearchandProductionManagementand the former Director General of the HEC Management School of the University of Liège,Belgium.HeiswidelyrecognizedasaprominentexpertinthefieldofBoolean functions,combinatorialoptimization,andoperationsresearch,andhehascoauthored morethanseventypapersandthreebooksonthesesubjects.Dr.Cramaisamemberof theeditorialboardofDiscreteAppliedMathematics,DiscreteOptimization,Journal ofScheduling,and4OR–TheQuarterlyJournaloftheBelgian,FrenchandItalian OperationsResearchSocieties. The late Peter L. Hammer (1936–2006) was a Professor of Operations Research, Mathematics,ComputerScience,ManagementScience,andInformationSystemsat RutgersUniversityandtheDirectoroftheRutgersUniversityCenterforOperations Research(RUTCOR).Hewasthefounderandeditor-in-chiefofthejournalsAnnals of Operations Research, Discrete Mathematics, DiscreteApplied Mathematics, Dis- creteOptimization,andElectronicNotesinDiscreteMathematics.Dr.Hammerwas theinitiatorofnumerouspioneeringinvestigationsoftheuseofBooleanfunctionsin operationsresearchandrelatedareas,ofthetheoryofpseudo-Booleanfunctions,and ofthelogicalanalysisofdata.Hepublishedmorethan240papersand19bookson thesetopics. encyclopedia of mathematics and its applications founding editor g.-c. rota EditorialBoard R.Doran,P.Flajolet,M.Ismail,T.-Y.Lam,E.Lutwak Thetitlesbelow,andearliervolumesintheseries,areavailablefrombooksellersorfrom CambridgeUniversityPressatwww.cambridge.org. 110 M.-J.LaiandL.L.SchumakerSplineFunctionsonTriangulations 111 R.T.CurtisSymmetricGenerationofGroups 112 H.Salzmannetal.TheClassicalFields 113 S.PeszatandJ.ZabczykStochasticPartialDifferentialEquationswithLévyNoise 114 J.BeckCombinatorialGames 115 L.BarreiraandY.PesinNonuniformHyperbolicity 116 D.Z.ArovandH.DymJ-ContractiveMatrixValuedFunctionsandRelatedTopics 117 R.Glowinski,J.-L.Lions,andJ.HeExactandApproximateControllabilityforDistributed ParameterSystems 118 A.A.BorovkovandK.A.BorovkovAsymptoticAnalysisofRandomWalks 119 M.DezaandM.DutourSikiriéGeometryofChemicalGraphs 120 T.NishiuraAbsoluteMeasurableSpaces 121 M.PrestPurity,SpectraandLocalisation 122 S.KhrushchevOrthogonalPolynomialsandContinuedFractions 123 H.NagamochiandT.IbarakiAlgorithmicAspectsofGraphConnectivity 124 F.W.KingHilbertTransformsI 125 F.W.KingHilbertTransformsII 126 O.CalinandD.-C.ChangSub-RiemannianGeometry 127 M.Grabischetal.AggregationFunctions 128 L.W.BeinekeandR.J.Wilson(eds.)withJ.L.GrossandT.W.TuckerTopicsin TopologicalGraphTheory 129 J.Berstel,D.Perrin,andC.ReutenauerCodesandAutomata 130 T.G.FaticoniModulesoverEndomorphismRings 131 H.MorimotoStochasticControlandMathematicalModeling 132 G.SchmidtRelationalMathematics 133 P.KornerupandD.W.MatulaFinitePrecisionNumbersSystemsandArithmetic 134 Y.CramaandP.L.HammerBooleanModelsandMethodsinMathematics,Computer Science,andEngineering 135 V.BerthéandM.RigoCombinatorics,AutomataandNumberTheory 136 A.Kristály,V.D.Raˇdulescu,andC.VargaVariationalPrinciplesinMathematicalPhysics, Geometry,andEconomics 137 J.BerstelandC.ReutenauerNoncommutativeRationalSerieswithApplications 138 B.CourcelleGraphStructureandMonadicSecond-OrderLogic 139 M.FiedlerMatricesandGraphsinGeometry 140 N.VakilRealAnalysisthroughModernInfinitesimals 141 R.B.ParisHadamardExpansionsandHyperasymptoticEvaluation       Boolean Functions Theory, Algorithms, and Applications YVES CRAMA UniversityofLiège,Belgium PETER L. HAMMER cambridge university press Cambridge,NewYork,Melbourne,Madrid,CapeTown, Singapore,SãoPaulo,Delhi,Tokyo,MexicoCity CambridgeUniversityPress 32AvenueoftheAmericas,NewYork,NY10013-2473,USA www.cambridge.org Informationonthistitle:www.cambridge.org/9780521847513 ©YvesCramaandPeterL.Hammer2011 Thispublicationisincopyright.Subjecttostatutoryexception andtotheprovisionsofrelevantcollectivelicensingagreements, noreproductionofanypartmaytakeplacewithoutthewritten permissionofCambridgeUniversityPress. Firstpublished2011 PrintedintheUnitedStatesofAmerica AcatalogrecordforthispublicationisavailablefromtheBritishLibrary. LibraryofCongressCataloginginPublicationData Crama,Yves,1958– Booleanfunctions/YvesCrama,PeterL.Hammer. p. cm.–(Encyclopediaofmathematicsanditsapplications) Includesbibliographicalreferencesandindex. Contents:Theory,algorithms,andapplications ISBN978-0-521-84751-3(hardback) 1. Algebraicfunctions. 2. Algebra,Boolean. I. Hammer,P.L.,1936–2006. II. Title. QA341.C732011 511.3(cid:1)24–dc22 2011009690 ISBN978-0-521-84751-3Hardback CambridgeUniversityPresshasnoresponsibilityforthepersistenceoraccuracyofURLsfor externalorthird-partyInternetWebsitesreferredtointhispublicationanddoesnotguaranteethat anycontentonsuchWebsitesis,orwillremain,accurateorappropriate. ToEdith, bywayofapologyforcountlessdays spentinfrontofthecomputer. YC Contents Contributors pagexiii Preface xv Acknowledgments xix Notations xxi PartI Foundations 1 Fundamentalconceptsandapplications 3 1.1 Booleanfunctions:Definitionsandexamples 3 1.2 Booleanexpressions 8 1.3 Duality 13 1.4 Normalforms 14 1.5 TransforminganarbitraryexpressionintoaDNF 19 1.6 OrthogonalDNFsandnumberoftruepoints 22 1.7 Implicantsandprimeimplicants 24 1.8 Restrictionsoffunctions,essentialvariables 28 1.9 Geometricinterpretation 31 1.10 MonotoneBooleanfunctions 33 1.11 RecognitionoffunctionalandDNFproperties 40 1.12 OtherrepresentationsofBooleanfunctions 44 1.13 Applications 49 1.14 Exercises 65 2 Booleanequations 67 2.1 Definitionsandapplications 67 2.2 ThecomplexityofBooleanequations:Cook’stheorem 72 2.3 OntheroleofDNFequations 74 2.4 Whatdoesitmeanto“solveaBooleanequation”? 78 2.5 Branchingprocedures 80 2.6 Variableeliminationprocedures 87 vii viii Contents 2.7 Theconsensusprocedure 92 2.8 Mathematicalprogrammingapproaches 95 2.9 Recenttrendsandalgorithmicperformance 103 2.10 MoreonthecomplexityofBooleanequations 104 2.11 Generalizationsofconsistencytesting 111 2.12 Exercises 121 3 PrimeimplicantsandminimalDNFs 123 PeterL.HammerandAlexanderKogan 3.1 Primeimplicants 123 3.2 Generationofallprimeimplicants 128 3.3 Logicminimization 141 3.4 Extremalandtypicalparametervalues 159 3.5 Exercises 165 4 Dualitytheory 167 YvesCramaandKazuhisaMakino 4.1 Basicpropertiesandapplications 167 4.2 Dualitypropertiesofpositivefunctions 176 4.3 Algorithmicaspects:Thegeneralcase 183 4.4 Algorithmicaspects:Positivefunctions 189 4.5 Exercises 198 PartII SpecialClasses 5 Quadraticfunctions 203 BrunoSimeone 5.1 Basicdefinitionsandproperties 203 5.2 WhyarequadraticBooleanfunctionsimportant? 205 5.3 Specialclassesofquadraticfunctions 207 5.4 QuadraticBooleanfunctionsandgraphs 209 5.5 Reducibilityofcombinatorialproblems toquadraticequations 218 5.6 Efficientgraph-theoreticalgorithmsforquadraticequations 230 5.7 Quadraticequations:Specialtopics 243 5.8 Primeimplicantsandirredundantforms 250 5.9 Dualizationofquadraticfunctions(Contributedby OyaEkinKaras¸an) 263 5.10 Exercises 266 6 Hornfunctions 269 EndreBoros 6.1 Basicdefinitionsandproperties 269 6.2 ApplicationsofHornfunctions 273 6.3 FalsepointsofHornfunctions 277