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
28 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
0answers
33 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
35 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
31 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
2answers
23 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
37 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'&...
3
votes
2answers
58 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 ...
0
votes
1answer
53 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))$
-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
169 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
18 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 \...
1
vote
0answers
48 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
0answers
82 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
14 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
1answer
21 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
0answers
82 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. ...
1
vote
1answer
74 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 ...
2
votes
1answer
134 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 \...
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
125 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
57 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
76 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
95 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 ...
0
votes
2answers
31 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 ...
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
27 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 ...
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
73 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
47 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
165 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
600 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
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
125 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
38 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
66 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
402 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
255 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
275 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 ...
0
votes
1answer
35 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
220 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 ...
4
votes
1answer
185 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 𝑥 \...
1
vote
1answer
284 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
51 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
37 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
81 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
591 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 |} \...