Why I believe this is not a duplicate: This question might be the same, but the accepted answer is only a partial answer, because it gives no reason as to why those are the only solutions. Since the answer is accepted, that question will likely not receive any further answers. I would like to reopen this question in order to place a bounty and hopefully get a more complete answer.

When does $s^*=s$?

$s^*$ represents the dual of $s$, where $s$ is a compound proposition involving only $T, F, \wedge, \vee, \neg $, and $s^*$ is obtained by interchanging $T$ for $F$, $F$ for $T$, $\wedge$ for $\vee$, and $\vee$ for $\wedge$.

A big obstacle is that question is from the $2^{nd}$ section of chapter $1$ of a $2000^-level discrete math book, so we are not even introduced to induction. I don't even know what sort of tools I'm supposed to use to solve this.

What I've tried:

First, I drew up some truth tables of compound prepositions and their duals to look for any patterns, and what I noticed (in the few examples that I tried) was that the number of "True" outputs of $s$ was equal to the number of "False" outputs from $s^*$. For example, if $s$ was a compound proposition of $p, q, r$ and $s$ was true in $5$ cases and false in $3$, $s^*$ was false in $5$ cases and true in $3$ (they didn't match up though).

I think that if $a=b$, then $a^*=b^*$. I'm not sure how to prove this or if it's even necessary to prove it, but I suspect it's true. If it is, then at least $s^*=s$ holds for compound propositions $s$ which can be simplified to a single proposition. For example $s=(p \vee F) \wedge (q \vee T)=p$, therefore $s=p=p^*=s^*$. I know that in the definition of "dual" $s$ has to be a compound proposition; but as an exercise, the book asked to find the dual of this $s$ so I guess it's valid. If this is the only time when $s^*=s$, then I was thinking we can prove this by induction (even though we're probably not supposed to use it.) We know that if $s$ reduces to $p \wedge q$ or to $p \vee q$, then $s^* \ne s$, and then maybe we could use induction to show that if it reduces to a simpler proposition of $n+1$ variables, $s^*=s$ also doesn't hold.

  • $\begingroup$ What does “$=$” mean here exactly? It seems that you are trying to say when $s$ and $s^*$ are logically equivalent. But it seems to me that perhaps you are being asked to say when $s$ and $s^*$ are identical formulas, which is much easier, and as you say this is a 200-level discrete math class. Perhaps you have overcomplicated the question? $\endgroup$ – MJD May 24 '16 at 19:44
  • $\begingroup$ @MJD That's a VERY interesting point actually which I hadn't thought about; we are never actually given a definition for "="; the only thing the book has talked about so far is equivalence, so I assumed that's what this means too. Also, what do you mean by two compound propositions having identical formulas?Do you mean that if $s_1=p \vee q$ and $s_2 = p \vee q$, then $s_1$ and $s_2$ have identical formulas? How would that be any different from showing they are equivalent? Sorry for my gross ignorance, I am just a 2000-level discrete math student after all :P $\endgroup$ – Ovi May 25 '16 at 3:20
  • $\begingroup$ Ovi: Equivalent formulas have the same truth table, but need not be the same. $\lnot(p\land q)$ and $(\lnot p\lor \lnot q)$ are equivalent, but they are not the same formula. $\lnot(\lnot p)$ and $p$ are equivalent formulas, but they are not the same. $\endgroup$ – MJD May 25 '16 at 3:25
  • $\begingroup$ @MJD Ah okay thanks, I understand. $\endgroup$ – Ovi May 25 '16 at 3:35
  • $\begingroup$ @carmichael561 Please see the edit, I wrote why I believe the question should be reopened $\endgroup$ – Ovi May 29 '16 at 19:07

I am assuming that by $=$, you mean logical equivalence, which I will denote by $\equiv$.

One thing that might be helpful is the following: For a compound formula $s$, let $s'$ be the formula you get by replacing every variable by its negation.

Then, you get the theorem that $s^* \equiv \lnot s'$. Unfortunately, you will need induction on $s$ to prove that:

  • If $s$ is $T$ or $F$, then $s^*$ will be $F$ or $T$, respectively, as will $\lnot s' = \lnot s$.
  • If $s$ is a variable $p$, then we have $s^* = p = s$, and, by the definition of $s'$, we have $s' = \lnot p = \lnot s$. Thus we have $s^* \equiv \lnot s'$.
  • If $s = a \lor b$, then we assume that $a^* \equiv \lnot a'$ and $b^* \equiv \lnot b'$. Then we have $$ s^* = a^* \land b^* \equiv \lnot a' \land \lnot b' \equiv \lnot (a' \lor b') = \lnot s' $$ by De Morgan's law.
  • If $s = a \land b$, then we assume that $a^* \equiv \lnot a'$ and $b^* \equiv \lnot b'$. Then we have $$ s^* = a^* \lor b^* \equiv \lnot a' \lor \lnot b' \equiv \lnot (a' \land b') = \lnot s' $$ by De Morgan's law as well.

Now, this has one important consequence: You mention that $s$ only contains $T$, $F$, $\land$, $\lor$ and $\lnot$, and no variables. In this case, you have $s' = s$ and thus $s^* \equiv \lnot s$, so you will never have $s^* = s$!

But if your $s$ involves variables anyways, you can find out if $s* \equiv s$ by looking at the truth table for $s$: For every entry, you check the "opposite" entry where all the variables are assigned the opposite truth value (for example the opposite of the entry where $p = T, q = F$ is the one where $p = F, q = T$), and then you check if the two entries are different.

One neat result of this is that if $s^* \equiv s$, then exactly half the ways of assigning truth values to the variables will result in $s$ becoming true!

But because the answer to the question if $s^* \equiv s$ depends on the truth table of $s$, I don't expect there to be a method of checking if $s^* \equiv s$ that is faster than just making the truth table.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.