# Propositions

• We know what sentences are (I hope):
1. John is going to the store.
2. That guy is going to the store.
3. John, go to the store.
4. Did John go to the store?
• Declarative sentences are propositions.
• i.e. Sentences that assert a fact that could either be true or false.
• i.e. Something you could make into a question with “对不对？”.
• Of the above, only (1) is a proposition as it is: we need all the details.
• (2) would be a proposition if we knew who “that guy” is.
• Not all sentences are propositions
• Above, (3) is a command: it's not true or false.
• (4) is a question, so definitely not a statement.
• Of course, this has something to do with mathematics.
• There are statements in math like “$$10 - 4 = 6$$” and “$$1+1=3$$”.
• One of those is true and one is false, but they are both propositions. (If you don't know which is which, you're in trouble.)
• Of course math has variables.
• In our propositions, they will be like “that guy” in the above examples.
• … if we know their value, we can decide if the proposition is true or false.
• e.g. $x+7=3\\x+y=0$
• In those examples, $$x$$ and $$y$$ probably stand for numbers.
• We also need variables to represent propositions: propositional variables.
• Typically use letters $$p,q,r,s,\ldots$$ for propositional variables.
• e.g. For a proposition $$p$$, we can ask if $$p$$ is true or false.
• When writing math, we'll write $$\mathrm{T}$$ and $$\mathrm{F}$$ instead true and false.
• What we're studying now is propositional logic: the study of these propositions and how they can be logically combined.

# Logic Basics

• A proposition can be negated.
• That is, if $$p$$ is true, its negation is false; if $$p$$ is false, its negation is true.
• [That sentence sucked: let's think of a better way to say those things.]
• Some examples with natural language statements:
• e.g. in English: the negation of “John is going to the store.” is “John is not going to the store.”
• e.g. in Chinese: the negation of “我去商店。” is “我不去商店。
• Some are less easy to negate: “I will not go to the store any day this week.” is negated to “I will go to the store some day this week.”
• Problem: natural languages (like English, Chinese) are imprecise and messy, so are hard to work with this way.
• Solution: better notation.
• We'll write “$$\neg p$$” for the negation of $$p$$.
• So we could say things like: “if $$p$$ is the proposition ‘$$2+2=4$$’, then its negation is $$\neg p$$, ‘$$2+2\ne 4$$’.”
• “$$\neg p$$” is itself a proposition: the “$$\neg$$” takes a proposition and makes a new one.
• Describing “if $$p$$ is true, its negation is false, …” was awkward.
• We will use a truth table to give all of the true/false values for predicates.
• Here is a truth table for negation:
• When writing a truth table, we have to list all of the possible combinations of values for the propositions ($$p$$, $$q$$, …) in it.
• Since “$$\neg p$$” contains only “$$p$$”, there are only two rows.
• Negation is the first way we have to manipulate propositions.
• We will need others.
• When propositions are manipulated to make another proposition, we call the result a compound proposition.
• Conjunction is a way to combine two propositions.
• The conjunction of $$p$$ and $$q$$ is written $$p\wedge q$$.
• $$p\wedge q$$ is true if both $$p$$ and $$q$$ are true.
• In other words, $$\wedge$$ means “and”.
• In a truth table:
• Notice that we got every possible combination of values for “$$p$$” and “$$q$$” in the truth table.
• Disjunction is another way to combine two propositions.
• The disjunction of $$p$$ and $$q$$ is written $$p\vee q$$.
• $$p\vee q$$ is true if $$p$$ is true, or $$q$$ is true, or both are true.
• In other words, $$\vee$$ means “or”.
• In a truth table:
• Notice the “both are true” case.
• This might not be a direct translation of “or”.
• “I have either an apple or an orange.” If I have both, is that true?
• 我有苹果或者橘子。” and “你要苹果还是橘子？” What if you have/want both? Also strange in Chinese?
• Even if we pronounce $$\vee$$ as “or”, remember that it's not always the same as the word.
• Either one or both are true → the disjunction is true.
• It's an “inclusive or” if you want to say it that way.

# Using Logical Operators

• Let's define propositions and translate some sentences into the logical notation.
• “Either John or Mary (or both) are going to the store today.”
• “John is going to the store today, but Mary isn't.”
• “The store is open today, and either John or Mary is going.”
• $$q \vee r$$
• $$r \wedge \neg q$$
• $$p \wedge (q \vee r)$$
• Sometimes the logic of a sentence is obvious, but sometimes it takes some thought to unwrap it.
• That's one of the reasons to have this notation: meaning is always clearly defined, unlike natural language sentences.
• The word “but” is logically the same as “and”. It just implies that the following part is a little surprising.
• Whether “or” includes “or both” can be ambiguous. We'll usually assume “or” translates to $$\vee$$, but it depends on the context.
• We can use parentheses to group parts together, just like in arithmetic.
• Some sentences we can't (easily) translate yet:
• “If the store is open today, then John will go.”
• “Either John or Mary (but not both) are going to the store today.”
• It would be nice to have notation for that…

# Exclusive Or

• The $$\vee$$ means “one or the other or both”: inclusive or.
• The “but not both” version is exclusive or.
• “Exclusive or” is written $$\oplus$$ and sometimes pronounced “xor”.
• $$p\oplus q$$ is true if $$p$$ is true, or $$q$$ is true, but not both.
• We actually could have expressed “exclusive or” with the operators we had:
• The last two columns are the same.
• So, we can say that the two are equivalent, and write $p\oplus q \equiv (p\vee q) \wedge \neg(p\wedge q)\,.$
• … but $$\oplus$$ is easier to write if we need it often.

# Conditionals

• The other sentence we couldn't easily translate before: “If the store is open today, then John will go.”
• That's a conditional statement or an implication.
• i.e. it expresses “If (something is true), then (something else).”
• We will write $$p\rightarrow q$$ for the conditional “If $$p$$ then $$q$$.”
• In this conditional, the thing before the $$\rightarrow$$ ($$p$$ in the example) is called the antecedent, premise, or hypothesis. The thing after the $$\rightarrow$$ ($$q$$ in the example) is called the conclusion or consequence.
• Like with “or”, one of the entries there might not match your expectations from English.
• Statements like “If the moon is larger than the earth, then all food is red.” are perfectly true: the premise is false, so the whole statement is true.
• It's easy to have conditionals like that one that don't make sense (when said in natural language) but are true.
• There are a lot of things in English (and probably Chinese) that translate into a conditional statement.
• Like “and” and “but”, they are logically equivalent but may have some subtle meaning when said.
• Examples of $$p\rightarrow q$$: “if $$p$$ then $$q$$”; “$$q$$ whenever $$p$$”; “$$p$$ implies $$q$$”; “$$q$$ follows from $$p$$”; “$$q$$ only if $$p$$”.
• We could also have written $$p\rightarrow q$$ using only $$\vee$$, $$\wedge$$, and $$\neg$$.
• Draw a truth table for $$\neg p \vee q$$ if you don't believe me.
• For a conditional proposition $$p\rightarrow q$$…
• $$q\rightarrow p$$ is its converse.
• $$\neg p\rightarrow \neg q$$ is its inverse.
• $$\neg q\rightarrow \neg p$$ is its contrapositive.
• A conditional statement and its contrapositive are equivalent.
• Not obvious, but:

# Bi-Conditionals

• A biconditional statement is written $$p\leftrightarrow q$$ and is the same as $$(p\rightarrow q) \wedge (q \rightarrow p)$$
• So, “if $$p$$ is true, then $$q$$ is true and if $$q$$ is true, then $$p$$ is true.”
• Or more simply: “$$p$$ and $$q$$ are the same.”
• There aren't many natural English sentences that translate to a biconditional, but mathematicians love them.
• When doing mathematical proofs (as we will later), you often end up needing to express “this thing is true under exactly the same conditions as that thing”, which is really $$p\leftrightarrow q$$.
• That usually gets written “if and only if”.
• For example, “I will give the next lecture if and only if I am not sick.”
• “$$\leftrightarrow$$” is usually pronounced “if and only if”.
• And sometimes “if and only if” is shortened to “iff” when it's written a lot.

# Translating Into Logic

• It is often necessary to translate a natural language (English, Chinese, …) sentence into logical notation.
• Makes it easier to do logical manipulations, makes sure you know the real meaning without any of the missing/hidden details of natural languages.
• Usually “not”, “and” and “or” are fairly obvious.
• … as long as you're careful about whether the “or” is $$\vee$$ or $$\oplus$$. Usually $$\vee$$.
• Biconditionals are rare.
• Usually just “if and only if”.
• Occasionally “is necessary and sufficient for” or some other weird language constructs.
• That leaves conditionals ($$\rightarrow$$) as the difficult one.
• It can appear in unexpected places.
• Consider “Only ZJU students can access the campus network.”
• Use $$s$$ for “is a ZJU student” and $$n$$ for “can access the campus network”.
• Two possible translations: $$s\rightarrow n$$ and $$n\rightarrow s$$.
• Which is right?
• My usual first thought is $$s\rightarrow n$$.
• That is literally “If you are a ZJU student, then you can access the network.”
• Or maybe “All ZJU students can access the network.”
• That's not what the original statement said.
• Consider a student that has been banned from the network.
• The correct translation is $$n\rightarrow s$$.
• “If you can access the network, then you are a ZJU student.”
• In other words, if you find someone and they can access the network, you know they are a ZJU student.
• That does match “Only ZJU students can access the campus network.”
• But when people say “If… then…” sentences, they often really mean the converse (or something).
• Be cafeful when translating to logic.
• In this course, I'll be careful to say what I mean.
• More examples with $$d$$: you are in the dual degree program, $$f$$: you are in first year, $$c$$: you are in this course.
• “If you are in the dual degree program, then you are either not in first year, or are in this course.”
• “You are in the dual degree program and in first year.”
• “Students must be in the dual degree program to register in this course.”
• “Anyone who is in the dual degree program and in first year is in this course.”
• “Can all first year students register in this course?”
• Translations?