One of the core concepts behind all of programming is logic. In particular, the boolean operators are used in almost every program that exists. While most people study arithmetic and algebra, many people do not realize that there is a similar amount of theory behind boolean logic.
The values that can exist in boolean logic are TRUE and FALSE. The operators available are NOT, AND, OR, XOR, XNOR, NAND and NOR. They are defined as follows:
NOT is a unary operator that returns the opposite value: NOT TRUE = FALSE, NOT FALSE = TRUE.
AND is a binary operator that returns TRUE if both values are TRUE, otherwise it returns FALSE.
OR is a binary operator that returns FALSE if both values are FALSE, otherwise it returns TRUE.
XOR is a binary operator that returns TRUE if the values are different, otherwise it returns FALSE.
XNOR is a binary operator that returns TRUE if both values are the same, otherwise it returns FALSE.
NAND is a binary operator that returns FALSE if both values are TRUE, otherwise it returns TRUE.
NOR is a binary operator that returns TRUE if both values are FALSE, otherwise it returns FALSE.
If your eyes are crossing, that means you're normal. To demonstrate this, we can instead use what is called a truth table to present the same information in an easy-to-read format.
With the binary operators, there are four rows:Code:A | NOT A --+------ T | F F | T
Code:A B | A AND B ----+-------- T T | T T F | F F T | F F F | FCode:A B | A OR B ----+-------- T T | T T F | T F T | T F F | FCode:A B | A XOR B ----+-------- T T | F T F | T F T | T F F | FCode:A B | A NAND B ----+-------- T T | F T F | T F T | T F F | TCode:A B | A NOR B ----+-------- T T | F T F | F F T | F F F | TFor each table, simply look up the row that has the values of the operands, and the result will be in the third column. The reality is that NAND, NOR, and XNOR are generally not used in programming languages. The reason for this is that they are redundant. NAND, for example, is equivalent to AND followed by NOT. To see this, look at this table:Code:A B | A XNOR B ----+-------- T T | T T F | F F T | F F F | T
The same logic applies to NOR and XNOR. An operation that is important, but usually not used in programming is IF ... THEN ..., or IMPLIES. Its table is.Code:A B || A NAND B || A AND B | NOT (A AND B) ----++----------++---------+-------------- T T || F || T | F T F || T || F | T F T || T || F | T F F || T || F | T
The idea for this can be best explained in terms of proving that someone has performed false advertising. If I say "If you bring me $100 then I will give you a HD TV", there are four possibilities when you show up at the store:Code:A B | A IMPLIES B ----+------------ T T | T T F | F F T | T F F | T
1) You give me $100 and I give you an HD TV. Obviously I kept my bargain.
2) You give me $100 and I tell you I changed my mind and want $1000. That's false advertising.
3) You offer me $50 and I give you an HD TV anyway. Generous on my part, no problem.
4) You offer me $50 and I tell you to get lost. You can't sue me... just scrape up $50 more dollars.
Only in case 2 can you accuse me of false advertising.
IMPLIES is used for determining whether an argument is valid in certain branches of logic (proofs), but is not really relevant here.
NOT, AND, and OR are the basis of all of the other operators (even XOR and IMPLIES). As a result, we will just analyze these three (with an occasional look at XOR). The ideas we will look at are the following (stolen blatantly from John): The principal of duality, identity elements, idempotent law, involution law, absorption law, commutative law, associative law, distributive law, DeMorgan's law, and the consensus theorem. (I stole the list from John because half these laws are not talked about regularly in mathy circles, and because you will need these for some tutorials he promises will be coming soon. To be honest, a lot of these are abstract algebra concepts that I hadn't associated with boolean algebra.)
For most of the items below, the law will be stated in general terms, then followed with concrete states for logic, then a truth table. # and @ will be used as generic operators.
Principal of Duality: A dual is what you get when you replace all the elements of a statement with its opposite element. So, if you have x' is the dual of x, you would have x#y=z changes to x'@y'=z'. In logic, AND and OR are duals, and TRUE and FALSE are duals. The following pair of truth tables illustrates this principal:
Identity Elements: For any operator, an identity element is an element that doesn't affect the other element when the operator is used. Using 1 for identity, 1#x=x, x#1=x. For AND, the Identity element is TRUE, for OR the Identity element is FALSE. You can see how this works below:Code:A B | A AND B A B | A OR B ----+-------- ----+------- T T | T F F | F T F | F F T | T F T | F T F | T F F | F T T | T
Code:T B | T AND B ----+-------- T T | T T F | FCode:A T | A AND T ----+-------- T T | T F T | FCode:F B | F OR B ----+-------- F T | T F F | FIdempotent Law: An Idempotent is something that doesn't change when it interacts with itself. x#x=x. AND and OR both satisfy this, while XOR does not, as seen below:Code:A F | A OR F ----+-------- T F | T F F | F
Code:A B | A AND B ----+-------- T T | T F F | FInvolution Law: Involution deals with the NOT operator. NOT NOT A = A, as seen below:Code:A B | A OR B ----+-------- T T | T F F | F
Absorption Law: The absorption law states that x#(x@y) = x, and x@(x#y) = x. A AND (A OR B) = A OR (A AND B) = A.Code:A | NOT A | NOT (NOT A) --+-------+------------ T | F | T F | T | F
Code:A B | A AND B | A OR (A AND B) ----+---------+--------------- T T | T | T T F | F | T F T | F | F F F | F | FCommutative Law: x#y = y#x. A AND B = B AND A, A OR B = B OR A. (note: IMPLIES does not satisfy this)Code:A B | A OR B | A AND (A OR B) ----+--------+--------------- T T | T | T T F | T | T F T | T | F F F | F | F
Code:A B | A AND B | B AND A ----+---------+-------- T T | T | T T F | F | F F T | F | F F F | F | FAssociative Law: x#(y#z) = (x#y)#z. A AND (B AND C) = (A AND B) AND C, A OR (B OR C) = (A OR B) OR C.Code:A B | A OR B | B OR A ----+--------+-------- T T | T | T T F | T | T F T | T | T F F | F | F
Code:A B C | A AND B | B AND C | A AND (B AND C) | (A AND B) AND C ------+---------+---------+-----------------+---------------- T T T | T | T | T | T T T F | T | F | F | F T F T | F | F | F | F T F F | F | F | F | F F T T | F | T | F | F F T F | F | F | F | F F F T | F | F | F | F F F F | F | F | F | FDistributive Law: x#(y@z) = (x#y)@(x#z). A AND (B OR C) = (A AND B) OR (A AND C), A OR (B AND C) = (A OR B) AND (A OR C).Code:A B C | A OR B | B OR C | A OR (B OR C) | (A OR B) OR C ------+--------+--------+---------------+-------------- T T T | T | T | T | T T T F | T | T | T | T T F T | T | T | T | T T F F | T | F | T | T F T T | T | T | T | T F T F | T | T | T | T F F T | F | T | T | T F F F | F | F | F | F
Code:A B C | A AND B | A AND C | B OR C | A AND (B OR C) | (A AND B) OR (A AND C) ------+---------+---------+--------+----------------+----------------------- T T T | T | T | T | T | T T T F | T | F | T | T | T T F T | F | T | T | T | T T F F | F | F | F | F | F F T T | F | F | T | F | F F T F | F | F | T | F | F F F T | F | F | T | F | F F F F | F | F | F | F | FDeMorgan's Law: NOT (A AND B) = NOT A OR NOT B, NOT (A OR B) = NOT A AND NOT B.Code:A B C | A OR B | A OR C | B AND C | A OR (B AND C) | (A OR B) AND (A OR C) ------+--------+--------+---------+----------------+----------------------- T T T | T | T | T | T | T T T F | T | T | F | T | T T F T | T | T | F | T | T T F F | T | T | F | T | T F T T | T | T | T | T | T F T F | T | F | F | F | F F F T | F | T | F | F | F F F F | F | F | F | F | F
Code:A B | A AND B | NOT A | NOT B | NOT (A AND B) | NOT A OR NOT B ----+---------+-------+-------+---------------+--------------- T T | T | F | F | F | F T F | F | F | T | T | T F T | F | T | F | T | T F F | F | T | T | T | TConsensus Theorem: (A AND B) OR (NOT A AND C) OR (B AND C) = (A AND B) OR (NOT A AND C)Code:A B | A OR B | NOT A | NOT B | NOT (A OR B) | NOT A AND NOT B ----+--------+-------+-------+--------------+---------------- T T | T | F | F | F | F T F | T | F | T | F | F F T | T | T | F | F | F F F | F | T | T | T | T
Code:A B C | A AND B | NOT A | NOT A AND C | B AND C | (A AND B) OR (NOT A AND C) OR (B AND C) | (A AND B) OR (NOT A AND C) ------+---------+-------+-------------+---------+-----------------------------------------+--------------------------- T T T | T | F | F | T | T | T T T F | T | F | F | F | T | T T F T | F | F | F | F | F | F T F F | F | F | F | F | F | F F T T | F | T | T | T | T | T F T F | F | T | F | F | F | F F F T | F | T | T | F | T | T F F F | F | T | F | F | F | F
great tutorial that will hopefully lead into some good tutorials from john. i will +rep you tonight when i come online
Posted via CodeCall Mobile
Wow, that is great tutorial! Very informative and descriptive. +rep
Exactly what I was looking for, but now I feel obligated to write mine. :[
Bwahahahaha! BTW, thanks for the kudos, guys.
There are currently 1 users browsing this thread. (0 members and 1 guests)
Posting Permissions
LinkBack URL
About LinkBacks
Reply With Quote
Bookmarks