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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
|
# Propositional Logic p1
- Def: A **proposiion** is a declarative sentence that is either true or false (but not both)
- A sentence that declares a fact
- Determine which of the following sentences are propositions:
1. Lebron James plays basketball
- it is declaring something
- it is true
- **it is a proposition** :)
2. All students live in dorms
- it is declaring something
- it is false
- **it is a proposition** :)
3. Where is Carmen?
- it is NOT declaring something
- **it is NOT a proposition** :(
4. Sit down!
- it is NOT declaring something
- **it is NOT a proposition** :(
5. `4 + 5 = 9`
- it is declaring something
- it is true
- **it is a proposition** :)
6. `x + 5 = 9`
- it is declaring something
- **it is NEITHER true or false**
- **it is NOT a proposition** :(
7. `x + 5y = 5y + x; x,y are real`
- it is declaring something
- it is true
- **it is a proposition** :)
- If a proposition is true: write `T`
- If a proposition is false: write `F`
- alternatively, sometimes an upside down 'T' instead
---
# Operators
- List of operators:
- ┓ ([a top right corner](negation.png))
- ^ (carrot)
- ∨ (descending wedge symbol)
- ⊕ ([plus inside a circle](plus_inside_circle.png))
- -> (right arrow)
- <-> (arrow pointed both ways)
- These are all **operators** on propositions
- Propositions involving operators are **compound propositions**
- (e.g. p^q)
- read as *p and q*
## Negation (┓)
- Let `p` be a proposition `┓p` (meaning *not p*)
- This is a **negation**
- This is a **proposition**
- Let `r` = "Lebron James plays basketball"
- `┓r` = "Lebron James does **not play** basketball"
## Introducing Truth Tables
example:
|p|┓p|
|-|--|
|T|F |
|F|T |
when `p` is true, `┓p` is false, and vice versa
## Conjunction (^)
- Let `p` and `q` be propositions
- "p and q" is a proposition called the **conjunction** of `p` and `q`, denoted by `p^q`
- read as "p and q"
### Truth Table
|p|q|p^q|
|-|-|---|
|T|T|T |
|T|F|F |
|F|T|F |
|F|F|F |
`p^q` is only true when both `p` and `q` are true
## Disjunction (∨)
- Let `p` and `q` be propositions
- "p or q" is a proposition called the **disjunction** of `p` and `q`, denoted `p∨q`
- read as "p or q"
### Truth Table
|p|q|p∨q|
|-|-|---|
|T|T|T |
|T|F|T |
|F|T|T |
|F|F|F |
- The disjunction is an **inclusive or**
- Either `p`, or `q`, or both need to be true for `p∨q` to be true
## Exclusive Or (⊕)
- Let `p` and `q` be propositions
- "p exclusive or q" is a proposition called **exclusive or** of `p` and `q` and is denoted `p⊕q`
- read as "p exclusive or q"
### Truth Table
|p|q|p⊕q|
|-|-|---|
|T|T|F |
|T|F|T |
|F|T|T |
|F|F|F |
- One of `p` or `q` need to be true for `p⊕q` to be true, but not both
## "Or" in English
- I can wake up early **or** I can sleep in.
- In English, this is an exclusive or (I can't wake up and sleep at the same time!)
- People with kids **or** pets get less sleep.
- In English, this is an inclusive or (both kids and pets can get less sleep)
## Memory Tip
- `^` looks like an intersection symbol (which means **and**)
- `∨` looks like an union symbol (which means **inclusive or**)
## Implication (->)
- Sometimes called conditional operator
- Let `p` and `q` be propositions
- "If p then q" is a proposition called the **implication** of `p` and `q` and is denoted `p->q`
- read as "if p then q" or sometimes "p implies q"
### Truth Table
|p|q|p->q|
|-|-|----|
|T|T|T |
|T|F|F |
|F|T|T |
|F|F|T |
- Example: "If it is Wednesday, we wear pink"
- `p` is "it is Wednesday" (sometimes called the hypothesis)
- `q` is "we wear pink" (sometimes called the conclusion)
- Only violated (`p->q` is false) if it is Wednesday (`p` is true) and we don't wear pink (`q` is false)
- Implication can be read in many different ways (example `p->q`):
- p implies q
- p only if q
- q when p
- p if sufficient for q
- q is necessary for p
## Biconditional (<->)
- Let `p` and `q` be propositions
- "p if and only if q" is a proposition called the **biconditional** of `p` and `q`, denoted `p<->q`
- read "p if and only if q" or "p iff q"
### Truth Table
|p|q|p<->q|
|-|-|----|
|T|T|T |
|T|F|F |
|F|T|F |
|F|F|T |
- Violated when one is `T` but other if `F`
- Satisfied when either `p` and `q` are both true or both false
- `p<->q` is "equivalent" to `(p->q)^(q->p)`
---
# Propositional Logic p2
- ex: What operator do we do first in `┓p^q<->r`
## Precedence (order of operations)
1. `┓`
2. `^`, `∨`, `⊕`
- "Exclusive or" (`⊕`) is sometimes referred to as "Ex Or" for short
- Need parenthesis to differentiate among these
3. `->`, `<->`
- Need parenthesis to differentiate among these
`┓p^q<->r` means `(┓p^q)<->r`
- ex: `p^q∨r`
- is ambiguous (not sure what to do first) because of lack of parethesis
- ex: Translate the following sentence to logic:
- "You can be Draco's friend **only if** you are in Slytherin **or** you eat floating cupcakes"
- let `d` = "You can be Draco's friend
- let `s` = "You are in Slytherin"
- let `c` = "You eat floating cupcakes"
- `d->s∨c` or `d->(s∨c)`
- Mean the same thing
- Note: "p if q" means `p<-q` (or `q->p`)
- Note: "p only if q" means `p->q`
- Note: "p if and only if q" means `p<->q`
---
[1.3 ->](1.3.md)
|
