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 P & Q represent two primitive premises:
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 is a way to make use of variables; the process is called quantifying, a clever way of notating bounds on unknown variables in logic. Take a look at the following, updates statement — is this now a premise?
for all x, x is larger than one hundred
Now that we’ve defined the universe, or 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 universal quantifier. Dictated by an upside down “A”, ∀, it’s easy to remember that it stands for All or every possible instance within the universe of the statement made. Inspect this second alteration:
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
