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.

Filter by
Sorted by
Tagged with
12
votes
4answers
63k views

Find DNF and CNF of an expression

I want to find the DNF and CNF of the following expression $$ x \oplus y \oplus z $$ I tried by using $$x \oplus y = (\neg x\wedge y) \vee (x\wedge \neg y)$$ but it got all messy. I also ...
4
votes
1answer
210 views

Conversion to Clausal Form

I want to convert this formula to clausal form: $\lnot \forall 𝑥 \exists 𝑦 \lnot((𝑃(𝑦, 𝑥) \land 𝑄(𝑦)) \to (\exists 𝑧 𝑅(𝑥,𝑧) \land ∃𝑧 𝑆(𝑧)))$ First I removed $\to$: $\lnot \forall 𝑥 \...
4
votes
1answer
792 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
520 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
2answers
447 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 ...
3
votes
3answers
8k views

Every sentence in propositional logic can be written in Conjunctive Normal Form

While reading through Artificial Intelligence: A Modern Approach by Stuart Russell and Peter Norvig, I came upon the following question: Any propositional logic sentence is logically equivalent to ...
3
votes
1answer
36 views

Is this CNF equivalent correct?

I am reading Wolf’s A Tour Through Mathematical Logic. In Section 1.2, Propositional Logic, he gives the following example: Example 6. The statement $ \mathsf{[(P\rightarrow\neg Q)\leftrightarrow (...
3
votes
2answers
3k views

From DNF to CNF

What is the most efficient way to switch from DNF to CNF?.
3
votes
1answer
98 views

Are my DNF and CNF for $A \land (A \lor C) \implies (C \lor B)$ correct?

Is this calucation of DNF and CNF for the formula $A \land (A \lor C) \implies (C \lor B)$ correct? $$ \begin{array}{|c|c|} \hline \text{Given:} & A \land (A \lor C) \implies (C \...
3
votes
2answers
947 views

Is it possible for the DNF and CNF to be the same

For example can $A \land C$ be both the conjunctive normal form and the disjunctive normal form of $(A \lor ((A \land B) \lor (\lnot A \land \lnot B \land \lnot C))) \land C$
3
votes
1answer
95 views

Transform formula to conjunctive normal form.

I need help with conjunctive normal form. Can you give me some tips? I have following formula. I did the first few steps. $$ [(p \implies q) \land (r \implies q)] \implies [( \neg q \vee \...
3
votes
3answers
2k views

Apply equivalence rules to convert to CNF

I am having trouble seeing how I could apply the equivalence rules mentioned here to the following formula in order to convert it into Conjunctive Normal Form (CNF). $$(p \wedge q) \vee (\neg p \...
3
votes
2answers
70 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 ...
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
3answers
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)
2
votes
3answers
384 views

Finding a logically equivalent conjunctive normal form.

Here is the definition of a conjunctive normal form: A conjunctive normal form is a conjunction of one or more conjuncts that are disjunctions of one or more literals (letters). For example, $A \...
2
votes
1answer
143 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 ...
2
votes
2answers
110 views

Is it ok this CNF of a Boolean function?

I have to find out the CNF of $$\begin{matrix} f(x,y,z)&=&(x\wedge y)\vee(x\wedge z),\end{matrix}$$ where $f$ is a Boolean function. $$\begin{matrix}&f(x,y,z)&=&(x\wedge y)\vee(x\...
2
votes
1answer
96 views

CNF Conversion and one $2015$ exam questions?!

if $\text{likes}(x,t)$ means that person $t$ likes food $x$, and $\text{food}(x)$ means $x$ is a food, $\text{CNF}$ of sentence "No food is liked by all person", and $F$ is Skolem function. The ...
2
votes
1answer
141 views

Boolean algebra - Converting DNF form to CNF

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: $$y= (A \wedge B \wedge \neg C \wedge D) \vee (A \wedge B \wedge C \wedge \...
2
votes
1answer
171 views

Logic - Rearranging CNF formula

Given a #2SAT problem such as how many ways can $(a \vee b) \wedge (\bar{a} \vee d) \wedge (\bar{b} \vee c) \wedge (\bar{c} \vee d)$ be satisfied? I am trying to find a way to rearrange the clauses ...
2
votes
1answer
652 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 ...
2
votes
1answer
52 views

Conjunction of Clauses and Well-Formed Formulas

Here is a theorem in my notes: If $\phi$ is any wff such that $\neg \phi$ is not a tautology, then $\phi$ is tautologically equivalent to a conjunction of clauses. My question is that...can this ...
2
votes
1answer
46 views

Help converting ANF to XORNF if even possible.

This equivalence: $C \leftrightarrow A · B$ can be written in ANF (algebraic normal form, where $+$ denotes $XOR$) as: $\lnot((A · B) + C)$ One step further, interning the negation we get: $(A · ...
2
votes
1answer
1k views

Get DNF from Karnaugh map

The following boolean expression in CNF form $$ (x \lor y) \land (x \lor \lnot z) $$ Has been mapped into the Karnaugh map below \begin{array}{| c | c | c | c | ...
2
votes
1answer
712 views

Translation of english sentences to first order logic in conjunctive normal form walkthrough?

I am having a hard time on a homework problem which involves converting a given English sentence into first order logic and then converting that into Conjunctive Normal Form. The sentences are (EDIT:...
2
votes
1answer
268 views

Write $(p\land q)\leftrightarrow (\neg p\lor \neg q)$ in CNF

I need to convert the below for a homework question and I am not entirely sure if it's correct. The last part is that I am not sure how to use the distributive laws in this scenario. Any guidance ...
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
1answer
579 views

Is 3-CNF to 2-CNF generally possible (or in particular)?

Consider the logic formula (where · denotes logical and/conjunction): $C \leftrightarrow A · B$ Using the Tseytin transformation we arrive at an equivalent CNF (where + denotes logical or/...
1
vote
1answer
1k views

First order logic, CNF

What steps do I need to follow to convert the next statements into CNF? Wich are the resulting clauses? $H \leftrightarrow C \vee D$ $R \rightarrow \neg D$ $R \wedge H$ $H \leftrightarrow C$ Thank ...
1
vote
2answers
65 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-...
1
vote
1answer
220 views

Which of the following formulas are in CNF (conjunctive normal form)?

could someone please be so kind to answer this question and explain the answer? Which of the following formulas are in CNF? ¬(A∨B∨C)∧(A∨B) (A∧B∧C)∨(A∧B) (A∨B∨¬C)∧(A∨B) (A∧B∧¬C)∨(A∧B)
1
vote
1answer
296 views

How to transform this CNF formula (A∨B∨C)∧(¬A∨¬C)∧(¬A∨¬B) into DNF?

I am not getting the formula below from Conjunctive Normal Form into Disjunctive Normal Form. Can anybody help me to transform it into DNF? $(A \lor B \lor C) \land (\neg A \lor \neg C) \land (\neg A ...
1
vote
3answers
2k views

Writing in CNF that only one statement can be true

Consider 5 Boolean variables $x_1, x_2, x_3, x_4, x_5$. Write a propositional formula that expresses the fact that one and at most one among the Boolean variables $x_1, x_2, x_3, x_4, x_5$ is ...
1
vote
1answer
359 views

How to determine if a propositional formula is in DNF or CNF or both

How can I determine if a propositional formula is in DNF or CNF or both. What conditions must a propositional formula satisfy? For example, why is $(a \land b)$ both in CNF and DNF?
1
vote
2answers
1k views

Convert form from CNF to DNF

I have a few question about converting forms to DNF, CNF and from CNF to DNF. 1) How can I convert this to DNF $(p \vee q) \wedge (q \vee \neg r) $ 2) How can I convert this to CNF $(p \wedge q) \...
1
vote
1answer
34 views

How to show this predicate logic equivalence?

I have been working on an assignment exercise that asks for the conjunctive normal form (CNF) of the logic predicate $\neg (p \iff \neg q \implies r)$. So far I've managed to obtain the expression $(p ...
1
vote
1answer
81 views

Boolean algebra - Converting DNF form to CNF form

I´ve tried at least dozen ways to convert DNF to CNF, yet I always end up with something wrong. Here is the DNF: (B ∧ D) ∨ (C ∧ D) ∨ (¬D ∧ ¬B) ∨ (¬D ∧ ¬C) . Is there someone who can help me with it ...
1
vote
2answers
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 ...
1
vote
1answer
195 views

Does this solve boolean satisfiability problem in polynomial time?

CNF can be easily converted into a formula that uses only AND and NOT operations, using the fact that ...
1
vote
2answers
60 views

Is this possible: ( neg X AND Y) OR neg Z <=> (neg X OR neg Z) AND (neg Y OR Z)

I think the following formula is not possible, right? How can I come from the left side to the right? Is there a rule for this transformation I am not aware of or is there an error in my solution? $$(...
1
vote
1answer
56 views

Question on using the Resolution Rule with an and statement after converting to CNF

So I need to show p ⊢ q → (p ∧ q) using the resolution rule. I converted into CNF to get q ^ ¬p, however in the answer it simply says: 1 p 2 q 3 ¬p 4 {}1,3 I know what the resolution rule is but ...
1
vote
1answer
38 views

Why is my teacher converting CNF this way?

I am learning CNF and I have a teacher who is doing something I truly don't understand. I want to ask him later on, yet I am struggling to finish my coursework so ...
1
vote
1answer
775 views

Show that this formula is a tautology by converting to CNF

I'm working through some refutation proof questions for propositional logic, and I've come across the following question: Show that the following formula is a tautology by negating it and then ...
1
vote
1answer
6k views

Disjunctive normal form (BOTH dnf and cnf) example help

Consider $$T \vee ( \neg x \wedge y ) \vee ( x \wedge y )\tag{1}$$ In class we went over examples of how many things can be both DNF and CNF... e.g., $(\neg z) \vee y$ can be thought of as both $...
1
vote
0answers
49 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
1answer
66 views

help prove this propositional logic equivalency [duplicate]

I'm really stuck on proving this propositional logic equivalency. I've tried De Morgan's law, and double negation to see if I could get it, but no luck. Any help is greatly appreciated! P.S Please, ...
1
vote
0answers
85 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
181 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 ...