# 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.

118 questions
Filter by
Sorted by
Tagged with
28 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)$$ ...
33 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 ...
35 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 \...
31 views

58 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 ...
53 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

82 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 ...
14 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. ...
21 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

73 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)
47 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?
165 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 ...
600 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 ...
125 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 ...
38 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 ...
66 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: $(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 ...