Propositional Logic - induction (a) Let C be the set {∧,∨} of propositional connectives, and let P be any set of propositional variables.
i. Suppose that:


*

*φ is a well-formed formula that uses only connectives in C and variables in P 

*I is a valuation such that makes each variable in P true (that is, I |= p for every p ∈ P ). Prove that I |= φ. Use induction on the structure of φ.


ii. Show that the set of connectives C above is not adequate for propositional logic.
 A: I've never actually solved a problem like this before, but it looks pretty trivial so I'll give it a shot. My apologies if this is wrong.
i. Let $\Phi$ denote the formulae of propositional logic that can be formed from the connectives in $C$ and the variables in $P$. More precisely, lets us defined that $\Phi$ is the smallest collection of formulae such that 


*

*If $X \in P$, then $X \in \Phi$

*If $\phi,\psi \in \Phi$ then $\phi \wedge \psi \in \Phi$.

*If $\phi,\psi \in \Phi$ then $\phi \vee \psi \in \Phi$.


Furthermore, let $I$ denote a valuation such that $I \models X$ for every $X \in P$, and let $\Phi'$ denote the set of all formulae $\phi$ of propositional logic such that $I \models \phi$. The problem becomes:
Show that $\Phi \subseteq \Phi'$.
Now for the important realization:
Since $\Phi$ is the least set satisfying 1,2 and 3, thus it suffices to show that $\Phi'$ also satisfies 1,2 and 3.
That's it, the rest is easy. We continue:
In other words, it suffices to show the following.


*

*If $X \in P$, then $I \models X$.

*If $I \models \phi,\psi$, then $I \models \phi \wedge \psi$.

*If $I \models \phi,\psi$, then $I \models \phi \vee \psi$.


But this is trivial.


*

*True, because we assumed that $I \models X$ for every $X \in P.$

*True, by the definition of $\wedge$.

*True, by the definition of $\vee$.


ii. I'm not sure what the definition of "adequate" is, but I'm guessing this is even easier. If it just means: "can be used to express all functions of the form $\mathbb{B}^n \rightarrow \mathbb{B},$" well just take any function returning "FALSE" whenever all arguments are true and you'll have your counterexample.
