Propositional Logic · Theory Problems
Lesson 3
- (25 points) Provide a function \(f \in B_{n}\) that cannot be represented by a formula over the basis \(\{\lor, \land, \neg\}\) (not necessarily in CNF or DNF) of size \(O(n)\).
- (30 points) Prove that \[2^{\binom{n}{\lfloor n/2 \rfloor}}\le |\mathcal{M}\cap B_{n}| \le 3^{\binom{n}{\lfloor n/2 \rfloor}}.\]