1
$\begingroup$

The proof (Theorem 2.5) refers to an induction proof that establishes that all formulae composed of $\{\to, \iff, \lnot, \land, \lor\}$ is logically equivalent to a conjunctive (CF) and disjunctive form (DF). It will be attached at the end of this question.

By CF it means the following: enter image description here

The question also asked for a disjunctive form, which is very similar to CF; but I think I got it, which is $\lnot P\lor(\lnot Q\lor(R\lor\lnot P) $ (or ignore the brackets).

But when it comes to CF I am stuck. So I applied various equivalences to change it to $\lnot P\lor \lnot(Q\land(\lnot R\land P))$ , but this is as close as I can get.

In a nutshell, this seems to be the form I have: $\bigwedge_{i=1}^n\theta_i\lor\lnot \bigwedge_{j=1}^m \psi_j$, where the LHS equals to $\lnot P$ and the RHS equals to $\lnot(Q\land(\lnot R\land P))$. If I can get rid of the negation on the RHS and get the RHS into just a chain of conjunction, I can use 2.41c (as attached below) to get what I need. But I just couldn't get rid of the negation.

Could anyone please help? I have been trying on my own for weeks and I still can't crack it. Thank you so much!


enter image description here enter image description here enter image description here enter image description here enter image description here

$\endgroup$
1
$\begingroup$

The formula $P→(Q→(R∨¬P))$ is equivalent to: $¬P∨(¬Q∨(R∨¬P))$, that - using distributivity and associativity - is equivalent to:

$(¬P∨¬P)∨(¬Q∨R) \equiv (¬P∨¬Q∨R)$,

which is in Conjunctive normal form because it is a conjunction of one or more clauses, where a clause is a disjunction of literals.

It has the form $\bigwedge_{i=1}^1 (\bigvee_{j=1}^3 q_{i,j})$.

In this case $i=1$, because we have only one conjunct.

$\endgroup$
1
  • $\begingroup$ Thank you so much! Now it all makes sense because I kept thinking for the last few weeks, that there is simply no way of forcing a formula with a $\land$ as the main operator into one with a $\lor $ (vice versa) as the main operator. But with this it all makes sense. Your answer is very clear and concise. $\endgroup$ – Daniel Mak Dec 28 '17 at 15:06

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.