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:

  \(p\)	\(\neg p\)
  \(\mathrm{T}\)	\(\mathrm{F}\)
  \(\mathrm{F}\)	\(\mathrm{T}\)

• 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:

    \(p\)	\(q\)	\(p\wedge q\)
    \(\mathrm{T}\)	\(\mathrm{T}\)	\(\mathrm{T}\)
    \(\mathrm{T}\)	\(\mathrm{F}\)	\(\mathrm{F}\)
    \(\mathrm{F}\)	\(\mathrm{T}\)	\(\mathrm{F}\)
    \(\mathrm{F}\)	\(\mathrm{F}\)	\(\mathrm{F}\)

• 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:

    \(p\)	\(q\)	\(p\vee q\)
    \(\mathrm{T}\)	\(\mathrm{T}\)	\(\mathrm{T}\)
    \(\mathrm{T}\)	\(\mathrm{F}\)	\(\mathrm{T}\)
    \(\mathrm{F}\)	\(\mathrm{T}\)	\(\mathrm{T}\)
    \(\mathrm{F}\)	\(\mathrm{F}\)	\(\mathrm{F}\)

• 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.

  \(p\)	The store is open today.
  \(q\)	Mary is going to the store today.
  \(r\)	John is going to the store today.

  • “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.”
• Answers:
  • \(q \vee r\)
  • \(r \wedge \neg q\)
  • \(p \wedge (q \vee r)\)
• Some notes about that:
  • 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.

    \(p\)	\(q\)	\(p\oplus q\)
    \(\mathrm{T}\)	\(\mathrm{T}\)	\(\mathrm{F}\)
    \(\mathrm{T}\)	\(\mathrm{F}\)	\(\mathrm{T}\)
    \(\mathrm{F}\)	\(\mathrm{T}\)	\(\mathrm{T}\)
    \(\mathrm{F}\)	\(\mathrm{F}\)	\(\mathrm{F}\)

• We actually could have expressed “exclusive or” with the operators we had:

  \(p\)	\(q\)	\(p\vee q\)	\(\neg(p\wedge q)\)	\((p\vee q) \wedge \neg(p\wedge q)\)	\(p\oplus q\)
  \(\mathrm{T}\)	\(\mathrm{T}\)	\(\mathrm{T}\)	\(\mathrm{F}\)	\(\mathrm{F}\)	\(\mathrm{F}\)
  \(\mathrm{T}\)	\(\mathrm{F}\)	\(\mathrm{T}\)	\(\mathrm{T}\)	\(\mathrm{T}\)	\(\mathrm{T}\)
  \(\mathrm{F}\)	\(\mathrm{T}\)	\(\mathrm{T}\)	\(\mathrm{T}\)	\(\mathrm{T}\)	\(\mathrm{T}\)
  \(\mathrm{F}\)	\(\mathrm{F}\)	\(\mathrm{F}\)	\(\mathrm{T}\)	\(\mathrm{F}\)	\(\mathrm{F}\)

  • 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\).”

    \(p\)	\(q\)	\(p\rightarrow q\)
    \(\mathrm{T}\)	\(\mathrm{T}\)	\(\mathrm{T}\)
    \(\mathrm{T}\)	\(\mathrm{F}\)	\(\mathrm{F}\)
    \(\mathrm{F}\)	\(\mathrm{T}\)	\(\mathrm{T}\)
    \(\mathrm{F}\)	\(\mathrm{F}\)	\(\mathrm{T}\)

  • 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:

    \(p\)	\(q\)	\(p\rightarrow q\)	\(\neg q\rightarrow \neg p\)
    \(\mathrm{T}\)	\(\mathrm{T}\)	\(\mathrm{T}\)	\(\mathrm{T}\)
    \(\mathrm{T}\)	\(\mathrm{F}\)	\(\mathrm{F}\)	\(\mathrm{F}\)
    \(\mathrm{F}\)	\(\mathrm{T}\)	\(\mathrm{T}\)	\(\mathrm{T}\)
    \(\mathrm{F}\)	\(\mathrm{F}\)	\(\mathrm{T}\)	\(\mathrm{T}\)

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.”

    \(p\)	\(q\)	\(p\rightarrow q\)	\(q\rightarrow p\)	\((p\rightarrow q) \wedge (q \rightarrow p) = p\leftrightarrow q \)
    \(\mathrm{T}\)	\(\mathrm{T}\)	\(\mathrm{T}\)	\(\mathrm{T}\)	\(\mathrm{T}\)
    \(\mathrm{T}\)	\(\mathrm{F}\)	\(\mathrm{F}\)	\(\mathrm{T}\)	\(\mathrm{F}\)
    \(\mathrm{F}\)	\(\mathrm{T}\)	\(\mathrm{T}\)	\(\mathrm{F}\)	\(\mathrm{F}\)
    \(\mathrm{F}\)	\(\mathrm{F}\)	\(\mathrm{T}\)	\(\mathrm{T}\)	\(\mathrm{T}\)

• 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.
  • I will ask questions about this, but will try to not play too many word games.
• 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?