2.2k views

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 to true.

2. For any formula, there is a truth assignment for 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 of the above.

is conjunctive normal form in digital logic ? never heard about it .... where can I read about it.
Conjunctive Normal form is nothing but Maxterm expansion or you can say products of sums expression and disjunctive normal form is sum of products or minterm expressio
You've got it backwards, CNF is similar to the Product Of Sums (POS) and DNF is similar to the Sum Of Products (SOP)

Habibkhan . I think you swapped the meaning of Conjunctive Normal form and Disjunctive Normal form .
Conjunctive Normal form = MAXTERM (product of sum)
Disjunctive Normal Form =Minterms (sum of Product )
Source: Wikipedia

pls explain this two form using truth table

M not getting this .. plz explain in easy way. @joshi_nitish

@Anu sir,

please have a look at this

Can we say same for the Disjunctive Normal form ?

Good question.

So Let us derive some formula -

Let us assume some DNF has $m$ terms(clause) and we have $k$ boolean variable.

Consider an arbitrary truth assignment. For each of its clause $i$, introduce a random variable. $$X_i = \begin{cases} 1 & \text{if clause } i \text{ is satisfied;} \\ 0 & \text{otherwise.} \end{cases}$$
Then, $X = \prod_{i=1}^{m} X_i$ is the number of satisfied clauses.

Probability that one clause will be TRUE ($X_{i}$) = $\frac{1}{2^{k}}$ .

So, $E(X_i) =1 \times \frac{1}{2^k} = \frac{1}{2^k}$

Summation on both sides to get $E(X)$,

Therefore, we have $E(X) = \sum_i E(X_i)$ =   $\frac{m}{2^{k}}$  --- where $m$ is the number of clauses.
$E(X)$ represents expected number of satisfied(to true) clauses in some random assignment of variables.

I hope this helps. Please notify if anything is not proper.

@Chhotu I am not sure whether any solution here has proved the statement completely (may be wrong). See this, You have tossed a fair coin 2 times, prove that you will get head at least half of the time in $any$ such attempt . Now,if you prove via expectation then of course you will find the statement true, but there is a case whether you get $TT$. So, I am not yet convinced that we can prove a statement using Expectation.

To Prove: For any formula, there is a truth assignment for which at least half the clauses evaluate to true

Proof:
Consider an arbitrary truth assignment. For each of its clause $i$, introduce a random variable. $$X_i = \begin{cases} 1 & \text{if clause } i \text{ is satisfied;} \\ 0 & \text{otherwise.} \end{cases}$$
Then, $X = \sum _i X_i$ is the number of satisfied clauses.

Given any clause $c$, it is unsatisfied only if all of its $k$ constituent literals evaluates to false; as they are joined by OR operator coz the formula is in CNF.
Now, because each literal within a clause has a $\frac{1}{2}$ chance of evaluating to true independently of any of the truth value of any of the other literals, the probability that they are all false is $\left( \frac{1}{2} \right)^k = \frac{1}{2^k}$.
Thus, the probability that $c$ is satisfied(true) is $1- \frac{1}{2^k}$

So, $E(X_i) =1 \times \left( 1- \frac{1}{2^k} \right) = 1- \frac{1}{2^k}$
This means that $E(X_i) \geq \frac{1}{2}$
(try putting arbitrary valid values of k to see that)

Summation on both sides to get $E(X)$,
Therefore, we have $E(X) = \sum_i E(X_i) \geq \frac{m}{2}$; where $m$ is the number of clauses.
$E(X)$ represents expected number of satisfied(to true) clauses.

So, there must exist an assignment that satisfies(to true) at least half of the clauses.

selected by
Can expectation be used for proof?
If we are talking in the context of this question, then Yes.
okay :) Since expected value is $X$, there must be some value $\geq X$.

## good proof :)

How E(Xi) is calculated above please elaborate .
Can we say same for the Disjunctive Normal form ?

@junaid, If we follow the above proof then we can conclude for DNF that, for any formula ,there is a truth assignment for which atleast half of the clause will not be satisfied.

@reena, For DNF shouldn't it be like even one clause is false then entire formula will be false as it uses AND operator??
nice explanation....what should be the answer in the case of DNF for the same question??

Therefore, we have $E(X)=∑_iE(X_i)≥m/2$; where m is the number of clauses. $E(X)$ represents expected number of satisfied(to true) clauses.

Here expectation of binomial distribution is used which is $n*p$. ( here $n = m$ and $p =1/2$)

check : http://goo.gl/ZruULw

edited

In two books it is given that

One can always satisfy at least half of the clause of cnf (the all true or the all false assignment will do)

https://goo.gl/TO2zVG
https://goo.gl/kmokQb

But i am unable to figure out reason behind that.

@Sonam, The link u provided, Proved like this

Proof: There are 'n' clauses and 'k' variables that appears in 'n' clauses. I pick one of the variable among 'k' then I assign a boolean value that satises at least half of the clauses in which it appears. Remove the satised clauses and continue. and so on.

This way, the assignment guarantees to satisfies half of the causes.

This is also not intuitive to me :(

Hi Sachin sir,

isn't option B also correct

Tanks.

@sachin You can divide the max-terms into 2 equivalence classes such that both are complementary having 2^(n-1) max-terms each for n variables.There is one-one correspondance.Now when you linearly iterate over any one of those classes,atleast one of th two(the image of function in other class or the element itself)must be true.
+1 vote
Easy proof:

You can divide the max-terms into 2  classes such that both are complementary having 2^(n-1) max-terms each for n variables.There is a clear one-one correspondance.Now when you linearly iterate over any one of those classes,atleast one of the two(the image of function in other class or the element itself)must be true.