All Questions
19
questions
18
votes
4
answers
125k
views
Find DNF and CNF of an expression
I want to find the DNF and CNF of the following expression
$$ x \oplus y \oplus z $$
I tried by using
$$x \oplus y = (\neg x\wedge y) \vee (x\wedge \neg y)$$
but it got all messy.
I also ...
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 ...
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 \...
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
votes
1
answer
804
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?
$$ ...
2
votes
0
answers
254
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 ...
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 ...
1
vote
1
answer
79
views
Transform a logical function into conjunctive form
For this function, i need to find the clause form for $A\Rightarrow B$
where
$$A \equiv (A\land B\land \sim C) \lor (\sim A \land C)$$
and
$$B\equiv (\sim A \land \sim B\land \sim C)$$
I understand ...
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 ...
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 ...
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 ...
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 \...
0
votes
1
answer
282
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 ...
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)?
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 ...