diff options
Diffstat (limited to '1.4.md')
-rw-r--r-- | 1.4.md | 90 |
1 files changed, 90 insertions, 0 deletions
@@ -0,0 +1,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` |