11
votes
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
4
votes
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
4
votes
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
4
votes
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
3
votes
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
3
votes
Accepted
convert boolean formula to DNF
Your work is fine, and it is in DNF form, which we can see by using parentheses to better show each of the disjuncts:
$$(¬d \lor a) \lor (\lnot a \land \lnot b) $$ $$\equiv (\lnot d) \lor (a) \lor (\...
- 211k
3
votes
Accepted
How to determine if a propositional formula is in DNF or CNF or both
It is $DNF$ because it can be seen as
$$
... \text{nothing} \vee (a \wedge b) \vee \text{nothing}...
$$
And $CNF$ :
$$
(...\text{nothing} \vee a \vee \text{nothing}...) \wedge (...\text{nothing} \...
- 4,153
3
votes
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
3
votes
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
3
votes
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
2
votes
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
2
votes
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
2
votes
Distributive law on two disjunctive terms
When doing boolean algebra it is common to encounter a formula like yours, and because it simplifies to something much smaller, it has been given a name:
Adjacency
$(X \lor Y) \land (X \lor \neg Y) \...
- 102k
2
votes
Accepted
Convert minterm formula to nor and not formula
Yes. You discovered that if you have a statement that is a disjunction of two disjuncts, and where each of the disjuncts is a conjunction of two literals (as in your example), then you can replace ...
- 102k
2
votes
Disjunctive normal form process
Yes, that would be good: just keep distributing any $\land $ over $\lor$ and you'll get there. In fact, you're just two such distributions away from it being in DNF
- 102k
2
votes
Is it possible for the DNF and CNF to be the same
A conjunctive normal form is a conjunction of a sequence of disjunctions of a sequence of literals or their negations. Abreviated as: a conjunction of disjunctions of literals or their ...
- 131k
2
votes
Accepted
How do I convert this propositional formula to DNF?
In fact, your proposition is always true. This is because the left term of the equivalence is true unless $V_1$ is true and $V_2$ is false, and the same is the case for the right term, so they are ...
- 5,146
2
votes
Accepted
Find minimal DNF and CNF of a logical expression $(A \implies C) \wedge \neg (B \wedge C \wedge D).$
I'll do my best to type up the K-maps in MathJax. For DNF, you just go with $G$ as follows:
$$
\begin{array}{c|c|c|c|c|}
AB &00 &01 &11 &10 \\ \hline
CD \\ \hline
00 &1 &1 &...
- 10.1k
2
votes
DNF and CNF look the same?
Since your formula has no $\land$ at all, it makes no difference whether the place they are absent from is above or below the $\lor$s in the syntax tree.
The formula is indeed in both CNF and DNF, ...
2
votes
DNF and CNF look the same?
First, note that the expression $\lnot s \lor \lnot q \lor \lnot s$ can be further simplified to $\lnot s \lor \lnot q$ by the commutativity of $\lor$ operator.
Then, $\lnot s \lor \lnot q$ is both ...
- 13.3k
2
votes
What's the most efficient way to convert any propositionnal logic formula to DNF
Well, I think there is no shortcut because of the satisfiability problem which is NP-complete.
What you can do to expand an expression to DNF is to multiply out first using the law of distributivity. ...
- 21.1k
2
votes
What's the most efficient way to convert any propositionnal logic formula to DNF
I know that using this method, the size of $G$ may be exponential in the size of $F$
That is not a failing of the method -- it is inherent in the problem that a DNF may need to be exponentially large....
2
votes
Boolean algebra - Converting DNF form to CNF form
Question already answered here Boolean algebra - Converting DNF form to CNF
avoid posting duplicate questions or asking for your homework
- 51
2
votes
Accepted
what is the canonical form (XOR Normal form)?
Here is an example. Take the statement $A \lor (\neg A \land B)$. Let's put it on a truh-table, using the convention that we put the reference columns in alphabetical order, and that we fill out the ...
- 102k
2
votes
Accepted
DNF constraint in integer linear programming
The logical proposition $$(x \land y \land z) \lor (\neg w \land \neg s \land \neg t) \lor (\neg x \land \neg y \land \neg z) \lor (w \land s \land t)$$ can be rewritten in conjunctive normal form as
$...
- 48.2k
2
votes
Converting to DNF from CNF
I'll first take the dual of your statement by swapping all $\lor$'s with $\land$'s, and vice versa:
$$\left(a_1 \land \neg a_2 \land \neg a_3 \land ... \land \neg a_K \right) \lor$$
$$\left(\neg a_1 ...
- 102k
2
votes
Accepted
CNF and DNF form of single logical variable
The statement $(1)$
$$A\land\lnot A,\tag{1}$$
is already in CNF (conjunctive normal form), and DNF (disjunctive normal form).
All conjunctions of literals and all disjunctions of literals are in ...
- 1,946
Only top scored, non community-wiki answers of a minimum length are eligible