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
|
[\<- 1.3](1.3.md)
---
# 1.4 Predicates and Quantifiers p1
## Propositional Functions
- Ex. Note "w < 5" and "x^2 + y^2 = z^2" are not propositions since a proposition is either true or false, but not both.
- The problem is they could be true or false depending on what the variables are
- Let P(w) be "w < 5"
- Once we specify a value for "w", this becomes a proposition
- E.g. P(3) -> 3<5 -> `P(3)≡T`
- E.g. P(6) -> 6<5 -> `P(6)≡F`
- We call P(w) a **propositional function**
- Ex. Let R(x,y,z) be the propositional function "x^2 + y^2 = z^2". Evaluate the truth values of R(1,2,3) and R(3,4,5)
- R(1,2,3) -> 1 + 4 = 9 -> `R(1,2,3)≡F`
- R(3,4,5) -> 9 + 16 = 25 -> `R(3,4,5)≡T`
---
## Quantifiers
- The proposition "for all (for every) x in the domain, P(x) is true" is denoted `∀x P(x)`
- `∀x P(x)` is read "for all x P(x) is true
- `∀` = "for all" and is called the universal quantifier
- Ex. Let P(x) be "x^2 >= 0" and Q(x) be "x^2 > 0". If the domain is all reals, evalueate the truth values of the propositions
- (a) `∀x P(x)`
- `∀x P(x) ≡ T`
- (b) `∀x Q(x)`
- `∀x Q(x) ≡ F` since "x^2 >= 0" is *not* true when x=0.
- Note: If there is even one value of x where Q(x) is false, then `∀x Q(x) ≡ F`
- Ex. Let L(x) be "x > 8" with domain {10, 11, 12}. Then,
- `∀x L(x) ≡ L(10) ^ L(11) ^ L(12) ≡ T`
- For a **finite domain**, we can rewrite `∀x L(x)` as a **conjunction**
---
- The proposition "there exists (there is) an x in the domain such that P(x) is true" is denoted by `Ǝx P(x)`
- `Ǝ` is read "there exists" and is called the existential quantifier
- To review:
- `Ǝx` means "there's at least one x in the domain..."
- `∀x` means "for all x in the domain, ..."
- Ex. Let M(x) be "2x + 3 = 29". Evaluate the truth value of `Ǝx M(x)` if the domain is
- (a) {10,11,12}
- `Ǝx M(x) ≡ M(10) ∨ M(11) ∨ M(12)`
- `M(10) ≡ F`
- `M(11) ≡ F`
- `M(12) ≡ F`
- Therefore, `Ǝx M(x) ≡ F`
- (b) Integers
- `Ǝx M(x) ≡ T` since x=13 makes M(x) true
- For a **finite** domain, we can write `Ǝx M(x)` as **disjunction** (or statement)
---
# 1.4 Predicates and Quantifiers p2
- The propositional function "there exists a **unique** x in the domain such that P(x) is true" is denoted by `Ǝ!x P(x)`
- The "!" means "unique"
- Ex. Let the domain of x be the reals. Let T(x) be "x^3 - 4 = 0" and S(x) be "x^2 = 4x". Evaluate the truth value of
- (a) `Ǝ!x T(x)`
- `Ǝ!x T(x) ≡ T` since x = 4^(1/3) is the **only** value that works
- (b) `Ǝ!x S(x)`
- How to apporach this problem:
- **Incorrect** dividing both sides by x (you get x=4) causes you to lose solutions
- **Correct** move everything to one side and factor (you get x(x-4)=0)
- `Ǝ!x S(x) ≡ F` since both x=0 and x=4 work (there is more than one x that works)
### Two ways to turn Propositional Function, R(x), into a Proposition
1. Assign a value to x
2. Put a quantifier in front of it
### Precedence
1. `∀`, `Ǝ`, `Ǝ!`
2. `┓`
3. `^`, `∨`, `⊕`
4. `->`, `<->`
- Ex. `∀x P(x) -> q`
- means `(∀x P(x)) -> q`
---
## Scope
- `T(x) -> r` is a propositional function
- T(x) and r are each propositions for which we do not know the truth values
- `(∀x T(x)) -> r` is a proposition
- **scope** of ∀x is T(x) (clarified by parenthesis)
- `∀x (T(x) -> r)` is a proposition
- **scope** of ∀x is `T(x)->r`
Takeaway: If there's a variable not in the scope of a quantifier, it's**not** a proposition
### Convert English into Logical Statements
- Ex. What is the negation of "all dogs bark"? Write in words and logical symbols (2 ways)
- Let B(x) be "x barks" and the domain of x is dogs
|Words|Symbols|
|-----|-------|
|All dogs bark|∀x B(x)|
|Not all dogs bark|┓∀x B(x)|
|There is at least one dog who doesn't bark|Ǝx ┓B(x)|
Takeaway:
- `┓∀x B(x) ≡ Ǝx ┓B(x)`
- `Ǝx ┓B(x) ≡ ∀x ┓B(x)`
- "It's not the case that there is a dog that barks" means the same as "No dogs bark"
---
- Ex. Convert the following sentences into logical statements
1. "There is a woman with a PhD and an MD"
- Let P(x) be "x has a PhD" and the domain of x is women
- Let M(x) be "x has an MD" and the domain of x is women
- `Ǝx (P(x) ^ M(x))`
2. "There is exactly one woman with a PhD and MD"
- Use the setup from the previous sentence
- `Ǝ!x (P(x) ^ M(x))`
3. "No one has seen an alien"
- Think about it: "No one" is the opposite of "at least one"
- Let A(x) be "x has seen an alien" where the domain of x is people
- `┓Ǝx A(x)` simplified to `∀x ┓A(x)`
4. "The campus is quiet when everyone is home"
- Let H(x) be "x is home" on the domain of x is people
- Let Q be "The campus is quiet"
- `(∀x H(x)) -> Q`
---
[1.5 ->](1.5.md)
|
