Math Is Fun Forum

Ivar Sand

Member

Registered: 2013-01-22

Posts: 20

Equivalence and Equality are the same in Bool

Theorem:
Let A, B be Boolean variables (1).
Then:
    (A <=> B) = (A = B)

Proof:
We prove this by evaluating the condition in the theorem text and demonstrating that the value is true in all cases.

There are three possible combinations of the values of A and B:
    A = B
    A = false, B = true
    A = true, B = false

We have:
    (A <=> B) = (A = B)
    = ((A => B) and (B => A)) = (A = B)        by definition of <=> (2)
    = ((~A or B) and (~B or A)) = (A = B)        by definition of => (2)

The case A = B:

We have:
    ((~A or B) and (~B or A)) = (A = B)
    = (((~B or B) and (~B or B)) = (B = B))        as A = B
    = ((true and true) = (B = B))            by negation law (2)
    = (true = (B = B))                by idempotent law (2)
    = (true = true)                    by reflexivity law (3)
    = true                        by reflexivity law (3)
which is what we set out to prove.

The case A = false, B = true:

We have:
    ((~A or B) and (~B or A)) = (A = B)
    = (((~false or true) and (~true or false)) = (false = true))    as A = false, B = true
    = (((true or true) and (false or false)) = (false = true))    as ~false = true and ~true = false (4)
    = ((true and false) = (false = true))                as true or true = true and false or false = false (1)
    = (false = (false = true))                    as true and false = false (1)
    = (false = false)                        as (false = true) = false as false and true are different values (3)
    = true                                by reflexivity law (3)

The case A = true, B = false:

We have:
    ((~A or B) and (~B or A)) = (A = B)
    = (((~true or false) and (~false or true)) = (true = false))        as A = true, B = false
    = (((false or false) and (true or true)) = (true = false))        as ~true = false and ~false = true (4)
    = ((false and true) = (true = false))            as false or false = false and true or true = true (1)
    = (false = (true = false))                as false and true = false (1)
    = (false = false)                as (true = false) = false as true and false are different values (3)
    = true                        by reflexivity law (3)

We have shown that the condition in the theorem text is true for all possible combinations of the values of A and B, so the proof is complete.

References:
1 Boolean algebra https://en.wikipedia.org/wiki/Boolean_algebra
2 Logical equivalence https://en.wikipedia.org/wiki/Logical_equivalence
3 Equality (mathematics) https://en.wikipedia.org/wiki/Equality_(mathematics)
4 False (logic) https://en.wikipedia.org/wiki/False_(logic)

---

I majored in Physics in 1976. Also, I studied mathematics and computer science. I worked as a computer programmer. I became a pensioner in 2016. I am from Norway.