Script Chapter 2

2.1 Mathematical Statements

1. What is a statement?
2. What does the symbol $\Longrightarrow$ mean and when is $S \Longrightarrow T$ true?

2.2 The Concept of a Proof

1. When do we use $\dot{\Longrightarrow}$ instead of $\Longrightarrow$?
2. Describe (informally) what a proof is.
3. What is the difference between a proof sketch and a formal proof?

2.3 Propositional Logic

1. Explain the symbols $\lnot, \land, \lor, \rightarrow, \leftrightarrow$.
2. What is a truth table? Can you sketch the truth tables for the symbols above?
3. How did we define a formula? What symbols are allowed to appear in a formula? Can you think of an arrow we saw that is not allowed to appear in a formula?
4. What does it mean for two formulas to be equivalent? What is the symbol for it?
5. Lemma 2.1 is important. Can you name and write down all the eight rules? Where did you shee similar rules before?
6. What does the symbol $\models$ mean? Is $A \models B$ a statement or a formula? Can you define $\equiv$ using $\models$?
7. What makes a formula (un)satisfiable and what is a tautology? What is the connection between $F$, $\lnot F$ and these terms?
8. Fill in the blanks with formula or statement:

• “____ $\rightarrow$ ____” is a ____
• “____ $\Rightarrow$ ____” is a ____
• “____ $\models$ ____” is a ____

2.4 Predicate Logic

1. Give an example of a predicate.
2. Recall the definitions of $\forall x P(x)$ and $\exists x P(x)$. What else needs to be specified apart from $P$?
3. Using both $\forall$ and $\exists$ at least once and two different predicates $P$ and $Q$, construct a formula which is true for $U = \mathbb{N}$.
4. Read through 2.4.8 again and do the exercise if you have not already. Then take a sheet of paper and try to write down all the rules you remember from that section.

2.6 Proof Patterns

1. Explain how an indirect proof works.
2. What is a Modus Ponens? Can you show with propositional logic why it works?
3. What steps does a proof by case distinction involve?
4. Show with propositional logic why a proof by contradiction works. How do you use this proof technique in prectice?
5. Explain intuitively and in your own words to yourself what a proof by induction is and why it works.
6. What is the pigeonhole principle?