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.
202
questions
0
votes
1
answer
16
views
Is there any kind of distributive law for $c\cdot\max(a,b)$, allowing both signs of $c$?
Notation: For any two numbers $a$ and $b$, let the maximum be $a\sqcap b$, and let the minimum be $a\sqcup b$. (No, my symbols aren't upside-down. Compare this with floor notation; $\lfloor a\rfloor\...
- 4,866
2
votes
1
answer
42
views
Is an idempotent logical expression considered to be in conjunctive normal form?
Is $$A \lor B \lor A$$ technically in conjunctive normal form?
Or must we apply the idempotent law for it to be in CNF?
$$A \lor B \lor A \equiv A \lor B$$?
0
votes
1
answer
123
views
Transform to CNF (conjunctive normal form)
I am trying to convert the following expression to CNF (conjunctive normal form):
$\left(A\Rightarrow B\right)\Rightarrow\left(A\Rightarrow C\right)$
As my first steps I am removing the implications ...
0
votes
0
answers
297
views
Convert formula of nested ORs into CNF
Let $A$, $B$, $C$ and $D$ be finite sets of integers. In addition, we have a supply of Boolean variables $a$ and $b$ with two subscripts. Then, let us define
$$Z(m) = \bigvee_{i \in A} ( a_{i,m-1} \...
- 1
1
vote
2
answers
65
views
CNF form of the logical $atleast(b) x_{i,k}$
Suppose there exists the following logical expression:
$$(\sum_{i=1}^I x_{(i,k)} \leq b) \implies (z_{(j,k)}=1) \quad \forall j \in J, k \in K \tag{1}$$
where all of variables, $x_{(i,k)}$ and $z_{(j,...
- 137
-2
votes
2
answers
58
views
How to form a CNF of following formula [closed]
We got an exercise to make a CNF out of the following formula: $$G = ((A \vee \neg B \vee C) \wedge (C \vee D)) \vee ((A \vee \neg C) \wedge (B \wedge D))$$ I've tried to make an equivalent equation ...
3
votes
1
answer
70
views
Is there a "standard" normal form for formulas in linear logic?
For propositional logic, for every formula, there is an equivalent formula in the CNF and DNF. These normal forms have the advantage of being representable in a "tabular" form rather than a &...
- 142
0
votes
1
answer
100
views
Resolution when CNF form has multiple conjoined disjunctive clauses
I've seen multiple examples of how resolution works when one has two disjunctive clauses with one having a negated literal present in the other clause. And when you resolve the two, you eliminate the ...
0
votes
1
answer
48
views
Question about clausal form
The propositional logic textbook I'm working through explains how to convert a formula in conjunctive normal form to clausal form, for instance:
((p ∨ ¬p ∨ r) ∧ (¬p ∨ ¬q ∨ r)) ∧ ((p ∨ ¬p ∨ q) ∧ (¬r ∨ ¬...
0
votes
1
answer
32
views
Trouble with converting the negation of a formula to CNF
I'm trying to convert the negation of the following formula to CNF:
(p → (q → r)) → ((p → q) → (p → r))
These are the steps I am following:
¬((p → (q → r)) → ((p → q) → (p → r)))
¬(¬(¬p ∨ (¬q ∨ r)) ∨ (...
0
votes
1
answer
65
views
CNF form of the logical $exactly(2) x_{i}$
Let's say, in order to linearize the product of the two binary variables the logical condition would be, z <=> (x and y), where x, y, and z are binary. The corresponding CNF form is as follows:
\...
- 137
0
votes
1
answer
99
views
Any proposition is equivalent to a formula in CNF.
A proposition is said to be in conjunctive normal
form (CNF) if it is $\land_{i=1}^{k}\lor_{j=1}^{n} \psi_{ij}$ where each $\psi_{ij}$ is either an atom or is the negation of an atom.
Show that any ...
- 1
1
vote
0
answers
30
views
How to define disjunctive normal form and conjunctive normal form?
The question is here:
(1) Obtain the disjunctive normal form of $(p\to q)\to(q\to p)$
(2) Obtain the conjunctive normal form of $(p\to q)\to(q\to p)$
I obtain the form $\lnot q\lor p$. Is it a ...
1
vote
1
answer
235
views
How to convert this CNF to a DNF?
(((p ∨ q) ∧ (¬q ∨ ¬r)) ∧ (¬p ∨ r))
I know we can use a truth table, but I'm trying to convert by equivalences. It seems like it will blow up, but I may be doing this wrongly. Could someone let me know ...
- 33
3
votes
1
answer
69
views
Prove 20-3-SAT is NP-Complete
so I have this problem that I can't figure out.
20-3-SAT={All satusfiable 3-CNF formulas where each variable appears at most 20 times}
I was able to prove it's in NP using verifier, but for NP-Hard ...
- 189
1
vote
1
answer
190
views
Duality in Disjunctive Normal Form and Conjunctive Normal Form
In my understanding, duality $s ^{*}$ of a compound proposition $s$ is obtained by replacing each $\vee$ to $\wedge$, each $\wedge$ to $\vee$, each $T$ to $F$, and each $F$ to $T$.
I have been looking ...
- 43
0
votes
1
answer
47
views
At most $k$ contiguous $\mbox{true}$ values in a Boolean array using SAT
Given an integer $k > 0$ and a Boolean array $A$ of length $n$, find a simplified and efficient CNF formula to ensure that there is not more than $k$ contiguous $\mbox{true}$ values in this array. ...
- 1,264
1
vote
1
answer
103
views
Is there a method to solve 3SAT problems using loss function?
Loss function seems to be used to solve optimization problems. I assumed that 3SAT problems can be treated as them. I would like to know whether there is a good loss function that is defined by ...
- 15
1
vote
1
answer
108
views
I'm studying boolean algebra in the discrete mathematics
problem
Let $a_4a_3a_2a_1a_0$ be a 5- bits binary numbers (each $a_i=0$ or $1$). Write an expression in Boolean algebra that evaluates to $1$ when odd number of bits of the number is $1$ and $0$ ...
- 121
0
votes
1
answer
174
views
Why doesn't Krom's method apply to solving the 3SAT in polynomial time?
In the paper "The Decision Problem for a Class of First-Order Formulas in Which all Disjunctions are Binary", Krom suggested a method to solve 2SAT problem.
My understanding is this.
Use ...
- 15
0
votes
0
answers
51
views
How to deduce the PDNF of ~A?
For my question, $A =\lnot P\land(Q \to R)$. After making the truth table, I managed to get the PDNF of it which is
$$(\lnot p\land q\land r)\lor(\lnot p\land\lnot q\land r)\lor(\lnot p\land\lnot q\...
1
vote
1
answer
126
views
Proposition is CNF and DNF
So I understand that CNF is the conjunction of one or more disjunctive clauses and that a DNF is a disjunction of one or more conjunctive clauses, however, I was wondering if there could be a case ...
0
votes
1
answer
63
views
Finding the CNF of PL formula
I have this expression and I'm trying to find the CNF for it.
(P ∨ (Q↔R))∧¬(Q→R)
I have followed the steps of simplification until the distribution of "V". This is my current expression:
(P ∨...
- 1
0
votes
1
answer
88
views
CNF boolean formula satisfiable for a subset of $\{0,1\}^n$
For a set $S\subseteq\{0,1\}^n$, I want to make a CNF boolean formula $\phi$ such that for $ a=( x_1,...,x_n)$ we have $\phi(a)=1$ if and only if $a\in S$. I would also like to know what the size of ...
- 423
-2
votes
1
answer
369
views
Normal disjunctive and conjuctive form from a truth table
Let's say that we get a table with zeros and ones. We need to get it into disjunctive normal form or conjuctive normal form. We also have discrete variables $x_1,..,x_n$ that are either $1$ or $0$. ...
- 2,527
-2
votes
1
answer
753
views
How to convert a boolean function to CNF?
Consider the boolean function:
$$f (x, y, z) = (x + \overline y) (y + \overline z) (z + \overline x)$$
I have converted it to DNF which is $xyz + \overline y \,\overline z \,\overline x$, but I have ...
- 1
0
votes
0
answers
65
views
Formalizing with Induction
In this thread here, it makes sense why there is exponential blow up because of the conversion. My question is how would we use induction to prove this? I've started, but I'm getting mixed up with the ...
- 177
-1
votes
1
answer
341
views
Checking tautology
Given a Boolean formula $\phi$ in CNF form, I'll check whether there exists a clause that can be falsified i.e. check for literals of the form $x \vee \neg x$. If there are not any such literals in a ...
0
votes
0
answers
102
views
Tseitin-Expansion for First-Order Logic
I want to transform an arbitrary formula of first-order logic into a CNF, or rather into a Skolem formula, whose matrix is in CNF. Standard procedure: First skolemize (the prenexed formula), then ...
- 1
0
votes
1
answer
319
views
For CNF and DNF why do we look at the interpretations that make the formula false and true respectively?
Okay so I know how to obtain CNF and DNF from a truth table but I do not understand why.
For example, for the formula $$P ⟺ Q$$
We are trying to convert the formula P ⟺ Q to an equivalent formula in ...
0
votes
0
answers
124
views
How do I expand this sigma/summation notation?
I don't know if it's correct to refer to this as summation notation since the operation is not addition so please correct me if that's inaccurate.
How do I expand this notation?
I believe it's for <...
- 227
0
votes
1
answer
31
views
Find the CNF of the following formular
I am looking at the CNF of $((A \to B) \to (B \to A)) \to A$. For this I tried the following:
$${\quad((A \to B ) \to (B \to A)) \to A\\ \equiv ((\neg A \vee B) \to (\neg B \vee A) \to A \\\equiv (\...
0
votes
1
answer
149
views
How do I re-write this propositional formula in conjunctive normal form (CNF)?
I'm struggling with this problem -- though it would seem simple enough. I think it's the parentheses that are getting me confused here.
I need to convert (p→(q⋁r))⋁(s↔t) to conjunctive normal form (...
- 103
1
vote
1
answer
40
views
Conjunctive Normal Form of a clause
Can the following clause be converted to conjunctive normal form? If so how?
$$
(a \implies b) \implies (c \implies d)
$$
I tried applying DeMorgans laws and am unable to get the result.
$$
(a \...
- 1,039
1
vote
0
answers
157
views
Help with Resolution Refutation Problem
I'm trying to convert Solve a Resolution Refutation problem. The problem states: Knowledge Base is ∀𝑥𝑦 𝐹(𝑥, 𝑦). Prove using resolution-refutation that ∀𝑥𝑦 𝐹(𝑦, 𝑥). Note: β = F(y, x) This ...
- 11
0
votes
1
answer
24
views
expanding disjunctive pairs of conjunctives using distributive law
I am having a bit of a brain malfunction. I am working through a functional programming class and I am trying to in parallel fake some knowledge of discrete mathematics.
I am working through a simple ...
- 111
1
vote
1
answer
159
views
Can clause normal form include true/false constants?
As Wikipedia puts it,
... the only propositional connectives a formula in CNF can contain are and, or, and not. The not operator can only be used as part of a literal, which means that it can only ...
- 235
0
votes
1
answer
230
views
How to get CNF of propositional formula form DNF of its complement?
Explain how to read off a CNF for propositional formula directly from a DNF from its complement.
I've managed to explain it in words, but can't write a rigorous proof of that. How to show this in ...
- 153
0
votes
0
answers
112
views
Generalisation of DNF to CNF for DNF of m choose l clauses
Given two values $m$ and $l$, I can create corresponding DNF formula which is a disjunction of all $m \choose l$ combinations, where each number corresponds to a variable. Each combination is, in ...
- 1
1
vote
1
answer
259
views
The Explanation on how to form CNF
I am currently reading Logic in Computer Science Modelling and Reasoning About Systems (by Michael Huth & Mark Ryan).
They introduced a fairly easy way to form conjunctive normal form (CNF) of an ...
- 17
0
votes
1
answer
115
views
HORN algorithm - clarity needed
I have been spending some time studying the HORN algorithm, but my textbook, as well as most posts online, are quite vague around the steps taken.
These are the steps from my textbook:
My questions:
...
0
votes
1
answer
487
views
How to introduce conjunctions into a conditional statements so as to get the CNF and DNF?
I have the following conditional statement: ((p → q) → p) → p
Knowing that CNF is a conjunction of disjunctions (and that DNF is a disjunction of conjunctions), we will obviously have to introduce ...
0
votes
1
answer
124
views
Converting propositional logic formula to CNF
I have been trying to do this all day but I am not getting anywhere with it, could anyone help me?
My formula is
r → (p ↔ ¬q)
And I want to convert it into CNF
...
0
votes
0
answers
120
views
Dominant set of a Graph - Convert to Conjunctive Normal Form
I am supposed to convert this problem to a Satisfiability Problem in Conjunctive Normal Form, but I have no idea how.
The Problem:
Determine, if there exists any dominant set for a Graph $G$ ...
- 13
0
votes
1
answer
776
views
Explain into disjunctive normal form
Can anyone tell me how to Express the following formula into disjunctive normal form ⌐ (p V q) ↔ (p ^ q). I have done few steps but I need your help.
0
votes
1
answer
73
views
Converting $3$-variable truth table to 3CNF
I have a truth table for length $3$ binary strings, say $110$ and $001$ map to $1$ and everything else to $0$. Is there an an algorithm to represent this table as a 3CNF which is satisfied only by $...
- 187
0
votes
1
answer
125
views
How to prove that a given disjunctive or conjuctive normal form is minimal?
what is the argument that a given canonical normalform cannot be reduced any further?
For example have a look at this $dnf(f) = (\neg a \wedge b \wedge c) \vee (a \wedge \neg b \wedge c) \vee(a \...
- 47
0
votes
1
answer
60
views
DNF to CNF of a simple expression
I have a formula like this:
$$\bigvee_{\substack{i \in [1,...,m] \\ j \in [1,...,m]}} x_{i} \wedge x_{j}$$
What is the equivalent formula in CNF (conjunctive normal form)?
- 81
0
votes
1
answer
177
views
1
vote
1
answer
74
views
CNF formula for manipulating words
I am trying to create CNF formula for manipulation of a word. word is a sequence of letters from a $\Sigma$ alphabet. A word is encoded by variables like $x_{i,a}$ which means that the letter $a$ is ...
- 81