#off:{0,1}n→{0,1} k0,12=2 of circuits with t gates: <2(2n+t+1)2t …n,v gates x1,,xn,7x1,,7xn,0,1 De Morgan's law: xi,7xi,0,1 (AVB)=7A∧B other (1-1)gates (A∧B)=AVB ∧,∨ # of circuits with t gates: ∧,∨ gates x1,...,xn,¬x1,...,¬xn,0,1 De Morgan’s law: ¬(A ⇤B) = ¬A ⇥¬B ¬(A ⇥B) = ¬A ⇤¬B 2 (2n + t +1) t 2t other (t-1) gates xi ,¬xi ,0,1 < # of f : {0, 1}n ￾ {0, 1} ￾ ￾ ￾{0, 1}2n ￾ ￾ ￾ = 22n