This is the only answer I got wrong on my HW and the prof does not want to give us the correct answers before our midterm
The dual of a compound proposition that contains only the logical operators $\lor$ , $\land$ , and $\neg$ is the compound proposition obtained by replacing each $\lor$ by $\land$ , each $\land$ by $\lor$ , each $\def\T{{\rm T}}\def\F{{\rm F}}$ $\T$ by $\F$ , and each $\F$ by $\T$ . The dual of $s$ is denoted by $s^*$. Find the dual of these compound propositions.
a) $p \lor\neg q$
I got $\neg p \land q$
b) $p \land (q \lor (r \land \T))$
My answer was $\neg p \lor (\neg q \land r)$
c) $(p \land \neg q) \lor (q \land \F)$
My answer was $(\neg p \lor q) \land \neg q$
I have tried googling the problem and cannot come up with anything on duals and our lectures are online and upon reviewing do not see anything. I am just confused and looking for a little guidance on what was incorrect with my answers.
$\endgroup$ 24 Answers
$\begingroup$What you have done is wrong. Why you have negated all the proposition and the then find the dual?
Like dual of (p ∧ ¬q) is (p ∨ ¬q) not (¬p ∨ q).
Here is the definition of dual of a compound proposition:
The dual of a compound proposition that contains only the logical operators ∨, ∧, and ¬ is the compound proposition obtained by replacing each ∨ by ∧, each ∧ by ∨, each T by F, and each F by T. The dual of s is denoted by s∗. (Reference: Discrete Mathematics (7th Edition) Kenneth H. Rosen)
Example: S =(p ∧ q)∨ (¬p ∨ q)∨ F
dual of S = (p ∨ q)∧ (¬p ∧ q)∧T
So the correct answer to your question is:
a) p∨¬q
dual: p∧¬q
b) p∧(q∨(r∧T))
dual: p∨(q∧(r∨F))
c) (p∧¬q)∨(q∧F)
dual: (p∨¬q)∧(q∨T)
$\endgroup$ 1 $\begingroup$When I first looked that this problem in Rosens, Discrete Mathematics and Its Applications, I was very confused. After a computer driven CTRL-F search, the word dual seemed to only be in the book twice. They Explain what a dual is inside the problem. If you're this far along in the assignment, then the real problem for the 3 part question is the way the word the question.
"The dual of a compound proposition that contains only the logical operators ∨, ∧, and ¬ is the compound propositionobtained by replacing each ∨ by ∧, each ∧ by ∨, each T by F, and each F by T. The dual of s is denoted by s ∗."
The wording makes it seem as though the dual of an equation is found by switching
- V to ∧
- ∧ to V
- T to F
- F to T
- ¬q to q
but really, its just
- V to ∧
- ∧ to V
- T to F
- F to T
No need for changing the negations
They included the "extra" information on the negation because you can only find the dual of problems containing those symbols. So a problem containing a bi-conditional would not work. As far as we know this far in the book.
$\endgroup$ $\begingroup$You did more as you should. Forming the dual just wants you to replace $p$ by $\neg p$ for each literal $p$, $\lor$ by $\land$ and vice versa and $T$ by $F$. You did more than that, in dualising (2), one obtains $$ \neg p \lor \bigl( \neg q \land (\neg r \lor F)\bigr) $$ (you missed a $\neg$ in front of $r$). We have of course $\neg r \lor F \equiv \neg r$, but this is not part of dualising. Same for (3), the dual proposition is $$ (\neg p \lor q) \land (\neg q \lor T)$$
$\endgroup$ 4 $\begingroup$To obtain the dual of a formula , replace ∧ with V and T with F vice versa.. eg: dual of pVq is p∧q it is not ¬p∧¬q reference: Discrete mathematical structures with applications to computer science by J.P Tremblay and R.Manohar.
$\endgroup$
