Eric Chapdelaine
Student at Northeastern University Studying Computer Science.
Notes
Projects
Articles
Resume

Email
GitHub

# Introduction and Fundamentals

## Definitions, Theorems, and Proofs

Mathematical Reasoning: Rigorous math based on logic

Statement: Declarative sentence that has a definite truth value

3 Types of Statements

1. Definition: Gives precise meaning. Always true.
2. Theorem: Have to prove to be true (8 is an even number).
3. Proof: Logical arguments to show a theorem is true

Proposition (more modest than theorem) = result. Another word is fact.

Undefined terms/Axioms: Don’t need to explicit state in proof.

1. Numbers: Integer, Real Number (We will define even, odd, rational, etc.)
2. Operations: Addition, Subtraction, Multiplication, and Division. (We will prove even + even = even)
3. Basic Properties of Arithmetic
4. Ordering of Real Numbers

When in doubt, prove it (or ask).

## Logical Connectives

NOTE:

The rows of a truth table can be determined by $2^{\text{number of compnent statements}}$

### Not

Takes one component statement

Notation: $\sim p$

Truth Table:

$p$ $\sim p$
T F
F T

### And

Conjunction

Takes 2 component statements

Notation: $p \wedge q$

Truth Table:

$p$ $q$ $p \wedge q$
T T T
T F F
F T F
F F F

### Or

Disjunction

Takes 2 component statements

Notation: $p \vee q$

Truth Table:

$p$ $q$ $p \vee q$
T T T
T F T
F T T
F F F

### If then

Conditional statement

Another way to say it is $p$ implies $q$.

• In this case, $p$ is the condition/hypothesis/premise/assumption and $q$ is the conclusion.

Truth Table:

$p$ $q$ $p \rightarrow q$
T T T
T F F
F T T
F F T

Warning:

It doesn’t say anything about the condition when $\sim p$ is true.

$p \rightarrow q$

• Inverse: $\sim p \rightarrow \sim q$
• Converse: $q \rightarrow p$

Note, the inverse and the converse have the same truth table and therefore they are the same.

### if and only if

Also called iff or biconditional

Notation: $p \leftrightarrow q$

• = $(p \rightarrow q) \wedge (q \rightarrow p)$
• = $(p \rightarrow q) \wedge (\sim p \rightarrow \sim q)$

Truth Table:

$p$ $q$ $p \leftrightarrow q$
T T T
T F F
F T F
F F T

NOTE:

All definitions are bidirectional. That is, if a definition has “if … then”, it means “if and only if”.