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.
206
questions
-1
votes
1
answer
35
views
Given a formula how can we figure out if it is CNF or DNF
Can anyone please help me understand if the following formulas are DNF, CNF, both CNF and DNF, and neither CNF nor DNF? From my understanding, CNF is a conjunction of disjunction literals and DNF is a ...
1
vote
1
answer
53
views
I've found the minimal AND-OR expression for a function, but I can't find the minimal OR-AND function
I am given a function $f(W,X,Y,Z)$ that only outputs $1$ if exactly three inputs are $1$.
The AND-OR function is easy enough to find:
$$
W'X\,YZ + WX'YZ + WX\,Y'Z + WX\,YZ'
$$
I think that function is ...
- 71
0
votes
0
answers
37
views
Provide a clause set representation of a formula in CNF with a minimal number of clauses which is semantically equivalent to the KV map provided.
$KV$ map:
So far I have tried brute forcing to generate a CNF formula, but that obviously doesn't give me the minimal CNF. I am left with $6$ sets with $4$ elements each and I can't simplify them.
...
0
votes
0
answers
61
views
What is the Tseitin transformation of a single literal?
The wikipedia page for Tseitin transformation includes a nice example of the transform itself. In the example, it is implied that there is no need to create a fresh variable for a single literal (that ...
- 521
0
votes
1
answer
28
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\...
- 5,651
2
votes
1
answer
50
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
312
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
306
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
77
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
61
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 ...
4
votes
1
answer
93
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 &...
- 162
0
votes
1
answer
152
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
64
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
37
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
92
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