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

125 questions
Filter by
Sorted by
Tagged with
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 ...
136 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 ...
68 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 ...
498 views

### Why Conjunctive Normal Form (CNF) is used instead of simply AND + NOT

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 ...
302 views

146 views

### finding the conjunctive normal form of a statement

I am currently trying to find the conjunctive normal form of this statement $(A \land B) \lor ((\lnot C \lor A) \land \lnot B) \lor B$. I think I have found the answer but I am unsure if it is ...
31 views

### Is this the disjunctive and conjunctive nromal form for my porpositional formula F?

I want to bring the following formula $F = A \land (A \lor B) \Rightarrow (B \lor C)$ into conjunctive normal form (CNF) and disjunctive normal form. Therefore, I applied the following 5 step ...
115 views

41 views

### How can I come from NOT x AND y OR NOT z to two formulas: NOT x OR NOT z and NOT y OR z

I dont understand how I come from NOT x AND y OR NOT z to two formulas: NOT x OR NOT z NOT y OR z Can somebody show me ...
266 views

### CNF with Nested Quantifiers

I have the following statement: $$\ \forall Z \forall X ((A(Z) \land S(Z,X)\land (\exists Q (P(Q) \land E(Z,Q)))) \implies E(X,Z))$$ Which (I hope) can be read as "For all X and Z, if A(Z) and S(Z,...
46 views

472 views

### Prove that every to $\varphi_n$ equivalent formula in DNF has at least $2^n$ conjunctive clauses

Let $n \in \mathbb{N}$ with $n \ge 1$, let $X_1,\ldots,X_n$ and $Y_1, \ldots, Y_n$ be exactly $2n$ different variables and $$\varphi_n:= \bigwedge_{i=1}^{n} (X_i \vee \neg Y_i)$$ Prove that ...
1k views

### Finding the negation of a formula in CNF that is also in CNF

I want to find the negation of a CNF expression which is also in CNF form. How do I do that? Do I do the negation into DNF and then convert that DNF to CNF?
4k views

### Conversion from FOL formula into CNF

I need some help to convert the following FOL formula into CNF?: ∀x((duck(x)∧∀y(duckling(y,x)→cannotswim(y)))→worried(x)) My attempt: Step 1: ∀x((duck(x)∧∀y (¬duckling(y,x)∨ cannotswim(y))→worried(...
378 views

### Help on understanding CNF(Conjunctive Normal Form) conversion

Currently i have 3 situations as such: B: You choose bibimbap H: You choose haggis M: You choose manakish I'm required to write a proposition in Conjunctive ...
44 views

### Proposition on scenarios

There are 3 statements with the following meanings: A: Annie came first in sports B: Jane came first in sports C: Erick came first in sports Use A,B,C to write ...
133 views

### Infinite countable set of propositional variables into CNF/DNF

It is known that for every finite formula, there is an equivalent formula in CNF (conjunctive normal form) and another equivalent formula in DNF (disjunctive normal form). But can any subset K of ...
380 views

### Convert logic formula into CNF

I'm trying to convert ¬(P∧ ¬R)∨(R∧Q) into conjunctive normal form by using logical rules, but I'm stuck. Can you help me?