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
4
votes
1answer
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 ...
4
votes
1answer
522 views

Turning CNF into DNF

I have a formula $(L\Leftrightarrow (A\vee J))$ and I am to turn it into DNF and CNF. When I use de Morgan rules and so on, the formula looks like $(L\Rightarrow (A\vee J))\wedge ((A\vee J)\...
3
votes
0answers
239 views

Does every CNF formula have an equivalent 2-CNF formula?

From Wolfram MathWorld: A statement is in conjunctive normal form if it is a conjunction (sequence of ANDs) consisting of one or more conjuncts, each of which is a disjunction (OR) of one or more ...
2
votes
0answers
124 views

k-CNF formulae and formulae that are not equivalent to them

I would like to understand the complexity of $k$-CNF formulae. For $k\geqslant 1$, can one please give me an example of a formula that is not equivalent to a $k$-CNF formula?
2
votes
0answers
4k views

Converting DNF to CNF and vice versa

I am fairly confident of the definition of CNF and DNF (e.g. why $ (P \land Q)$ in both CNF and DNF. However, I'm a little shaky when it comes to converting between the two normal forms. Is it ...
1
vote
2answers
15 views

How to convert (F⇒(H⇒G))⇒(F⇒(G⇒H)) to Conjunctive Normal Form?

I've expanded the formula to: $$(F \wedge H \wedge\neg G) \vee (\neg F \vee\neg G \vee H)$$ but don't know how to switch the first set to or and the middle or to an and.
1
vote
0answers
51 views

A fomular for CNF-DNF conversion

I just see this nice generalisation of sets: $$\bigcup_{(i,j) \in I \times J} (A_i \times B_j) = \bigcup_{i \in I} \bigcup_{j \in J} (A_i \times B_j) = \Biggl(\bigcup_{i \in I} A_i\Biggr) \times \...
1
vote
0answers
89 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 ...
1
vote
2answers
191 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 ...
1
vote
1answer
183 views

How to convert to formula to disjunctive normal form (DNF)?

I know how to convert a formula to a CNF, but how do I convert to a DNF? Can I use the first three steps of CNF and change the distributive transformation to $P \land (Q \lor R) \text{ becomes } (P \...
1
vote
0answers
132 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 ...
1
vote
1answer
262 views

Conversion to CNF - eliminate implications

On the web I found a solution to an exercise on resoulution. Basically, it asks to use resolution refutation to prove $$ (P \Rightarrow (Q \Rightarrow R)) \Rightarrow ((P \Rightarrow Q) \Rightarrow (P ...
0
votes
1answer
34 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: ...
0
votes
1answer
36 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!
0
votes
0answers
45 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 ...
0
votes
1answer
27 views

Applying Distributivity law on 2 conjunctive statements seperated by a disjunction

I have been given this statement to convert to CNF: $$((a \to x) \land (b \to c)) \to (a \to ¬c)$$ and so far I have gotten rid of the implications and applied de Morgan's law after which I have: ...
0
votes
0answers
22 views

Using Tseitin transformation to avoid CNF clauses explosion

I'm working with propositional calculus to model a puzzle to be solved for an SAT solver, so the format of the clauses should be a CNF. The problem is that I have clauses like this: $[a \wedge (b \...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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. ...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
0
votes
0answers
49 views

Given is a set of clauses. Find a logic formula in CNF such that..

Given is the set of clauses $$\tau_1 := \left\{\left\{P, \neg S\right\}, \left\{S\right\},\left\{S,R\right\},\left\{\neg S, \neg P\right\}\right\}$$ For this set of clauses, find a logic formula $...
0
votes
2answers
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 ...
0
votes
2answers
96 views

Is is possible to transform the conjunction of inequalities into one single equation?

I am wondering if there is a way to transform the conjunction of inequalities into one single equation. For example, let $x_i$ be variables and $a_i$ be fixed integers. The following condition $$(x_1 ...
0
votes
0answers
198 views

Convert to Conjunctive Normal Form

I am trying to covert the following to Conjunctive Normal Form (CNF) and cannot get the answer. (¬A ∨ C) → B Can anybody explain how to get the correct answer? Many thanks
0
votes
2answers
65 views

First Order Logic - Negation in embed functions

Given the First Order Logic Sentence : ¬SubsetOf((Intersection(s,t),s) where Constants : s,t are Sets and Functions: SubsetOf(.,.) , Intersection(.,.) are Sets ...
0
votes
0answers
57 views

How does checking for CNF satisfiability by going via DNF compare to using a truth table or DPLL?

In terms of efficiency, I know DPLL would be most efficient, and probably going via a DNF would be least efficient, but my question is asking for reasons why and trying to understand by how much?
0
votes
1answer
97 views

Some confusing steps with Resolution by refutation FOL

Here is the thing.. There are two step that confuses me In the famous example "Everyone who loves all animals is loved by someone etc..." We need to prove that who killed the cat "curiosity or jack" ...
0
votes
0answers
85 views

How to turn this formula into CNF?

This formula $$(p \land q) \lor ( \neg q \lor r) \land ( \neg p \lor r)$$ has the CNF $$(\neg p \lor q \lor r) \land ( p \lor \neg q \lor r)$$ I understand how CNF works, but I can't seem to ...
0
votes
1answer
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 ...
-1
votes
1answer
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?
-1
votes
1answer
3k views

Converting DNF to CNF (Boolean Logic)

I've tried at least a dozen ways to convert this DNF to CNF, yet I always end up with something unusable. Here is the DNF -> z:(C∧D∧B)∨(¬B∧¬C∧D)∨(¬D∧C) I need to convert it mathematically (with ...
-1
votes
2answers
584 views

Conversion of disjunctive normal form to conjunctive normal form

Explain how $ (p \lor q \lor r \lor s) $ can be re-written into an equivalent CNF formula such that each clause contains exactly $3$ variables or negations of variables.