NOT isn't a binary operator. It's unary. (I'm using "binary" here to mean "has two parameters", not "pertains to ones and zeroes". You may be thinking of "boolean".) That's why I didn't include it.Phydios wrote:Excellent explanation! I seem to have learned binary logic a little differently, though: I learned that the basic operators were AND, OR, and NOT, because all the other gates could be constructed from them.
It's actually possible to construct every possible logical operation from just NAND or NOR.
NOT x = x NAND x
x AND y = NOT (x NAND y)
x OR y = (NOT x) NAND (NOT y)
x IMPLIES y = x NAND (NOT y)
TRUE = x NAND (x NAND x) (regardless of where you got x from)
FALSE = NOT TRUE
NOT x = x NOR x
x OR y = NOT (x NOR y)
x AND y = (NOT x) NOR (NOT y)
x IMPLIES y = NOT ((NOT x) NOR y)
FALSE = x NOR (x NOR x) (regardless of where you got x from)
TRUE = NOT FALSE
The IMPLIES operator is almost sufficient, but requires you to have FALSE as a defined constant:
NOT x = x IMPLIES FALSE
x OR y = (NOT x) IMPLIES y
x AND y = NOT (x IMPLIES (NOT y))
The DOESN'T IMPLY operator (let's shorten it to NIMP) similarly works if you have TRUE as a defined constant:
NOT x = TRUE NIMP x
x AND y = x NIMP (NOT y)
x OR y = NOT ((NOT x) NIMP y)
AND, OR, and NOT are usually used as the basic operators simply because they're the most intuitively convenient for humans. Well, and because many applications call for them directly rather than for more complicated operators that can be constructed from them.
XOR is also rather convoluted to design from other operators, so it's useful to have it available on its own:
x XOR y = (x OR y) AND (NOT (x AND y))
x XOR y = (x AND NOT y) OR (y AND NOT x)
x XOR y = (x NAND NOT y) NAND (y NAND NOT x)
Well, you'll see it a lot in mathematical logic, usually written out as an arrow rather than as a word.Phydios wrote:Never heard of the IMPLIES operator before- but it looks like it's just an unfamiliar name for a familiar concept.
It can be counterintutive because, mathematically speaking, something that is never true can imply every other thing, even if there's no logical connection. "pigs can fly IMPLIES the sky is blue" is a correct statement in our world, both because pigs cannot fly and because the sky is indeed blue (either one would be sufficient to make the implication true regardless of what I put in the other half), even though it's not like there's any reason pigs flying would change the sky's color. "x is a unicorn IMPLIES x has two horns" is a correct statement because unicorns do not exist, and so all of the ones that exist indeed have two horns. "this post is totally on-topic for this thread IMPLIES the moon is made of cheese" is a correct statement because... well, you get the point.