# Questions tagged [conjunctive-normal-form]

A formula is in conjunctive normal form (CNF) if it is a conjunction of clauses, where a clause is a disjunction of literals.

123 questions
Filter by
Sorted by
Tagged with
32 views

### Finding Disjunctive Normal Form and Conjunctive Normal Form of (𝑎 ∨ 𝑏) → ¬𝑐

Given an expression (𝑎 ∨ 𝑏) → ¬𝑐, I am able to obtain the following truth table: As for DNF and CNF, I got the following: ...
34 views

### What paper proved the completeness of Ordered Resolution?

I am having trouble finding online the original proof of the completeness of Ordered Resolution. Does anyone happen to know where it exists? Thanks!
43 views

### Use Tseytin transformation to find $T(\phi)$, where $\phi\equiv¬(((P → Q) ∧ (Q → R)) → (P → R))$

Use Tseytin transformation to find $T(\phi):$ $$\phi\equiv¬(((P → Q) ∧ (Q → R)) → (P → R))$$ I did find an example on wiki for Tseytin transformation, and try to follow it to solve this, but not ...
59 views

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$)...
8k views

### Every sentence in propositional logic can be written in Conjunctive Normal Form

While reading through Artificial Intelligence: A Modern Approach by Stuart Russell and Peter Norvig, I came upon the following question: Any propositional logic sentence is logically equivalent to ...
38 views

### How to convert this formula to CNF

I have the following formula and want to turn it into CNF without creating a truth table: ~((X -> ~(Y or Z)) and ((X and Y) or ~Z)) I was doing the following ...
65 views

### Constructive proof layers-norm (propositional logic)

I have to write a constructive proof that for every propositional formula has an equivalent formula in Layers-Norm We define Layer-Norm for propositional formulas as follows: Literals are in Layer-...
195 views

### Does this solve boolean satisfiability problem in polynomial time?

CNF can be easily converted into a formula that uses only AND and NOT operations, using the fact that ...
92 views

### A reduction of 3-CNF down to 2-CNF for boolean satisfiability

Could you please review the following candidate solution for the boolean satisfiability problem? It is known that 2-CNF has a polynomial solution. Now consider we have a 3-CNF (AFAIK, it's proven ...
1k views

### Reduction from Circuit-Sat to 3-Sat

I'm reading the following notes on reduction from circuit-sat to 3-sat http://www.cs.cmu.edu/~avrim/451f11/lectures/lect1108.pdf On the third page i'm unsure how they arrived at the following In ...
31 views

### Simplifying boolean expression to minimum CNF

I have the boolean expression, $$(a\not\to b)\lor(c\not\to d)\lor(a\not\to d)\lor(b\not\to d)$$ Can I simplify this to, $$(a \vee c \vee b ) \wedge (a \vee \neg d) \wedge (\neg b \vee \neg d)$$ ...
46 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 \...
35 views

72 views

### Convert to Conjunctive Normal Form exercise

I got confused in some exercises I need to convert the following to CNF step by step(I need to prove it with logical equivalence) $1.¬(((a→b)→a)→a)$ $2.¬((p→(q→r)))→((p→q)→(p→r))$
70 views

### First Order Logic - exactly one predicate is true

I am working on a question for an assignment and I am to declare a clause in Conjunctive Normal Form that says exactly one of three predicates is true. Or given a bit of context - given three suspects ...
32 views

15 views

### Convert into CNF form

How could I convert this into CNF? I'm stuck because I don't see anyway to add ANDs in here to get it in the proper from. Usually, I would use DeMorgan's or distribute, but that isn't an option here. ...
81 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 ...
50 views

86 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 ...
160 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 ...
41 views

### converting p ∧ (p→q) into conjunctive form

I want to convert p ∧ (p→q) into conjunctive form. I started like this: P ∧ (¬p ∨ q) But I'm not sure how to continue and how to change this formula to ...
1k views

### Get DNF from Karnaugh map

The following boolean expression in CNF form $$(x \lor y) \land (x \lor \lnot z)$$ Has been mapped into the Karnaugh map below \begin{array}{| c | c | c | c | ...
19 views

### Using notation of conjunctive normal forms for multi-objective optimization.

I need to maximize several objective functions $f_i(x)$, that I have arranged in a vector. $f(x) = [ f_1(x) , f_2(x) \cdots, f_K(x) ]^T$. Essentially, my question is whether I can represent the ...
29 views

### Tseytin transformation for equations with more than 2 inputs

My goal is to transfer logical equations, such as $x_1=x_2\ NAND \ x_3$ into CNF form. From the Wikipedia page of Tseytin transformations, I learned that a direct translation exists for equations with ...
I want to find the DNF and CNF of the following expression $$x \oplus y \oplus z$$ I tried by using $$x \oplus y = (\neg x\wedge y) \vee (x\wedge \neg y)$$ but it got all messy. I also ...