7-First Order Logic

First Order Logic: Formal/Natural Languages

Whereas propositional logic assumes world contains facts, fitst-order logic(like natural language) assumes the world contains.

Three kinds of symbols
- Constant: objects
- Predicate: relations
- Function: functions (i.e. can return values other than truth vals)
Predicate and Function have arity.
Symbols have an interpretation.
Terms: $function(term_1 ,…, term_n)$ or constant or variable, i.e. $LeftLeg(John)$
Atomic Sentences state facts: $predicate(term_1,…,term_n)$ or $term_1 = term_2$, i.e. $Brother(Richard, John)$
Complex Sentences: $Brother(R,J) \bigwedge Brother(J,R)$
Universal Quantifiers: $\forall (variable) (sentence)$, i.e. $\forall King(x) \Rightarrow Person(x)$
- A common mistake to avoid:
  - Typically, $\Rightarrow$ is the main connective with $\forall$.
  - Common mistake: using $\bigwedge$ as the main connective with $\forall$: $\forall x At(Berkeley) \bigwedge Smart(x)$ means “Everyone is at Berkeley and everyone is smart”, not “Everyone at Berkeley is smart”, which should to be $\forall x At(x, Berkeley) \Rightarrow Smart(x)$
Existential Quantifiers: $\exists
$, i.e. $\exists Crown(x) \bigwedge OnHead(x,John)$
- A common mistake to avoid:
  - Typically, $\bigwedge$ is the main connective with $\exists$.
  - Common mistake: using $\Rightarrow$ as the main connective with $\exists$: $\exists x At(x, Standford) \Rightarrow Smart(x)$ is true even if there is anyone who is at Stanford! The correct one is $\exists x At(x, Standford) \bigwedge Smart(x)$

$term_1 = term_2$ is true under a given interpretation if and only if $term_1$ and $term_2$ refer to the same object.

E.g. $1=2$ and $\forall xMutiple(Sqrt(x), Sqrt(x)) = x$ are satisfiable, $2=2$ is vaild.