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
32 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
34 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
43 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
59 views

Task about Conjunctive and Disjunctive normal form.

Happy new year to all! I have a question related to my Discrete Mathematics examination: Consider the following (parametrized) propositional formula $𝜑_𝑛$: ($p_1$V$p_{2n+1}$) & (!$p_1$V!$p_2$)...
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 ...
0
votes
1answer
38 views

How to convert this formula to CNF

I have the following formula and want to turn it into CNF without creating a truth table: ~((X -> ~(Y or Z)) and ((X and Y) or ~Z)) I was doing the following ...
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
195 views
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
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 ...
0
votes
1answer
31 views

Simplifying boolean expression to minimum CNF

I have the boolean expression, $$(a\not\to b)\lor(c\not\to d)\lor(a\not\to d)\lor(b\not\to d)$$ Can I simplify this to, $$ (a \vee c \vee b ) \wedge (a \vee \neg d) \wedge (\neg b \vee \neg d) $$ ...
0
votes
1answer
46 views

Converting to DNF from CNF

I'm having a bit of a problem when trying to convert this CNF formula to DNF: \begin{align} & \left(a_1 \vee \neg a_2 \vee \neg a_3 \vee ... \vee \neg a_K \right) \wedge \\ & \left(\neg a_1 \...
0
votes
1answer
35 views

CNF simplification

I would like to know if it is possible to simplify the CNF equation. I have this equation - $$ (x_{1} \lor x_2 \lor \lnot x_3 \lor \lnot x_4) \land (x_1 \lor \lnot x_2 \lor x_3 \lor \lnot x_4) \land (...
0
votes
1answer
26 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
1answer
41 views

Is there any procedure that guaranteed to find the Minimal CNF form of an expression $?$

For example: Find the Minimal CNF form of $abcd+a'b'c'd'$: My attempts: Consider $$abcd+a'b'c'd'$$ By Distributeive law we have: $$\boxed{\begin{array}{ccccc}d' &\color{orange}{a+d'}&b+d'&...
0
votes
1answer
72 views

Convert to Conjunctive Normal Form exercise

I got confused in some exercises I need to convert the following to CNF step by step(I need to prove it with logical equivalence) $1.¬(((a→b)→a)→a)$ $2.¬((p→(q→r)))→((p→q)→(p→r))$
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 ...
-1
votes
1answer
32 views

Combination of AND OR in Linear Programming

I have three binary variables: $x,y,z$. I want to define $U$ as follows: $$U = x \wedge (y \vee z)$$ Following this, I have already tried defining $$yz = y \vee z$$ and then, doing $$U = x \...
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 ...
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 \...
4
votes
1answer
521 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)\...
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 ...
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 \...
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. ...
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
0answers
50 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 \...
0
votes
1answer
15 views

Converting Natural Language Problem to CNF

I'm struggling in converting this problem to Conjunctive Normal Form. I'd appreciate any help or guiding. There are $n$ stones in the river. Every stones has two states: above or below the water. ...
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
23 views

conjunctive normal form distribution over logical or?

when converting to CNF do you have to distribute ors over ors ex. (A or B) or C, or can you leave it just like that I am wondering because I have to convert a bunch of first order logic to clausal ...
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 ...
0
votes
2answers
38 views

DNF and CNF look the same?

When constructing both a DNF and CNF of the below, my solutions look the same. I must be off somewhere. This is what they look like: $\lnot s ∨ \lnot q ∨ \lnot s$ How would you construct a DNF and ...
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 ...
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
1answer
221 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)
0
votes
2answers
61 views

Converting an Expression to CNF (conjunctive normal form)

I am trying to convert the following expression to CNF (conjunctive normal form): $$ (A \wedge B \wedge M) \vee ( \neg F \wedge B).$$ So I apply the distributive law and get: $$ \neg F \wedge B \vee (...
1
vote
0answers
86 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 ...
0
votes
1answer
160 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
1answer
41 views

converting p ∧ (p→q) into conjunctive form

I want to convert p ∧ (p→q) into conjunctive form. I started like this: P ∧ (¬p ∨ q) But I'm not sure how to continue and how to change this formula to ...
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 | ...
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 ...
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 ...
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 (...
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)
-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
vote
2answers
183 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 ...
2
votes
1answer
655 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 ...
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
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
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 ...