All Questions
19
questions
-2
votes
2
answers
62
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 ...
0
votes
1
answer
280
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 ...
user752336
0
votes
1
answer
66
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
1
vote
1
answer
76
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
0
votes
1
answer
55
views
CNF for modilisation of a word
Imagine that we are interested in problem of words. A word is a sequence of letters from a $\Sigma$ alphabet. For encoding a word in SAT we are using variable like $x_{i,a}$ which means that in ...
- 81
2
votes
0
answers
253
views
How can I find the CNF of ($A$ and $B$ or $C$) and ($B$ or not $C$) using a Karnaugh map?
$$(A\land B \lor C) \land (B \lor \lnot C)$$
I know how to create the truth table and Karnaugh map of a logic expression. But I couldn't find exactly how to calculate the simplified CNF of it using ...
2
votes
1
answer
799
views
CNF and DNF form of single logical variable
I am learning boolean algebra. So apologies for this naive question. During our discussion among friends, we came across following puzzle,
How can I convert following statement into CNF and DNF?
$$ ...
- 123
0
votes
1
answer
665
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 \...
- 1
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
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
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
606
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
0
votes
2
answers
345
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 ...
4
votes
1
answer
5k
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 ...
- 43
2
votes
2
answers
1k
views
Is it ok this CNF of a Boolean function?
I have to find out the CNF of $$\begin{matrix} f(x,y,z)&=&(x\wedge y)\vee(x\wedge z),\end{matrix}$$ where $f$ is a Boolean function.
$$\begin{matrix}&f(x,y,z)&=&(x\wedge y)\vee(x\...
- 2,269