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

41 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
798 views

### Is the minimal conjunctive normal form for positive formula unique? If so, how do you calculate it?

I am considering positive Boolean formulas (no negations). Take for example $A$. Here are two of its positive conjunctive normal forms. $$A$$ $$A \land (A \lor B)$$ The minimal example is $A$. Does ...
522 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 ...
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 ...
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. ...
178 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 ...
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 ...
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 ...
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 ...
43 views

### Context-Free grammar - Normal form

Termials = a,b,c. non-Termials = A,S. Production Rules: (1) S → aS (2) S → bA (3) A → bA (4) A → cA (5) A → c (6) S → a How do you write the following in normal form, I understand that it is ...
276 views

### Converting boolean logic to disjunctive normal form and conjunctive normal form

$(\lnot q \lor \lnot r) \rightarrow (\lnot r \land (q \rightarrow p))$ Put the statement into disjunctive normal form Put the statement into conjunctive normal form I don't know how to convert the ...
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 ...