3
$\begingroup$

I proved the following statement by induction:

Let $A$ be a propositional formula which uses only the connectives $→$ and $↔$. Prove (by induction on the complexity of $A$) that if every propositional variable is true then $A$ is true.

which was fairly straight forward to prove but then there was a follow up question which I was a little unsure of that referred to the previous proof:

Then deduce that there is a truth function $f$ that is not expressed by any propositional formula that uses only the connectives $→$ and $↔$

By the previous proof it was obvious to see that A would be true if every variable was true but if there was some variable that was not true it may be that A is not true. So by this the truth function may be different from the truth table of some propositional formula that uses only the connectives → and ↔ and then it would not be expressed by this formula?

Does this prove the statement correctly? My understanding of the truth functions and the idea of 'expressing a formula' So I'm unsure if my example is entirely true.

$\endgroup$
1
$\begingroup$

If you can express a truth function as a propositional formula of some sort, it means that both give the same output for every input (combination of truth values for atoms). If they differ on at least one input, then they are not the same. Since you have done the first part correctly, you should be able to easily figure out a truth function that must be different from every propositional formula that uses only implication and equivalence operators.

Hint:

You already know what every propositional formula of that kind does to the all-true input combination. So make a truth function that does not do the same.

$\endgroup$
1
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$
    – user642796
    Jun 8 '15 at 19:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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