Intro

Logic is something that comes up again and again – not only in daily life, but on the job as well. That’s because logic, by definition, is a language you can use to reason about stuff. And you reason about stuff everywhere: picking your favorite drink in a coffee shop, negotiating your internet bill with your ISP, reasoning about the behavior of an engineering system, etc. Logic is one of the super powers that up-levels you as a human. You can use it to defend your arguments. You can also use it to prove yourself wrong.

The roots of logic are in philosophy and math. Here, I won’t go over the history, but I just plan to list out the tools that I have picked along the way that have helped me reason and think. I believe that all of us should strive to be more objective and logical in our reasoning – it is really helpful when you think on our own.

For a more formal introduction of logical literacy, read Matt Might’s excellent post on logic.

Definition

For me, logic is a language to reason. Formally, you can use it to “read a theorem” or “prove a statement”. I won’t go all formal here, and will try to keep it light on math, but will instead use practical examples to describe what I mean. However, like with any topic, it helps if you learn the basic building blocks first, and then slowly build from the fundamentals. In the context of logic, this would mean knowing the terms used in logical reasoning, and what they mean. So let’s cover those first.

Building blocks

Statement

A sentence that can be either true or false.

Examples: “The color of a tennis ball is green.", or “1 + 1 = 2”.

To determine if a statement is true or false is actually very tricky. Typically, there are two types of statements:

• Facts. These are statements for which truth or false is well agreed upon.
• Logically derived statements. These are statements that we found out were true or false based on our thinking and logical tools.

A statement is also sometimes referred to as propositions.

Some statements are also conditional. That is, them being true or false depends on something else.

Example: “You will get an A if you score at least 81 in tomorrow’s exam.”

Formally, this is sometimes called a predicate, which is a statement whose value of true or false depends on the value of its variables. In programming, people generally use the term “predicate filter”, which can be thought of as a function which filters its input based on some conditions.

Assertion

Assertion is judgement of a statement. In programming, it is typically used in testing to verify expected behavior. It is is also sometimes used to enforce invariants in the system.

Argument, Premise, Conclusion

Argument is a set of statements that starts from a set of premises, and ends with a conclusion. Premises are statements in the argument that are assumed to be true for the sake of the argument. Conclusion is then formed on the basis of the premises. The whole process is called an argument.

Example of an argument:

• “We will not hike tomorrow if it rains or if it is too hot.” <– premise
• “The weather tomorrow will be sunny and hot.” <– premise
• “We will not hike tomorrow.” <– conclusion

Arguments can be valid, invalid, sound, etc. To read more about these and fallacies, check out these lecture notes on reasoning.

Infer and imply

To infer means to conclude something from evidence and reasoning.

Example: “I inferred from your reaction yesterday that you were not happy.”

Infer is about receiving information.

A similar term, imply, is about giving information. Imply means to suggest the truth or false of something based on evidence and reasoning.

Example: “The heavy clouds today imply that it can rain today.”

Imply is about suggesting, and is generally seen from the point of view of someone giving information. Infer is about concluding, and is generally seen from the point of view of someone receiving information.

More examples here.

Induction and deduction

Induction and deduction are two types of reasoning or in other words, two types to solve a problem.

The main difference between them is that induction starts from observations while deduction starts from a theory – the image below taken from here describe this:

Theorem

Theorem is a conclusion statement based on deduction from other statements (that are proven to be true or false). These other statements that form a basis of the theorem are similar to what a premise is for an argument. Formally, they are sometimes called axioms. I think of these as assumptions you make in your theorem. I am using the word “assumption” loosely here – typically, these axioms are proven in a well reasoned way, and form a starting point to build a theorem upon.

Generally, you prove a theorem to be true. Or you disprove a theorem to be false. More about this here.

Lemma

There are countless ways (formal and creative) to prove theorems. I will discuss them in a later section. But to prove a theorem, you can use lemmas as building blocks. A lemma is a true statement used in proving other true statements. In other words, it’s a sub theorem meant to prove the overall theorem.

Corollary

Corollary is a true statement that is deduced from another theorem or proposition. Think of this as a transformation on an existing theorem.

Hypothesis and Conjecture

A hypothesis is a proposed explanation made on the basis of limited evidence. In other words, it is an “educated guess”.

Example: “Our hypothesis is that the bulk job caused disk thrashing, which caused too many application threads to wait on disk I/O, thereby resulting in high CPU usage, and eventually causing the node to go down.”

Hypothesis are made all the time in science (experiments) and day to day engineering. Typically, someone will “verify” the hypothesis and move towards to a final conclusion.

A similar term, theory is also used interchangeably but actually it means something slightly different. Taken from here:

A hypothesis proposes a tentative explanation or prediction. A scientist bases their hypothesis on a specific observed event, making an educated guess as to how or why that event occurs. Their hypothesis may be proven true or false by testing and experimentation. A theory, on the other hand, is a substantiated explanation for an occurrence. Theories rely on tested and verified data, and scientists widely accepted theories to be true, though not unimpeachable.

A similar term, conjecture, is statement that is “believed” to be true, but for which we have no proof. From here:

Hypothesis is testable, and explanation is based on accepted grounds. Conjecture is proposition based on inconclusive grounds, and sometimes can not be fully tested.

Implication

To connect different statements, a very useful building block is implication, which in sentences, forms a “if then ” kind of pattern:

“If it rains, then I will take an umbrella.”

Here raining imply that I will take an umbrella. Interestingly, not all statements are true in the reverse order. Take this false statement:

“If I take an umbrella, then it will rain.”

Mathematically, the symbol for imply is \(\implies\). Let’s say you have two statements: \(P\) and \(Q\). \(P \implies Q\) is saying that if \(P\) is true, then \(Q\) is true. It is not saying that if \(Q\) is true, then \(P\) is true. We can also say that \(P\) is necessary and sufficient for \(Q\).

Interestingly, \((P \implies Q)\) \(\implies\) \((not \space Q \implies not \space P)\). From our last example, we can deduce this true statement:

“If I do not take an umbrella, then it means it did not rain.".

In addition to forwards implication, there is also “bidirectional implication” or “if and only if (iff)” – the symbol for which is \(\iff\). \(P \iff Q\) means that \(P\) is true when \(Q\) is true, and \(Q\) is true when \(P\) is true.

A programming example from the Linux kernel:

1
2
3
4
5

/* Return true if and only if the ARMv6 unaligned access model is in use. */
static bool cpu_is_v6_unaligned(void)
{
	return cpu_architecture() >= CPU_ARCH_ARMv6 && get_cr() & CR_U;
}

This code is saying the obvious thing: if the unaligned access model is in use, then this functions returns true. But it’s also saying that: if the function returned true, then it means that the unaligned access model must be in use at the time it was called. A lot of times, programming function documentation can use a stricter “iff” rather than a one way “if”.

Proof techniques

In the sections below, instead of writing about proof techniques myself, I have just referenced proof techniques that I found useful.

Formal

Creative (pictures)

Pictures and visualizations sometimes can do wonders when it’s hard to express something in words. See this proof without words thread for a lot of interesting examples.

One example is the proof for \(1+2+\cdots + (n-1) = \binom{n}{2}\):

How not to prove

A light-hearted list of techniques you should not use for your proofs. Ironically, proof by pictures makes the list here. For mathematical rigor, maybe proof by pictures does not count but I find them pretty useful since visualizations help me think.