Lemma 1.1.For every Boolean function f ofn variables,it is possible to fix one variable such that the resulting subfunction f satisfies 0s(-).0n Before proving the lemma,let's get some feelings of the parameters and see why it's nontrivial. Suppose F is a minimal formula which computesf,and F has s=L(f)leaves.Since f has n variables, there exists one variable x;which appears at least s/n times in the leaf level(though some of the appearances are in the form of )If we fix x,to be some constant,then the leaf size will reduce to s-s/n =(1-1/n)s.The lemma says that actually one can reduce the size by more.Now we prove it. Proof.Define F and s as in the above discussion.The idea is that if there is a subtree H in F which is of the form xi AG for some subtree G,then setting xi=0 will kill the whole subtree G.(You can handle the cases where the gate is OR,or where the occurrence ofx;is in negation,in a similar way.) Therefore,suppose variable iappears t>s/n times,then foreach appearance there is an assignment of x;=0/1 to kill its"neighbor"subtree G.Then one of the two assignments,x;=0 and x;=1,kills more,at least t/2,subtrees.Use that assignment.The leaf size reduces to at most s-t-s(-别ss1-)s as claimed. The above analysis is almost correct except that it forgets to consider the case in which the subtrees G intersect.Consider the extreme case that there is a subtree H of the form xixixi.This looks weird since clearly some xi's are redundant.We can indeed make this rigorous by claiming the following:For any leaf xi or i its neighbor subtree G doesn't contain variable i.(Thus the G's don't intersect.) The claim is not hard to prove.Basically,if we see xiA G and G contains xi,then it is observed that one can simply replace the x;in G by I without changing the function.(If x;=1,then we"guessed correctly"by replacing xi in G by 1.If xi=0,then xiAG=0 anyway.)Othercases such as G contains i or the gate connecting xi and G is OR,can be handled similarly.This completes the proof of the lemma. Repeatedly applying the lemma gives the following theorem.Lemma 1.1. For every Boolean function f of n variables, it is possible to fix one variable such that the resulting subfunction 𝑓′ satisfies 𝐿(𝑓 ′) ≤ (1 − 1 𝑛 ) 3/2 ⋅ 𝐿(𝑓). Before proving the lemma, let’s get some feelings of the parameters and see why it’s nontrivial. Suppose F is a minimal formula which computes f, and F has s = L(f) leaves. Since f has n variables, there exists one variable xi which appears at least s/n times in the leaf level (though some of the appearances are in the form of 𝑥̅𝑖 ). If we fix xi to be some constant, then the leaf size will reduce to s − s/n = (1 − 1/n)s. The lemma says that actually one can reduce the size by more. Now we prove it. Proof. Define F and s as in the above discussion. The idea is that if there is a subtree H in F which is of the form xi ∧ 𝐺 for some subtree G, then setting xi = 0 will kill the whole subtree G. (You can handle the cases where the gate is OR, or where the occurrence of xi is in negation, in a similar way.) Therefore, suppose variable i appears t ≥ s/n times, then for each appearance there is an assignment of xi = 0/1 to kill its “neighbor” subtree G. Then one of the two assignments, xi = 0 and xi = 1, kills more, at least t/2, subtrees. Use that assignment. The leaf size reduces to at most s − t − t 2 ≤ (1 − 3 2n) s ≤ (1 − 1 𝑛 ) 3/2 s, as claimed. The above analysis is almost correct except that it forgets to consider the case in which the subtrees G intersect. Consider the extreme case that there is a subtree H of the form 𝑥𝑖 ∧𝑥𝑖 ∧ 𝑥𝑖… This looks weird since clearly some xi’s are redundant. We can indeed make this rigorous by claiming the following: For any leaf 𝑥𝑖 or 𝑥̅𝑖 , its neighbor subtree G doesn’t contain variable i. (Thus the G’s don’t intersect.) The claim is not hard to prove. Basically, if we see xi ∧ 𝐺 and G contains xi , then it is observed that one can simply replace the xi in G by 1 without changing the function. (If xi= 1, then we “guessed correctly” by replacing xi in G by 1. If xi= 0, then xi ∧ 𝐺 = 0 anyway.) Other cases such as G contains 𝑥̅𝑖 , or the gate connecting xi and G is OR, can be handled similarly. This completes the proof of the lemma. □ Repeatedly applying the lemma gives the following theorem