# Tag Info

## Hot answers tagged disjunctive-normal-form

Accepted

### What does disjunct mean?

A disjunct of a disjunction is simply one its two inputs. So, $$P\lor Q$$ has disjuncts $P$ and $Q.$ The compound disjunction $$P\lor Q\lor R\lor S$$ can be considered to have four disjuncts, $P,Q,R$ ...
• 40.5k
Accepted

### Prove that every to $\varphi_n$ equivalent formula in DNF has at least $2^n$ conjunctive clauses

Your approach is a valid approach, but I don't see how one could finish that argument. So instead, I'll give you my idea. Let's look at one (satisfiable) clause $c_k$ from the minimal DNF. How many ...
• 804

### Boolean algebra - Converting DNF form to CNF

HINT Are you familiar with FOIL, that says that $(A+B)(C+D) = AC+AD+BC+BD$? Well, that principle generalizes more larger or more terms, simply by systematically taking all possible ways of taking 1 ...
• 102k
Accepted

### Can a logical formula that is a contradiction be represented as Disjunctive Normal Form?

$P \land \neg P$ is in DNF It may not look like it, but it really is. Here's the thing: a statement is in DNF iff it is a generalized disjunction of generalized conjunctions of literals. And by ...
• 102k

### New to discrete mathematics - Disjunctive normal form

Here is a concrete example: Suppose we have the following truth-table ($P * Q$ is some arbitrary formula involving atomic propositions $P$ and $Q$): \begin{array}{cc|c} P & Q & P * Q\\ \...
• 102k
Accepted

• 4,153

### Converting formula to disjunctive normal form

You've made mistakes in failing to use DeMorgans. First, I use, like you did, the equivalence of $P\rightarrow Q \equiv \lnot P \lor Q$, and second, I use DeMorgan's Law in step $(1);$ DeMorgan's ...
• 211k
Accepted

### Every $n$-ary logical connective has a DNF

If you were to put the function on a truth-table, you can always find an expression (that is automatically in DNF) that is equivalent to that function: for every row where the function value is true, ...
• 102k
Accepted

### Normal disjunctive and conjuctive form from a truth table

When you are looking for a DNF, you focus on all rows where the table result is a $1$, and you generate a conjunction for that row exactly the way you did, and than you disjunct together all those ...
• 102k

### Find DNF and CNF of an expression

For DNF: look at each row where $p = 1$ encode a proposition from the atoms $p_i$ for row $i$ (that gives $p$ is 1) that has $a_i$ if that atom is 1 in the truth table and $\neg a_i$ if it's 0. You ...
• 6,644
Accepted

### How can DPLL formula be used to check whether a DNF formula is valid?

OK, so the assumption here is that you are given a (single) DNF formula, and you have to test whether it is valid, i.e. whether it is a tautology, right? OK, yes, we can do something akin to DPLL ...
• 102k