{"id":3822,"date":"2012-01-09T00:06:25","date_gmt":"2012-01-08T23:06:25","guid":{"rendered":"http:\/\/djalil.chafai.net\/blog\/?p=3822"},"modified":"2014-06-17T20:57:23","modified_gmt":"2014-06-17T18:57:23","slug":"few-bits-on-boolean-functions","status":"publish","type":"post","link":"https:\/\/djalil.chafai.net\/blog\/2012\/01\/09\/few-bits-on-boolean-functions\/","title":{"rendered":"Few bits on Boolean functions"},"content":{"rendered":"<p style=\"text-align: center;\"><a href=\"http:\/\/djalil.chafai.net\/blog\/wp-content\/uploads\/2012\/01\/George_Boole.jpg\"><img loading=\"lazy\" class=\"aligncenter wp-image-3835 size-full\" title=\"George Boole\" src=\"http:\/\/djalil.chafai.net\/blog\/wp-content\/uploads\/2012\/01\/George_Boole.jpg\" alt=\"George Boole\" width=\"213\" height=\"267\" \/><\/a><\/p>\n<p style=\"text-align: justify;\"><b>Boolean functions.<\/b> A function \\( {f:\\{0,1\\}^n\\rightarrow\\{0,1\\}} \\) defined on the discrete cube \\( {\\{0,1\\}^n} \\) and taking its values in \\( {\\{0,1\\}} \\) is called a Boolean function. Such a function encodes typically the status of a complex system with \\( {n} \\) components. Here are two basic examples:<\/p>\n<ul>\n<li>\\( {f(x)=\\mathbf{1}_{\\det(x)\\neq0}} \\) for every \\( {x\\in\\mathcal{M}_m(\\{0,1\\})\\equiv\\{0,1\\}^{m^2}} \\). Here \\( {n=m^2} \\).<\/li>\n<li>same set and \\( {f(x)=1} \\) iff the graph with adjacency matrix \\( {x} \\) is connected.<\/li>\n<\/ul>\n<p style=\"text-align: justify;\">More generally, any property of a graph can be seen as a Boolean function by encoding the graph with its adjacency matrix, which is a Boolean object. Boolean = binary = logical = \\( {\\{0,1\\}} \\). Let us recall some basic facts about Boolean calculus. For every \\( {b,b'\\in\\{0,1\\}} \\),<\/p>\n<ul>\n<li><b>negation<\/b> operator: \\( {\\mathbf{not}\\ b = 1-b} \\)<\/li>\n<li><b>and<\/b> operator: \\( {b\\ \\mathbf{and}\\ b' = bb'} \\)<\/li>\n<li><b>or<\/b> operator: \\( {b\\ \\mathbf{or}\\ b' = b+b'-bb'=1-(1-b)(1-b')} \\)<\/li>\n<li><b>equality<\/b> operator: \\( {\\mathbf{1}_{b=b'} = 1-b-b'+2bb'} \\)<\/li>\n<\/ul>\n<p style=\"text-align: justify;\">Note: \\( {\\mathbf{and}_{i\\in I}b_i=\\prod_{i\\in I}b_i} \\) and \\( {\\mathbf{or}_{i\\in I}b_i=1-\\prod_{i\\in I}(1-b_i)} \\) for every \\( {b\\in\\{0,1\\}^I} \\).<\/p>\n<p style=\"text-align: justify;\"><b>Naive representation of Boolean functions.<\/b> For every Boolean function \\( {f} \\), if we define \\( {Z=\\{x\\in\\{0,1\\}^n:f(x)=0\\}} \\) then we have for all \\( {x\\in\\{0,1\\}^n} \\),<\/p>\n<p style=\"text-align: center;\">\\[ f(x)={\\mathbf{or}}_{s\\not\\in Z}{\\mathbf{and}}_{1\\leq i\\leq n}(x_i=s_i) =1-\\prod_{s\\not\\in Z}\\left(1-\\prod_{1\\leq i\\leq n}(1-s_i-x_i+2s_ix_i)\\right) \\]<\/p>\n<p style=\"text-align: justify;\">and<\/p>\n<p style=\"text-align: center;\">\\[ f(x)={\\mathbf{and}}_{s\\in Z}{\\mathbf{or}}_{1\\leq i\\leq n}(x_i\\neq s_i) =\\prod_{s\\in Z}\\left(1-\\prod_{1\\leq i\\leq n}(1-s_i-x_i+2s_ix_i)\\right). \\]<\/p>\n<p style=\"text-align: justify;\">The left hand side formulas mean that \\( {f} \\) can be expressed as a finite combination of the logical variables \\( {x_1,\\ldots,x_n} \\) and logical operators. In binary terms, the right hand side formulas mean that \\( {f} \\) is a polynomial in \\( {x_1,\\ldots,x_n} \\). This is a remarkable polynomial fact! We will see that the notion of <b>minimal cuts<\/b> allows to reduce the representation complexity. On the other hand, we may observe that since \\( {b^2=b} \\) for all \\( {b\\in\\{0,1\\}} \\), any polynomial in Boolean variables is identical to a polynomial of degree at most \\( {2} \\) in each variable.<\/p>\n<p style=\"text-align: justify;\"><b>Cuts.<\/b> A cut of a Boolean function \\( {f} \\) is a couple \\( {(I,s)} \\) where \\( {\\varnothing\\neq I\\subset\\{1,\\ldots,n\\}} \\) and \\( {s\\in\\{0,1\\}^I} \\) such that for all \\( {x\\in\\{0,1\\}^n} \\) we have \\( {f(x)=0} \\) if \\( {x_i=s_i} \\) for all \\( {i\\in I} \\). The Boolean function identically equal to \\( {1} \\) does not have cuts. For a Boolean function \\( {f} \\), if \\( {f(x)=1} \\) for some \\( {x\\in\\{0,1\\}^n} \\), then for any cut \\( {(I,s)} \\) of \\( {f} \\) we have \\( {x_i\\neq s_i} \\) for some \\( {i\\in I} \\). Conversely, if \\( {f(x)=0} \\) for some \\( {x\\in\\{0,1\\}^n} \\) then there exists a cut \\( {(I,s)} \\) of \\( {f} \\) such that \\( {x_i=s_i} \\) for all \\( {i\\in I} \\) (take for instance the cut \\( {(I,s)=(\\{1,\\ldots,n\\},x))} \\).<\/p>\n<p style=\"text-align: justify;\"><b>Representation of Boolean functions with their minimal cuts.<\/b> For a Boolean function \\( {f} \\), let us consider the partial order on its cuts defined by \\( {(I,s)\\leq (I',s')} \\) iff \\( {I\\subset I'} \\) and \\( {s_i=s'_i} \\) for all \\( {i\\in I} \\). The minimal elements are called minimal cuts.<\/p>\n<p style=\"text-align: justify;\">For every \\( {x\\in\\{0,1\\}^n} \\), we see that \\( {f(x)=1} \\) iff for any minimal cut \\( {(I,s)} \\) we have \\( {x_i\\neq s_i} \\) for some \\( {i\\in I} \\). Also, if \\( {\\mathcal{S}} \\) stands for the set of minimal cuts, then for all \\( {x\\in\\{0,1\\}^n} \\),<\/p>\n<p style=\"text-align: center;\">\\[ f(x) =\\mathbf{and}_{(I,s)\\in\\mathcal{S}}\\mathbf{or}_{i\\in I}(x_i\\neq s_i) =\\prod_{(I,s)\\in\\mathcal{S}}\\left(1-\\prod_{i\\in I}(1-s_i-x_i+2s_ix_i)\\right). \\]<\/p>\n<p style=\"text-align: justify;\">We have taken the convention \\( {\\prod_\\varnothing=1} \\). The Boolean function \\( {f} \\) is polynomial in the Boolean variables \\( {x_1,\\ldots,x_n} \\). We already know that it can be simplified into a polynomial of degree at most two in each variable. The total degree is at most \\( {n} \\), and this is achieved by the Boolean function \\( {x_1\\cdots x_n} \\), for which the minimal cuts are \\( {(\\{1\\},0),\\ldots,(\\{n\\},0)} \\). Note that the Boolean function \\( {\\mathbf{1}_{x_1+\\cdots+x_n\\neq0}} \\) has a unique minimal cut \\( {(\\{1,\\ldots,n\\},(0,\\ldots,0))} \\), and<\/p>\n<p style=\"text-align: center;\">\\[ \\mathbf{1}_{x_1+\\cdots+x_n\\neq0}=1-\\prod_{i=1}^n(1-x_i). \\]<\/p>\n<p style=\"text-align: justify;\"><b>Percolation.<\/b> Let us consider the square graph obtained by taking the edges of \\( {\\mathbb{Z}^2} \\) with vertices in \\( {\\{0,\\ldots,L\\}^2} \\) for some fixed \\( {L\\in\\{1,2,\\ldots\\}} \\). On each edge we put a Boolean variable and we consider the Boolean function \\( {f} \\) equal to \\( {1} \\) iff there exists a path with edges marked \\( {1} \\) connecting \\( {(0,0)} \\) with \\( {(L,L)} \\). Could you list the minimal cuts? They give a polynomial representation of \\( {f} \\). The number of cuts is huge, as for most complex systems.<\/p>\n<p style=\"text-align: justify;\"><b>Related.<\/b> Boolean functions are called <b>structure functions<\/b> in systems reliability and engineering. Two other famous problems on Boolean functions:<\/p>\n<ul>\n<li><a href=\"http:\/\/wiki-math.univ-mlv.fr\/gemecod\/doku.php\/openproblems#invertibility_of_random_matrices\"> Invertibility of Boolean matrices and \\( {(1\/2+o(1))^n} \\) conjecture<\/a><\/li>\n<li><a href=\"http:\/\/wiki-math.univ-mlv.fr\/gemecod\/doku.php\/openproblems#the_fourier-entropy-influence_conjecture\"> Fourier-Entropy-Influence conjecture<\/a><\/li>\n<\/ul>\n<p style=\"text-align: justify;\">Goodies: <a href=\"http:\/\/wiki-math.univ-mlv.fr\/gemecod\/doku.php\/winterschool2012#lectures\"> recent lecture notes by G. Kalai and E. Mossel<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Boolean functions. A function \\( {f:\\{0,1\\}^n\\rightarrow\\{0,1\\}} \\) defined on the discrete cube \\( {\\{0,1\\}^n} \\) and taking its values in \\( {\\{0,1\\}} \\) is called&#8230;<\/p>\n<div class=\"more-link-wrapper\"><a class=\"more-link\" href=\"https:\/\/djalil.chafai.net\/blog\/2012\/01\/09\/few-bits-on-boolean-functions\/\">Continue reading<span class=\"screen-reader-text\">Few bits on Boolean functions<\/span><\/a><\/div>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"iawp_total_views":23},"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/posts\/3822"}],"collection":[{"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/comments?post=3822"}],"version-history":[{"count":39,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/posts\/3822\/revisions"}],"predecessor-version":[{"id":7432,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/posts\/3822\/revisions\/7432"}],"wp:attachment":[{"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/media?parent=3822"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/categories?post=3822"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/djalil.chafai.net\/blog\/wp-json\/wp\/v2\/tags?post=3822"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}