%% LyX 1.3 created this file.  For more info, see http://www.lyx.org/.
%% Do not edit unless you really know what you are doing.
\documentclass[english]{amsbook}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\setlength\parskip{\smallskipamount}
\setlength\parindent{0pt}
\usepackage{amssymb}

\makeatletter
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands.
 \numberwithin{section}{chapter}
 \theoremstyle{plain}    
 \newtheorem{thm}{Theorem}[section]
 \numberwithin{equation}{section} %% Comment out for sequentially-numbered
 \numberwithin{figure}{section} %% Comment out for sequentially-numbered
 \theoremstyle{definition}
  \newtheorem*{example*}{Exemple}
 \theoremstyle{definition}
 \newtheorem*{defn*}{Définition}
 \theoremstyle{definition}
  \newtheorem{xca}{Exercice}
 \theoremstyle{definition}
  \newtheorem{problem}[thm]{Problem}
 \theoremstyle{remark}    
 \newtheorem{summary}[thm]{Résumé} 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands.
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\usepackage{hyperref}

\usepackage[francais,american]{babel}
\makeatother
\begin{document}

\newcommand{\Imp}{\textrm{ }\rightarrow\textrm{ }}

\newcommand{\Equiv}{\textrm{ }\Leftrightarrow\textrm{ }}
 
\newcommand{\s}{\textrm{ }}



\newcommand{\E}[1]{(\exists#1 )\textrm{ }}



\newcommand{\A}[1]{(\forall#1 )\textrm{ }}



\chapter{Predicate Logic (sections 1.3, 1.4)}


\section{Introduction}

\begin{example*}
{}``Every man has a brain; Socrate is a man; therefore Socrate has
a brain.''

Is propositional logic expressive enough for this sentence ?

What is missing ?
\end{example*}
%

%

%

%

%

%

%

%%


\subsection{Quantifiers, Predicates, Validity}

\begin{example*}
{}``Every man has a brain''

{}``For all man, this man has a brain''
\end{example*}
New features: constants / variables / quantifier / predicates

\begin{defn*}
Quantifiers:
\begin{itemize}
\item For all
\item For every
\item There exists
\item For at least one
\item For each
\item For any
\item For some
\end{itemize}
\emph{Universal quantifier}: $(\forall x)$

\emph{Existential quantifier}: \emph{$(\exists x)$}

Always place the quantifiers inside $($ $)$.
\end{defn*}

\subsection{Predicates:}

\begin{defn*}
\emph{Predicate}: a statement that describes a property of a variable
\end{defn*}
\begin{example*}
$P(x)$ : $x$ has a brain

{}``For all man, this man has a brain''

Translates into $\A{x}P(x)$ 
\end{example*}
As in propositional logic, we can build \emph{well formed formulas}
from predicates and logic connectives.

\begin{example*}
$\A{x}B(x)\rightarrow R(x)'$: if $x$ is blue, then $x$ is not red.
\end{example*}

\subsection{Domain of interpretation:}

If $x$ is a car, the sentence above $\A{x}P(x)$ is false.

The truth of the sentence depends on where you take $x$ from!

\begin{defn*}
\emph{Domain of interpretation}:

The collection of objects from which $x$ may be selected
\end{defn*}
\begin{example*}
$\A{x}(x>0)$

DOI: all integers

DOI: all integers > 10

DOI: all humans
\end{example*}
%

\begin{example*}
For any thing, if it's a man then it has a brain

$P(x)$: $x$ is a man

$Q(x)$: $x$ has a brain

$\A{x}P(x)\rightarrow Q(x)$
\end{example*}
\begin{xca}
Write a formula for the following sentence:

{}``There exists a man which is called Socrate''
\end{xca}

\subsection{N-Ary predicates:}

\begin{defn*}
\emph{Binary predicate}: predicate which takes two variables

\emph{N-Ary predicate} : predicate which takes several variables
\end{defn*}
\begin{itemize}
\item $P(x,y)=x>y$ (DOI: integers)
\item $P(Q,B)$: $Q$ is the author of the book $B$ (DOI: all authors /
books)
\item Everyone has exactly one best friend:


$B(X,Y)$: $Y$ is the best friend of $X$

$\A{x}\E{y}B(X,Y)\wedge[\s(\forall Z)\textrm{ }B(X,Z)\rightarrow(Z=Y)\s]$ 

For any person $X$, there exists a person $Y$, such that:

\begin{enumerate}
\item $Y$ is the best friend of $X$
\item For any person $Z$, if $Z$ is the best friend of $X$, then $Z$
is actually $Y$.
\end{enumerate}
\end{itemize}

\subsection{Truth value}

Can we define the Truth table of a wff ?

\begin{problem}
The domain of interpretation may be infinite.
\end{problem}
To assess the truth value, we need to know:

\begin{enumerate}
\item What is the domain of interpretation.
\item What property of elements of the DOI does P(x) represent.
\item An assignment for each constant.
\end{enumerate}
\begin{defn*}
This is called an \emph{interpretation.}
\end{defn*}
\begin{example*}
\cite[Exercise 1 p.~41]{Gersting.MSCS}

What is the truth value of the following wffs for this interpretation:

DOI: integers; $O(x)$: x is odd; $L(x)$: $x<10$; $G(x)$: $x>9$
\begin{enumerate}
\item $\E{x}O(x)$


There exists an odd number

\item $\A{x}[L(x)\rightarrow O(x)]$


For any integer x, if x is strictly lower than 10, then x is odd;

Any integer strictly lower than 10 is odd;

\item $\E{x}[L(x)\wedge G(x)]$


There exists an integer x such that x is strictly lower than 10 and
x is strictly larger than 9

\item $\A{x}[L(x)\vee G(x)]$


For any integer, either x is strictly lower than 10 or x is strictly
bigger that 9

\end{enumerate}
\end{example*}
\begin{xca}
\cite[Exercise 3 p.~41]{Gersting.MSCS} 

Are the following wffs true for this interpretation:

DOI: states of the US.

$Q(x,y)$: $x$ is north of $y$; $P(x)$: $x$ starts with the letter
M; $a$ is \char`\"{}Mississippi\char`\"{}.
\begin{enumerate}
\item $\A{x}P(x)$
\item $\A{x}\A{y}\A{z}[\textrm{ }(Q(x,y)\wedge Q(y,z))\textrm{ }\rightarrow\textrm{ }Q(x,z)\textrm{ }]$
\item $\E{y}\E{x}Q(x,y)$
\item $\A{x}\E{y}[P(y)\wedge Q(x,y)]$


For any state $x$, there exists a state $y$ such that $y$ starts
with M and $x$ is north of $y$.

\item $\E{y}Q(a,y)$
\end{enumerate}
\end{xca}
%

\begin{xca}
Translate the following sentences into wffs, with: 

DOI: world; $D(x)$: x is a day; $S(x)$: x is sunny; $R(x)$: x is
rainy;

$M$ is \char`\"{}Monday\char`\"{}; $T$ is \char`\"{}Tuesday\char`\"{}.
\end{xca}
\begin{enumerate}
\item All days are sunny:
\item Some days are not rainy:
\item Every day that is sunny is not rainy:
\item Some days are sunny and rainy:
\item No day is both sunny and rainy:
\item It is always a sunny day only if it is a rainy day:
\item No day is sunny:
\item Monday was sunny; therefore every day will be sunny:
\item It rained both Monday and Tuesday:
\item If some day is rainy, then every day will be sunny:
\end{enumerate}

\subsection{Dummy variables / free variables:}

\begin{defn*}
A \emph{dummy variable} is a variable which is linked to a quantifier.

The name of the variable is irrelevant.

Same thing as a local variable in a program.
\end{defn*}
\begin{example*}
$\E{x}Q(x)$ is the same wff as $\E{z}Q(z)$

$\E{x}\A{y}Q(x,y)$ is the same wff as $\E{z}\A{t}Q(z,t)$ or $\E{y}\A{x}Q(y,x)$
\end{example*}
\begin{defn*}
A variable is \emph{free} if it is not linked to a quantifier.

Same thing as a global variable in a program.
\end{defn*}

\subsection{Validity}

\begin{summary}
Where are we?
\end{summary}
\begin{enumerate}
\item We can build all the wff of predicate logic.
\item Given a wff P, and an interpretation, we can decide the truth value
of P.
\end{enumerate}
\begin{defn*}
\emph{Argument}: $P_{1}\wedge P_{2}\wedge\cdots\wedge P_{k}\Imp Q$
\end{defn*}
\begin{itemize}
\item In propositional logic, an argument is \emph{valid} if it's a tautology. 


I.e. if it's true whatever truth value are assigned to each basic
proposition.

\item In predicate logic, an argument is \emph{valid} if it's intrinsically
true.


I.e. if it's true for ANY interpretation.

\end{itemize}
\begin{xca}
\cite[Exercise 16 p.~35]{Gersting.MSCS}

Give interpretations to prove that the following wffs are not valid:
\end{xca}
\begin{enumerate}
\item $\E{x}A(x)\wedge\E{x}B(x)\Imp\E{x}[\textrm{ }A(x)\wedge B(x)\textrm{ }]$
\item $\A{x}\E{y}P(x,y)\Imp\E{x}\A{y}P(x,y)$
\item $\A{x}[P(x)\rightarrow Q(x)]\Imp\A{x}[P(x)\vee Q(x)]$
\item $\A{x}[\textrm{ }A(x)'\textrm{ }]\s\leftrightarrow\s[\A{x}A(x)\textrm{ }]'$
\end{enumerate}

\section{Predicate logic}

There is an infinity of interpretations, so there is no algorithm
to check the validity of a predicate.

We will have to use REASON:

\begin{itemize}
\item Reuse the rules from propositional logic
\item Accept a few basic new rules as intuitively valid
\item Use formal logic with those rules to prove arguments
\end{itemize}

\subsection{Universal instantiation:}

\begin{example*}
We want to be able to prove the following argument:

Every human is mortal; Socrate is a man; Therefore Socrate is mortal.

$H(x)$: $x$ is a human; $M(x)$: $x$ is a mortal; $s$: Socrate

$\A{x}[H(x)\s\rightarrow\s M(x)]\wedge H(s)\Imp M(s)$
\end{example*}
\begin{defn*}
Rule of \emph{universal instantiation} (ui):

From: $\A{x}P(x)$

Can derive: $P(s)$

Note: $s$ can be any constant.
\end{defn*}
We decide that this rule is valid, because it is \emph{intuitively}
valid.

Proof sequence for: $\A{x}[H(x)\rightarrow M(x)]\wedge H(s)\Imp M(s)$

\[
\begin{array}{lll}
1. & \A{x}[H(x)\rightarrow M(x)] & (\textrm{hyp})\\
2. & H(s) & (\textrm{hyp})\\
3. & H(s)\rightarrow M(s) & (\textrm{ui }1)\\
4. & M(s) & (\textrm{mp }2,\textrm{ }3)\end{array}\]


\begin{xca}
Prove $\A{x}[\s P(x)\rightarrow R(x)\s]\wedge[\s R(y)'\s]\s\rightarrow\s[\s P(y)'\s]$
\end{xca}

\subsection{Universal generalization:}

\begin{example*}
{}``Every human is a living being. Every living being is mortal.Therefore
every human is mortal.''

$H(x)$: is a human

$L(x)$: is a living being

$M(x)$ is mortal

$\A{x}[H(x)\rightarrow L(x)]\s\wedge\s\A{x}[L(x)\rightarrow M(x)]\Imp\A{x}[H(x)\rightarrow M(x)]$
\end{example*}
This is clearly something we want to be able to prove, but we cannot
use hypothetical syllogism directly!

\begin{defn*}
Rule of \emph{universal generalization} (ug)

From: $P(s)$

Can derive: $\A{x}P(x)$ 

$s$ must be an arbitrary element of the domain.
\end{defn*}
\begin{example*}
$\A{x}[H(x)\rightarrow L(x)]\s\wedge\s\A{x}[L(x)\rightarrow M(x)]\Imp\A{x}[H(x)\rightarrow M(x)]$
\end{example*}
\[
\begin{array}{lll}
1. & \A{x}H(x)\rightarrow L(x) & (\textrm{hyp})\\
2. & \A{x}L(x)\rightarrow M(x) & (\textrm{hyp})\\
3. & H(s)\rightarrow M(s) & (\textrm{ui }1)\\
4. & L(s)\rightarrow M(s) & (\textrm{ui }2)\\
5. & H(s)\rightarrow M(s) & (\textrm{hs }3,4)\\
6. & \A{x}[H(x)\rightarrow M(x)] & (\textrm{ug }5)\end{array}\]


\begin{example*}
$s$: Socrate; $H(x)$: $x$ is a man; $M(x)$: $x$ is mortal:

\[
\begin{array}{lll}
1. & M(s) & (\textrm{hyp})\\
2. & H(s)'\vee M(s) & (\textrm{add }1)\\
3. & H(s)\rightarrow M(s) & (\textrm{imp }2)\\
4. & \A{x}[H(x)\rightarrow M(x)] & (\textrm{ug }3)\end{array}\]


Socrate is a mortal, therefore every man is a mortal.
\end{example*}
This proof sequence is incorrect: you cannot apply ug at step 4.

Indeed $s$ is Socrate, and not an arbitrary element of the domain.

\begin{xca}
Prove the following arguments:
\end{xca}
\begin{enumerate}
\item $\A{x}[P(x)\wedge Q(x)]\Imp\A{x}P(x)\wedge\A{x}Q(x)$
\item $\A{x}P(x)\wedge\A{x}Q(x)\s\Imp\A{x}(P(x)\wedge Q(x))$
\item $\A{x}[P(x)\wedge\A{y}Q(x,y)]\Imp\A{x}\A{y}Q(x,y)$
\end{enumerate}

\subsection{Existential instantiation:}

\begin{example*}
DOI: contents of the fridge.

There exists a fruit; therefore, I can take a fruit.

$F(x)$: $x$ is a fruit

$\E{x}F(x)\Imp F(s)$
\end{example*}
\begin{defn*}
Rule of \emph{existential instantiation} (ei):

From: $\E{x}P(x)$

Can derive: $P(s)$

$s$ must be a newly created variable
\end{defn*}
\begin{example*}
$\A{x}[P(x)\rightarrow Q(x)]\s\wedge\E{y}P(y)\Imp Q(s)$

\[
\begin{array}{lll}
1. & \A{x}[P(x)\rightarrow Q(x)] & (\textrm{hyp})\\
2. & \E{y}P(y) & (\textrm{hyp})\\
3. & P(s) & (\textrm{ei }2)\\
4. & P(s)\rightarrow Q(s) & (\textrm{ui }1)\\
5. & Q(s) & (\textrm{mp }3,4)\end{array}\]

\end{example*}

\subsection{Existential generalization:}

\begin{example*}
DOI: contents of the fridge

I see a fruit, therefore there exists a fruit.

$F(s)\Imp\E{x}F(x)$
\end{example*}
\begin{defn*}
Rule of \emph{existential generalization} (eg)

From: $F(s)$

Can derive:$\E{x}F(x)$
\end{defn*}
\begin{example*}
$\A{x}[P(x)\rightarrow Q(x)]\s\wedge\s\E{y}P(y)\Imp\E{y}Q(y)$

\[
\begin{array}{lll}
1. & \A{x}[P(x)\rightarrow Q(x)] & (\textrm{hyp})\\
2. & \E{y}P(y) & (\textrm{hyp})\\
3. & P(s) & (\textrm{ei }2)\\
4. & P(s)\rightarrow Q(s) & (\textrm{ui }1)\\
5. & Q(s) & (\textrm{mp }3,4)\\
6. & \E{y}Q(y) & (\textrm{eg }5)\end{array}\]

\end{example*}
%

\begin{example*}
$\E{x}P(x)\wedge\E{x}Q(x)\Imp\E{x}[P(x)\wedge Q(x)]$

\[
\begin{array}{lll}
1. & \E{x}P(x) & (\textrm{hyp})\\
2. & \E{x}Q(x) & (\textrm{hyp})\\
3. & P(s) & (\textrm{ei }1)\\
4. & Q(s) & (\textrm{ei }2)\\
5. & P(s)\wedge Q(s) & (\textrm{add }3,4)\\
6. & \E{x}[P(x)\wedge Q(x)] & (\textrm{eg }5)\end{array}\]

\end{example*}
%

%

%%

We have seen that the previous argument is incorrect:

So, where is the flaw in the following proof ?

For example, s cannot have been created by existential instantiation

\begin{xca}
Prove or disprove the following arguments
\begin{enumerate}
\item $\E{x}\A{y}Q(x,y)\Imp\A{y}\E{x}Q(x,y)$
\item $\A{x}\E{y}Q(x,y)\Imp\E{y}\A{x}Q(x,y)$
\end{enumerate}
\end{xca}

\subsection{Deduction Method and Temporary Hypothesis:}

\begin{example*}
$P(s)\rightarrow\A{y}Q(x,y)\Imp\A{y}[P(s)\rightarrow Q(x,y)]$
\end{example*}

\section{Conclusion}

Goal: formalization of arguments and proofs.

\begin{description}
\item [Propositional~logic:]~


propositions $A$, $B$, \ldots{}

connectives, well formed formula

truth table

argument valid iff wff is a tautology

proofs:

\begin{itemize}
\item compute the truth table (algorithm)
\item formal logic, deduction rules
\end{itemize}
Ex 24, 37

\item [Predicate~logic]~


variables, predicates

domain of interpretation

connectives, wff

interpretation

truth table: all possible interpretations (infinite)

argument valid iff wff is true for all possible interpretations

proofs:

\begin{itemize}
\item no algorithm
\item formal logic, deduction rules
\end{itemize}
\end{description}
Those two logic are correct and complete.

They are still not powerful enough to represent all real life argument.

For this we would need of more powerful logics (2nd order), that allows
for quantifying other sets.

Problem: it's often difficult, if not impossible to prove that those
logics are complete and correct!

We won't need to go into those details.

We have seen enough low-level logic to help us write safely less formal
proofs.
\end{document}
