2

Which of the Following is TRUE about formulae in Conjunctive Normal form?

  1. For any formula, there is a truth assignment for which at least half the clauses evaluate true.
  2. For any formula, there is a truth assignment for a which all the clauses evaluate to true.
  3. There is a formula such that for each truth assignment at most one fourth of the clauses evaluate to true.
  4. None

I think Option 2 is correct, because Conjunctive normal form would be truth only when all the clauses evaluate to true.But according to the solution given in book, option is D. Why?

Carl Mummert
  • 81,604
Rishi Prakash
  • 393

1 Answers1

3

Option 2 is equivalent to saying "all formulas are satisfiable", which is obviously false, for instance $x\wedge \neg x$ has no valid instanciation.

Option 1 seems true. To prove it, take a variable $x$, and look at the clauses where $x$ appears. Instanciate $x$ by true if at least half of these clauses contain $x$ positively, and false otherwise. This sets at least half of the clauses where $x$ appears to true. Reiterate with other variables on remaining clauses. For instance for the formula $(x\vee y)\wedge x\wedge (\neg x\vee \neg y)\wedge y \wedge y \wedge \neg y$, you start by putting $x$ to true (by two against one), and then $y$ also to true (by two against one of the remaining clauses). In the end you satisfy $4$ out of $6$ clauses.

This implies that Option 3 is false, since it is always possible to satisfy at least half the clauses of any formula.

Denis
  • 6,945
  • 1
  • 21
  • 22
  • 1
    oooh ,it seems I misunderstood the term clause , see if formula is x∧¬x1∧x2 ,I was taking clauses as x,x1,x2 individually. But it seems all clauses means all combinations of truth values applied to this proposition. – Rishi Prakash Feb 04 '14 at 17:53
  • 1
    no you were right, your example has three clauses with one literal each. If "clause" in the question is something different, then it should be explicited. – Denis Feb 04 '14 at 17:59
  • you said "all formulas are satisfiable" ,is it somehow related to interpretation of proposition? – Rishi Prakash Feb 04 '14 at 18:02
  • "satisfiable" means there is a truth assignement that sets all the clauses to True. It is just a reformulation of Option 2. – Denis Feb 04 '14 at 18:04
  • that's contingency.Got what you want to say. Can you give examples against 1 and 3rd Option,and how can I define conjunctive normal form in the same language as that of Options . – Rishi Prakash Feb 04 '14 at 18:09
  • Both option 1 and negation of option 3 say something of the form "for all formula $\varphi$, blabla", so I cannot find examples that prove them. The only case where a witness is a proof is to contradict option 2, as I did. See here for info about CNF: http://en.wikipedia.org/wiki/Conjunctive_normal_form – Denis Feb 04 '14 at 18:13
  • 1
    I added an example of application of Option 1. – Denis Feb 04 '14 at 18:15
  • @Denis if I have 4 clauses say (a+b)(c+d)(e+f)(g+h) now how can I say that for this formula to evaluate to true I just need half of clauses to evaluate to true..??? Here all literals are different – Piyush Sawarkar Jun 29 '20 at 05:58
  • @PiyushSawarkar The claim is different here, what we say is that there is a way to instantiate variables to make at least half of the clauses true. In your example, we can even make all the clauses true. Your claim does not hold: it is possible that half of the clauses evaluate to true but not all of them. – Denis Jun 29 '20 at 09:03
  • @Denis oh yes!! I'll tell you what I understood..! So in the question its given that "there is a truth assignment" this doesn't mean that Product of sum expressions value is 1(I was thinking in that sense.)..but it actually means like this..: say in my POS expression if there are in totality 4 different literals used then out of total $2^16$ combinations the question asks that is there exists a combination which makes atleast half of the clauses to be evaluated to true.(and its evaluation to true has absolutely nothing to do with the POS expressions value to come true..) am I right? – Piyush Sawarkar Jun 29 '20 at 09:18
  • @PiyushSawarkar yes that's it – Denis Jun 29 '20 at 18:07
  • Okay Thank you @Denis! – Piyush Sawarkar Jun 29 '20 at 18:10