I'm really stuck at proving general versions for any propositional formula for example:

I) Use truth table to prove this De Morgan's law $$ \lnot (P \land Q) \equiv \lnot P \lor \lnot Q $$

Which is very simple, we construct truth table and compare the results column, if they are the same they are equivalent

II) Also show the general version $$ \lnot (A \land B) \equiv \lnot A \lor \lnot B $$ of the equivalence holds, for any propositional formula A and B. Hint: it is not possible to use the truth table method here, because A and B are arbitrary formulas

The only way that I know is to assume A or B to be tautologies or contradictions so we can substitute A or B with 1 or 0 and proceed with the truth table. However, that doesn't sound about right and we can't use truth tables as well..

Thank you

  • $\begingroup$ Substitution theorem. $\endgroup$ – Mauro ALLEGRANZA Nov 7 '16 at 19:50
  • $\begingroup$ I still don't get it, I don't think we use or doing the subject you referred me to. Thank you $\endgroup$ – Zed Nov 7 '16 at 20:19
  • $\begingroup$ Well, Mauro is right: the fact that you can substitute arbitrary formulas for atomic statements in equivalences is called the Substitution Theorem... So that's exactly what you want. It's not simple enough to put in a comment though, so the best thing to do is for you to do some research about this theorem. $\endgroup$ – Bram28 Nov 7 '16 at 23:13
  • $\begingroup$ @MauroALLEGRANZA I have no idea of the basis for a proof theory here, but I'm less than half 'tempted' to try to use axioms with functorial variables to prove this, including the encoding of the principle of bivalence. But, is that (C (δ 0) (C (δ 1) (δ p))) or is it C(δ(0) C(δ(1) δ(p))? It's the former. I also have the difficulty that I want to correlate one for each row of the truth tables to a δ expression, and that implies that we lose basically independence of axioms/definitions. Also, this probably appeared in a course where you can't use functorial variables in the first place. $\endgroup$ – Doug Spoonwood Nov 8 '16 at 6:47
  • $\begingroup$ @MauroALLEGRANZA Actually, on second thought, I don't know that independence would get lost here, but nor do I know that we would have independence either. $\endgroup$ – Doug Spoonwood Nov 8 '16 at 14:59

Your Answer

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

Browse other questions tagged or ask your own question.