1
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ Substitution theorem. $\endgroup$ Commented Nov 7, 2016 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$ Commented Nov 7, 2016 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$ Commented Nov 7, 2016 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$ Commented Nov 8, 2016 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$ Commented Nov 8, 2016 at 14:59

0

Reset to default

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.