1
$\begingroup$

Denoting boolean values (0 or 1) as $\mathbb{B}$, if $a, b \in \mathbb{B}$, is $a \equiv b$ mathematically identical to $a \Longleftrightarrow b$, given that they have identical truth tables?

$\endgroup$
  • 2
    $\begingroup$ $\equiv$ and $\iff$ are equivalent $\endgroup$ – J. W. Tanner May 21 at 1:47
  • $\begingroup$ In some cases can be useful to use different symbols for the boolean operator: $\equiv$, a symbol used to write a formula in the language of boolean algebra, and the symbol $\Leftrightarrow$ to express the equivalence between two formulas of boolean algebra. $\endgroup$ – Mauro ALLEGRANZA May 21 at 8:59
  • $\begingroup$ If so, the difference is that $x \equiv y$ is a formula of the language and the symbol $\equiv$ "connects" boolean variables, while e.g. $x\equiv y \Leftrightarrow \neg {(x\oplus y)}$ is an expression in the meta-language and the symbol $\Leftrightarrow$ connects formulas. $\endgroup$ – Mauro ALLEGRANZA May 21 at 9:00
  • $\begingroup$ @J.W.Tanner if that's the case, what difference is there between them? $\endgroup$ – Raymo111 May 21 at 17:38
  • 1
    $\begingroup$ to my mind, there is no difference in their meaning $\endgroup$ – J. W. Tanner May 21 at 18:16
1
$\begingroup$

There is another way of thinking about the logical operator $\iff$. If we think of the boolean value false as $0$ and the boolean value true as $1$, then the value of an equation involving boolean variables $a$ and $b$ like this one $a\iff b$ can be though of as $a+b+1(mod 2)$.

Let us check that indeed these two equation compute the same thing.

\begin{array} {|r|r|}\hline a & b & a+b+1(mod 2) & a \iff b \\ \hline 1 & 0 & 0 & 0 \\ \hline 1 & 1 & 1 & 1 \\ \hline 0 & 0 & 1 & 1 \\ \hline 0 & 1 & 0 & 0 \\ \hline \end{array}

This way of viewing the boolean operator $\iff$ is very useful sometimes. For example, consider the claim that a boolean expression involving a finite number of variables and that each variable is used an even number of times, and the logical operator is restricted also to only the $\iff$ operator, then the boolean expression is a tautology, namely, the boolean expression is always true no matter the value $\{0,1\}$ that you assign to the variables.

If you were to use the definition of the logical operator $\iff$, it is probably not going to be very easy to prove the claim. But if you view the logical expression $a \iff b$ as $a+b+1(mod2)$, then the problem could be much easier. Namely, if you first change your boolean expression in the modular addition format and get rid of the parenthesis, you will get the sum of each variable an even number of times. The sum of the variable will therefore be equals to $0(mod2)$. Futhermore , each variable appear an even number of times means that there are an odd number of $\iff$ operators in the original boolean expression. When you converted the boolean expression into the expression involving sums of the variable + $1$, you essentially converted the odd number of $\iff$ operators into the sum of odd numbers of $1$'s plus the variables. We know that the sum of the variables is $0(mod2)$ and the sum of odd number of $1$'s is $1(mod2)$, therefore, the value of your converted expression is also $1(mod2)$. And since $1$ correspond to the boolean value True, you know that your expression is always true, hence a tautology.

Therefore, you see that this is a powerful technique of converting a boolean operator into arithmetic in mod2.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This doesn't answer my question? I asked about the difference between $a \equiv b$ and $a \Longleftrightarrow b$, not $a \Longleftrightarrow b$ and $a + b + 1(mod2)$ $\endgroup$ – Raymo111 May 21 at 17:35
  • $\begingroup$ I think they are equivalent. The symbol $\equiv$ is used in modular arithmetic as well. When you write $a \equiv b(modk)$, that means that $a,b$ have the same remainder after division by $k$. In the context of boolean algebra, each variable takes two values. If we think of them in mod2, then $a \equiv b(mod2)$ is true/fase if and only if $a \iff b$ is true/false. This is confirmed by the many comments that you got in your post as well. Given that stack exchange is a prestigious math discussion site, it is fun to learn a few extra :) $\endgroup$ – user614287 May 21 at 19:01

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.