blob: 86af4e48c04cae4bd7ae99e2ceff2a243dc814f5 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
|
[\<- 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)
|
