# 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: ...
35 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!
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 ...
70 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-...
60 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$)...
36 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)$$ ...
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 ...
47 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 \...
36 views

71 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 ...
76 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))$
32 views

91 views

### Localizing Predicate Activity in CNF Resolution Derivations

Has the below theorem been proven? I believe I have proven it, and am curious whether my work, if correct, would represent a novel contribution to the field. $\textbf{Theorem}$ : Given any ...
15 views

### Converting Natural Language Problem to CNF

I'm struggling in converting this problem to Conjunctive Normal Form. I'd appreciate any help or guiding. There are $n$ stones in the river. Every stones has two states: above or below the water. ...
23 views

### conjunctive normal form distribution over logical or?

when converting to CNF do you have to distribute ors over ors ex. (A or B) or C, or can you leave it just like that I am wondering because I have to convert a bunch of first order logic to clausal ...
34 views

76 views

### Natural deduction on exclusive OR

How do I formulate a natural deduction rule such that the conclusion is for example; a ∨ b (∨ being exclusive OR)
50 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?
190 views

### First Order Logic to CNF for Knowledge Base

I am doing some Homework for an Artificial Intelligence Course, we are covering some First Order Logic and Conjuctive Normal Form. Here are the questions that I have to answer that I am having ...
658 views

### Tseytin transformation example

I am trying to understand Tseytin transformation and I can't really find any reliable info on the internet. I pretty much understand the steps until I get to the point I have to convert all ...
22 views

### Convert to conjunctive normal form (for Gentzen-Formulae)

unfortunately I don't quite get how I should reach Step 2 with the Distributive Laws and I'm getting also confused how it is allowed to put the OR's in Step 1 in brackets. Task & Solution The ...
129 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 ...
39 views

### Issue with converting to conjunctive normal form

I am learning how to convert proposition logic formulae into conjunctive normal form, and came across this example: ¬(¬p ∧ (q ∨ ¬(r ∧ s))) [line 1] ≡ ¬¬p ∨ ¬(q ∨ ¬(r ∧ s))) [line 2, using De ...
67 views

### Proof of satisfiability of CNF

I need to proof that if formula F in CNF form is satisfiable, then any subset of CNF which belongs to F must be satisfiable. I know that CNF is basically conjuncted sets of disjunctions so from ...
I am looking at Conjunctive Normal Form examples, such as this: ${\displaystyle (A\lor \neg B\lor \neg C)\land (\neg D\lor E\lor F)}$ where it is a conjunction (AND) of disjunctions (ORs). So it's ...