0
$\begingroup$

I have one formula that I do not understand why it is CNF and one that is not CNF, namely.

  1. p && !q (NOT NCF)

and

  1. !!p(CNF).

According to the exercise where I found these examples, 1 is not CNF and 2 is CNF.

How can the first formula not be CNF, when for example p && q is CNF. If for example !!p is part of a formula we will translate it to p, how can we say that it is CNF?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

Your examples do not look correct according to my understanding of the definition of CNF. The first formula is CNF; it has two clauses, each with a single literal. I would say that the second isn't, but the equivalent formula p is. See https://en.wikipedia.org/wiki/Conjunctive_normal_form.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Yes, that was exactly my thought! This was just some exercise and I could not understand how the examples above could be correct. Will update my question.. $\endgroup$
    – mattssoncode
    Nov 13, 2020 at 17:58

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.