Propositional Logic - induction

Question

(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.

Answer 1

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

1. If $X \in P$, then $X \in \Phi$
2. If $\phi,\psi \in \Phi$ then $\phi \wedge \psi \in \Phi$.
3. 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.

1. If $X \in P$, then $I \models X$.
2. If $I \models \phi,\psi$, then $I \models \phi \wedge \psi$.
3. If $I \models \phi,\psi$, then $I \models \phi \vee \psi$.

But this is trivial.

1. True, because we assumed that $I \models X$ for every $X \in P.$
2. True, by the definition of $\wedge$.
3. 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.