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
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 ...
1
vote
2answers
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 ...
0
votes
1answer
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 ...
3
votes
2answers
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 ...
0
votes
1answer
302 views

Conversion from PL to CNF

I am trying to convert some formulas into CNF even if I understood both concepts and rules of it I cannot always get a solution. For example I have this statement to convert: $(p\Leftrightarrow p)\...
0
votes
1answer
300 views

Is it possible to get the CNF out of the DNF of this expression

Can i get the CNF of the following expression if i know the DNF? I've the following expression: $$\Bigl(\bigl(A\rightarrow (\overline A \land B) \bigr)\land \bigl((\overline A \land B)\rightarrow A\...
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 ...
3
votes
2answers
3k views

From DNF to CNF

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

satisfying boolean n variable DNF formula

I have an n variable boolean DNF formula and an input set,z consisting of n-tuples. Each tuple consists of truth/false assignment to n variable. the number of tuples in Z is not fixed, obviously <= ...
0
votes
1answer
310 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
1answer
5k views

Difference between DNF and CNF

I'm stuck on this particular question: Let $A$ be the following propositional formula $$(\lnot p \rightarrow q) \leftrightarrow\ (\lnot q \rightarrow \lnot r)$$ Find a propositional formula $B$ in ...
4
votes
1answer
224 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 𝑥 \...
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 ...
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
41 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
84 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
683 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
100 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
996 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
3answers
408 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
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 ...
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 ...
2
votes
2answers
115 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
1answer
211 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 ...
2
votes
1answer
716 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:...
1
vote
1answer
207 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
2answers
61 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 ...
0
votes
1answer
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,...
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
593 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
63 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
58 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
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 ...
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
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 ...
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
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 ...
-1
votes
1answer
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?
-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
230 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 “...
-1
votes
2answers
589 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.
0
votes
1answer
237 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 ...