In last week’s post, we addressed the basic operations of Boolean algebra—AND, OR, XOR, NOT—that lay the foundation for modern digital logic. In this post, we will extend this repertoire to include more obscure operations that are nevertheless ubiquitous in everyday conversation and thought.

De Morgan’s Laws

Before these operations are reviewed, let us consider an anomaly with the basic operations that was formulated by British mathematician Augustus De Morgan (1806-1871). Supposing there exist conditions A and B, the following statements hold true:

• NOT (A OR B) = NOT A AND NOT B
• NOT (A AND B) = NOT A OR NOT B

In the context of language, De Morgan’s Laws inherently make sense. If it is not raining or snowing, then it is both not raining and not snowing. Likewise, if it is not raining and snowing simultaneously, we can conclude that either it is not raining or it is not snowing (or both).

Implication (–>)

The Boolean implication operation takes the form of an “if-then” statement, much like a scientific hypothesis. To understand the nature of the implication, let us put aside the harmlessness of liquid precipitation and assume that an umbrella is a necessity to go outside during a rainstorm. Consider the following four statements:

• IF it is raining THEN I will take an umbrella.
• IF it is NOT raining THEN I will NOT take an umbrella.
• IF it is NOT raining THEN I will take an umbrella.
• IF it is raining THEN I will NOT take an umbrella.

These four statements comprise all of the possible situations in which I could be: it is either raining or it is not, and I will either take an umbrella or I will not. The first two statements are manifestly sensical and can thus be considered TRUE; I need an umbrella if it is raining and do not need one otherwise.

The third and fourth statements are less trivial. If it is not raining, then although I do not need an umbrella, there is no harm in taking one anyway. On the other hand, if it is raining and I neglect taking an umbrella, I will be (hypothetically) harmed as a result. Thus, while the third statement is TRUE, the final statement is FALSE.

Image Courtesy of Richard Coyne

The results convey that the implication is based on specificity vs generality. Consider the general case B and the specific case A, as illustrated in the diagram above. If A is true (1), then B must be true (1) as a result. It is impossible for the specific case to hold without the general case. If A is false (0), then B may be either true (1) or false (0). In the example, whether it is raining comprises the specific case while my taking an umbrella comprises the general case—I am able to take my umbrella during any type of weather. The only case that does not make sense is when the presence of rain (1) implies that I do not take my umbrella (0). In symbols:

• 0 –> 0 = 1
• 0 –> 1 = 1
• 1 –> 0 = 0
• 1 –> 1 = 1

Interestingly, if A –> B, the implication can be expressed as NOT A OR B, for the only false statement occurs when A is true (1) and B is false (0), consistent with the behavior of the OR and NOT operations.

Biconditional (<=>)

A stricter operation than the implication is the biconditional, characterized as an “if and only if” statement. If I say, “I will take my umbrella if and only if it is raining,” the generality of the umbrella condition is annihilated. That is, if it is not raining, I do not take my umbrella, and if it is raining, I take it; no other cases can be regarded as true. Symbolically, the biconditional deduces the following:

• 0 <=> 0 = 1
• 0 <=> 1 = 0
• 1 <=> 0 = 0
• 1 <=> 1 = 1

If A <=> B, then A must imply B and B must imply A. The biconditional can thus be written as A –> B AND B –> A. One condition no longer supersedes the other in generality; there is a one-to-one correspondence between event A and event B. If one condition is met, the other must also be must; conversely, failure to meet one condition directly implies failure to meet the other. Thus, the statement, “I will take my umbrella if and only if it is not raining,” no longer makes sense and is FALSE.

Arithmetic, algebra, geometry, calculus, and statistics are the five main pillars of mathematics that are enacted in curricula from grade school through postsecondary education. As such, one of the more under-appreciated domains of mathematics is logic, with its syntactics rarely examined but its semantics ubiquitous in every aspect of society. Logic has been a human formulation since the dawn of humanity itself, but the foundations for modern digital logic were laid by English mathematician George Boole (1815-1864) in his 1854 work Laws of Thought. An understanding of Boolean logic–and by extension, Boolean algebra–is essential in understanding the workings of modern digital technology that are widely taken for granted.

Image Courtesy of Britannica

To maintain quantitative structure, True and False, the basic units of logic, are assigned values of 1 and 0, respectively. We will now examine the fundamental operations of Boolean algebra.

AND [*]

By definition, a statement containing the conjunction “and” is true only when both conditions in question are true. If I say, “I am at home AND I am in my dorm,” then the entire statement is false, even though the first condition (me being at home) is true. If the truth or falsity of each condition is denoted by 1 or 0, respectively, the following holds:

• 0 AND 0 = 0
• 0 AND 1 = 0
• 1 AND 0 = 0
• 1 AND 1 = 1

It is clear that the Boolean AND operation can be modeled as a traditional multiplication (*), for any false condition is said to annihilate the entire statement to 0 (False).

Inclusive OR [+]

In contrast with the definition of AND, an inclusive OR statement is true when either of the conditions in question is true. Inclusive means that the statement is still regarded as true if both conditions are true. This deviates from the traditional English definition of the word “or,” which is defined in the exclusive sense. As expressed below, an inclusive OR statement is only false when both conditions are false:

• 0 OR 0 = 0
• 0 OR 1 = 1
• 1 OR 0 = 1
• 1 OR 1 = 1

Boole synthesizes the inclusive OR operation with the arithmetic operation of addition (+). This differs from the traditional definition of addition in the last statement (1 + 1 = 1).

Exclusive Or (XOR)

As mentioned in the previous section, the exclusive OR operation excludes from truth the statement where both conditions are true:

• 0 XOR 0 = 0
• 0 XOR 1 = 1
• 1 XOR 0 = 1
• 1 XOR 1 = 0

NOT [~]

Trivially, the NOT operation simply reverses the truth value of a singular (non-combinational) statement. Indeed, something that is “not false” is “true,” and something that is “not true” is “false.”

• ~0 = 1
• ~1 = 0

It is important to note that there exists an order of operations in Boolean algebra. Just as traditional algebraic expressions with several terms are evaluated in this order–

1. Parentheses/Brackets/Grouping Symbols
2. Exponentiation
3. Multiplication and Division
4. Addition and Subtraction–

the Boolean operations are evaluated in this order–

1. Parenthetical Terms/NOT (corresponds to grouping of terms)
2. AND (similar to multiplication)
3. OR/XOR (similar to addition)

For example, the expression 1 AND (0 XOR 1) OR ~1 OR (1 AND ~0) AND ~~~1 is evaluated by the following procedure:

1. Separately evaluate expressions in parentheses and simplify negated (NOT) terms: 1 AND 1 OR 0 OR 1 AND 0
2. Evaluate AND expressions: 1 OR 0 OR 0
3. Evaluate OR expressions (although there is a triple instead of a pair of conditions, it remains that any true condition yields a true statement) 1

In next week’s post, I will detail more involved and intriguing operations as well as the innumerable (indeed, uncountably infinite) applications of Boolean logic that permeate modern life.

With the COVID-19 pandemic severely disrupting my typical research habits, I shall no longer tailor subsequent posts around the Smart Dust project and the entailed mathematics. While I still remain very much engaged with the project, it is only appropriate to revert to the original intention of this blog: the conveyance of my lifelong passion of teaching theoretical mathematics. Today, I shall write about infinity and its several variations.

Ever since the birth of numbers themselves, humans have struggled to explain the nature of infinity. What does it mean for something to “go on forever?” Does the universe extend infinitely in all directions? Can one break an object into infinitely small (infinitesimal) pieces? While cosmologists and chemists have universally agreed upon negative answers to each of the two respective questions, the theoretical nature of numbers legitimizes the concept in counting. Indeed, our decimal number system is constructed so that one is able to begin counting “1, 2, 3, 4, 5, 6,…” and continue indefinitely. Because each number can be assigned an ordinal position (1 is the “1st number,” 2 is the “2nd number,” 3 is the “3rd number,” etc.), we say that the natural numbers—or whole numbers if 0 is included—are countably infinite. That is, although it would take an eternity, one is hypothetically able to enumerate the entire set of natural (or whole) numbers in a list.

This raises the question, “Which is larger: the set of natural numbers or the set of even numbers?” One may be quick to assert that because the even numbers are simply alternate natural numbers (1, 2, 3, 4, 5, 6, 7, 8,…), there are half as many even numbers as natural numbers. However, notice how each even number can be assigned to an ordinal number just like the natural numbers:

• 2 is the “1st number”
• 4 is the “2nd number”
• 6 is the “3rd number”
• 8 is the “4th number,” etc.

Since the even numbers are also countably infinite, it is only reasonable to conclude that the even numbers and the natural numbers have the same amount of elements (technically, are equivalent in cardinality). Assigning ordinal positions in more complex ways, one can deduce that the following sets have the same cardinality—i.e., are equal in size—as the natural numbers, and thus are also countably infinite:

• Integers (natural numbers plus 0 and negatives)
• Rational numbers (positive and negative ratios of natural numbers)
• Algebraic numbers (numbers that are solutions to algebraic equations—e.g., the square root of 2 is the solution to x^2 – 2 = 0)

The above observations are attributed to the German mathematician Georg Cantor (1845-1918).

Image Courtesy of Wikipedia

In determining whether the real numbers (all rational and irrational numbers) are also countably infinite, Cantor established his diagonal method, which takes the form of a reductio ad absurdum proof (proof by contradiction) and is illustrated below:

Cantor’s Diagonal Method

Suppose that one has compiled a comprehensive enumeration of all real numbers and has listed some below (recall that irrational numbers are non-terminating, non-repeating decimals):

• 0.738972491301701703724… is the “1st number”
• 0.218390218432041809123… is the “2nd number”
• 0.182043928417132908121… is the “3rd number”
• 0.213897412912010901010… is the “4th number”
• 0.631913630329878119937… is the “5th number,” etc.

Now, we form a number by taking the nth decimal digit of the nth number. Thus, the first digit of the number is the first decimal digit of the first enumerated number; the second digit of the new number is the second decimal digit of the second enumerated number; and so on. There is a “diagonal” of sorts that is constituted:

• 0.738972491301701703724…
• 0.218390218432041809123…
• 0.182043928417132908121…
• 0.213897412912010901010…
• 0.631913630329878119937…

Using this process, we deduce the decimal number 0.71281…. Let us now form a new number by adding 1 to each decimal digit of the current number: we obtain 0.82392….

Can 0.82392… be in our list? It certainly cannot be the first number, for the 8 in the tenths place differs from the 7 in the first number in the list. It cannot be the second number; the 2 in the hundredths place differs from the 1 in the second number. In fact, the nth digit in the newly formed number differs from the nth digit in the nth enumerated number. Therefore, our seemingly comprehensive list of all real numbers is incomplete, for a new number can always be added by the method above. As a result, the real numbers exhibit an entirely different level of infinity—i.e., they are uncountably infinite.

Such “levels” of infinity are quantified in the transfinite numbers symbolized by the Hebrew letter aleph. Aleph-null signifies the countable infinity of the natural numbers (and additional sets like the rational and algebraic numbers). “Uncountable infinity” is expressed as aleph-1. In fact, there are an infinity of transfinite numbers (aleph-2, aleph-3, etc.); there exist infinities beyond that of the real numbers, but they encompass a higher mathematics that is much beyond the scope and demands of this blog.

It was my original intention to thoroughly read up on Smart Dust in the past week to prepare for my research and to gain a solid mathematical footing for this post. However, due to several exams and assessments with which I have been occupied, the “time got away from me,” and I was only able to read broad introductory pieces into the history and basic terminology associated with the technology. Thus, it is only fitting to freshly resume my endeavor after Spring Break—and to go into the break discussing time, particularly the calendar anomalies associated with this time of year.

1. Leap Day

This past Saturday was February 29, a day supposedly annexed to the shortest month every four years to account for the inexactness of a 365-day year. I say supposedly because it is popularly believed that any year divisible by 4—alternatively, every presidential election year—is a leap year. However, the algorithm has one caveat that has not been of interest recently but may be of interest to us should we live long enough to experience it:

A. Any year divisible by 4 and not by 100 is a leap year

B. If a year is divisible by 100, it must also be divisible by 400 to be a leap year.

Image Courtesy of General Blue

The second provision dictates that while years such as 1600, 2000, and 2400 are leap years like any other, century years not divisible by 400 (e.g., 1800, 1900, 2100, 2200) are not leap years. This was precisely the adjustment made by Pope Gregory XIII in 1582, when the dates of October 5-14 were eliminated to correct the fallacy of the Julian Calendar (the assumption that a leap year should unconditionally be every four years), which had let the calendar drift 12 days askew. To this day, the Gregorian Calendar forces leap-day babies who live through century years such as 1700, 1800, 1900, etc. to wait 8 years between birthdays instead of the already-intriguing 4. For the historian’s appeal, Thomas Jefferson and William McKinley are the only two U.S. presidents to have been elected in common years (non-leap years), and whoever is sworn in on January 20, 2101 will be the third.

2. Daylight Saving Time

This Sunday, March 8 (unless you are traveling to Hawaii or the non-Navajo part of Arizona for Spring Break), you will experience a 23-hour day, with 1:59 AM changing to 3:00 AM. The agricultural and statistical reasons for Daylight Saving Time (DST) notwithstanding, there is a growing movement to either abolish it (“fall back forever”) or stay in DST for 12 months of the year instead of the traditional 8. Keep in mind that the switch to and from Daylight Saving Time shifts the daily sunrise and sunset times by one hour; one can analyze this in the context of the longest and shortest days of the year (June 21 and December 21, respectively, with the opposite true in the Southern Hemisphere):

Currently, in State College (about 40 degrees N latitude), the Sun rises and sets at approximately 5:30 AM and 9:00 PM, respectively, on the summer solstice (6/21), which is in DST. Without DST, these times would be 4:30 AM and 8:00 PM.

On the winter solstice (12/21), which is in standard time, the Sun rises and sets at approximately 7:30 AM and 5:00 PM. If DST were year-round, these times would be 8:30 AM and 6:00 PM.

Image Courtesy of Business Insider

Image Courtesy of Blue Delaware

Based on this information, what is your opinion of Daylight Saving Time? Would you abolish it in favor of a super-early sunrise and a more modest sunset time in the summer, or would you abolish standard time to obtain an extra hour of daylight in evenings while waking up to darkness in the winter?

3. When Is Easter?

As a Catholic, Easter Sunday is the holiest day of the liturgical year. While it is not until April 12 this spring, the theme of this final pre-Smart Dust post bestows the ideal opportunity to discuss the little known formula of how the date is determined. In 2019, Easter fell on April 21; in 2018, April 1; in 2017, April 16. Next year, it will fall on April 4, 2021. The date seems to constitute a randomly chosen Sunday in March or April without rhyme or reason. However, it is actually derived as follows:

Easter falls on the first Sunday after the first full moon after the Vernal (Spring) Equinox.

For example, this year, the Vernal Equinox—“first day of spring”—is on Thursday, March 19. The next full moon after the equinox occurs on Tuesday, April 7. Easter is thus celebrated on the following Sunday, April 12. If the so-called paschal full moon happens to occur on a Sunday, Easter is placed the following week in lieu of the same day.

Due to the quasi-periodic nature of the moon phases, there exists an algorithm to mathematically determine the date of Easter Sunday for any given year. I will not regurgitate the algorithm in this post, but I link to it here and highly encourage you to read about it yourself. As an exercise, use the algorithm to determine Easter Sunday in your birth year (probably 2000 or 2001) and compare your result to a Google search.

Image Courtesy of Active Christianity