December 17, 2018

Beyond Calculus

The origin of logic theory starts at the concept of an *argument*. The majority of logic textbooks contain an opening, central definition for an argument — one that likely sounds much like the following:

*An argument contains one or more special statements, called **premises **, offered as a reason to believe that a further statement, called the conclusion, is true*

Premises are the atoms of logic theory: everything is built up from them. A premise is a declarative statement that *must* strictly evaluate to only either true or false. A single premise is referred to as a **primitive premise** — *there are 50 states in the U.S.A *(which is true). Connecting multiple premises together form a **compound premise** — *there are 50 states in the U.S.A **and** it snowed in Miami today* (which is false). How does one connect multiple statements? Like you see in the previous example, with operators that you’re already familiar with but that require their own language & syntax.

Similar to other branches of math, premises have their own set of fundamental operators (adding, subtracting, etc…). In logic theory, **five** basic logical connectors, collectively known as ** connectives**, fill this role. They’re summarized in the table below, assume the letters

If you’ve been exposed to programming at any level, then it’s highly likely that the table above seems at least vaguely familiar. This is because connectives are at the very core of common language syntax & almost always have some special character designated for each connective (&& = and, | = or, etc…).

Which of the five connectives is used as a logical connector between two premises determines the overall truth value of the compound statement based on the truth values of the premises being modified. An important principle here that might seem counter-intuitive at first is worth extracting: when analyzing compound statements it’s *not* necessary to know what parts P & Q actually say, only whether those parts are true or false.

Of the five connectives, one is immediately worthy of further inspection — the implication, aka, if-then statements. The implication is a connective with the standard form of P → Q where P is known as the hypothesis (or antecedent), & Q is known as the conclusion (or consequent).

While the implication has a standard form defined above, there exists three other common types of conditionals that are worth reviewing. The following four conditionals are simple yet quite common & powerful compound statements made by combining conditionals with the core connectives introduced:

A conditional is itself a compound premise, that is, it strictly evaluates to either true or false. For any implication, just like for any other connective, the truth value of the compound premise is determined by the truth values of its two independent premises. Corresponding with the definitions introduced above, for example, an implication is *true* either when the hypothesis is false, *or* when the conclusion is true; which leaves only one way for an implication to be false: when the hypothesis is true & the conclusion is false.

If that seemed like a lot to track mentally, as it did for me, then breath easy & rest assure that powerful tools lay in the near future that makes analyzing complex conditionals as simple as following a blueprint. The main tool we’ll use is a nifty logic-101 tool by the name of ** truth tables**. Before we get into truth tables, however, let’s make a quick detour to fill one last gap in our knowledge of basic logic theory notation. Inspect a peculiar scenario — is the following statement a premise?

*x is larger than ten*

Under our strict definition introduced in the opening paragraph, a premise *must *evaluate to either true or false — the statement *cannot *be ambiguous or left open-ended. Which means that variables, as we’re used to seeing them since algebra, is a no-no in logic theory; not at least without some modification.

The bolded statement above is *not* considered a premise as ** x** could be 5 or 25, making the statement true or false, but currently neither. This, however, doesn’t mean that we have to delete variables from our tool set altogether. There

*for all x, x is larger than one hundred*

Now that we’ve defined the *universe*, *o*r domain, of the variable, the statement is no longer ambigious — it’s now a premise as it evaluates to categorically *false. *The use of this “for all x” is known in logic theory as applying a ** quantifier. **There are two main types of quantifiers. The first, which we’ve just seen, is aptly named the

*there exists an x larger than one hundred*

Once again without removing the variables we’ve found a way to convert a statement into a premise by applying a quantifier as the statement now evaluates strictly to *true*. This second type of quantifier is known as the ** existential quantifier**. Notated by a backwards “E”, ∃, it usually reads as “there exists” or “there is.” Both quantifiers are summarized below:

Now with basic notation out of the way, it’s time to leap to an elementary form of application through truth tables. In the next part, we’ll start by first defining equivalency in logic; in order to use truth tables to analyze which, if any, of the four conditionals we introduced are equal to each other. After inspecting a few example statements, we’ll finally head to the core of logic theory: proofs.

*sources*

Logic: The Theory of Formal Inference

The Foundations of Mathematics