\documentclass[12pt]{article}

\usepackage{enumerate}
\fontfamily{lmss}
\usepackage{fullpage}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{hyperref}
\hypersetup{
    colorlinks=true, %set true if you want colored links
    linkcolor=blue,  %choose some color if you want links to stand out
}
\usepackage[math-style=upright]{unicode-math}

\setlength{\parindent}{0pt}

\newtheorem{note}{Note}
\newtheorem{definition}{Definition}
\newtheorem{exercise}{Exercise}
\newtheorem{notation}{Notation}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}

\newcommand{\true}{\text{T}}
\newcommand{\false}{\text{F}}

\newcommand{\op}{\text{op}}
\newcommand{\cl}{\text{cl}}
\newcommand{\Pro}{\text{P}}

\usepackage{245assignments}

\usepackage{listings}
\usepackage{graphicx}
\usepackage{proof}


\title{CS245 Logic and Computation}
\author{Alice Gao}

\begin{document}

\maketitle

\tableofcontents

\newpage
\section{Propositional Logic}
\subsection{Translations}

\begin{exercise}
Translate the following three sentences into propositional logic.  

\vspace{20mm}
\begin{itemize}
\item
{\bf Nadhi will eat a fruit if it is an apple.}  

\vspace{40mm}
\item
{\bf Nadhi will eat a fruit only if it is an apple.}  

\vspace{40mm}
\item
{\bf Nadhi will eat a fruit if and only if it is an apple.} 

\vspace{40mm}
\end{itemize}

\end{exercise}

\newpage
\begin{exercise}
Translate the following sentence into multiple propositional formulas.  Show that they are logically equivalent using a truth table.

\medskip
{\bf Soo-Jin will eat an apple or an orange but not both.}
\end{exercise}

\vspace{60mm}
\begin{exercise}
Translate the following sentence into at least three syntactically different propositional formulas.  Show that they are logically equivalent using a truth table.

\medskip
{\bf If it is sunny tomorrow, then I will play golf, provided that I am relaxed.}
\end{exercise}





\newpage
\begin{exercise}
Translate the following sentence into a propositional formula.  

\medskip
{\bf If I ace CS 245, I will get a job at Google;  otherwise I will apply for the Geek Squad.}
\end{exercise}

\vspace{60mm}
\begin{exercise}
Translate the following sentence into two propositional formulas and prove that the formulas are not logically equivalent using a truth table.

\medskip
{\bf Sidney will carry an umbrella unless it is sunny.}
\end{exercise}





\newpage
\subsection{Structural Induction}
\begin{theorem}
Every well-formed formula has an equal number of opening and closing brackets.
\end{theorem}

\begin{proof}[Proof by Structural Induction]
Let $\Pro(\varphi)$ denote that the well-formed formula $\varphi$ has an equal number of opening and closing brackets.
Let $\op(\varphi)$ and $\cl(\varphi)$ denote the number of opening and closing brackets of $\varphi$ respectively.
\begin{itemize}

\item[] Base case: $\varphi$ is a propositional variable $q$.   Prove that $\Pro(q)$ holds.

\vspace{30mm}

\item[] Induction step: 

\begin{itemize}
\item[] Case 1: $\varphi$ is $(\neg a)$, where $a$ is well-formed.  

Induction hypothesis: Assume that $\Pro(a)$ holds.  

We need to prove that $\Pro((\neg a))$ holds.

\vspace{40mm}

\medskip
\item[] Case 2: $\varphi$ is $(a * b)$ where $a$ and $b$ are well-formed and $*$ is a binary connective.

Induction hypothesis: Assume that $\Pro(a)$ and $\Pro(b)$ hold.  

We need to prove that $\Pro((a * b))$ holds.

\vspace{40mm}

\end{itemize}
\item[]
By the principle of structural induction, $\Pro(\varphi)$ holds for every well-formed formula $\varphi$.  QED
\end{itemize}

\end{proof}

\newpage
\begin{theorem}
Every proper prefix of a well-formed formula has more opening than closing brackets.
\end{theorem}

\begin{proof}[Proof by Structural Induction]
Let $\Pro(\varphi)$ denote that every proper prefix of the well-formed formula $\varphi$ has more opening than closing brackets.

\begin{itemize}

\item[] Base case: $\varphi$ is a propositional variable $q$.  Prove that $\Pro(q)$ holds.

\item[] Induction step: 

\begin{itemize}
\item[] Case 1: $\varphi$ is $(\neg a)$, where $a$ is well-formed.  

Induction hypothesis: Assume that $\Pro(a)$ holds.  

We need to prove that $\Pro((\neg a))$ holds.

\medskip
\item[] Case 2: $\varphi$ is $(a * b)$ where $a$ and $b$ are well-formed and $*$ is a binary connective.

Induction hypothesis: Assume that $\Pro(a)$ and $\Pro(b)$ hold.  

We need to prove that $\Pro((a * b))$ holds.

\end{itemize}
\item[]
By the principle of structural induction, $\Pro(\varphi)$ holds for every well-formed formula $\varphi$.  QED
\end{itemize}

\end{proof}



\newpage
\subsection{Tautology, Contradiction, and Satisfiable but Not a Tautology}

\begin{exercise}
Determine whether each of the following formulas is a tautology, satisfiable but not a tautology, or a contradiction.
\end{exercise}

\begin{itemize}
\item
$p$
\vfill

\item
$((r \land s) \rightarrow r)$
\vfill

\item
$((\neg (p \leftrightarrow q)) \leftrightarrow (q \lor p))$
\vfill

\item
$((((p \lor q) \land (p \lor (\neg q))) \land ((\neg p) \lor q)) \land ((\neg p) \lor (\neg q)))$
\vfill

\end{itemize}



\newpage
\subsection{Logical Equivalence}

\begin{exercise}
"If it is sunny, I will play golf, provided that I am relaxed."

$s$: it is sunny.  $g$: I will play golf.  $r$: I am relaxed.

\medskip
There are three possible translations:
\begin{enumerate}
	\item $(r \rightarrow (s \rightarrow g))$
	\item $((s \land r) \rightarrow g)$
	\item $(s \rightarrow (r \rightarrow g))$
\end{enumerate}

Prove that all three translations are logically equivalent.
\end{exercise}

Problem 1: $(r \rightarrow (s \rightarrow g)) \equiv ((s \land r) \rightarrow g)$.
\vfill

Problem 2: $(r \rightarrow (s \rightarrow g)) \equiv (s \rightarrow (r \rightarrow g))$.
\vfill

\newpage
\begin{exercise}
"If it snows then I will not go to class but I will do my assignment."

$s$: it snows.  $c$: I will go to class.  $a$: I will do my assignment.

\medskip
There are two possible translations:
\begin{enumerate}
	\item $((s \rightarrow (\neg c)) \land a)$
	\item $(s \rightarrow ((\neg c) \land a))$
\end{enumerate}

Prove that the two translations are NOT logically equivalent.
\end{exercise}
\vfill

\newpage
\subsection{Analyzing Conditional Code}

Consider the following code fragment: 

\begin{lstlisting}[language=C,basicstyle=\ttfamily,keywordstyle=\color{red},showstringspaces=false]

if (input > 0 || !output) {
  if (!(output && queuelength < 100)) {
    P1 
  } else if (output && !(queuelength < 100)) { 
    P2 
  } else { 
  	P3 
  }
} else { 
  P4 
}
\end{lstlisting}

Define the propositional variables:

\begin{itemize}
\item
$i$: input > 0
\item
$u$: output
\item
$q$: queuelength < 100
\end{itemize}

The code fragment becomes the following.  We'll call this code fragment \#1.

\begin{lstlisting}[language=C,basicstyle=\ttfamily,keywordstyle=\color{red},showstringspaces=false]
if ( i || !u ) {
  if ( !(u && q) ) {
    P1
  } else if ( u && !q ) {
    P2
  } else { P3 }
} else { P4 }
\end{lstlisting}

Code fragment \#2: 

\begin{lstlisting}[language=C,basicstyle=\ttfamily,keywordstyle=\color{red},showstringspaces=false]

if (( i && u) && q) {
  P3
} else if (!i && u) {
  P4
} else { 
  P1 
}
\end{lstlisting}

Prove that these two pieces of code fragments are equivalent:

\newpage
Prove that the condition leading to $P_2$ is logically equivalent to $\fals$.

The condition leading to $P_2$: 
\vfill

Prove that the condition leading to $P_3$ is true if and only if all three variables are true.

The condition leading to $P_3$:
\vfill

Prove that the condition leading to $P_4$ is true if and only if $i$ is false and $u$ is true.

The condition leading to $P_4$:
\vfill

The condition leading to $P_1$: 
\vfill




\newpage
\subsection{Circuit Design}

Basic gates:
\begin{center}
\includegraphics[width=0.20\linewidth]{circuit_design/gates.PNG}
\end{center}

Problem: Your instructors, Alice, Carmen, and Collin, are choosing questions to be put on the midterm.  For each problem, each instructor votes either yes or not.  A question is chosen if it receives two or more yes votes.  Design a circuit, which outputs yes whenever a question is chosen.

\begin{enumerate}
\item
Draw the truth table based on the problem description.

\begin{center}
\begin{tabular}{c|c|c|c}
x & y & z & output \\\hline
\tru  & \tru  & \tru  & \\
\tru  & \tru  & \fals & \\
\tru  & \fals & \tru  & \\
\tru  & \fals & \fals & \\
\fals & \tru  & \tru  & \\ 
\fals & \tru  & \fals & \\
\fals & \fals & \tru  & \\
\fals & \fals & \fals & 
\end{tabular}
\end{center}

\item
Convert the truth table a propositional formula. 

\item
Then, convert the formula to a circuit.

\end{enumerate}

\newpage
Solution 1: 

\begin{enumerate}
\item
Convert the truth table a propositional formula. 
\vfill

\item
Draw the circuit.
\vfill

\end{enumerate}


\newpage
Solution 2:

\begin{enumerate}
\item
Convert the truth table a propositional formula. 
\vfill

\item
Draw the circuit.
\vfill

\end{enumerate}

\newpage
Solution 3:

\begin{enumerate}
\item
Convert the truth table a propositional formula. 

\vfill

\item
Draw the circuit.

\vfill

\end{enumerate}


\newpage
\subsection{Semantic Entailment}

\begin{exercise}
Let $\Sigma = \{(p \rightarrow q), (q \rightarrow r)\}$.  Is $\Sigma$ satisfiable?  Why or why not?
\end{exercise}
\vfill

\begin{exercise}
Let $\Sigma = \emptyset$.  Is $\Sigma$ satisfiable?  Why or why not?
\end{exercise}
\vfill

\begin{exercise}
Let $\Sigma = \{p, (\neg p)\}$.  Is $\Sigma$ satisfiable?  Why or why not?
\end{exercise}
\vfill


\newpage
\begin{exercise}
Prove that $\{(\neg(p \land q)), (p \rightarrow q)\} \models (\neg p)$.
\end{exercise}
\vfill

\begin{exercise}
Prove that $\{(\neg(p \land q)), (p \rightarrow q)\} \not\models (p \leftrightarrow q)$.
\end{exercise}
\vfill

\begin{exercise}
Prove that $\emptyset \models ((p \land q) \rightarrow p))$.
\end{exercise}
\vfill


\newpage
\begin{exercise}
Prove that $\{r, (p \rightarrow (r \rightarrow q)) \} \models (p \rightarrow (q \land r))$.
\end{exercise}
\vfill

\begin{exercise}
Prove that $\{ (\neg p), (q \rightarrow p) \} \not\models ((\neg p) \land q)$.
\end{exercise}
\vfill

\begin{exercise}
Prove that $\{p, (\neg p) \} \models r$.
\end{exercise}
\vfill


\newpage
\subsection{Natural Deduction}

\subsubsection{Strategies for writing a natural deduction proof}

General strategies:
\begin{itemize}
\item
Write down all of the premises

\item
Leave plenty of space.  Then write down the conclusion.

\item
Look at the conclusion carefully.  What is the structure of the conclusion (what is the last connective applied in the formula?  Can you apply an introduction rule to produce the conclusion?

\item
Look at each premise carefully.  What is the structure of the premise (what is the last connective applied in the formula)?  Can you apply an elimination rule to simplify it? 

\item
Working backwards from the conclusion is often more effective than working forward from the premises.  It keeps your eyes on the prize.

\item
If no rule is applicable, consider using a combination of $\neg$i and $\neg\neg$e.
\end{itemize}

Working with subproofs
\begin{itemize}
\item
To apply an introduction rule to produce the conclusion, {\bf lay down the structure of the subproof before you proceed to fill in the subproof}.  That is, draw the box for the subproof, write down the assumption on the first line, copy the conclusion to the last line of the subproof.  

\item
Every subproof must be created to apply a particular rule.  If you don't know what rule you are trying to apply, don't create a subproof.

\item
When filling in a subproof, you can use all the formulas that come before as long as the formula is not in a previous subproof that has already closed.

\item
Outside of a subproof, you have to use the subproof as a whole.  You cannot use any individual formula in the subproof.
\end{itemize}

\newpage
\subsubsection{And elimination and introduction}

\begin{exercise}
Show that $\{\pfm{p \And q}, \pfm{r \And s}\} \proves \pfm{q \And s}$.
\end{exercise} 

\vfill

\begin{exercise}
Show that $((p \land q) \land r) \proves (p \land (q \land r))$.
\end{exercise}

\vfill

\newpage
\subsubsection{Implication introduction and elimination}

\begin{exercise}
Show that $\{ \implof{p}{q}, \implof{q}{r} \} \proves \implof{p}{r}$.
\end{exercise}

\vfill

\begin{exercise}
Show that $\{ (p \rightarrow (q \rightarrow r)), (p \rightarrow q) \} \proves (p \rightarrow r)$.
\end{exercise}

\vfill 

\newpage
\begin{exercise}
Show that $\{ (p \rightarrow (q \rightarrow r)) \} \proves ((p \land q) \rightarrow r)$.
\end{exercise}

\vfill


\begin{exercise}
Show that $\{ ((p \land q) \rightarrow r) \} \proves (p \rightarrow (q \rightarrow r))$.
\end{exercise}

\vfill


\newpage
\subsubsection{Or elimination and introduction}

\begin{exercise}
Show that $\{ (p \land (q \lor r)) \} \proves ((p \land q) \lor (p \land r))$.
\end{exercise}

\vfill

\begin{exercise}
Show that $\{ ((p \land q) \lor (p \land r)) \} \proves  (p \land (q \lor r))$.
\end{exercise}

\vfill

\newpage
\begin{exercise}
Show that $\{ (p\Or q) \} \proves ((p\rightarrow q) \Or (q\rightarrow p))$.
\end{exercise}

\vfill

\begin{exercise}
Show that $\{ (p \rightarrow q) \} \proves ((r \lor p) \rightarrow (r \lor q))$.
\end{exercise}
 
\vfill

\newpage
\subsubsection{Negation introduction and double negation elimination}

\begin{exercise}
Show that $\{ (p \rightarrow (\neg p)) \} \proves (\neg p)$.
\end{exercise}
\vfill


\begin{exercise}
Show that $\{ (p \rightarrow (q \rightarrow r)), p, (\neg r) \} \proves (\neg q)$.
\end{exercise}

\vfill


\newpage
\begin{exercise}
Show that $\{ ((\neg p) \rightarrow (\neg q)) \} \proves (q \rightarrow p)$.
\end{exercise}

\vfill

\begin{exercise}
Show that $\{((p \land (\neg q)) \rightarrow r), (\neg r), p \} \proves q$.
\end{exercise}

\vfill



\newpage
\subsubsection{Negation elimination}

\begin{exercise}
Show that $\{ (p \lor q), (\neg p) \} \proves q$.
\end{exercise}

\vfill

\begin{exercise}
Show that $\emptyset \proves ((\neg p) \rightarrow (p \rightarrow (p \rightarrow q)))$.
\end{exercise}

\vfill

\newpage
\subsubsection{Putting it together!}

\begin{exercise}
(De Morgan's Law) Show that $\{ (\neg (\alpha \lor \beta)) \} \proves ((\neg \alpha) \land (\neg \beta))$.
\end{exercise}

\vfill

\begin{exercise}
(De Morgan's Law) Show that $\{ ((\neg \alpha) \land (\neg \beta)) \} \proves (\neg (\alpha \lor \beta))$.
\end{exercise}

\vfill



\newpage
\begin{exercise}
(De Morgan's Law) Show that $\{ ((\neg \alpha) \lor (\neg \beta)) \} \proves (\neg (\alpha \land \beta))$.
\end{exercise}

\vfill

\begin{exercise}
(De Morgan's Law) Show that $\{ (\alpha \lor \beta) \} \proves (\neg ((\neg \alpha) \land (\neg \beta)))$.
\end{exercise}

\vfill

\newpage
\begin{exercise}
(De Morgan's Law) Show that $\{ (\neg (\alpha \land \beta)) \} \proves ((\neg \alpha) \lor (\neg \beta))$.
\end{exercise}

\vfill
  
  
\begin{exercise}
Show that $\{ (\neg (p \rightarrow q)) \} \proves (q \rightarrow p)$.
\end{exercise}  

\vfill
 
 
\newpage
\subsubsection{Other problems}
\begin{exercise}
E4 Exercise 4: Prove that for any set of propositional formulas $\Sigma$ and any propositional variables $p$ and $q$, if $\Sigma \proves p$, then $\Sigma \proves ((\neg p) \rightarrow q)$.
\end{exercise}  
  
 
\newpage
\subsection{Soundness and Completeness of Natural Deduction}
\subsubsection{The soundness of inference rules}

\begin{exercise}
The following inference rule is called Disjunctive syllogism.

\begin{displaymath}
\infer[\text{Disjunctive syllogism}]{\beta}{(\neg \alpha) & (\alpha \lor \beta)}
\end{displaymath}
where $\alpha$ and $\beta$ are well-formed propositional formulas.

\medskip
Prove that this inference rule is sound.  That is, prove that the following semantic entailment holds.

\begin{displaymath}
\{(\neg \alpha), (\alpha \lor \beta)\} \models \beta
\end{displaymath}

You must use {\bf the definition of semantic entailment} to write your proof.  Do not use any other technique such as truth table, valuation tree, logical identities, natural deduction, soundness, or completeness.
\end{exercise}

\newpage
\begin{exercise}
Consider the following inference rule:
\begin{displaymath}
\infer[\text{Flip the implication}]{(\beta \rightarrow \alpha)}{(\alpha \rightarrow \beta)}
\end{displaymath}
where $\alpha$ and $\beta$ are well-formed propositional formulas.

\medskip
Prove that this inference rule is NOT sound.  That is, prove the following statement:
\begin{displaymath}
\{(\alpha \rightarrow \beta)\} \not\models (\beta \rightarrow \alpha)
\end{displaymath}

You must use {\bf the definition of semantic entailment} to write your proof.  Do not use any other technique such as truth table, valuation tree, logical identities, natural deduction, soundness, or completeness.

\end{exercise}

\newpage
\subsubsection{Soundness and Completeness of Natural Deduction}
\begin{exercise}
Prove or disprove this statement:  If $\{a, b\} \proves c$, then $\emptyset \models ((a \land b) \rightarrow c)$.
\end{exercise}

\newpage
\begin{exercise}
Prove or disprove this statement:  If $\{ \alpha \} \models \beta$, then $\emptyset \proves (\beta \rightarrow \alpha)$.
$\alpha$ and $\beta$ are well-formed propositional formulas.
\end{exercise}
\vfill

\newpage
\section{Predicate Logic}

\subsection{Translations}

\begin{exercise}
Let the domain be the set of animals.  Let $B(x)$ mean that $x$ is a bear.  Let $H(x)$ mean that $x$ likes honey.

\medskip
Translate ``every bear likes honey'' into predicate logic.
\end{exercise}


\newpage
\begin{exercise}
Let the domain be the set of animals.  Let $B(x)$ mean that $x$ is a bear.  Let $H(x)$ mean that $x$ likes honey.

\medskip
Translate ``some bear likes honey'' into predicate logic.
\end{exercise}



\newpage
\begin{exercise}
Could you summarize the general patterns of translations based on the two exercises above?  Which binary connectives usually go with the universal and the existential quantifiers?

\medskip
Alice: I put this exercise here so that I will have a place to put down a summary.
\end{exercise}



\newpage
\begin{exercise}
Translate the following sentences into predicate formulas.
\end{exercise}

Let the domain contain the set of all students and courses. 
Define the following predicates:

$C(x)$: $x$ is a course.

$S(x)$: $x$ is a student.

$T(x,y)$: student $x$ has taken course $y$.

\begin{enumerate}
\item
Every student has taken some course.

\vfill

\item
A student has taken a course.

\vfill

\item 
No student has taken every course.

\vfill

\item
Some student has not taken any course.

\vfill

\item
Every student has taken every course.

\vfill
\end{enumerate}



\newpage
\begin{exercise}
Translating ``at least'', ``at most'', and ``exactly''.

Translate the following sentences into predicate formulas.
\end{exercise}

\begin{itemize}
\item
There is at least one bear.

\vfill

\item
There are at least two bears.

\vfill

\item
There is at most one bear.

\vfill

\item
There is exactly one bear.

\vfill

\end{itemize}




\newpage
\subsection{Semantics of Predicate Formulas}

Consider this language of predicate logic:
\begin{itemize}
\item
Constant symbols: $a, b, c$
\item
Variable symbols: $x, y, z$
\item
Function symbols: $f^{(1)}, g^{(2)}$
\item
Predicate symbols: $P^{(1)}, Q^{(2)}$
\end{itemize}

\subsubsection{Evaluating Formulas with No Variables}
\begin{exercise} \label{pred_semantics_1}
Give an interpretation $I$ such that $Q(f(c), a)^I = \tru$ where $dom(I) = \{1, 2, 3\}$.
\end{exercise}

\vfill

\newpage
\begin{exercise} \label{pred_semantics_2}
Give an interpretation $I$ such that $Q(f(c), a)^I = \fals$.
\end{exercise}

\vfill

\subsubsection{Evaluating Formulas with Free Variables Only}
\begin{exercise} \label{pred_semantics_3}
Give an interpretation $I$ and an environment $E$ such that $Q(f(x), a)^{(I,E)} = \tru$.
\end{exercise}

\vfill


\newpage
\subsubsection{Evaluating Formulas with Free and Bound Variables}
\begin{exercise} \label{pred_semantics_5}
Give an interpretation $I$ and an environment $E$ such that $I \models_E \alpha$ where $\alpha$ is $(\exists x~Q(x,y))$.  Start with the domain $dom(I) = \{1, 2, 3\}$.
\end{exercise}

\vfill

\begin{exercise} \label{pred_semantics_6}
Give an interpretation $I$ and an environment $E$ such that $I \models_E \alpha$ where $\alpha$ is $(\forall x~Q(x,y))$.
\end{exercise}

\vfill

\newpage
\subsubsection{Evaluating Formulas with Bound Variables Only}
\begin{exercise}
Give an interpretation $I$ and an environment $E$ such that $I \models_E (\exists x (\forall y~Q(x,y)))$.  Start with the domain $dom(I) = \{1, 2, 3\}$.
\end{exercise}

\vfill

\begin{exercise}
Give an interpretation $I$ and an environment $E$ such that $I \nvDash_E (\exists x (\forall y~Q(x,y)))$.  Start with the domain $dom(I) = \{1, 2, 3\}$.
\end{exercise}


\vfill





\newpage
\subsection{Semantic Entailment}

\begin{exercise}
Show that $\{ (\forall x~P(x)) \} \models (\exists x~P(x))$.
\end{exercise}

\vfill

\begin{exercise}
Show that $\{ (\exists x~P(x)) \} \nvDash (\forall x~P(x))$.
\end{exercise}

\vfill

\newpage
\begin{exercise}
Show that $\{ (\exists y~(\forall x~Q(x,y))) \} \models (\forall x~(\exists y~Q(x,y)))$.
\end{exercise}

\vfill

\newpage
\begin{exercise}
Show that $\{ (\forall x~(\exists y~Q(x,y))) \} \nvDash (\exists y~(\forall x~Q(x,y)))$.
\end{exercise}
\vfill

\newpage
\begin{exercise}
Show that $\{ (\forall x~(\alpha \rightarrow \beta)) \} \models ((\forall x~\alpha) \rightarrow (\forall x~\beta))$, where $x$ is a variable symbol and $\alpha$ and $\beta$ are well-formed predicate formulas.
\end{exercise}
\vfill

\newpage
\begin{exercise}
Show that $\{ ((\forall x~\alpha) \rightarrow (\forall x~\beta)) \} \nvDash (\forall x~(\alpha \rightarrow \beta))$, where $x$ is a variable symbol and $\alpha$ and $\beta$ are well-formed predicate formulas.
\end{exercise}
\vfill







\newpage
\subsection{Natural Deduction}

\begin{itemize}
\item
$\forall$e (analogous to $\land$e)
\item
$\forall$i (analogous to $\land$i)
\begin{itemize}
\item
We know nothing about the fresh variable $u$ except that $u $ is a domain element.  (If $u$ is special, our conclusion may not be valid.)
\item
The fresh variable $u$ cannot escape the subproof box.  For example, we cannot conclude $\alpha[u/x]$ outside of the box.
\item
When you choose the fresh variable $u$, make sure that it has not appears anywhere outside of the subproof box in the proof.
\end{itemize}
\item
$\exists$e (analogous to $\lor$e)
\begin{itemize}
\item
Proof by cases.
\item
The conclusion may have nothing to do with the starting formula.
\end{itemize}
\item
$\exists$i (analogous to $\lor$i)
\end{itemize}

\newpage

\subsubsection{Forall-elimination}

\begin{exercise}
Show that $\{ P(t), (\forall x~(P(x) \rightarrow (\neg Q(x)))) \} \proves (\neg Q(t))$.
\end{exercise}
\vfill

\subsubsection{Exists-introduction}

\begin{exercise}
Show that $\{ (\neg P(y)) \} \proves (\exists x~(P(x) \rightarrow Q(y)))$.
\end{exercise}
\vfill


\begin{exercise}
Show that $\{ (\forall x~P(x)) \} \proves (\exists y~P(y))$.
\end{exercise}
\vfill

\newpage






\newpage



\newpage
\subsubsection{Forall-introduction}

\begin{exercise}
Show that $\{ (\forall x~P(x)) \} \proves (\forall y~P(y))$.
\end{exercise}

\vfill


\begin{exercise}
Show that $\{ (\forall x~(P(x) \rightarrow Q(x))), (\forall x~P(x)) \} \proves (\forall x~Q(x))$.
\end{exercise}

\vfill

\begin{exercise}
Show that $\{ (\forall x~(P(x) \rightarrow Q(x))) \} \proves ((\forall x~P(x)) \rightarrow (\forall y~Q(y)))$.
\end{exercise}

\vfill





\newpage
\subsubsection{Exists-elimination}

\begin{exercise}
Show that $\{ (\exists x~P(x)) \} \proves (\exists y~P(y))$.
\end{exercise}

\vfill

\begin{exercise}
Show that $\{ (\forall x~(P(x) \rightarrow Q(x))), (\exists x~P(x)) \} \proves (\exists x~Q(x))$.
\end{exercise}

\vfill

\begin{exercise}
Show that $\{ (\forall x~(Q(x) \rightarrow R(x))), (\exists x~(P(x) \land Q(x))) \} \proves (\exists x~(P(x) \land R(x)))$.
\end{exercise}

\vfill





\newpage
\subsubsection{Putting them together}
\begin{exercise}
Show that $\{ (\exists x~P(x)), (\forall x~(\forall y~(P(x) \rightarrow Q(y)))) \} \proves (\forall y~Q(y))$.
\end{exercise}

\vfill

\begin{exercise}
Show that $\{ (\exists y~(\forall x~P(x,y))) \} \proves (\forall x~(\exists y~P(x,y)))$.
\end{exercise}

\vfill



\newpage
\begin{exercise}
Show that $\{ (\neg (\exists x~P(x)))  \} \proves (\forall x~(\neg P(x)))$. (De Morgan)
\end{exercise}

\vfill


\begin{exercise}
Show that $\{ (\forall x~(\neg P(x)))  \} \proves (\neg (\exists x~P(x)))$. (De Morgan)
\end{exercise}

\vfill

\newpage
\begin{exercise}
Show that $\{ (\exists x~(\neg P(x)))  \} \proves (\neg (\forall x~P(x)))$. (De Morgan)
\end{exercise}

\vfill

\begin{exercise}
Show that $\{ (\neg (\forall x~P(x)))  \} \proves (\exists x~(\neg P(x)))$. (De Morgan)
\end{exercise}

\vfill



\newpage
\subsection{Soundness and Completeness of Natural Deduction}

\subsubsection{Proving that an inference rule is sound or not sound}

\begin{lemma} \label{lemma_term_meaning}
 Let $t$ be a predicate term.  Let $I$ be an interpretation with domain $dom(I)$.  Let $E$ be an environment.  Then we have that
$t^{(I, E)} \in dom(I)$.
\end{lemma}

\begin{lemma} \label{lemma_term_override}
Let $\alpha$ be a well-formed predicate formula.  Let $t$ be a predicate term.  Let $I$ and $E$ be an interpretation and environment.  Let $x$ be a variable.  Then we have that 
$\alpha [t/x]^{(I, E)} = \alpha ^{(I, E[x \mapsto t^{(I, E)}])}$.
\end{lemma}

\begin{exercise}
Prove that the $\forall$e inference rule is sound.  That is, prove that the entailment holds:
\begin{align}
\{ (\Forall x \alpha) \} \models \alpha [t/x]
\end{align}
where $\alpha $ be a Predicate formula, $x$ is a variable, and $t$ is a Predicate term.
\end{exercise}
\vfill

\begin{exercise}
Prove that the $\exists$i inference rule is sound.  That is, prove that the entailment holds:
\begin{align}
\{ \alpha[t/x] \} \entails (\exists x~\alpha)
\end{align}
where $\alpha$ is a predicate formula, $t$ is a predicate term, and $x$ is a variable.
\end{exercise}
\vfill





\newpage
\begin{exercise}
Prove that the following inference rule is NOT sound.
\begin{align}
\infer[\forall i*]{(\forall x~\alpha)}{ \alpha[t/x]}
\end{align}
where $\alpha$ is a predicate formula, $t$ is a predicate term, and $x$ is a variable.
\end{exercise}
\vfill

\newpage
\begin{exercise}
Prove that the following inference rule is NOT sound.
\begin{align}
\infer[\forall e*]{ \alpha[t/x] }{ (\forall x (\alpha \rightarrow \beta)) & \beta[t/x]}
\end{align}
where $\alpha$ and $\beta$ are predicate formulas, $t$ is a predicate term, and $x$ is a variable.
\end{exercise}


\end{document}





























