Representing First-Order Logic

(excerpts from lecture notes on Artificial Intelligence by G. Tecuci)

1. Representing knowledge in first-order logic
   • The objects in the real world are represented by constant symbols (a,b,c,...) For instance, the symbol Tom may represent a certain individual named Tom.
   • Predicates: Properties of objects may be represented by predicates applied to those objects.

     female(Sue) represents that Sue is a female.

   • Relationships between objects are represented by predicates with more arguments:
     father(Bill, Sue) = T means that "Bill is the father of Sue".
   • The quantifiers $\forall$ (for all X) and $\exists$ (there exists an x)
     are used to build new formulas from old ones.
     • $\exists x (P(x))$ means that there is at least one element of the domain that makes P(x) true.
     • $\exists x (mother(x, Bob))$ means that there is an x such that x is the mother of Bob, or otherwise stated, Bob has a mother.
     • $\forall x (P(x))$ means that for all elements of the domain P(x) is true.
2. Logical Operators: $\wedge, \vee, \neg, \rightarrow, \leftrightarrow$
   • $X \wedge Y$ is TRUE if X is TRUE and Y is TRUE, otherwise $X \wedge Y$ is FALSE
   • $X \vee Y$ is TRUE if either X is TRUE or Y is TRUE or both not X is TRUE if X is FALSE, and FALSE if X is TRUE
   • $X \rightarrow Y$ means X implies Y. This implication is
     • TRUE if X is TRUE and Y is TRUE
     • TRUE if X is FALSE
     • FALSE if X is TRUE and Y is FALSE
     • In summary, this implication is TRUE if X is FALSE or Y is TRUE
   • $X \leftrightarrow Y$ is TRUE if
     • both X and Y are TRUE,
     • or both X and Y are FALSE

3. The following table summarizes these definitions:
   

   		AND	OR	Implication	Negation	Equivalence
   X	Y	$X \wedge Y$	$X \vee Y$	$X \rightarrow Y$	$\neg X$	$X \leftrightarrow Y$
   T	T	T	T	T	F	T
   T	F	F	T	F	F	F
   F	T	F	T	T	T	F
   F	F	F	F	T	T	T

   
   

   Note: $X \rightarrow Y$ is equivalent to $\neg X \vee Y$
   and $X \leftrightarrow Y$ is equivalent to $(\neg X \vee Y) \wedge (\neg Y \vee X)$