Today we'll discuss basic logic. We'll talk about how you can combine statements that are true or false via a few different logical operators and evaluate the combination is true or false.
This logical discussion lacks a certain degree of subtlety: we assume we have perfect access to knowledge establishing statements as true or false; we're not taking into account a range of uncertainty about a statement or the risks of being wrong. Often these statements are the results of comparisons: 5 > 10 is false; 50 > 10 is true.
Boolean variables are variables that can have only one of two values: true or false. The adjective "boolean" comes from the last name of a 19th-century mathematician; there isn't any deeper meaning buried in the etymology. There are three basic logical operators: \(\land\) (and), \(\lor\) (or), and \(\lnot\) (not).
\(\land\) ("and") evaluates to true if its left and right sides are both true. \(\lor\) ("or" evaluates to true if either its left side or its right side evaluates to true. \(\lnot\) negates the logical value of what follows: if the value is true, \(\lnot\) makes it evaluate to false and vice-versa. In summary,
| Logical expression | Reads as... | Evaluates to true only when... | Written in JavaScript (and many programming languages) as... |
|---|---|---|---|
| \(p \land q\) | "p and q" | p is true and q is true | p && q |
| \(p \lor q\) | "p or q" | either p is true or q is true (or both are true) | p || q |
| \(\lnot p\) | "not p" | p is false | !p |
Truth tables are helpful charts of what a logical expression evaluates to for every variable involved. Here is what the truth tables for and (\(\land\)) , or (\(\lor\)) , and not (\(\lnot\)) look like (0 = false, 1 = true):
| \(p\) | \(q\) | \(p \land q\) | \(p \lor q\) | \(\lnot p\) |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 1 | 1 | 1 | 0 |
Okay, this might need a touch more explanation. Let's read the second-to-last row as an example. This row tells us, from left to right, that when \(p\) is true and \(q\) is false, \(p\) and \(q\) (\(p \land q\)) is false, \(p\) or \(q\) (\(p \lor q\)) is true, and not p (\(\lnot p\)) is false. The other rows can be read the same way.
Note that because this chart has two variables (\(p\) and \(q\)), each of which can take on either of two values (true or false), there are \(2^2 = 4\) rows in our truth table.
Exercise:
Every new variable in a boolean expression doubles the number of rows in our truth table, so our table above with two variables has four rows.
For each row in our truth table, the expression we examine can either evaluate to true or false (2 distinct values). This means that for an expression with \(n\) different variables, our truth table has \(2^n\) rows which can be true or false giving \(2^\left(2^n\right)\) boolean expressions which are different from each other in terms of the set of outputs given for all sets of inputs.
The boolean operators \(\land\), \(\lor\), and \(\lnot\) are all that is needed to make any of these other expressions. For example, if we wanted to fill in a truth table whose outputs looked like
| \(p\) | \(q\) | ??? |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
we could make this happen by replacing ??? with \(\lnot p \lor q\). See if you can fill up the entire two-variable truth table using only \(\land\), \(\lor\), and \(\lnot\) (with parentheses, if it makes life easier). The truth tables we've seen above are filled in below. Hint: there's one more entry given to you from today's Bonus.
| \(p\) | \(q\) | 0 | \(p \land q\) | ??? | \(p\) | ??? | \(q\) | ??? | \(p \lor q\) | ??? | ??? | ??? | ??? | \(\lnot p\) | \(\lnot p \lor q\) | ??? | 1 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
The 0000 and 1111 columns are known as "contradictions" and "tautologies," respectively. The 1001 column is often read "p if and only if q" (abbreviated as "p iff q" (two f's in iff: "p if q" corresponds to column 1101)).
Bonus:
When we evaluate expressions in basic arithmetic, there is an order of operations. We evaluate exponentiation before multiplication, which we evaluate before addition. We can also change the order of operations by using parentheses, so
\[3 \times 4^2 + 2 = 48 + 2 = 50\], but
\[(3 \times 4)^2 + 2 = 144 + 2 = 146\]
To save us from always showing parentheses, logical operators have an order of precedence as well. Just like our arithmetic operators, from highest to lowest precedence, are exponentiation, multiplication, and addition, the order of operations for the logical operations we have seen, from highest to lowest, is negation (\(\lnot\)), then logical conjunction (the official name for "and," \(\land\)), then logical disjunction (the official name for "or," \(\lor\)).
This means we can actually remove the extra parentheses from the expression \((p \land (\lnot q)) \lor ((\lnot p) \land q)\) and it means the exact same thing. In fact, this function is actually kind of interesting. Let's take a look at its truth table:
| \(p\) | \(q\) | \(p \land \lnot q \lor \lnot p \land q\) |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
This expression evaluates to true when either p or q or true, but not both. This expression is known as an "exclusive or" (\lor meaning "inclusive or") or XOR and comes with its own fancy symbol as well: \(\oplus\). This expression could be written as \(p \oplus q\). It's very convenient for us to have this symbol, since having it allows us to write
\[(p \oplus q) \oplus r\]
rather than
\[\lnot p \land \lnot q \land r \lor \lnot p \land q \land \lnot r \lor p \land \lnot q \land \lnot r \lor p \land q \land r\]
by analogy to the above, or, equivalently,
\[\lnot (p \lor q) \land r \lor \lnot (p \lor r) \land q \lor p \land \lnot (q \lor r) \lor p \land q \land r\]
by writing it the way we think about the concept of an "exclusive or." In fact, it turns out that like addition and multiplication, the exclusive or operation is also associative, so we can even drop the parentheses: \(p \oplus q \oplus r\)
I'm dizzy, too. Thank God for \(\oplus\) in times like these.
Here is the truth table for \(p \oplus q \oplus r\):
| \(p\) | \(q\) | \(r\) | \(p \oplus q \oplus r\) |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 |
There's no actual bonus exercise; you're just a trooper for getting through the extra material. Honestly, I tend to get a little carried away when I start using math symbols in my blog. Here's a brainteaser as a reward:
Is the following statement true or false?
"This statement is false."
"This statement is false."
No comments:
Post a Comment