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
1
vote
1answer
297 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 ...
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 ...
1
vote
1answer
38 views

Find an expression, which is the and of clauses, equivalent to $( p \lor q) \to r$ .

I have to do the following problem : Find an expression, which is the and of clauses, equivalent to $( p \lor q) \to r$. But I don't understand what ''which is the and of clauses'' means. (I am ...
0
votes
1answer
82 views

DNF and CNF missing law/rule

I have tried simplify some expressions to DNF and CNF but I'm stuck in one step and I can't find some rule or law what can I apply on it. I used Wolfram and found that my expression is not in DNF/CNF ...
0
votes
2answers
648 views

Find minimal DNF and CNF of a logical expression $(A \implies C) \wedge \neg (B \wedge C \wedge D).$

I want to find the minimal CNF and DNF for the following expression: $$(A \implies C) \wedge \neg (B \wedge C \wedge D).$$ I've created a truth table: \begin{array}{| c | c | c | c | c | c | c |} \...
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 \...
1
vote
1answer
196 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 ...
2
votes
3answers
390 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 \...
3
votes
2answers
956 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$
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
111 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\...
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
1answer
200 views

How to transform a knowledge base (CNF) from propositional logic in a set? [closed]

I have a proposition logic knowledge base which contains my neg query in CNF: $$\begin{split}1.~& \neg P \lor Q\\ 3.~& P \\ 4.~& R \lor S\\ 5.~& \neg R\end{split}$$ Is it possible to ...
-3
votes
1answer
60 views

Converting $\big( (A \lor B) \land ((B \leftrightarrow A) \to C) \big) \lor (C \to \neg A)$ to CNF. [closed]

Converting logic formula to CNF $$\big( (A \lor B) \land ((B \leftrightarrow A) \to C) \big) \lor (C \to \neg A)$$ I have attached an image showing my workout. Is this correct?blue [enter image ...
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? $$(...
0
votes
1answer
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 ...
1
vote
1answer
175 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 \...
0
votes
1answer
257 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,...
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
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?
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/...
0
votes
2answers
60 views

Find the conjunctive normal form in the smallest possible number of variables of $x+x^{'}y$.

Find the conjunctive normal form in the smallest possible number of variables of $x+x^{'}y$. $x+x^{'}y=(x+yy^{'})+x^{'}y$ How can I proceed?Please help. The answer is given to be $x+y$ which I don'...
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
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 ...
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
1answer
462 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 ...
0
votes
1answer
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?
0
votes
2answers
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(...
0
votes
1answer
375 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 ...
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 ...
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
votes
1answer
373 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?
-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 ...
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
2answers
48 views

Converting $\lnot a \land \lnot b$ to CNF

I tried as much as I could. I tried adding a double negation in front, which led to $$ \lnot a \land \lnot b=\lnot (a \lor b) $$ I also tried to "and" with the same formula again but I got no result. ...
0
votes
1answer
227 views

“Standardizing variables” in the procedure of converting First Order Logic to CNF?

In below question of converting the given formula into clause normal form, I stuck in the step “Standardizing variables”.Can someone explain to me whether my steps are correct and how to do “...
0
votes
1answer
231 views

Convert minterm formula to nor and not formula

If I had the following equation, it is easy to convert to only NAND and NOT gates $$(A\land \neg B) \lor (C\land B) \iff (A\text{ NAND } \neg B) \text{ NAND } (C\text{ NAND } B)$$ Just replace all ...
2
votes
1answer
2k 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 | ...
0
votes
2answers
326 views

Show that every well formed formula has a disjunctive and a conjunctive normal form.

If $\varphi$ is a $wff$, then there exist $\varphi^c$ and $\varphi^d$ on conductive normal form and disjunctive normal form respectively, such that $\varphi \sim \varphi^c$ and $\varphi \sim \varphi^d$...
1
vote
2answers
530 views

Converting predicate logic formulas into Skolem Normal Form

I would like to transform the following predicate logic formulas into Skolem Normal Form, simplifying them as much as possible. I am trying to show my working clearly, writing each step in a line of ...
0
votes
0answers
197 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
2
votes
1answer
713 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:...
0
votes
1answer
46 views

Transform a logical function into conjunctive form

For this function, i need to find the clause form for $A\Rightarrow B$ where $$A \equiv (A\land B\land \sim C) \lor (\sim A \land C)$$ and $$B\equiv (\sim A \land \sim B\land \sim C)$$ I understand ...
0
votes
1answer
410 views

Reduce the Compound Proposition to a Conjunctive Normal Form

I would like to know how to reduce the following compound proposition to a Conjunctive Normal Form please? $$(P∨Q)→(R∧(S∧T))$$
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 ...
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 ...
0
votes
1answer
68 views

What is the difference between (P=>Q)=>R and ((P=>Q)=>R)

Currently, I am enrolled in logic as undergraduate student. For assignment, the lecturer gave us the assignment to convert the problem in CNF. And, there were two questions: $$(P\:=>\:Q)\:=>\:R$...
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 ...
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?
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 \...