Prove that a boolean function using only $\vee$ and $\wedge$ must attain the value $1$ at least once

54 Views Asked by At

Please give me feedback on this

Prove that a boolean function constructed only by using $\vee$ and $\wedge$ (without using $\sim$ ) must attain the value $1$ at least once.

1

There are 1 best solutions below

0
On

HINT: Every Boolean function $f$ in $n$ Boolean variables is defined by a propositional formula $\tau_f$ in $n$ propositional variables. Prove by induction on the complexity of $\tau_f$ that $f(1,\ldots,1)=1$ for every Boolean function $f$ such that $\tau_f$ is constructed using only the Boolean connectives $\land$ and $\lor$. Use the recursive construction of such formulas: the individual propositional variables are the basic ones, and if $\sigma$ and $\tau$ are propositional formulas constructed using only $\land$ and $\lor$, so are $\sigma\land\tau$ and $\sigma\lor\tau$.