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
|
[\<- 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`
|
