While I'm relatively new to Boolean algebra, I feel like I understand the rules reasonably well. I was legitimately surprised to find that what I call A NAND B, i.e. $\lnot(A\land B)$, has an identical truth table to what I call (NOT A) OR (NOT B), i.e. $\lnot A \lor \lnot B$. That table is here:
A | B | out
0 | 0 | 1
0 | 1 | 1
1 | 0 | 1
1 | 1 | 0
I believe that if two different logical statements share the same truth table, then they are equivalent, but my algebraic manipulations of the two statements don't lead me to find that they're equivalent.
My questions, then:
- Is it correct that if the truth tables of two (or more) statements are identical, then we know those statements are logically identical?
- How does one show that these two are identical statements algebraically?
I have done study on my own on this subject, but haven't had formal training in it. Any help is appreciated.
The answer to your first question is yes. The algebraic equivalence is simply one of the De Morgan’s laws.
Intuitively the equivalence is actually pretty straightforward. $\neg(A\land B)$ says that it is not the case that both $A$ and $B$ are true. That’s the same as saying that at least one of $A$ and $B$ is false, which is precisely what $(\neg A)\lor(\neg B)$ says: either $A$ is false, or $B$ is false, or both. Remember, logical or ($\lor$) is inclusive or.