CS211: Boolean Logic

It is that following this method [binary], all numbers are written by the co-mingling of the unit and zero, much the same as all creatures coming uniquely from God and nothingness…my main object…has been to furnish you with new conformation of the Christian religion… — Gottfried Leibniz to Joachim Bouvet, Feb 15, 1701

Ascribing divinity to mathematics has deeper roots than that of the written word. In fact, some scholars believe that ordinal numbers developed before cardinal numbers due to the advent of ritual practices which required the ranking of deities¹. The ancient greeks developed cult-like religious orders around what they thought to be the beauty of mathematics (the word itself coined by Pythagoras meaning "that which is learned"). Numbers even had their own distinct mythologies:

• 1 → the generator of number - female number - the number of opinion
• 2 → first even number - female number - the number of opinion
• 3 → first true male number - the number of harmony
• 4 → number of justice or retribution - the squaring of accounts
• 5 → number of marriage - the union of the first male and female numbers
• 6 → number of creation
• 10 → the holiest of all - the number of the universe - the sum of all possible geometric dimensions

Echoes of these cults could be heard in Plato's Academy, whose door had the phrase "let no one ignorant of geometry enter here" centered above it. This sentiment lived on for thousands of years, eventually finding itself expressed by one of the great minds of the 17th century, one Gottfried Liebniz. Liebniz believed deeply in the power of binary numbers, going so far as to try to construct a mathematical system capable of containing the entirety of human logic itself—he called it the calculus ratiocinator (rational calculator). Leibniz's oft overlooked algebraic logic, wherein he aspired to demonstrate that all human thought could be captured in symbols, would prove to be a premonition of the contributions a shoemaker's son in England would make over a hundred years later.

In 1847, George Boole published a short work titled The Mathematical Analysis of Logic which broke down the history of logic into three stages: (1) Greek logic, (2) Scholastic logic, and (3) mathematical logic. The last of which represented the importance of symbols in the construction of mathematical wisdom—a formal system is created which then is overlaid back over daily life. Boole argued that logic should be placed squarely under the purview of mathematics, the two were not completely different entities. In 1854, Boole published a book titled Investigation of the Laws of Thought which further espoused his views on logic as mathematics and formally introduced his "algebra of logic". This algebraic logic was later called boolean algebra.

Boolean logic is meant to represent abstract "things". Boole would use x, y, z, etc. to represent objects of a subset of things—numbers, points, ideas, etc.—selected from a universal discourse. The totality of that discourse he denoted with 1. If 1 represented all students then x might represent freshman, y might represent students with a GPA above 3.5, and z might represent students with two majors. 0 would indicate the empty set. Operations such as union, ​+, or intersection, ×, were meant to combine the logical symbols. x + y would be all freshman and all students with a 3.5​+ GPA; whereas, x × y would be all freshmen with a 3.5​+ GPA.

In boolean algebra, all five fundamental laws of algebra still hold:

1. x + y = y + x
2. xy = yx
3. x + (y + z) = (x + y) + z
4. x(yz) = (xy)z
5. x(y + z) = xy + xz

However, some fundamental rules of traditional algebra are violated by boolean algebras. The most obvious being that 1 + 1 = 1, as 1 represents totality.

As stated above, in boolean algebra there are only two values: 1 and 0. 1 is often mapped to true and 0 is mapped to false.

There are only three operations in boolean algebra: conjunction, disjunction, and negation.

Often, discussions of boolean algebra will lead to the discussion of one of its most popular laws which was discovered by Augustus De Morgan, a mathematician and friend of George Boole. It goes as follows:

• The negation of "A and B" is the same as "not A or not B".
• The negation of "A or B" is the same as "not A and not B".

Translated into C syntax it would be:

• !(a && b) == !a || !b
• !(a || b) == !a && !b

The law shows that both conjunction and disjunction can be expressed in terms of the other, as long as negation is possible. This is used to simplify circuit design, as only an AND or an OR gate is necessary as long as there is a possible NOT gate.

Boole's discovery of this symbo-logical algebra paved the way for later mathematicians to formalize the connection between logic and electrical circuits. For example, the logician and philosopher Charles Sanders Pierce was one of the first people to realize that logical operations could be performed by logical circuits due to their binary, on/off nature. Claude Shannon, the father of information theory, proved in his Master's thesis that electrical circuits and boolean algebra were logically equivalent. Many computer programming languages will offer a type in their type systems called bools or booleans to pay homage to Boole's algebraic system².

1. Evaluate the following boolean expressions by hand, then verify by writing a C program that prints each result using printf("%d\n", expr):
   • !(1 && 0)
   • (!1 && !0) || (1 || (1 && 1))
   • (1 || 0 || 1 || 0 || 1 || 0) && 0
2. Using De Morgan's Law, rewrite the following expressions without the outer negation and verify both forms produce the same result in C:
   • !(1 && 1)
   • !(0 || 1)
   • !(1 && 0)
3. Using Boole's original framing from the lecture, let 1 represent all students at Binghamton University, x represent CS majors, y represent students with a GPA above 3.5, and z represent seniors. Express the following in boolean algebra and evaluate:
   • All CS majors with a GPA above 3.5
   • All seniors who are not CS majors
   • All students who are either CS majors or seniors, but not both
4. Construct a truth table by hand for each of the three operations (AND, OR, NOT) listing all possible input combinations and their outputs. Then write a C program that prints the same truth table to the screen.
5. The lecture states that 1 + 1 = 1 in boolean algebra. Why would this be a violation of traditional algebra? In terms of Boole's original framing using sets, explain intuitively why this rule makes sense.
6. Using only && and ! (no ||), rewrite the following expressions and verify in C that they produce the same result:
   • 1 || 0
   • 1 || 1
   • 0 || 0
7. In C, any non-zero integer is treated as true and zero as false. Write a program that tests this by printing the result of the following expressions using printf("%d\n", expr): !0, !1, !2, !-1, !100. What do you notice about the output? What does this tell you about how C treats non-zero integers in a boolean context?
8. Write a C program that declares two int variables and uses all three boolean operators to produce and print at least five different boolean expressions combining them. For each expression, predict the result before running.