1

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.

Rodrigo de Azevedo
  • 1
Kevin
  • 35
  • 1
    This can't be "easy" if you didn't get it right. How about a slightly more descriptive title instead? – Asaf Karagila Oct 17 '13 at 10:11
  • Sorry about the misleading title. When I first did it I thought it was very simple and now that I see the answer it was just a simple mistake on my part. – Kevin Oct 17 '13 at 11:03

3 Answers3

3

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 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 ∗."

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.

Julian Weidner
  • 31
3

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)

Sumit Ranjan
  • 81
  • Fairly new to discrete math here, so there's a very real chance I'm wrong, but c can be shortened. (q or T) is a tautology, so it's always T. That leaves (p or not q) and T, which is just p or not q because T has no actual impact on the answer – Zoe is on strike Aug 25 '20 at 11:15
0

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.

sowjanya
  • 1