So we have to show that given a particular set of propositional connectives that the set is not adequate. I am comfortable with what a set being adequate means but I can't get my head around why the proof by induction works and is sufficient. This is a question and solution which is given in my notes:

"Q) Prove that the connective § with truth table shown below is not adequate.

$$\begin{array}{cc|c} p & q & p§q \\ \hline T& T& F\\ T& F& F\\ F& T& T\\ F& F & F\\ \end{array}$$

A) We prove by induction on complexity of terms, that for any term built up from a set L of propositional variables using § only - let us denote the set of such terms by Term§(L) - and for any valuation v, if v(p) = F for every p ∈ L, then v(s) = F for every s ∈ Term§(L). That will be enough since then there will be no term in Term§(L) which is a tautology.

Base case (s a propositional variable): this is our hypothesis.

Induction step (just one): Suppose that s = t§u where, by induction, we may assume that v(t) = F = v(u). Then, consulting the truth table for §, we see that v(s) = F, as required."

I understand why the result shows that the set is not adequate as it shows that there is no term that can be built from the connectives that make a tautology, however I don't understand the assumption that:

"If v(p) = F for every p ∈ L, then v(s) = F for every s ∈ Term§(L)"

How can we just make this assumption? What about the valuations where v(p) = T? Don't they need to be accounted for? Struggling with the whole idea with the proof on complexity on terms so thanks for reading.

up vote 0 down vote accepted
  1. I think you agree that in order to show that § is inadequate, it is enough to show that there is no way to express a tautology with just §.

  2. A tautology is a term $t$ whose value $v(t)$ is true for every assignment of values to the variables of $t$.

  3. If there is any assignment of values to $t$'s variables that results in $t$ having a false value, then $t$ is not a tautology.

  4. In particular, if assigning false values to all the variables of $t$ results in $t$ having a false value also, then $t$ is not a tautology. (This is the crucial point that seems to be giving you trouble.)

  5. But it is the case that if $t$ is made of only §, then assigning false values to all its variables results in $t$ also having a false value. (This is the step that is justified by the induction proof.)

  6. Therefore, any term $t$ made of only § is not a tautology.

  7. Therefore, § is not adequate.

Is this clearer now?


You said you don't understand how to go from step 3 to step 4.

Consider this silly example, which follows the same pattern:

  1. A paradise is a country where every inhabitant is happy.
  2. Gaston, who lives in France, is not happy.
  3. Therefore, France is not a paradise.

“But,” you say, “why don't we have to consider Pierre? Pierre also lives in France!”

Pierre doesn't matter. France is only a paradise if every person in France is happy. To show that France is not a paradise, we only have to find one person in France who is not happy.

  1. A tautology is a term for which every assignment of values to its variables results in its having a true value.
  2. Assigning all false values to the variables of the term $t$ results in $t$ having a false value.
  3. Therefore, $t$ is not a tautology.

“But,” you say, “why don't we have to consider other assignments of values to the variables of $t$? Those are assignments too!”

Those assignments don't matter. $t$ is only a tautology if every assignment results in $t$ having a true value. To show that $t$ is not a tautology, we only have to find one assignment that results in $t$ having a false value.

  • I understand 1-3. For 4. Why do we look at the value of t where all the variables of t are false? What about all the other valuations? Why do we only look at this case? – user141673 Apr 8 '14 at 15:58
  • @user141673 Do you understand why we only need to look at one case, and you are asking why it is this case and not some other? Or do you not understand why it is sufficient to look at this one case? – MJD Apr 8 '14 at 16:04
  • I do not understand why it is sufficient to look at one case AND why it is this case in particular. Thanks – user141673 Apr 8 '14 at 16:10
  • I have elaborated on why one can show that a term is not a tautology by giving a single valuation for which the term is false. – MJD Apr 8 '14 at 16:19
  • I am very happy now thank you. I think what was giving me trouble was the fact that the valuation applies to all possible terms made by the given connective and I was confusing all valuations with all possible terms that can be made. You have made it very clear for me thank you. – user141673 Apr 8 '14 at 16:34

You must first show that the Basis step holds.

Whay does it mean ? That a formula built up with the § connective with only one propositional variable $p$ can never be a tautology.

This is because $p§p$ must be only $True-True$ or $False-False$, and both are mapped into $False$ by the truth-table.

Having proved this, you must use it in the Induction step that "reduce" the case $\alpha § \beta$ to the verification (via the truth-table) that the property hold for it, assuming that it holds for $\alpha$ and $\beta$ (being "shorter", the induction hypotheses applies to them).

Your set of terms T, I take it, is the smallest subset of the set of strings, S, generated from your propositional variables P, and the symbols §, (, and ) using the production

s,t in T => (s§t) is in T. (1)

That is, T is the smallest subset of S containing P and closed under (*).

Now if we have a valuation of v: P --> {T,F} which maps every element of P to F, then let TF be the subset of T on which v has value F, that is, let TF = {t in T | v(t) = F}. Now by our choice of v, P is contained in TF. Further if s,t are in TF then by the truth table definition of §, (s§t) is in TF. Hence TF contains P and is closed under (1). But your set of terms that I have called T is the smallest subset of S containing P and closed under (1). Hence TF = T and indeed T contains no tautologies.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.