Normally you would be expected to read sections of the textbook before watching lectures. However, that's a big ask for the first week of classes. So the logic lectures will use a more traditional style where everything is included in the lecture. By somewhere during the second week, we'll stop including basic definitions that you could reasonably be expected to understand from the readings. The lectures will then focus on doing examples and discussing aspects of the topic that are harder or more subtle, which you probably didn't absorb on your first pass through the readings.
There are two main types of logic used in computer science:
In this video, we'll see propositional logic. It's very primitive, and not really up to the job of representing English sentences. So the translations will look very stilted. Its main use is in representing computer circuits. You may also see it some specialized applications within computer science, notably theorem proving and complexity theory.
Predicate logic is an upgrade to propositional logic, to add quantifiers (e.g. "all"). This is the primary language used for representing the foundations of proofs and formal mathematics. Translations between predicate logic and English will still seem somewhat artificial, but this is primarily due to features of natural language that aren't used in mathematics. For example, changes over time are very important in ordinary life, but pure mathematics lives in a static timeless world. With somem effort, beyond the scope of this class, you can add these features to predicate logic.
The lectures this week won't cover all of logic in full detail. You can take entire classes on logic from math or philosophy. We're just covering the basics. Later lectures will return to some of the subtle points, as we need them.
The basic building block for propositional logic is a proposition. By "proposition," we mean a statement that is true or false. So a proposition can be a false statement (e.g. "Chicago is the capital of the US") or one whose truth you don't know (e.g. "Margaret is physically in Illinois right now."). A proposition cannot be
The problem with variables is that we can't determine what value they have, so there is no way to decide whether a statement like "x is larger than 7" is true or false. The upgrade to predicate logic (next video) will also allow us to include variables.
When we are discussing the rules of propositional logic, we will use some variables that refer to whole propositions. E.g. p could stand in for "Obama is president." This is different from a variable that is used inside a proposition.
Predicate logic includes four basic connectives that let you form complex propositions out of simple ones. These are:
"Implies" is often written out as "if/then" in English. So these two propositions mean the same thing, but the second is more fluent and therefore easier to understand.
In an implication (aka if/then statement) "if p, then q", p is called the "hypothesis" and q is the "conclusion."
Shorthand notation is just what the name implies: it's shorter to read and write. It means the same thing as the equivalent words and is not more formal. Much of mathematics is written out in words, because it is intended to be read by other people. But the words have specialized meanings that don't always match how they are used in ordinary English. This is just like how "work" means something much more specific in physics class.
Shorthand is typically used to talk about the overall structure of a complicated expression. This should be familiar from algebra, where arithmetic would be very hard to do if you had to write out each equation in words. The main flow of a proof is typically written out in words, including the logical connectives.
Other connectives can be built out of these basic ones. So mathematicians often use \(\leftrightarrow\) for an implication in both directions, read out as "if and only if". Circuit designers combine "and" and "not" into "nand." These extra connectives are easy to understand if you understand the four basic connectives.
To make the meaning of each connective precise, let's see how the truth value of its output is derived from the truth values of inputs. Since we have only a small number of inputs (1 or 2), we can do this easily with a table. Here are the truth tables for "not" and "and", which are probably what you would have guessed.
|
|
|
The truth table for "or" (below left) is mostly what you'd guess. However, notice the value of the first row: "or" is true if both of its inputs are true. Unless there is explicit indication to the contrary, "or" in mathematics always means this "inclusive" or. The truth table for an "exclusive or" (XOR) is shown below right. This connective has some interesting applications in areas like graphics and cryptography. However, this version of "or" is rarely used in math and will always be explicitly labelled in this class.
|
The counter-intuitive part of the basic connectives is the truth table for implies (if/then).
The first two row are probably what you expected. For example, if we know that the pot has boiled dry and the pot is hot, then it makes sense to say that the first sentence below is true and the second is false.
However, in normal English, we don't normally think about the truth of an if/then statement in which the hypothesis is known to be false. Consider a sentence like "If Chicago is in China, then zombies are attacking the ECE building." This seems too absurd to have a truth value. Or perhaps it's meant to get you thinking about an alternative universe in which Chicago was in China. Either way, most people do not have intuitions about its truth value. In fact, there are non-standard types of logic in which such statements would be neither true nor false. In standard mathematics, an "if/then" statement is true when its hypothesis is false. So "If Chicago is in China, then zombies are attacking the ECE building" is considered to be true. This is a just a convention, but one that will have real consequences when we start applying definitions to special cases involving objects that have zero size (e.g. a list with no elements). And (unlike some details of notation), it is standard across mathematics. So it's important to get used to it. Another problem with this sentence is that there isn't any kind of causal connection between Chicago being in China and zombies attacking the ECE building. In normal English, if/then statements are primarily used when there is some reason why the hypothesis being true should cause the conclusion to be true. Although this is frequently also true in mathematics, it is not required. An if/then statement in propositional logic has a truth value that is determined only by the truth values of the input propositions, even if the statements refer to completely unrelated aspects of mathematics or the real world. A useful way to remember this is to think about when an if/then statement is false. An if/then statement is false only when its hypothesis is true but its conclusion is false. Useful identitiesFrom these basic truth tables, we can prove a number of useful facts about what complex propositions are equivalent to one another. Here is a big table of equivalences. Most of them aren't worth memorizing. Here is one of the exceptions: \(p \rightarrow q \equiv q \vee (\neg p) \) \(\equiv\) is shorthand for "logically equivalent to," i.e. has the same truth value. Notice that we use 3-bar equals to compare two propositions, rather than the 2-bar equals sign used to compare two numbers. We can use a truth table to prove that the two sides are equivalent:
The identity \(p \rightarrow q \equiv q \vee (\neg p) \) is somewhat counter-intuitive because the meaning of the implies operator is somewhat counter-intuitive. However, this identity is used a lot and well worth memorizing. Similarly, we can use a truth table to show one of the DeMorgan's laws: \(\neg(p \wedge q) \equiv (\neg p) \vee (\neg q)\)
Truth tables are tedious to build, but a very effective way to show that simple equivalences hold. |