Questions tagged [disjunctive-normal-form]

A formula is in disjunctive normal form (DNF) if it is a disjunction of conjunctive clauses.

Filter by
Sorted by
Tagged with
1 vote
1 answer
62 views

I'm studying boolean algebra in the discrete mathematics

problem Let $a_4a_3a_2a_1a_0$ be a 5- bits binary numbers (each $a_i=0$ or $1$). Write an expression in Boolean algebra that evaluates to $1$ when odd number of bits of the number is $1$ and $0$ ...
user avatar
  • 55
0 votes
0 answers
32 views

How to deduce the PDNF of ~A?

For my question, $A =\lnot P\land(Q \to R)$. After making the truth table, I managed to get the PDNF of it which is $$(\lnot p\land q\land r)\lor(\lnot p\land\lnot q\land r)\lor(\lnot p\land\lnot q\...
user avatar
1 vote
1 answer
35 views

Proposition is CNF and DNF

So I understand that CNF is the conjunction of one or more disjunctive clauses and that a DNF is a disjunction of one or more conjunctive clauses, however, I was wondering if there could be a case ...
user avatar
3 votes
0 answers
32 views

Number of irreducible DNFs of cyclic boolean function

Let us say that cyclic boolean function is a function such that we can connect all its True vertices with edges (in boolean cube) and get a cycle. Let the number of edges in this cycle equals $n$. I ...
user avatar
-2 votes
1 answer
83 views

Normal disjunctive and conjuctive form from a truth table

Let's say that we get a table with zeros and ones. We need to get it into disjunctive normal form or conjuctive normal form. We also have discrete variables $x_1,..,x_n$ that are either $1$ or $0$. ...
user avatar
  • 2,323
0 votes
0 answers
42 views

Formalizing with Induction

In this thread here, it makes sense why there is exponential blow up because of the conversion. My question is how would we use induction to prove this? I've started, but I'm getting mixed up with the ...
user avatar
0 votes
1 answer
78 views

For CNF and DNF why do we look at the interpretations that make the formula false and true respectively?

Okay so I know how to obtain CNF and DNF from a truth table but I do not understand why. For example, for the formula $$P ⟺ Q$$ We are trying to convert the formula P ⟺ Q to an equivalent formula in ...
user avatar
0 votes
0 answers
32 views

A question on a specific kind of prenex normal form

We say that a first-order formula is in DNF if it can be obtained from a propositional formula in DNF by replacement of propositional variables with atomic predicate formulas. We say that $A$ is in ...
user avatar
0 votes
0 answers
40 views

Relationship between disjuncts of $a,b$ when $(a \rightarrow b)$ is tautology

What is the relationship between the disjuncts of formulae $a,b$ ( in DNF) when $ \neg a$ is not a tautology and $(a \rightarrow b)$ is a tautology? Say (up to logical equivalence) $ a= a_1 \vee a_2 ....
user avatar
2 votes
1 answer
74 views

Find the disjunctive normal form

I am looking for the disjunctive normal form of $(A \to B) \wedge ((B \;\vee \; C) \to A)$. I know that $\neg A \vee B \equiv A \to B$. So when use this I get and the morgan law together I get: $$(A \...
user avatar
0 votes
1 answer
86 views

Reduce ((y ⊕ z) ⇒ (x + y)) ⇒ yz to disjunctive normal form (DNF)

How can I reduce this boolean function to disjunctive normal form? $$((y ⊕ z) ⇒ (x + y)) ⇒ yz$$ It may be possible to do using truth tables, but I am not sure. If it's possible to give examples with ...
user avatar
0 votes
1 answer
16 views

expanding disjunctive pairs of conjunctives using distributive law

I am having a bit of a brain malfunction. I am working through a functional programming class and I am trying to in parallel fake some knowledge of discrete mathematics. I am working through a simple ...
user avatar
0 votes
1 answer
76 views

How to get CNF of propositional formula form DNF of its complement?

Explain how to read off a CNF for propositional formula directly from a DNF from its complement. I've managed to explain it in words, but can't write a rigorous proof of that. How to show this in ...
user avatar
  • 123
0 votes
0 answers
68 views

Generalisation of DNF to CNF for DNF of m choose l clauses

Given two values $m$ and $l$, I can create corresponding DNF formula which is a disjunction of all $m \choose l$ combinations, where each number corresponds to a variable. Each combination is, in ...
user avatar
  • 1
0 votes
1 answer
92 views

How to introduce conjunctions into a conditional statements so as to get the CNF and DNF?

I have the following conditional statement: ((p → q) → p) → p Knowing that CNF is a conjunction of disjunctions (and that DNF is a disjunction of conjunctions), we will obviously have to introduce ...
user avatar
0 votes
0 answers
17 views

Find a set of variables for which an specific expression evaluates to true

Description. I have $m \in \mathbb N$ and three possible logical expressions, which I immediately presented in the most convenient notation: $X \to Y = \lnot X \lor Y$ $X \to \lnot Y = \lnot X \lor \...
user avatar
0 votes
1 answer
238 views

Explain into disjunctive normal form

Can anyone tell me how to Express the following formula into disjunctive normal form ⌐ (p V q) ↔ (p ^ q). I have done few steps but I need your help.
user avatar
0 votes
1 answer
29 views

How to prove that a given disjunctive or conjuctive normal form is minimal?

what is the argument that a given canonical normalform cannot be reduced any further? For example have a look at this $dnf(f) = (\neg a \wedge b \wedge c) \vee (a \wedge \neg b \wedge c) \vee(a \...
user avatar
0 votes
1 answer
46 views

DNF to CNF of a simple expression

I have a formula like this: $$\bigvee_{\substack{i \in [1,...,m] \\ j \in [1,...,m]}} x_{i} \wedge x_{j}$$ What is the equivalent formula in CNF (conjunctive normal form)?
user avatar
0 votes
1 answer
21 views

Turn Disjunctive Normal Form into only AND and NOT statements

I'm working on implementing logic gates and want to implement an OR gate using only AND and NOT gates. I came up with this canonical form for the OR function. $$Or(x, y) = (\lnot{x} \land y) \lor (x \...
user avatar
0 votes
1 answer
59 views

Need help for turn this form $\neg ((p \Rightarrow q) \Rightarrow r)$ into DNF

How can I turn this form $\neg( ( p \Rightarrow q ) \Rightarrow r )$ to disjunctive normal form and to the disjunctive normal form fully developed ? I have done the truth table see below I ...
user avatar
0 votes
0 answers
75 views

Is a DNF without negations or duplicate terms a disjunction of prime implicants?

Disclaimer: I am a software engineer with a Bsc. in Informatics, and no signifcant background in Mathematics (sadly). I have a real life programming problem, which is equivalent to finding all prime ...
user avatar
  • 11
1 vote
1 answer
227 views

CNF and DNF form of single logical variable

I am learning boolean algebra. So apologies for this naive question. During our discussion among friends, we came across following puzzle, How can I convert following statement into CNF and DNF? $$ ...
user avatar
  • 113
0 votes
0 answers
81 views

Kleene closure of a disjunctive normal form for regular expressions

$\newcommand{\Kstar}[1]{#1^\ast}$ I would like to write the regular expression $$ a^\ast b^\ast + ( a + b )^\ast b a ( a + b )^\ast $$ as a Kleene closure of a union of catenations or in other words, ...
user avatar
  • 691
2 votes
2 answers
523 views

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

Hi I was trying to solve this math problem in mathematics. Obtain the D.N.F, C.N.F, P.D.N.F, P.C.N.F of the following expression : $(Q \to P) \land (\lnot P \land Q)$ I understand that there is no ...
user avatar
  • 61
1 vote
1 answer
29 views

Is this DNF right? [duplicate]

The question asks to convert $\neg(p \lor \neg q) \rightarrow (\neg r \land (p \rightarrow r))$ to a DNF. I got it till $\neg(\neg p \land q) \lor (\neg r \land \neg p)$. I dont know how to simplify ...
user avatar
0 votes
1 answer
109 views

How to convert to Disjunctive Normal Form

The question gives the following: ¬(p ∨ ¬q) → (¬r ∧ (p → r)) With my own working, I have come to the answer of (p ∨ ¬q) ∧ (¬r ∧ ¬p) ∧ (¬r ∧ r). Can anyone tell me if this is correct? Also, please ...
user avatar
0 votes
1 answer
106 views

Task about Conjunctive and Disjunctive normal form.

Happy new year to all! I have a question related to my Discrete Mathematics examination: Consider the following (parametrized) propositional formula $𝜑_𝑛$: ($p_1$V$p_{2n+1}$) & (!$p_1$V!$p_2$)...
user avatar
1 vote
0 answers
55 views

can you help me find the dnf of this expression ? i got messy

I want to find the DNF of the following expression but it got all messy. I also tried it in wolfram alpha, and of course it showed i really need the steps you need to make to get there $\dots$ This ...
user avatar
0 votes
1 answer
292 views

Converting to DNF from CNF

I'm having a bit of a problem when trying to convert this CNF formula to DNF: \begin{align} & \left(a_1 \vee \neg a_2 \vee \neg a_3 \vee ... \vee \neg a_K \right) \wedge \\ & \left(\neg a_1 \...
user avatar
2 votes
1 answer
61 views

CNF or DNF, $p(x)=0 \implies f=1$

Write either a $CNF$ or a$\;DNF$ of the expression $f$ such that $f=0\iff (x_2x_1x_0)_{(2)}$ is a zero point of the polynomial: $$p(x)=x^3-8x^2+12x=x(x-2)(x-6)$$ $$p(x)=0\iff x\in \{0,2,6\}$$ $$\begin{...
user avatar
1 vote
0 answers
63 views

A fomular for CNF-DNF conversion

I just see this nice generalisation of sets: $$\bigcup_{(i,j) \in I \times J} (A_i \times B_j) = \bigcup_{i \in I} \bigcup_{j \in J} (A_i \times B_j) = \Biggl(\bigcup_{i \in I} A_i\Biggr) \times \...
user avatar
  • 5,100
4 votes
1 answer
82 views

Transform into DNF

Transform into a DNF form $$[(p \lor q) \to (q \lor r)] \to [(p \to q) \land \neg r]$$ I transformed it into following formula, but don't know what to do next: $$[(p\lor q) ∧ (\neg q∧\neg r)]\lor[(\...
user avatar
  • 41
1 vote
3 answers
62 views

DNF constraint in integer linear programming

I have the following logical constraint which I am having difficulty to put into an equation (or set of equations): $((x = 1 \text{ AND } y = 1 \text{ AND } z = 1) \text{ OR } (w = 0 \text{ AND } s = ...
user avatar
  • 1,128
1 vote
1 answer
983 views

what is the canonical form (XOR Normal form)?

I'm studying discrete mathematics now. And a slide said "If a normal form leads to a unique representation for every Boolean function, we call it canonical. One canonical form("xor normal form") ...
user avatar
  • 17
0 votes
1 answer
230 views

Propositional logic DNF when formula is unsatisfiable [closed]

I understand that every formula in propositional logic can be represented in the form of a DNF, and such DNF can be constructed either by extracting true propositions from a truth table or using ...
user avatar
2 votes
3 answers
1k views

Boolean Algebra: How does $\bar A\bar BC+\bar A\bar C\bar D+A\bar CD+\bar AB\bar C$ become $\bar A\bar BC + \bar A\bar C\bar D+A\bar CD+B\bar CD$?

I'm trying to understand one of the steps taken during the process of getting a cnf in Boolean algebra but I just cant understand what is happening here. $$\bar A \bar B C + \bar A \bar C \bar D + ...
user avatar
1 vote
1 answer
118 views

Boolean algebra - Converting DNF form to CNF form

I´ve tried at least dozen ways to convert DNF to CNF, yet I always end up with something wrong. Here is the DNF: (B ∧ D) ∨ (C ∧ D) ∨ (¬D ∧ ¬B) ∨ (¬D ∧ ¬C) . Is there someone who can help me with it ...
user avatar
  • 21
2 votes
1 answer
331 views

Boolean algebra - Converting DNF form to CNF

I've tried at least a dozen ways to convert this DNF to CNF, yet I always end up with something unusable. Here is the DNF: $$y= (A \wedge B \wedge \neg C \wedge D) \vee (A \wedge B \wedge C \wedge \...
user avatar
1 vote
0 answers
136 views

Learning algorithm for a CNF

I want to create an algorithm for a CNF formula with clause length n on m literals that is mistake bound by $m^{O(n)}$. I know that I want to take the input and use feature expansion to create a ...
user avatar
  • 49
1 vote
1 answer
1k views

Disjunctive normal form and Conjunctive normal form from truth tables

Hi hope you're having a good day. I'm working through some work about CNF and DNF and one of the questions was write the answer from a truth table in the CNF, then DNF from the table. So I wrote the ...
user avatar
2 votes
2 answers
138 views

What's the most efficient way to convert any propositionnal logic formula to DNF

In every paper that I've read so far, authors say that they convert a formula into disjunctive normal form (DNF) but they don't give any detail on how they are doing it. The only way of converting a ...
user avatar
  • 21
0 votes
2 answers
218 views

DNF and CNF look the same?

When constructing both a DNF and CNF of the below, my solutions look the same. I must be off somewhere. This is what they look like: $\lnot s ∨ \lnot q ∨ \lnot s$ How would you construct a DNF and ...
user avatar
-1 votes
1 answer
167 views

Semantics of exclusive or

How do I get a description of $\text {XOR}$ (exclusive or) only using the operators $\wedge$, $\vee$, $\neg$, $\rightarrow$ And is it possible to prove the correctness of such description?
user avatar
0 votes
2 answers
2k views

Disjunctive normal form of (¬(p → q) → (q ∧ ¬r))

I learning how to convert to disjunctive normal forms, I have the following, (¬(p → q) → (q ∧ ¬r)) I understand any p→q can be represented as (¬p)∨q, therefore ...
user avatar
  • 199
0 votes
0 answers
26 views

Convert expression to disjunctive normal form (DNF)

Problem Convert following to DNF $$ p \rightarrow (q \wedge \neg p) $$ Attempt to convert $$ p \rightarrow (q \wedge \neg p) $$ $$ \iff \neg p \vee (q \wedge \neg p) $$ $$ \iff q \vee (\neg p ...
user avatar
  • 2,221
2 votes
1 answer
792 views

Correctness of DNF representation of XOR

I'm trying to show that XOR can be written as a DNF with $2^{n-1}$ terms. Note that $\mathrm{XOR}_n(x_1, \dots, x_n) := \oplus_{k=1}^n x_k$, where $\oplus$ is addition in $\mathbf{F}_2$, and $\...
user avatar
  • 2,382
1 vote
2 answers
891 views

Exponential blow-up of DNF to CNF $2^{n}$ terms?

Why does every DNF formula for $(x_{1} \vee y_{1}) \wedge (x_{2} \vee y_{2})\wedge \ldots \wedge (x_{n} \vee y_{n})$ have at least $2^{n}$ terms? This statement is on the Wikipedia page for DNF ...
user avatar
0 votes
1 answer
677 views

Is it possible to get the CNF out of the DNF of this expression

Can i get the CNF of the following expression if i know the DNF? I've the following expression: $$\Bigl(\bigl(A\rightarrow (\overline A \land B) \bigr)\land \bigl((\overline A \land B)\rightarrow A\...
user avatar
0 votes
1 answer
145 views

satisfying boolean n variable DNF formula

I have an n variable boolean DNF formula and an input set,z consisting of n-tuples. Each tuple consists of truth/false assignment to n variable. the number of tuples in Z is not fixed, obviously <= ...
user avatar