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.
205
questions
0
votes
1
answer
39
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:
...
- 1
0
votes
1
answer
247
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'&...
- 5,283
3
votes
2
answers
1k
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 ...
- 31
0
votes
1
answer
1k
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
1
answer
57
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 \...
- 3
2
votes
1
answer
220
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 ...
- 2,554
1
vote
0
answers
70
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 \...
- 5,283
0
votes
1
answer
63
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
1
answer
163
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 ...
- 381
1
vote
1
answer
92
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 ...
- 167
1
vote
0
answers
1k
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 ...
- 153
0
votes
0
answers
26
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.
...
- 199
1
vote
1
answer
150
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 ...
- 21
2
votes
1
answer
610
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 \...
- 21
1
vote
1
answer
78
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, ...
