A formal vocabulary Imagine an offer where, for a mere $6.99, you can get: EE, (FF or CF or OB or HB) or CC and PH and BR and GR or WB and PJ. Some fine print clarifies for us that BR includes T (Whi, Whe, Ra, or Hb), FT, HM (Bb, Ba, or Ca), EM, B with CrCh, BB (GR from 6-11am). Unfortunately, it's not clear at all how the “and” and “or”s relate. Fundamentally, is “x and y or z” meant to be interpreted as “(x and y) or z”, or as “x and (y or z)”? 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. proposition A statement which can be either true or false. “Your meal will include hashbrowns.” propositional variable A variable that can either be true or false, representing whether a certain proposition is true or not. HB 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 X, rather than write “X is true”, it is more succinct to simply write “X”. Likewise, “X is false” is indicated as “X”. 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 statements 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.”

A particular vocabulary for WaterWorld 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 A contains a pirate” (“A-unsafe”), “location G has 2 adjacent pirates” (“G-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-unsafe doesn't mean “I'm not sure whether or not B is safe”; rather it means “B 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, or . Every WaterWorld board has the same set of propositions to describe it: A-unsafe, B-has-2, etc. However, different boards will have different underlying values of those propositions.

Connectives Some statements in the above proof were simple, e.g., the single proposition “A-has-2”. Some statements had several parts, though, e.g., “(F-unsafe and G-unsafe)”. We build these more complicated statements out of propositions. If you know both F-unsafe is false, and G-unsafe is false, what can you deduce about the truth of the statement “(F-unsafe and G-unsafe)”? Clearly, it is also false. What about when F-unsafe is false, but G-unsafe is true? What about when both propositions are true? In fact, we can fill in the following table: Truth table for ∧ (AND) ab(a∧b)

truth table A truth table for an expression has a column for each of its propositional variables. It has a row for each different / 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 “a or b” looks like? Hint: To fill out one row of the table, say, for a and b , ask yourself “For this row, is it true that (a is true, or b is true)?” Truth table for ∨ (OR) ab(a∨b)

The above proof also used subexpressions of the form “not b-unsafe”. What is the truth table for “not a”? Truth table for ¬ (NOT) a¬a

What is the truth table for the expression “(not a) or b”? Truth table for ⇒ (IMPLIES) ab(a⇒b)

connective The syntactic operator combining one or more logical expressions into a larger expression. Two operators are ∧ and ∨. 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 a and b, and returns true exactly when a b is not true — that is, ↑ 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. Connectives Connective Pronunciation Meaning Alternative pronunciations / notations ¬ not a: a is false -a; !a ∧ and a b a and b are both true a*b; ab; a&&b; a&b ∨ or a b: at least one of a b is true a+b; a||b; a|b ⇒ implies a b: equivalent to ab a→b; a⊃b; if a then b; a only if b; b if a; b is necessary for a; a is sufficient for b

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 , which is true when a and b have the same truth value. So, as its name implies, it can be defined as ab ba . It is also commonly known as “a is equivalent to b” and “a is necessary and sufficient for b”. Another connective is “exactly-one-of”, which is more traditionally called exclusive-or or xor (since it excludes both a and b holding, unlike the traditional “inclusive” or.) How would you define a “xor” b in terms of the above connectives? Exactly one is true if either (a is true, and b is false) or (a is false, and b is true). So, one way to define it is ⊕ a b a b a b . The two halves of that formula also correspond to the two true rows of xor's truth table: Truth table for xor ab(a⊕b)

Note that the conventional ab is sometimes called inclusive-or, to stress that it includes the case where both a and b 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).