4

So I am studying computer science and right now I am stuck on a problem.

When does s∗ = s, where s is a compound proposition?

So far the only thing I can come up with is:

s* = s when the compound proposition is composed only of the same propositions. (ex. p ∧ p = p ∨ p)

The book defines duality as:

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∗. (Discrete Mathematics and its Applications, Rosen, 7e)

Any help would be great, this is a tricky one.

Greg
  • 145
  • Oh just in case, the problem explicitly states that the equals sign is used and that it is not the same as equality. – Greg Jan 31 '14 at 18:50
  • Could you give your definition of "dual"? – hmakholm left over Monica Jan 31 '14 at 18:50
  • From the book:

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

     – Greg Jan 31 '14 at 18:51
  • If you get the dual proposition by replacing each occurrence of $\land, \lor, T, F$ with something different, doesn't that mean that you will necessarily get a different proposition whenever the original proposition contains any of those? So to be self-dual, a proposition must be of the form $\lnot(\lnot(\cdots\lnot P)\cdots)$ for some atom $P$. Or does $=$ here denote logical equivalence rather than exact identity? – MJD Jan 31 '14 at 19:02
  • See thats the confusing part I am really not sure. The instructor only said that = is not the same as ≡ – Greg Jan 31 '14 at 19:11
  • @Greg: And what does $\equiv$ mean in your context? (Sometimes it is logical equivalence, sometimes textual identity, something identity-by-definition, sometimes something entirely different). – hmakholm left over Monica Jan 31 '14 at 19:13
  • Sorry ≡ means logical equivalence. So p ≡ q would mean that both p and q have the same truth values. – Greg Jan 31 '14 at 19:15

2 Answers2

7

I hope this is going to help somebody; I came up with the same solution which is known as idempotent law, plus the others: p ∧ T = p ∨ F (identity law) p∧(p∨q)=p∨(p∧q) (absorption law) (try proving logical equivalences)

navy
  • 86
  • 2
    That was one of the answers if I remember correctly. Sorry I forgot to update. Thanks for taking the time, I am sure it will help someone someday. – Greg Jul 19 '14 at 17:20
  • @Greg Helped me, stuck on the exact same problem in the 6th edition of the book :D – Ovi May 25 '16 at 03:39
0

Even I use Discrete Mathematics by Rosen ,7r. Duality & its really pretty awesome book for Discrete mathematics.

The dual of a compound proposition that contains only the logical operators of AND (^) ,OR (v) and negation (~) is the compound proposition obtained by replacing each v by ^, each ^ by v, each T by F,and each F by T. The dual of of a compound proposition s is denoted by s*.

so we will have dual s = s* & you can verify it by using truth tables.

For. e.g: p ^ p is equivalent to its dual p v p and as you construct a truth table for those duals, you'll see that both are logically equal. So, s = s* = s.

Similar is for (s*)* = s i.e., as we know that a dual is formed by replacing And with an OR and vice-versa is also possible and same is the case when dealing with T and F .

To be precise, a dual for p v p is p^p i.e., s* is dual of s and again if you apply the duality law for s* again, you'll see that you get back s again i.e.,s = s* = (s*)* = s.

justExploring
  • 1