\documentclass[12pt,twoside]{article}
\input{macros-course}

\usepackage{amsmath}
\usepackage{latexsym}
\usepackage{graphics}
\usepackage{amsfonts}

\addtolength{\textheight}{.05in}

\begin{document}

\pset{4}{March 11, 2003}{Start of class on Tuesday, March 18}

%\newcommand{\solution}[1]{}                          % hide solutions
\newcommand{\solution}[1]{\textbf{Solution.} #1}    % show solution

\newcommand{\beqn}{\begin{eqnarray*}}
\newcommand{\eeqn}{\end{eqnarray*}}
\newcommand{\ex}[1]{\text{Ex} \left[ #1 \right] }
\newcommand{\pr}[1]{\text{Pr} \left\{ #1 \right\} }
\newcommand{\true}{\text{T}}
\newcommand{\false}{\text{F}}

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem In lecture, we introduced five logical connectives: $\wedge$,
$\vee$, $\neg$, $\rightarrow$, and $\leftrightarrow$.  However, we
could get by with just two connectives: $\neg$ and $\rightarrow$.
Show how to rewrite each of the following propositions using just
those two.

\begin{problemparts}

\problempart $A \wedge B$

\solution{$\neg (A \rightarrow \neg B)$}

\problempart $A \vee B$

\solution{$\neg A \rightarrow B$}

\problempart $A \leftrightarrow B$

\solution{$\neg ((A \rightarrow B) \rightarrow \neg (B \rightarrow A))$}

\problempart $((A \vee \neg B) \wedge (\neg C \rightarrow D)) \leftrightarrow (A \vee C)$

\solution{
\\
$((A \vee \neg B) \wedge (\neg C \rightarrow D)) \leftrightarrow (A \vee C)$ can be re-written as \\
$((\neg A \rightarrow \neg B) \wedge (\neg C \rightarrow D)) \leftrightarrow (\neg A \rightarrow C)$, which can be re-written as \\ 
$\neg ((\neg A \rightarrow \neg B) \rightarrow \neg (\neg C \rightarrow D)) \leftrightarrow (\neg A \rightarrow C)$, which can be re-written as \\
$\neg (( \neg ((\neg A \rightarrow \neg B) \rightarrow \neg ( \neg C \rightarrow D)) \rightarrow (\neg A \rightarrow C)) \rightarrow \neg ((\neg A \rightarrow C) \rightarrow \neg ((\neg A \rightarrow \neg B) \rightarrow \neg (\neg C \rightarrow D))))$.
}

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem Translate the following statements into predicate logic.  For
each, specify the domain of discourse.  In addition to logic symbols,
you may build predicates using arithmetic and relational symbols and
constants.  For example, the statement ``$n$ is an odd number'' could
be translated as $\exists m (2m+1 = n)$ where the domain of discourse
is $\mathbb{Z}$, the set of integers.

\begin{problemparts}

\problempart (Lagrange's Four-Square Theorem) Every natural number is
expressible as the sum of four perfect squares.

\solution{
The domain of discourse is $\mathbb{N}$.

\[
\forall n \exists w \exists x \exists y \exists z (n = w^2 + x^2 + y^2 + z^2)
\]
}

\problempart $p$ is a prime number.

\solution{
The domain of discourse is $\mathbb{N}$.

\[
(p > 1)
\wedge
\neg \left( \exists m \exists n (m > 1 \wedge n > 1 \wedge mn = p) \right)
\]
}

\problempart (Goldbach Conjecture) Every even integer greater than two
is the sum of two primes.

\solution{
The domain of discourse is $\mathbb{N}$.

Denote $prime(p)$ as 
\[
(p > 1)
\wedge
\neg \left( \exists m \exists n (m > 1 \wedge n > 1 \wedge mn = p) \right)
\]

the statement could be translated as 

\[
\forall n 
\left(
((n > 2) \wedge \exists m (n = 2m)) \rightarrow \exists p \exists q (prime(p) \wedge prime(q) \wedge (n = p + q))
\right)
\]
}


\problempart The function $f : \mathbb{R} \mapsto \mathbb{R}$ is
continuous.

\solution{The domain of discourse is $\mathbb{R}$

\[
\forall a \forall x \exists b \forall y
\left(
(a > 0 \wedge b > 0 \wedge |x-y| < b) \rightarrow |f(x) - f(y)| < a
\right)
\]
}

\problempart (Fermat's Last Theorem) There are no nontrivial solutions
to the equation:

\beqn
x^n + y^n & = & z^n
\eeqn

over the natural numbers when $n > 2$.

\solution{
The domain of discourse is $\mathbb{N}$.

\[
\forall x \forall y \forall z \forall n
    \left(
    (x > 0 \wedge y > 0 \wedge z > 0 \wedge n > 2)
    \rightarrow
    \neg (x^n + y^n = z^n)
    \right)
\]
}

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage

\problem Use induction to prove each of the following assertions.

\begin{problemparts}

\problempart For all $n \in \mathbb{N}$:

\beqn
\sum_{k=0}^n k & = & \frac{n(n+1)}{2}
\eeqn

\solution{
\begin{proof}
The proof is by induction on $n$. Let $P(n)$ be the proposition that 
\beqn
\sum_{k=0}^n k & = & \frac{n(n+1)}{2}
\eeqn

Base case: we must prove that $P(0)$ is true; that is, we must show that 
\beqn
\sum_{k=0}^0 k & = & \frac{0(0+1)}{2}
\eeqn
This equation holds because both sides are equal to zero.

Inductive step: for all $n \geq 0$, we assume that $P(n)$ is true in order to prove that $P(n+1)$ is true.

\beqn
\sum_{k=0}^{n+1} k & = & \left( \sum_{k=0}^n k \right) + (n+1) \\
                   & = & \frac{n(n+1)}{2} + (n+1) \\
                   & = & \frac{n(n+1)}{2} + \frac{2(n+1)}{2} \\
                   & = & \frac{(n+1)(n+2)}{2}
\eeqn

Therefore, $P(n)$ holds for all $n \geq 0$ by induction. That is, for all $n \in \mathbb{N}$:

\beqn
\sum_{k=0}^n k & = & \frac{n(n+1)}{2}
\eeqn
 
\end{proof}
}

\problempart For all $n \in \mathbb{N}$ and $x \in \mathbb{R}$ such
that $x \neq 1$:

\beqn
\sum_{k=0}^n x^k & = & \frac{1-x^{n+1}}{1-x}
\eeqn

\solution{
\begin{proof}
The proof is by induction on $n$. Let $P(n)$ be the proposition that $x \neq 1$

\beqn
\sum_{k=0}^n x^k & = & \frac{1-x^{n+1}}{1-x}
\eeqn

Base case: we must prove that $P(0)$ is true; that is, we must show that 
\beqn
\sum_{k=0}^0 x^k & = & \frac{1-x^{0+1}}{1-x}
\eeqn
This equation holds because both sizes are equal to 1 if $x \neq 1$.

Inductive step: for all $n \geq 0$, we assume that $P(n)$ is true in order to prove that $P(n+1)$ is true.

\beqn
\sum_{k=0}^{n+1} x^k & = & \left( \sum_{k=0}^n x^k \right) + x^{n+1} \\
                     & = & \frac{1-x^{n+1}}{1-x} + x^{n+1} \\
                     & = & \frac{1-x^{n+1}}{1-x} + \frac{(1-x)x^{n+1}}{1-x} \\
                     & = & \frac{1-x^{n+2}}{1-x}
\eeqn

Therefore, $P(n)$ holds for all $n \geq 0$ by induction. That is, for all $n \in \mathbb{N}$ and $x \in \mathbb{R}$ such
that $x \neq 1$:

\beqn
\sum_{k=0}^n x^k & = & \frac{1-x^{n+1}}{1-x}
\eeqn

\end{proof}
}

\problempart For all $n \in \mathbb{N}$:

\beqn
1^3 + 2^3 + 3^3 + \ldots + n^3 & = & (1 + 2 + 3 + \ldots + n)^2
\eeqn

\solution{
\begin{proof}
The proof is by induction on $n$. Let $P(n)$ be the proposition that 
\beqn
1^3 + 2^3 + 3^3 + \ldots + n^3 & = & (1 + 2 + 3 + \ldots + n)^2
\eeqn

Base case: $P(0)$ is true vacuously. We must prove that $P(1)$ is true; that is, $1^3 = 1^2$. This equation holds since bothe sides are equal to 1.

Inductive step: for all $n \geq 1$, we assume that $P(n)$ is true in order to prove that $P(n+1)$ is true.

\beqn
\sum_{k=1}^{n+1} k^3 & = & \left( \sum_{k=1}^n k^3 \right) + (n+1)^3 \\
                     & = & \left( \sum_{k=1}^n k^2 \right)^2 + (n+1)^3 \\
                     & = & \left( \frac{n(n+1)}{2} \right)^2 + (n+1)^3 \\
                     & = & \frac{n^2(n+1)^2}{4} + \frac{4(n+1)^3}{4} \\
                     & = & \frac{(n+1)^2(n^2+4n+4)}{4} \\
                     & = & \frac{(n+1)^2(n+2)^2}{4} \\
                     & = & \left( \sum_{k=1}^{n+1} k^2 \right)
\eeqn

Therefore, $P(n)$ holds for all $n \geq 0$ by induction. That is, for all $n \in \mathbb{N}$:

\beqn
1^3 + 2^3 + 3^3 + \ldots + n^3 & = & (1 + 2 + 3 + \ldots + n)^2
\eeqn

\end{proof}
}

\problempart For all $n \in \mathbb{N}$ and $x \in \mathbb{R}$ such
that $x \geq 0$:

\beqn
(1 + x)^n & \geq & 1 + x n
\eeqn

\solution{
\begin{proof}
The proof is by induction on $n$. Let $P(n)$ be the proposition that $x \geq 0$

\beqn
(1 + x)^n & \geq & 1 + x n
\eeqn

Base case: we must prove that $P(0)$ is true; that is, 
\beqn
(1 + x)^0 & \geq & 1 + x 0
\eeqn
which holds since both sides are equal to 1.

Inductive step: for all $n \geq 0$, we assume that $P(n)$ is true in order to prove that $P(n+1)$ is true.

\beqn
(1+x)^{n+1} & = & (1+x)^n (1+x) \\
            & \geq & (1+xn) (1+x) \\
            & = & 1 + x(n+1) + x^2 n \\
            & \geq & 1 + x(n+1)
\eeqn
In the first step, we put the last term out of the product. The second step uses the induction hypothesis.
The third step uses only algebra. The final step uses the fact that $x^2 n \geq 0$, since $x \geq 0$ and $n \geq 0$.

Therefore, $P(n)$ holds for all $n \geq 0$ by induction. That is, for all $n \in \mathbb{N}$ and $x \in \mathbb{R}$ such
that $x \geq 0$:
\beqn
(1 + x)^n & \geq & 1 + x n
\eeqn

\end{proof}
}

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem Use induction to prove the following generalization of the
the law of total expectation.  Let $R$ be a random variable.  Let
$A_1$, $A_2$, $\ldots$, $A_n$ be disjoint events with nonzero
probabilities whose union is the whole sample space.  Then:

\beqn
\ex{R} & = & \sum_{i=1}^n \pr{A_i} \cdot \ex{R \mid A_i}
\eeqn

\solution{
\begin{proof}
The proof is by strong induction on $n$. Let $P(n)$ be the proposition that 
\beqn
\sum_{i=1}^n \pr{A_i} \cdot \ex{R \mid A_i}
   & = & \pr{A_1 \cup \ldots \cup A_n} \cdot \ex{R \mid A_1 \cup \ldots \cup A_n}
\eeqn
where $R$ is a random variable and $A_1$, $\ldots$, $A_n$ are disjoint events with nonzero probabilities.

Base cases: 

we must prove that $P(1)$ is true; that is
\beqn
\pr{A_1} \cdot \ex{R \mid A_1} & = & \pr{A_1} \cdot \ex{R \mid A_1}
\eeqn
which holds since both sides are in the same format.

we must prove that $P(2)$ is true. Let $S$ be the sample space.
\beqn
\lefteqn{\pr{A_1} \cdot \ex{R \mid A_1} + \pr{A_2} \cdot \ex{R \mid A_2}} \quad \\
  & = & \pr{A_1} \left( \sum_{s \in S} R{s} \cdot \pr{s \mid A_1} \right) + 
        \pr{A_2} \left( \sum_{s \in S} R(s) \cdot \pr{s \mid A_2} \right) \\
  & = & \sum_{s \in S} R(s) \left( \pr{s \mid A_1} \pr{A_1} + \pr{s \mid A_2} \pr{A_2} \right) \\
  & = & \sum_{s \in S} R(s) \left( \pr{s \cap A_1} + \pr{s \cap A_2} \right) \\
  & = & \sum_{s \in S} R(s) \left( \pr{(s \cap A_1) \cup (s \cap A_2)} \right) \\
  & = & \sum_{s \in S} R(s) \left( \pr{s \cap (A_1 \cup A_2)} \right) \\
  & = & \sum_{s \in S} R(s) \left( \pr{s \mid A_1 \cup A_2} \pr{A_1 \cup A_2} \right) \\
  & = & \pr{A_1 \cup A_2} \left( \sum_{s \in S} R(s) \cdot \pr{s \mid A_1 \cup A_2} \right) \\
  & = & \pr{A_1 \cup A_2} \cdot \ex{R \mid A_1 \cup A_2}
\eeqn
The first step uses the definition of conditional expectation. 
In the second step we merge the two sums into one. 
The third step uses the definition of conditional probability. 
The fourth step uses the fact that $A_1$ and $A_2$ are disjoint events. 
The fifth step uses the distributive laws. 
The sixth step uses the definition of conditional probability. 
In the seventh step we move the common term out of the summation.
The last step uses the definition of conditional expectation.

Inductive step: for all $n \geq 2$, 
we assume that $P(1)$, $\ldots$, $P(n)$ are true in order to prove that $P(n+1)$ is true.
\beqn
\lefteqn{\sum_{i=1}^{n+1} \pr{A_i} \cdot \ex{R \mid A_i}} \\
  & = & \left( \sum_{i=1}^n \pr{A_i} \cdot \ex{R \mid A_i} \right) + \pr{A_{n+1}} \cdot \ex{R \mid A_{n+1}} \\
  & = & \pr{A_1 \cup \ldots \cup A_n} \cdot \ex{R \mid A_1 \cup \ldots \cup A_n} + 
        \pr{A_{n+1}} \cdot \ex{R \mid A_{n+1}} \\
  & = & \pr{A_1 \cup \ldots \cup A_{n+1}} \cdot \ex{R \mid A_1 \cup \ldots \cup A_{n+1}}
\eeqn
In the first step we put the last term out of the summation. 
The second step uses the induction hypothesis that $P(n)$ is true.
The last step uses the induction hypothesis that $P(2)$ is true and the fact that $A_1 \cup \ldots \cup A_n$ and $A_{n+1}$ are disjoint events, since $A_1$, $\ldots$, $A_{n+1}$ are disjoint events.

Therefore, $P(n)$ holds for all $n \geq 1$ by strong induction. That is, 
\beqn
\sum_{i=1}^n \pr{A_i} \cdot \ex{R \mid A_i}
   & = & \pr{A_1 \cup \ldots \cup A_n} \cdot \ex{R \mid A_1 \cup \ldots \cup A_n}
\eeqn
where $R$ is a random variable and $A_1$, $\ldots$, $A_n$ are disjoint events with nonzero probabilities.

Since the union of $A_1$, $\ldots$, $A_n$ is the whole sample space $S$, 

\beqn
\sum_{i=1}^n \pr{A_i} \cdot \ex{R \mid A_i}
   & = & \pr{A_1 \cup \ldots \cup A_n} \cdot \ex{R \mid A_1 \cup \ldots \cup A_n} \\
   & = & \pr{S} \cdot \ex{R \mid S} \\
   & = & \ex{R}
\eeqn

\end{proof}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage

\problem We intended to ask you to prove an analogous generalization
of the law of total probability.  But, apparently, some subset of the
6.042 tutorials made off with it:

\textbf{Theorem 1 \ (Law of Total Probability)}  Let $E$ be...

\bigskip
\begin{center}
\em{\small{MMWWwaahAHAHAH! It's ourz now suckahs!}}
\end{center}
\bigskip

You see the problem.  The following tutorial sections are under
suspicion:

\begin{itemize}
\item Empty Set
\item Cthulhu
\item Just Fines
\item Amazings
\item Burninator
\item Mostly Harmless
\end{itemize}

The course staff has recorded the available evidence in predicate
logic, where the domain of discourse is the set of suspect tutorial
sections.  The predicate $G$ is true for guilty sections, the
predicate $S$ is true for sections tutored by Sam Daitch, and the
predicate $F$ is true for sections that meet on Friday.

\newcommand{\guilty}{G}
\newcommand{\sam}{S}
\newcommand{\friday}{F}

\begin{enumerate}

\item $\exists x \exists y \exists z
    (x \neq y \wedge y \neq z \wedge x \neq z
     \wedge \guilty(x) \wedge \guilty(y) \wedge \guilty(z))$

\solution{At least three different tutorials are guilty.}

\item $\forall x (\neg \guilty(x) \rightarrow \exists y \exists z
    (x \neq y \wedge y \neq z \wedge x \neq z \wedge
     \neg (\guilty(y) \wedge \guilty(z))))$

\solution{If there exists one tutorial that is not guilty, then at least two tutorials are not guilty.}

\item $\neg \forall x (\sam(x) \rightarrow \neg \guilty(x))$

\solution{At least one of Sam's tutorials is guilty.}

\item $\exists x (\neg \sam(x) \wedge  \guilty(x))$

\solution{At least one of the guilty tutorials is not Sam's.}

\item $\guilty(\text{Empty Set}) \rightarrow \neg \guilty(\text{Cthulhu})$

\solution{If the Empty Set is guilty, then Cthulhu is not.}

\item $\forall x
    ((\neg \sam(x) \wedge \neg \friday(x)) \rightarrow \neg \guilty(x))$

\solution{If a tutorial is not Sam's and does not meet on Friday, then
it is not guilty.  In other words, Mostly Harmless is not guilty.}

\item $\guilty(\text{Burninator}) \rightarrow \guilty(\text{Mostly Harmless})$

\solution{If Burninator is guilty, then so is Mostly Harmless.}

\item $\neg (\neg \guilty(\text{Just Fines}) \vee \guilty(\text{Cthulhu}))$

\solution{The Just Fines are guilty and Cthulu is not.}

\end{enumerate}

The list of tutorial assignments on the course web page may be helpful
to you as well.

\begin{problemparts}

\problempart Translate each assertion above into an equivalent English
statement.  Make the statements as simple as you can.

\problempart Which tutorial sections, if any, swiped the law of total
probability?  Explain your reasoning.

\solution{
Most Harmless is not guilty by 6.
Burninator is not guilty by 7 and the fact that Most Harmless is not guilty.
Cthulhu is not guilty and Just Fines is guilty by 8.
Empty Set and Amazings are guilty by 1.

2, 3, 4, 5 are satisfied.
}

\problempart State the law of total probability, generalized as the
law of total expectation was in the preceding problem.

\solution{Law of total probability:
Let E be an event. Let $A_1$, $A_2$, $\ldots$, $A_n$ be disjoint events with nonzero probabilities whose union is the whole sample space. Then

\beqn
\pr{E} & = & \sum_{i=1}^n \pr{A_i} \cdot \pr{E \mid A_i}
\eeqn
} 

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage

\problem A group of $n \geq 1$ people can be divided into disjoint
teams, each containing either 4 or 7 people.  What are all the
possible values of $n$?  Prove that your answer is correct.

\solution{
Based on the following observations
\beqn
\lefteqn{4 = 4} \\
\lefteqn{7 = 7} \\
\lefteqn{8 = 4 + 4} \\
\lefteqn{11 = 4 + 7} \\
\lefteqn{12 = 4 + 4 + 4} \\
\lefteqn{14 = 7 + 7} \\
\lefteqn{15 = 4 + 4 + 7} \\
\lefteqn{16 = 4 + 4 + 4 + 4} \\
\lefteqn{18 = 4 + 7 + 7} \\
\lefteqn{19 = 4 + 4 + 4 + 7} \\
\lefteqn{20 = 4 + 4 + 4 + 4 + 4} \\
\lefteqn{21 = 7 + 7 + 7} \\
\eeqn
we claim and will prove the statement ``A group of $n \geq 18$ people can be divided into disjoing teams, each containing either 4 or 7 people''.

\begin{proof}
The proof is by strong induction on $n$. Let $P(n)$ be the proposition that a group of $n \geq 18$ people can be divided into disjoing teams, each containing either 4 or 7 people.

Base cases:
$P(18)$ is true since $18 = 4 + 7 + 7$. 
$P(19)$ is true since $19 = 4 + 4 + 4 + 7$. 
$P(20)$ is true since $20 = 4 + 4 + 4 + 4 + 4$.
$P(21)$ is true since $21 = 7 + 7 + 7$.

Inductive steps:
For all $n \geq 21$, we assume that $P(18)$, $P(19)$, $\ldots$, $P(n)$ are true in order to prove that $P(n+1)$ is true.
Since $n+1 = (n-3) + 4$ and $n-3 \geq 18$, $n+1$ people can be first divided into 2 disjoint teams with 4 people and $n-3$ people. The team with $n-3$ people can be further divided into disjoint teams with 4 or 7 people by the induction hypothesis. That is, $P(n+1)$ is true.

Therefore, $P(n)$ holds for all $n \geq 18$ by strong induction.

All the possible values of $n$ are 4, 7, 8, 11, 12, 14, 15, 16, and $\geq 18$.
\end {proof}
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem (Optional) This problem is credited to Sir Aurthur Eddington,
noted astronmer and physicist: ``If $A$, $B$, $C$, and $D$ each speak
the truth with probability $\frac{1}{3}$ and $A$ affirms that $B$
denies that $C$ declares that $D$ is a liar, what is the probability
that $D$ was speaking the truth?''  Solve this problem, making the
following assumptions:

\begin{itemize}

\item All four people made statements.

\item $A$, $B$, and $C$ each made a statement that either affirmed or
denied the statement that followed.

\item A lying affirmation is a denial, and a lying denial is an
affirmation.

\item The people lie mutually independently.

\end{itemize}

\end{problems}

\solution {
Let us define the following propositions:

\begin{itemize}

\item proposition R is ``person A speaks the truth''.

\item proposition S is ``person B speaks the truth''.

\item proposition T is ``person C speaks the truth''.

\item proposition W is ``person D speaks the truth''.

\item proposition X is ``person C declares that person D is a liar''. That is, ``person C declares $\neg W$''. 

\item proposition Y is ``person B denies X''.

\item proposition Z is ``person A affirms Y''

\end{itemize}

We can construct a truth table of 16 different combinations of T's or F's for R, S, T, and W, which represent 16 outcomes.

\[
\begin{array}{c|cccc|ccc|c}
outcome & R & S & T & W & X & Y & Z & Pr \\
\hline
1 & \true & \true & \true & \true & \false & \true & \true & \frac{1}{81} \\
2 & \true & \true & \true & \false & \true & \false & \false & \frac{2}{81} \\
3 & \true & \true & \false & \true & \true & \false & \false & \frac{2}{81} \\
4 & \true & \true & \false & \false & \false & \true & \true & \frac{4}{81} \\
5 & \true & \false & \true & \true & \false & \false & \false & \frac{2}{81} \\
6 & \true & \false & \true & \false & \true & \true & \true & \frac{4}{81} \\
7 & \true & \false & \false & \true & \true & \true & \true & \frac{4}{81} \\
8 & \true & \false & \false & \false & \false & \false & \false & \frac{8}{81} \\
9 & \false & \true & \true & \true & \false & \true & \false & \frac{2}{81} \\
10 & \false & \true & \true & \false & \true & \false & \true & \frac{4}{81} \\
11 & \false & \true & \false & \true & \true & \false & \true & \frac{4}{81} \\
12 & \false & \true & \false & \false & \false & \true & \false & \frac{8}{81} \\
13 & \false & \false & \true & \true & \false & \false & \true & \frac{4}{81} \\
14 & \false & \false & \true & \false & \true & \true & \false & \frac{8}{81} \\
15 & \false & \false & \false & \true & \true & \true & \false & \frac{8}{81} \\
16 & \false & \false & \false & \false & \false & \false & \true & \frac{16}{81} \\
\end{array}
\]

By assigning the probability to each of the outcomes, we have

\noindent $\pr{\text{``D was speaking the truth given A affirms that B denies that C declares that D is liar''}} \\
   = \pr{\text{W is true} \mid \text{Z is true}}
   = \frac{13}{41}$ 
}

\end{document}
