monotone boolean function
for two vectors 
we write 
if 
for all positions 
. a boolean function 
is monotone, if implies 
.
if we view
as a set-theoretic predicate 
, then is monotone iff 
and 
implies 
[cite:;taken from @complexity_jukna_2012 chapter 1 our adversary: the circuit]
we write if for all positions . a boolean function is monotone, if implies .if we view
as a set-theoretic predicate , then is monotone iff and implies [cite:;taken from @complexity_jukna_2012 chapter 1 our adversary: the circuit]
the following problems can be formulated as monotonic functions:
- is a given graph connected?
- does the graph contain a hamiltonian cycle?
- does the graph contain a clique of size
?
a replacement rule is a rule that allows a function computed at a vertex of a circuit to be replaced by another without changing the function computed by the circuit.
we present a replacement rule for monotone functions that captures the following idea: if a function 
computed by a gate of a monotone circuit has a monom 
that is not a monom of the function computed by the complete circuit, then can be removed from without affecting the value of . this idea is valid in monotone circuits because the absence of negation provides only one way to eliminate extra monoms, namely, by ORing them with products containing a subset of their variables. taking the AND of a monom with another term creates a longer monom. thus, since monoms that are not monoms of the function computed by a circuit must be eliminated, there is no loss of generality in assuming that they are not produced in the first place.let 
and 
be two monotone functions. let be computed within a monotone circuit for . the following is a replacement rule for :
we show that any monom and be two monotone functions. let be computed within a monotone circuit for . the following is a replacement rule for :- let
and let 
be defined by 
. replace the gate computing by one computing if for all monoms 
(including the empty monom), 
.
satisfying this rule can be removed from 
because it contributes nothing to the computation of .let and be two monotone functions and let be such that for all monoms (including the empty monom), . let be defined by . if is computed in some monotone circuit for , the circuit obtained by replacing by also computes .
[cite:;taken from @computation_savage_1998 lemma 9.6.1]
and be two monotone functions and let be such that for all monoms (including the empty monom), . let be defined by . if is computed in some monotone circuit for , the circuit obtained by replacing by also computes .[cite:;taken from @computation_savage_1998 lemma 9.6.1]
let 
, where each 
, 
, is a monotone boolean function on 
-tuple 
and 
-tuple 
; that is, 
. 
is a bilinear form if each prime implicant of each 
, 
, contains one variable of and one of . a function is a semi-disjoint bilinear form if in addition 
for 
, and each variable is contained in at most one prime implicant of any one function.
[cite:;taken from @computation_savage_1998 definition 9.6.4]
before deriving a lower bound on the number of gates needed for a semi-disjoint bilinear form, we introduce a new replacement rule peculiar to these forms., where each , , is a monotone boolean function on -tuple and -tuple ; that is, . is a bilinear form if each prime implicant of each , , contains one variable of and one of . a function is a semi-disjoint bilinear form if in addition for , and each variable is contained in at most one prime implicant of any one function.[cite:;taken from @computation_savage_1998 definition 9.6.4]
no gate of a monotone circuit of minimal size for a semi-disjoint bilinear form computes a function whose prime implicants include either two variables of or of .
[cite:;taken from @computation_savage_1998 lemma 9.6.2]
computes a function whose prime implicants include either two variables of or of .[cite:;taken from @computation_savage_1998 lemma 9.6.2]
we suppose that a minimal monotone circuit does contain a gate whose prime implicants contain either two variables of 
or two of 
and show that a contradiction results. without loss of generality, assume that contains 
and 
, 
. if there is a gate satisfying this hypothesis, there is one that is closest to an input variable. this must be an 
gate because 
gates increase the length of prime implicants. because the gate in question is closest to inputs, at least one of and is either an input to this gate or is the input to some gate that is on a path of gates to this gate.
a simple proof by induction on its circuit size demonstrates that if a circuit for
contains a gate computing then , 
, can be written as follows ([cite:;see @computation_savage_1998 problem 9.36]):
here 
and 
are boolean functions. of course, if for no 
is a function of , then we can set 
and the circuit is not minimal.
if depends on , 
. however, 
because otherwise both and are prime implicants of (for every ), contradicting its definition. also, 
cannot have any monoms containing one or more instances of a variable in or two or more instances of variables in because when ed with they produce monoms that could be removed by replacement rule 1 and the circuit would not be minimal. it follows that can contain only single variables of . but this implies that for some , 
, which together with the fact that 
implies that 
. but 
and 
cannot both be prime implicants of , because they violate the requirement that no two prime implicants of contain the same variable. it follows that does not depend on .
[cite:;taken from @computation_savage_1998 lemma 9.6.2]
the boolean convolution function is a semi-disjoint bilinear form. each implicant of each component of whose prime implicants contain either two variables of or two of and show that a contradiction results. without loss of generality, assume that contains and , . if there is a gate satisfying this hypothesis, there is one that is closest to an input variable. this must be an gate because gates increase the length of prime implicants. because the gate in question is closest to inputs, at least one of and is either an input to this gate or is the input to some gate that is on a path of gates to this gate.a simple proof by induction on its circuit size demonstrates that if a circuit for
contains a gate computing then , , can be written as follows ([cite:;see @computation_savage_1998 problem 9.36]):here and are boolean functions. of course, if for no is a function of , then we can set and the circuit is not minimal.if
depends on , . however, because otherwise both and are prime implicants of (for every ), contradicting its definition. also, cannot have any monoms containing one or more instances of a variable in or two or more instances of variables in because when ed with they produce monoms that could be removed by replacement rule 1 and the circuit would not be minimal. it follows that can contain only single variables of . but this implies that for some , , which together with the fact that implies that . but and cannot both be prime implicants of , because they violate the requirement that no two prime implicants of contain the same variable. it follows that does not depend on .[cite:;taken from @computation_savage_1998 lemma 9.6.2]
contains one variable of 
and one of 
. in addition, the prime implicants of 
and 
are disjoint if . finally, each variable appears in only one implicant of a component function, although it may appear in more than one such function.let 
, 
, be a semi-disjoint bilinear form, where . let 
be the number of functions in 
that are essentially dependent on the input variable , 
. then the monotone circuit size of must satisfy the following lower bound:
[cite:;taken from @computation_savage_1998 theorem 9.6.4]
, , be a semi-disjoint bilinear form, where . let be the number of functions in that are essentially dependent on the input variable , . then the monotone circuit size of must satisfy the following lower bound:[cite:;taken from @computation_savage_1998 theorem 9.6.4]the proof is by induction. the basis for induction is the semi-disjoint bilinear form on two variables 
. in this case 
and 
. we assume that any semi-disjoint bilinear form in 
or fewer variables satisfies the lower bound. we show that setting 
produces another function that is a semi-disjoint bilinear form and allows the removal of at least 
gates. the lower bound follows by induction. we consider only minimal circuits.
let
denote the number of functions in 
that are essentially dependent on and have a single prime implicant (such as 
and 
for convolution). setting eliminates the 
gates at which these outputs are computed. we show that at least 
gates can also be eliminated. since 
, we have the desired conclusion.
let
denote those outputs that depend on whose associated function has at least two prime implicants. then 
. there must be at least one gate on each path 
from to 
because, if not, each path contains only s and has only one prime implicant (the one that contains ), in contradiction to the definition of .
we claim that on each path from an input labeled to some there is an gate computing a function 
such that 
for some 
. let 
be those gates closest to an input vertex . call 
the bottleneck for variable (this is demonstrated in broken link: blk:fig-bool-func-1). we shall show that 
and that each of the gates in can be eliminated by setting 
.
broken link: xopp-figure:/home/mahmooz/brain/pen/1733575184.2236493.xopp
if the claim is false, then there is a path from input to output such that for each gate (let it compute ) on there is no 
such that . therefore, either all monoms of 
: a. contain or b. are monoms that are not implicants of an output (they are not of the form 
). in case (a), setting causes the gates on to have value 0, which forces the gates on and to have value 0, contradicting the definition of (it has at least two prime implicants). in the second case under replacement rule 1 the monomos not containing can be removed without changing the functions computed. thus, when , the output of each gate on has value 0, which contradicts the definition of since it contains at least two prime implicants.
we now show that
. since each of the gates in has a prime implicant not containing , their outputs can be set to 1 by setting 
for 
. this eliminates all dependence of on . however, since inputs have only been assigned value 1 (and not 0), this dependence on can be eliminated only if all functions in have value 1; that is, at least one prime implicant of each of them is set to 1 by this assignment. since each variable appears in at most one prime implicant of a function, the number of different variables 
(and 
) that are set to 1 is at most 
. thus, at most 
prime implicants can be assigned value 1 by this assignment. thus, if 
, we have a contradiction since 
.
we now show that gates can be eliminated by setting . since each gate in is the closest gate to an input labeled , setting eliminates one of the two inputs to the gate and the need for the gate itself.
[cite:;taken from @computation_savage_1998 chapter 9.6 lower-bound methods for monotone circuits]. in this case and . we assume that any semi-disjoint bilinear form in or fewer variables satisfies the lower bound. we show that setting produces another function that is a semi-disjoint bilinear form and allows the removal of at least gates. the lower bound follows by induction. we consider only minimal circuits.let
denote the number of functions in that are essentially dependent on and have a single prime implicant (such as and for convolution). setting eliminates the gates at which these outputs are computed. we show that at least gates can also be eliminated. since , we have the desired conclusion.let
denote those outputs that depend on whose associated function has at least two prime implicants. then . there must be at least one gate on each path from to because, if not, each path contains only s and has only one prime implicant (the one that contains ), in contradiction to the definition of .we claim that on each path
from an input labeled to some there is an gate computing a function such that for some . let be those gates closest to an input vertex . call the bottleneck for variable (this is demonstrated in broken link: blk:fig-bool-func-1). we shall show that and that each of the gates in can be eliminated by setting .broken link: xopp-figure:/home/mahmooz/brain/pen/1733575184.2236493.xopp
if the claim is false, then there is a path
from input to output such that for each gate (let it compute ) on there is no such that . therefore, either all monoms of : a. contain or b. are monoms that are not implicants of an output (they are not of the form ). in case (a), setting causes the gates on to have value 0, which forces the gates on and to have value 0, contradicting the definition of (it has at least two prime implicants). in the second case under replacement rule 1 the monomos not containing can be removed without changing the functions computed. thus, when , the output of each gate on has value 0, which contradicts the definition of since it contains at least two prime implicants.we now show that
. since each of the gates in has a prime implicant not containing , their outputs can be set to 1 by setting for . this eliminates all dependence of on . however, since inputs have only been assigned value 1 (and not 0), this dependence on can be eliminated only if all functions in have value 1; that is, at least one prime implicant of each of them is set to 1 by this assignment. since each variable appears in at most one prime implicant of a function, the number of different variables (and ) that are set to 1 is at most . thus, at most prime implicants can be assigned value 1 by this assignment. thus, if , we have a contradiction since .we now show that
gates can be eliminated by setting . since each gate in is the closest gate to an input labeled , setting eliminates one of the two inputs to the gate and the need for the gate itself.