5

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.

Community
  • 1
Ovi
  • 23,737
  • 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? – MJD May 24 '16 at 19:44
  • @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 – Ovi May 25 '16 at 03:20
  • 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. – MJD May 25 '16 at 03:25
  • @MJD Ah okay thanks, I understand. – Ovi May 25 '16 at 03:35
  • @carmichael561 Please see the edit, I wrote why I believe the question should be reopened – Ovi May 29 '16 at 19:07
  • Finally, trough a linear combination of bounties, downvotes, and upvotes I have reached the perfect reputation of 5000 :p – Ovi Jun 03 '16 at 14:56
  • $ s = s^* $ precisely when negating all variables negates $ s $. – cardboard_box Jun 04 '16 at 17:15

1 Answers1

2

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.

dankness
  • 1,141