Imagine an offer where, for a mere $6.99, you can get:
EEEE, (FFFF or CFCF or
OBOB or HBHB) or CCCC and
PHPH and BRBR and GRGR or
WBWB and PJPJ.
Some fine print clarifies for us that BRBR includes
TT
(WhiWhi, WheWhe, RaRa, or
HbHb), FTFT, HMHM (BbBb,
BaBa, or CaCa), EMEM, BB
with CrChCrCh, BBBB (GRGR from 6-11am).
Unfortunately, it's not clear at all how the
“and” and “or”s relate.
Fundamentally, is “xx and yy or zz”
meant to be interpreted as “(xx and yy) or zz”,
or as “xx and (yy or zz)”?
With some context, we might be able to divine what the author intended:
the above offer is the direct translation from the menu of a
local diner:
2 eggs, potatoes (french fries, cottage fries, O'Brien or hashed
brown) or cottage cheese and peach half (grits before 11am) and
choice of bread with gravy or whipped butter and premium jam.
Bread choices include toast (white, wheat ,raisin or herb), hot flour
tortillas, homemade muffin (blueberry, banana or carrot), English
muffin, bagel with cream cheese, homemade buttermilk
biscuits. Grits available from 6:00am to 11:00am.
(In a brazen display of understatement,
this meal was called “Eggs Alone”.)
Even given context, this offer still isn't necessarily clear to everybody:
can I get both french fries and a peach half?
Happily, coffee is available before having to decipher the menu.
In this example, parentheses would have clarified how we should
interpret “and”, “or”.
But before we discuss how to connect statements,
we will consider the statements themselves.
- Definition 1: proposition
A statement which can be either true or false.
“Your meal will include hashbrowns.”
- Definition 2: propositional variable
A variable that can either be true or false,
representing whether a certain proposition is true or not.
We will often refer to “propositional variables” as just plain
ol' “propositions”, since our purpose in studying logic
is to abstract away from individual statements
and encapsulate them in a single variable,
thereon only studying how to work with the variable.
For a proposition or propositional variable XX,
rather than write “XX is true”,
it is more succinct to simply write “XX”.
Likewise, “XX is false” is indicated as
“¬XX”.
Compare this with Boolean variables in a programming language.
Rather than (x == true)
or (x == false),
it's idiomatic to instead write
x or !x.
Observe that not all English sentences are propositions,
since they aren't true/false issues.
Which of the following do you think might qualify
as propositions?
If not, how might you phrase similar statements that are propositions?
-
“Crocodiles are smaller than Alligators.”
-
“What time is it?”
-
“Pass the salt, please.”
-
“Hopefully, the Rice Owls will win tomorrow's game.”
-
“Mr. Burns is filthy rich.”
-
“Fresca® is the bee's knees.”
When playing WaterWorld, what particular propositions are involved?
To consider this, we think of a generic board, and
wonder what the underlying statements are.
They are statements like
“location AA contains a pirate”
(“A-unsafeA-unsafe”),
“location GG has 2 adjacent pirates”
(“G-has-2G-has-2”)
and so on.
Each of these statements may be true or false,
depending on the particular board in question.
Here are
all the WaterWorld propositions
that we'll use.
Remember that B-unsafeB-unsafe doesn't mean
“I'm not sure whether or not BB is safe”;
rather it means “BB is unsafe” —
it contains a pirate.
You may not be sure whether
(the truth of) this proposition follows what you see,
but in any given board the variable has one of two values, true or false.
Every WaterWorld board has the same set of
propositions to describe it: A-unsafeA-unsafe, B-has-2B-has-2, etc.
However, different boards
will have different underlying values of those propositions.
Some statements in the above proof were simple,
e.g., the single proposition “A-has-2A-has-2”.
Some statements had several parts, though, e.g.,
“(F-unsafeF-unsafe and G-unsafeG-unsafe)”.
We build these more complicated statements out of propositions.
If you know both F-unsafeF-unsafe is false, and G-unsafeG-unsafe is false,
what can you deduce about the truth of the statement
“(F-unsafeF-unsafe and G-unsafeG-unsafe)”?
Clearly, it is also false.
What about when F-unsafeF-unsafe is false, but G-unsafeG-unsafe is true?
What about when both propositions are true?
In fact, we can fill in the following table:
Table 1: Truth table for ∧ (AND)| aa | bb | (a∧b)(a∧b) |
|---|
| false | false | false |
| false | true | false |
| true | false | false |
| true | true | true |
- Definition 3: truth table
A truth table for an expression has a column for each of its
propositional variables.
It has a row for each different true/false combination of
its propositional variables.
It has one more column for the expression itself, showing the
truth of the entire expression for that row.
What do you think the truth table for
“aa or bb” looks like?
Hint: To fill out one row of the table,
say, for
a=truea and
b=falseb , ask yourself
“For this row, is it true that (aa is true, or bb is true)?”
Table 2: Truth table for ∨ (OR)| aa | bb | (a∨b)(a∨b) |
|---|
| false | false | false |
| false | true | true |
| true | false | true |
| true | true | true |
The above proof
also used subexpressions of the form “not bb-unsafe”.
What is the truth table for “not aa”?
Table 3: Truth table for ¬ (NOT)| aa | ¬a¬a |
|---|
| false | true |
| true | false |
What is the truth table for the expression
“(not aa) or bb”?
Table 4: Truth table for ⇒ (IMPLIES)| aa | bb | (a⇒b)(a⇒b) |
|---|
| false | false | true |
| false | true | true |
| true | false | false |
| true | true | true |
- Definition 4: connective
1.
The syntactic operator combining one or more logical expressions into
a larger expression.
Two operators are ∧∧ and ∨∨.
2.
A function with one or more Boolean inputs and a Boolean result.
I.e., the meaning of a syntactic operator.
The meaning of ∧∧ and ∨∨, e.g.,
as described by their truth tables.
nand (mnemonic: “not and”), written ↑↑,
takes in two Boolean values aa and bb,
and returns true exactly when a∧ba b is
not true — that is,
a↑b≡¬(a∧b)
↑ a b
a b
.
The following are the connectives we will use most often.
At least some of these should already be familiar from
Boolean conditional expressions.
Table 5: Connectives
| Connective |
Pronunciation |
Meaning |
Alternative pronunciations / notations |
| ¬¬ |
not |
¬aa:
aa is false |
-aa;
!aa |
| ∧∧ |
and |
a∧b
aa ba and bb are both true |
aa*bb;
abab;
aa&&bb;
aa&bb |
| ∨∨ |
or |
a∨ba b:
at least one of
aba b is true |
aa+bb;
aa||bb;
aa|bb
|
| ⇒⇒ |
implies |
a⇒ba b:
equivalent to
¬a∨bab
|
aa→bb;
aa⊃bb;
if aa then bb;
aa only if bb;
bb if aa;
bb is necessary for aa;
aa is sufficient for bb |
Many other connectives can also be defined.
In fact, it turns out that
any connective for propositional logic can be defined
in terms of those above.
Another connective is if-and-only-if or iff,
written as
a⇔b
⇔
a
b
,
which is true when aa and bb have the same truth value.
So, as its name implies, it can be defined as
(a⇒b)∧(b⇒a)
ab
ba
.
It is also commonly known as
“aa is equivalent to bb” and
“aa is necessary and sufficient for bb”.
Another connective is “exactly-one-of”,
which is more traditionally
called exclusive-or or xor
(since it excludes both aa and bb holding, unlike the
traditional “inclusive” or.)
How would you define aa “xor” bb
in terms of the above connectives?
Exactly one is true if either (aa is true, and bb is false) or
(aa is false, and bb is true). So, one way to define it is
a⊕b≡a∧¬b∨¬a∧b
⊕
a
b
a b
a b
.
The two halves of that formula also correspond to the two true
rows of xor's truth table:
Table 6: Truth table for xor| aa | bb | (a⊕b)(a⊕b) |
|---|
| false | false | false |
| false | true | true |
| true | false | true |
| true | true | false |
Note that the conventional a∨bab
is sometimes called
inclusive-or, to stress that it includes the case
where both aa and bb hold.
In English, the word “or” may sometimes
mean inclusive-or, and other times mean exclusive-or, depending
on context.
Sometimes the term “and/or” is used
to emphasize that the inclusive-or really is intended.
For each of the following English sentences,
does “or”
mean inclusive-or or exclusive-or?
-
“Whether you are tired or lazy,
caffeine is just the drug for you!”
-
“Whether you win a dollar or lose a dollar,
the difference in your net worth will be noticed.”
-
“If you own a house or a car, then
you have to pay property tax.”
-
“Give me your lunch money, or you'll never see your precious
hoppy taw again!”
-
Inclusive.
-
Exclusive.
-
Inclusive.
-
Exclusive (hopefully).
