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

• Don't close this! The asker just isn't sure how to get started. He has a whole sequence of questions to do, and probably just needs a "kickstart," see here. – goblin Sep 25 '13 at 7:47
• And I think that kickstart will be easier to provide if we have more information about what the user already understands, hence my vote to close as lacking context. – mdp Sep 25 '13 at 11:04
• To be as constructive as possible: if the OP really doesn't know how to start, and would like to see a solution to the first of the problems to help with the others, then this information should be in the body of the question - I would probably not vote to close if this was there. – mdp Sep 25 '13 at 11:08
• @MattPressland, fair enough, but it appears to be a first-time user, so I think we should be gentle. – goblin Sep 25 '13 at 11:12
• @user18921 Fair point. I think I now feel that the rewording of "closed" to "on hold", and the descriptive message explaining what can be done to have the question reopened make this sort of thing gentle enough, but it is hard to imagine exactly how the average new user will respond to it. – mdp Sep 25 '13 at 11:20

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.