# Questions tagged [disjunctive-normal-form]

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

109 questions
Filter by
Sorted by
Tagged with
1 vote
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$ ...
• 55
32 views

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 ...
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 ...
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 ...
• 123
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 ...
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 ...
17 views

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)?
21 views

• 113
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, ...
• 691
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 ...
• 61
1 vote
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 ...
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 ...
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$)...
1 vote
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 ...
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 \...
61 views

• 5,100
82 views

• 21
1 vote
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 ...
• 21
331 views

• 2,221