[\<- 1.1](1.1.md)

---

# 1.3 Propositional Equivalences p1

- Definition: We say propositinos `p` and `q` are **logically equivalent** if they have the **same truth table outputs**
	- Notated as `p≡q` (three lign equal sign)
	- kind of similar to `<->`

- Defining terms using the conditional `p->q`
	- **Converse**: `q->p` (if q, then p)
	- **Inverse**: `┓p->┓q`
	- **Contrapositive**: `┓q->┓p` (if not q, then not p)
	- The original conditional and the contrapositive are equivalent
		- So are the converse and the inverse
	- Why is `p->q≡┓q->┓p`
Reason 1: Truth Table

|p|q|p->q|┓p|┓q|┓q->┓p|
|-|-|----|--|--|------|
|T|T|T   |F |F |T
|T|F|F   |T |F |F
|F|T|T   |F |T |T
|F|F|T   |T |T |T

- Since their truth table outputs are the same, these two statements are the same

Reason 2: Logic/Venn Diagram

- `p->q` -> "If we are in p, then we are in q"
- `┓q->┓p` -> "If we are not in q, then we are not in p"
- Both these statements describe the same venn diagram

---

- Ex: Show `(p->q)^(q->p)≡p<->q

Truth Table:

|p|q|p->q|q->p|(p->q)^(q->p)|p<->q|
|-|-|----|----|-------------|-----|
|T|T|T   |T   |T            |T    |
|T|F|F   |T   |F            |F    |
|F|T|T   |F   |F            |F    |
|F|F|T   |T   |T            |T    |

- The output is logically equivalent since their truth table outputs are the same

- Ex: Fill in the blank:  ┓(I'm tall and I have black hair) ≡ I'm not tall _____ I don't have black hair
	- The negation is saying, "it is not the case that..."
	- The correct answer is `∨` (or)
	
- Now use a truth table to show `┓(p^q)≡┓p∨┓q`

Truth Table:

|p|q|┓(p^q)|┓p∨┓q|
|-|-|------|-----|
|T|T|F     |F    |
|T|F|T     |T    |
|F|T|T     |T    |
|F|F|T     |T    |

- This example is true because of DeMorgan's Law

- Ex: Use a truth table to show that `p->q≡┓p∨q`

Truth Table:

|p|q|p->q|┓p∨q|
|-|-|----|----|
|T|T|T   |T   |
|T|F|F   |F   |
|F|T|T   |T   |
|F|F|T   |T   |

---

# 1.3 Propositional Equivalences p2

## Definitions
- A proposition that is **always true** is a **tautology**
	- (tautology≡`T`)
	- e.g. `p∨┓p≡T`

- A proposition that is **always false** is a **contradiction**
	- (contradiction≡`F`)
	- e.g. `p^┓p≡F`

- A proposition that can be **true or false** is a **contingency**

[Table of Common Equivalences](1.3.pdf)

### Ways to show p≡q

1. Truth Tables
2. Show `p<->q` is a tautology (multiple options)
	- with a truth table
	- by (3)
3. Use table of Common Equivalences (see link above)

---

# Using the Table of Common Equivalences

- Ex. Show `(p^q)->(p->q)` is a tautology without a truth table
	- We are goint to solve this using a proof
	- **Goal**: `(p^q)->(p->q)≡T`

|Proof: (p^q)->(p->q)|Reason|
|--------------------|------|
|≡(p^q)->(┓p∨q)      |Implication|
|≡┓(p^q)∨(┓p∨q)      |Implication|
|≡(┓p∨┓q)∨(┓p∨q)     |De Morgan|
|≡┓p∨(┓q∨(┓p∨q))     |Associative|
|≡┓p∨(┓q∨(q∨┓p))     |Commutative|
|≡┓p∨((┓q∨q)∨┓p))    |Associative|
|≡┓p∨(T∨┓p))         |Negation|
|≡┓p∨T               |Domination|
|≡T                  |Domination|

- Why use this method?
	- This method is useful for compound propositions with many propositions

- `n` propositions -> truth table has 2^n rows
	- e.g 5 propositions -> truth table has 32 rows (!)

---

[1.4 ->](1.4.md)