# Predicate Logic

Why do we need a new logic, i.e. Predicate Logic, when we already have Predicate Logic, when we already have Propositional Logic?

Consider the following example:

- Every child likes ice cream. (A)
- Billy is a child. (B)
- Therefore, Billy likes ice cream. (C)

If we try to formalize in Propositional Logic, the best we can do is $A,Bβ¨C$. However, this is not a valid argument.

Predicate Logic allows us to make use of predicates to capture relationships. You can thus do the following:

- adult(x) means x is an adult
- round(Earth)

A **predicate** is a symbol denoting the meaning of an attribute (property) of a value or the meaning of a relationship between two or more values.

- unary predicate = predicate that takes a single value as an argument
- binary predicate = predicate that takes two values as arguments
- n-ary predicate = predicate that takes $n$ arguments

constant = symbol denoting a particular value.

To help us in our proofs, use `xg`

when itβs a Genuine Variable and `xu`

when itβs an Genuine Variable and `xu`

when itβs an Unknown Variable.

How do the semantics and proof theory in Predicate Logic differ from Predicate Logic differ from Propositional Logic?

**Substitution**
We define $P[t/x]$ to be the formula obtained by replacing in $P$ every free occurrence of variable $x$ with $t$.

Be careful with Variable Capture

Whenever we use $P[t/z]$, $t$ must be free for $z$ in $P$. Else this would be a Variable Capture.

- forall_i (assume xg, conclude q(xg), and then you can conclude for all x . q(x)) β any variable you want afterwards,
`xg`

β Genuine Variable - forall_e β you can get any
- exists_i β new variable
`xu`

β Unknown Variable - exists_e β (exists x . p(x), for some xu assume p(xu), conclude Q, and you can pull Q out) β N/a

- Forall_nb β you can choose any legal substitution
- not_forall_nb β use the same variable
- exists_nb β you must choose a new variable
- not_exists_nb β Use the same variable

### Examples

#### Counterexample

For a counter example, use the following format:
Notice the capitalization of `P`

in the meaning, as well as the `:=`

sign, though I have noticed the prof use without it sometimes.

##### Natural Deduction

$β’(βx,yβp(x,y))βΉ(βy,xβp(x,y))$

$βxβp(x,x)β’βyβp(x,y)$

$βxβp(x)β’Β¬(βxβΒ¬p(x))$

$Β¬(βxβp(x))β’βxβΒ¬p(x)$

##### Semantic Tableaux

predicate gives you truth values

$βxβp(x)β’Β¬(βxβΒ¬p(x))$

$βxβΒ¬p(x)β’βxβp(x)βΉq(x)$

$βxββyβΒ¬wins(x,y)β’Β¬(βxββyβwins(x,y))$