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.
118
questions
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 |}
\...
