[Math] When does the dual of $s =s$

discrete mathematicslogicpropositional-calculus

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.

Best Answer

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.

Related Question