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