\documentstyle[11pt]{article}
%\pagestyle{}                   % no page #'s
\setlength{\topmargin}{0.5 in}     % try to get 0.5'' top and bottom margin
\setlength{\textheight}{9 in}
\setlength{\footskip}{0pt}
\setlength{\footheight}{1 in}
\setlength{\headsep}{0pt}
\setlength{\headheight}{0pt}
\begin{document}\
\hspace*{\fill}{\LARGE{\bf Take Home Final}}\hspace*{\fill}
\par
\vspace {.1 in}
\hspace*{\fill}{\large{\bf 24.241}}\hspace*{\fill}
\par
\vspace {.05 in}
\hspace*{\fill}{\large{\bf Logic I}}\hspace*{\fill}
\par
\vspace{.1 in}
\hspace*{\fill}{\large{\bf Andr\'e DeHon}}\hspace*{\fill}
\par
\vspace{.3 in}
\normalsize
\par

%\forall \exists

% note: fix or's replace \vee with proper symbol

{\large {\bf Problem 1 -}}  Supposing ``Px'' to mean ``x is a pundit'',
translate the following into clear and idiomatic English: \par
$\exists x \exists y \exists z \forall w (Pw \rightarrow (w=x \vee w=y \vee w=z))$.
\par
\vspace{0.1 in}

$\exists x \exists y \exists z \forall $w$ (Pw \rightarrow (w=x \vee w=y \vee w=z))$ claims that if $w$ is an element of the domain such that $w$ is a pundit,
then $w$ must be identically one of three specific elements of the domain.
Since the three elements of which $w$ would have to be if it were a pundit
are not constrained to be different, then there can be at most 3 pundit's
in the domain; since the existentially quantified elements only apear in
the consequent of the conditional, the symboliztion does not constrain
that there is any element that satisfies ``$Px$''.  Thus under the specified 
extension for ``$Px$'',  the above expression translates to:
\par
\vspace{0.1 in}
{\bf There are at most three pundits. }
\par
\par 
\vspace {0.5 in}

\newpage

{\large {\bf Problem 2 -}}  Symbolize: Everyone who loves a parent of each cat is kinder than someone who loves a parent of each dog.  
\par
\vspace {0.1 in}

{\bf Predicate letters used:}
\par
%\begin{tabular}{l c l}
Lxy  means  x loves y           \par
Pxy  means  x is a parent of y  \par
Kxy  means  x is kinder than y  \par
Cx   means  x is a cat          \par
Dx   means  x is a dog          \par
Hx   means  x is a human being  \par
%\end{tabular}
\par
\vspace {0.1 in}
{\bf Ambiguities}
\par
	The use of ``each'' in the original statement is ambiguous.
For the sake of my symbolization, I assummed that the ``each'' refered
to every or all (i.e. ``a parent of each cat'' is equivalent to
``a parent of every cat'').
\par
	In my symbolization ``everyone'' and ``someone'' were constrained to
refering to people only, as one might reasonably expect.
\par
\vspace {0.1 in}

{\bf Reduction to Symboliziation}
\par

\begin{enumerate}

\item Everyone who loves a parent of each cat is kinder than someone who
loves a parent of each dog.

\item (Everyone who loves a parent of every cat) is kinder than (someone who loves a parent of every dog)

\item $(\forall x) ( Hx \wedge (x  \hspace {5 pt} {\normalsize loves \hspace {5 pt} a\hspace {5 pt} parent \hspace {5 pt}of \hspace {5 pt}each\hspace {5 pt} cat} ) \rightarrow \newline
(\exists y)[Kxy \wedge Hx \wedge ( y {\normalsize \hspace {5 pt}  \hspace {5 pt}loves \hspace {5 pt}a \hspace {5 pt}parent \hspace {5 pt}of \hspace {5 pt}every \hspace {5 pt} dog} )])$

\item $(\forall x) ( Hx \wedge (\forall w) ( w  {\normalsize \hspace {5 pt}is \hspace {5 pt}a \hspace {5 pt}cat}  \rightarrow ( x {\normalsize \hspace {5 pt}loves \hspace {5 pt}a \hspace {5 pt}parent \hspace {5 pt}of\hspace {5 pt}} w)) \rightarrow \newline
(\exists y) [Kxy \wedge Hx \wedge (\forall z) (z {\normalsize \hspace {5 pt}is \hspace {5 pt}a \hspace {5 pt}dog} \rightarrow (y {\normalsize \hspace {5 pt}loves \hspace {5 pt}a \hspace {5 pt}parent \hspace {5 pt} of} \hspace {5 pt} z))])$

\item $(\forall x) ( Hx \wedge (\forall w) ( Cw  \rightarrow (\exists s)
(Cs \wedge Psw \wedge Lxw)) \rightarrow \newline
(\exists y) [Kxy \wedge Hy \wedge (\forall z) (Dz \rightarrow (\exists r)(Dr \wedge Prz \wedge
Lyr))])$



\end{enumerate}
\vspace {0.1 in}

{\bf Result:} \par
\vspace {0.05 in}
$(\forall x) ( Hx \wedge (\forall w) ( Cw  \rightarrow (\exists s)
(Cs \wedge Psw \wedge Lxw)) \rightarrow$ \par \hspace{0.7 in} $
(\exists y) [Kxy \wedge Hy \wedge (\forall z) (Dz \rightarrow (\exists r)(Dr \wedge Prz \wedge
Lyr))])$
\par

\newpage

{\large {\bf Problem 3 -}}  Symbolize: No one admires all and only those persons who admire none of their own admirers.  Deduce it if it is valid; otherwise give an interpretation in which it is false.
\par
\vspace{0.1 in}
{\bf Possiblibilities for parsing statement} \par
\begin{enumerate}

\item (No one admires all) $\wedge$ (no one admires only those persons who
admire none of their own admirers).

\item No one admires all and admires only those persons who admire none of their own admirers.

\item No one admires (all and only) those persons who admire none of their own admirers. [Note: here ``all and only'' is treated like ``just'' or ``exactly'']

\end{enumerate}

\par
	All three of these ways of parsing the statement are awkward.
I chose to go with three because it seemed the least awkward and the least
contradictory in nature.
\par
\vspace {0.1 in}
{\bf Symbolization:} \par

Axy means x admires y
\par
Note:  the ``all and only'' translates into the biconditional.
\par

	$\neg (\exists y) (\forall x) ( (\forall w) (Awx \rightarrow \neg
Axw) \leftrightarrow Ayx)$

\par
\vspace{0.1 in}
{\bf Test statement for Validity} \par
Approach: The statement is valid just in case the negation of the statement
is unsatisfiable;  to test for validity, I start with the negation of the
statement and attempt to demonstrate that it is unsatifiable.  If this fails,
the interpretation that will satisfy the result of the deduction will also
be one underwhich the original statement was false. \par

[1]     (1)  $(\exists y) (\forall x) ( (\forall w) (Awx \rightarrow \neg Axw) \leftrightarrow Ayx)$ \hspace{0.7 in}     P \par

[2]     (2)  $(\forall x) ( (\forall w) (Awx \rightarrow \neg Axw) \leftrightarrow Ayx)$ \hspace{1 in}     P \par

[2]     (3)  $(\forall x) ( \neg Ayx \wedge (\forall w) (Awx \rightarrow \neg Axw) \vee $  \par \hspace {1.0 in} $
Ayx \wedge \neg (\forall w) (Awx \rightarrow \neg Axw))$      \hspace{0.4 in}(2) TF \par

[2]     (4)  $  \neg Ayx \wedge (\forall w) (Awx \rightarrow \neg Axw) \vee  $\par \hspace{1.0 in}$
 Ayx \wedge \neg (\forall w) (Awx \rightarrow \neg Axw)$      \hspace{0.5 in}(3) UI \par
[5]     (5)  $ \neg [Ayx \wedge \neg (\forall w) (Awx \rightarrow \neg Axw)]$ \hspace{1.1 in} P \par
[2,5]   (6)  $ \neg Ayx \wedge (\forall w) (Awx \rightarrow \neg Axw) $   \hspace{0.7 in}(4)(5) TF \par
[2,5]   (7) $ \neg Ayx $ \hspace{2.4 in} (6) TF \par
[2,5]   (8) $ (\forall w) (Awx \rightarrow \neg Axw) $  \hspace{1.4 in} (6) TF \par
[2,5]   (9) $ (Aww \rightarrow \neg Aww) $   \hspace{1.7 in}(8) UI  \par
[2,5]   (10) $ (\neg Aww \vee \neg Aww) $   \hspace{1.6 in}(9) TF  \par
[2,5]   (11) $ \neg Aww  $   \hspace{2.2 in} (10) TF  \par

\vspace{0.2 in}
\newpage
At this point in the deduction, it is obvious that there are interpretations
under which the negation (which the deduction began with) is satisfiable;
thus the original statement cannot be valid.
\{Note: Discharging [5] will only add a disjunct to the result and then
EII can be used to make the final result depend on 1 rather than 2.\}  
\par
\vspace{0.1 in}
{\bf Counterexample to Validity}
\par
	To Illustrate that the statement is not valid, consider the following
interpretation: \par

Universe of Discourse = finite group of people \par

The extension of A is defined as follows: 
	There is exactly one person in the universe, call him $\beta$, that admires no one; everyone else admires everyone.
\par

	$\neg (\exists y) (\forall x) ( (\forall w) (Awx \rightarrow \neg
Axw) \leftrightarrow Ayx)$

	Since $\beta$ admires no one and everyone else admires everyone,
$(\forall w) (Awx \rightarrow \neg Axw)$ is satisfied by $\beta$ only
(i.e. $\beta$ admires no one since everyone admires him).  Since everyone
except $\beta$ admires $\beta$, the outermost consequent is satisfied
(i.e. $Ayx$ for $x=\beta$ since x is the only one for whom the antecedent
is satisfied) by all members of the universe except $\beta$.  Since this
is the case, the statement is certainly true disregarding the negation;
hence when the full statement including the initial negation is false. \par
	Since there is an interpretation under which this statement is
demonstrated to be false, the statement cannot be valid.

\newpage
{\large {\bf Problem 4a -}}  Can $\vee$ be defined in terms of $\rightarrow$ alone? \par
\vspace{0.1 in}
Consider: \par
\vspace{0.1 in}
\begin{tabular}{c|c|c|c|c} 
$A$ & $B$ & $A \rightarrow f$ & $(A \rightarrow f) \rightarrow B $ & $A \vee B$ \\ \hline
T & T & F & T & T \\
T & F & F & T & T \\
F & T & T & T & T \\
F & F & T & F & F \\
\end{tabular}
\par \vspace {0.1 in}
[note: $f$ = false] \par
\vspace{0.2 in}
Obviously $(A \rightarrow f) \rightarrow B $ is equivalent to 
$A \vee B$.  Hence $\vee$ can be expressed in terms of $\rightarrow$ alone

\vspace{0.5 in}

{\large {\bf Problem 4b -}}  Can $\wedge$ be defined in terms of $\rightarrow$ and $\leftrightarrow$ alone?
\vspace{0.1 in}

Consider:
\vspace{0.1 in}

\begin{tabular}{c|c|c|c|c|c} 
$A$ & $B$ & $B \leftrightarrow f$ & $A \rightarrow (B \leftrightarrow f) $ &  $(A \rightarrow (B \leftrightarrow f )) \leftrightarrow f $ & $A \wedge B$  \\ \hline
T & T & F & F & T & T \\
T & F & T & T & F & F \\
F & T & F & T & F & F \\
F & F & T & T & F & F \\
\end{tabular}
\par
\vspace{0.2 in}
Obviously  $A \wedge B$ is equivalent to $(A \rightarrow (B \leftrightarrow f )) \leftrightarrow f $.  Hence $\wedge$ can be expressed in terms of $\rightarrow$ and $\leftrightarrow$ alone.

\vspace{0.5 in}

{\large {\bf Problem 4c -}}  Can $\rightarrow$ be defined in terms of $\leftrightarrow$ and $\neg$ alone?
\vspace{0.1 in}

{\bf No}.  The biconditional ($\leftrightarrow$) is a connector that is insensitive to the order of its consituent statements (i.e. $A \leftrightarrow B$
is equivalent to $B \leftrightarrow A$, whereas $A \rightarrow B$
is not equivalent to $B \rightarrow A$).  Because of this, it is 
impossible to extract a relation from the biconditional that treats its
components unequally, such as the conditional ($\rightarrow$). Since the
negation operation ($\neg$) operates on only one statement letter, it
cannot be used to overcome this limiting behavior of the biconditional.  It is instructional to note: 
$\neg (A \leftrightarrow B)$ is equivalent to $\neg A \leftrightarrow B$ is equivalent to $A \leftrightarrow \neg B$.  Hence $ \leftrightarrow $ and $\neg$ alone are not adequate to define $\rightarrow$.

\vspace{0.1 in}
\newpage
{\large {\bf Problem 5 -}}  Is the following inference valid: \par
For all x, for all y, x is a minimal element of y iff both x is an element of
y and no element of x is an element of y. \par
For all x, x is grounded iff everything of which x is an element has a minimal
element. \par
Therefore, if all elements of x are grounded, then so is x. \par
\vspace{0.2 in}
{\bf Symbolization} \par \vspace {0.1 in}
\vspace{0.1 in}
x $\in$ y  means  x is an element of y \par
Mxy  means  x is a minimal element of y \par
Gx  means x is grounded \par
\vspace{0.1 in}
$(\forall x)(\forall y)(Mxy \leftrightarrow ((x \in y) \wedge (\forall w)(w \in x \rightarrow \neg w \in y)))$ \par
$(\forall x) (Gx \leftrightarrow (\forall w)(x \in w \rightarrow (\exists y) Myw))$ \par \vspace {0.05 in}
% put line here
\hrule 
\vspace {0.05 in}
$(\forall x)((\forall w)(w \in x \rightarrow Gw)) \rightarrow Gx) $ \par

\vspace{1 in}
\hspace*{\fill}{\bf \{ Deduction on following page \} }\hspace*{\fill}


\newpage
{\bf Deduction } \par
\vspace {0.1 in}

[1]     (1) $(\forall x)(\forall y)(Mxy \leftrightarrow ((x \in y) \wedge (\forall w)(w \in x \rightarrow \neg w \in y)))$  \hspace{0.5 in}    P \par
[2]     (2) $(\forall x) (Gx \leftrightarrow (\forall w)(x \in w \rightarrow (\exists y) Myw))$  \hspace{1.5 in}    P \par
[3]     (3)  $(\forall w)(w \in x \rightarrow Gw) $ \hspace{2.75 in}   P \par
[3]     (4)  $w \in x \rightarrow Gw $ \hspace{2.9 in}  (3) UI  \par
[2]     (5) $ Gx \leftrightarrow (\forall w)(x \in w \rightarrow (\exists y) Myw)$  \hspace{2 in}    P \par
[2]     (6) $ Gw \leftrightarrow (\forall z)(w \in z \rightarrow (\exists y) Myz)$  \hspace{1.1 in}    P (Relettering) \par
[7]     (7) $ w \in x$ \hspace{3.8 in} P \par
[3,7]   (8) $Gw$ \hspace{3.2 in} (4)(7) TF \par
[2,3,7] (9) $(\forall z)(w \in z \rightarrow (\exists s) Msz)$  \hspace{0.8 in}    (6)(8) TF (Relettering)\par
[2,3,7] (10) $w \in y \rightarrow (\exists s) Msy$  \hspace{2.3  in}    (9) UI \par
[11]    (11) $(\forall z)(x \in z \rightarrow (\exists y) Myz)$  \hspace{2.3           in}    P  \par
[11]    (12) $x \in y \rightarrow (\exists s) Msy$  \hspace{1.5 in}    (12) UI  (Relettering) \par
[]      (13) $(\forall z)(x \in z \rightarrow (\exists y) Myz)  \rightarrow
(x \in y \rightarrow (\exists s) Msy)$ \par \hspace{3.0 in}    [11] (12) D  (Relettering) \par
[2]     (14) $(x \in y \rightarrow (\exists s) Msy) \rightarrow Gx $ \hspace{1.7 in}    (5)(13) TF \par
[1]     (15) $(\forall y)(Mxy \leftrightarrow ((x \in y) \wedge (\forall w)(w \in x \rightarrow \neg w \in y))$  \hspace{0.5 in}  (1)  UI \par
[1]     (16) $Mxy \leftrightarrow ((x \in y) \wedge (\forall w)(w \in x \rightarrow \neg w \in y)$  \hspace{0.8 in}  (15)  UI \par
[17]    (17) $(\forall w)(w \in x \rightarrow \neg w \in y)$  \hspace{2.4 in} P \par
[17]    (18) $ w \in x \rightarrow \neg w \in y $  \hspace{2.4 in} (17) UI \par
[]      (19) $(\forall w)(w \in x \rightarrow \neg w \in y) \rightarrow (w \in x \rightarrow \neg w \in y)$  \hspace{0.5 in} [17] (18) D \par
[1]     (20) $ (x \in y) \wedge (w \in x \rightarrow \neg w \in y) \rightarrow Mxy $ \hspace{0.9 in} (16)(19) TF \par
[21]    (21) $ x \in y$ \hspace{3.5 in} P \par
[1,21]     (22) $ (w \in x \rightarrow \neg w \in y) \rightarrow Mxy $ \hspace{1.3 in} (20)(21) TF \par
[23]      (23)  $w \in y$ \hspace{3.6 in} P \par
[2,3,7,23] (24) $(\exists s) Msy$  \hspace{2.3  in}    (10)(23) TF \par
[2,3,7,23] (25) $x \in y \rightarrow (\exists s) Msy$  \hspace{2 in}    (24) TF \par
[2,3,7] (26) $w \in y \rightarrow (x \in y \rightarrow (\exists s) Msy)$  \hspace{1.2  in}    [23] (25) D \par
[27]      (27)  $ \neg (w \in y)$ \hspace{3.4 in} P \par
[1,21,27] (28)  $Mxy$    \hspace{2.7 in}     (22)(27) TF \par
[1,21,27] (29) $(\exists s)(Msy)$ \hspace{2.5 in}  (28) EG \par
[1,27]    (30) $x \in y \rightarrow (\exists s)(Msy)$ \hspace{1.9 in} [21] (29) D \par
[1]       (31) $ \neg (w \in y) \rightarrow (x \in y \rightarrow (\exists s) Msy)$  \hspace{1.2 in}    [27] (30) D \par
[1,2,3,7] (32)  $x \in y \rightarrow (\exists s) Msy$  \hspace{1.8  in}    (26)(31) TF \par
[1,2,3,7] (33) $Gx$ \hspace{2.7 in} (14)(32) TF \par
[1,2,7] (34) $(\forall w)(w \in x \rightarrow Gw) \rightarrow Gx$ \hspace{1.5 in}  [3](33) D  \par
[1,2] (35) $w \in x \rightarrow (\forall w)(w \in x \rightarrow Gw) \rightarrow Gx$ \hspace{1 in}  [7](34) D  \par
[1,2] (36) $(\forall w)(w \in x \rightarrow Gw) \rightarrow Gx$ \hspace{1.7 in}  (35) TF  \par
[1,2] (37) $((\forall x)(\forall w)(w \in x \rightarrow Gw) \rightarrow Gx)$ \hspace{1.2 in}  (36) UI  \par
\vspace{ 0.2 in}
	Therefore, the deduction is valid as the conclusion can be deduced
depending only on the premises.

\newpage
{\large {\bf Problem 6 -}}  Is there a satisfiable schema in prenex normal form, in whose prefix all existential quantifies precede all universal quantifies, that is ture in no interpretation whose domain is finite?  \par
\vspace{0.1 in}

	That is we want to know if a schema exists of the form \par
 $\Phi = (\exists w_1)(\exists w_2)(\exists w_3) \cdots (\exists w_i)(\forall x_1)(\forall x_2)(\forall x_3) \cdots (\forall x_j) \phi w_1 w_2 \cdots w_i x_1 x_2 \cdots x_j $ such that the schema is satisfiable in an infinite domain, but false in all 
interpretations whose domain are finite. \par
	Let us start by assuming that the $\Phi$ is satisfiable.
By the {\bf Central Lemma}, we know that it must be impossible to 
obtain by strict UI and strict EII a number of quantifier-free
schemata whoe conjunction is truth-functionally unsatisfiable.
Further, because of the special form of $\Phi$, we know that application
of the rigid plan to $\Phi$ to test $\Phi$ for satisfiability will
eventually terminate after a finite number of steps.  Hence there are
a finite number of quantifier free schema derived from $\Phi$ by the 
rigid plan.  Since $\Phi$ is known to be satisfiable, the {\bf Central
Lemma} constrains that all conjunctions of subsets of the derived schema
be satisfiable.  Since this is the case and there are a finite number
of quantifier free schema derived in this maner. This mutual satisfiability
holds for at least one finite domain of elements; that is $\Phi$ holds
for the set of elements that are contained in the derived schema.  \par
	This immediately demonstrates that there must be an interpretation 
of $\Phi$ whose domain is finite.  Since this was derived only from the 
assumtions of the form, $\Phi$, and the fact that $\Phi$ was satisfiable
in the infinite domain, it is apparent the answer to the original question
is ``no''.  That is to say there is no satisfiable schema in prenex normal,
in whose existential quantifiers precede all universal quantifiers, that is 
true in no interpretation whose domain is finite.

\newpage
{\large {\bf Problem 7 -}}  Is there a schema containing only one-place predicate letters (and hence not '=') and one free variable, of which the existential, but not the universal, quantification with respect to the variable is valid?
\par \vspace {0.1 in}

	We want to know if there is an $R$, constructed entirely from 
mondaic predicate letters with free $v$ and $v$ only free, 
such that $(\forall v)R$ is not valid while $(\exists v)R$ is valid. \par
	Let us start with an $R$ such that $(\exists v)R$ is valid.  This
means for every universe of discourse and all interpretations of the
predicate letters contained in $R$, and every assignment of values to $v$,
$(\exists v)R$ is true.  All of the predicate letters in $R$ are 
constrained to be one-place.  Taking these facts into consideration,
we can see that $R$ cannot constrain relations between variables (since
there are no multiple place predicate letters).  Then in order for $R$ to 
have the generality necessary to be valid when existentially quantified, 
$R$ must be equivalent in form
to a truth functional logic validity (i.e. treating $Px$'s as $A_{i}$'s,
$R$ must have the same form as some truth functional validity).  Since
this must be the case, $R$ is valid whenever $(\exists v)R$ is valid
(as it has identical form to a truth functional validity).  Now since
the free $R$ is valid, then the universal, $(\forall v) R$ is also
valid as we know that an open schema is valid just in case its
universal quantification is valid. \par
	Thus we have derived that in order for $(\exists v)R$ to be
valid,  $(\forall v)R$ must also be valid.  Then we must conclude that there is
no such schema containing only one-place predicate letters and one
free variable, of which the existential, but not the universal, quantification
with respect to the free variable is valid.


	


\newpage

{\large {\bf Problem 8 -}}  Find a simpler equivalent of: \par
 $\forall w \forall x \forall y \forall z (Awxyz \rightarrow (Awxyz \wedge Awxzy \wedge Awyxz \wedge Awyzx \wedge Awzxy \wedge Awzyx \wedge Axwyz \wedge Axwzy \wedge Axywz \wedge Axyzw \wedge Axzwy \wedge Axzyw \wedge Aywxz \wedge Aywzx \wedge Ayxwz \wedge Ayxzw \wedge Ayzwx \wedge Ayzxw \wedge Azwxy \wedge Azwyx \wedge Azxwy \wedge Azxyw \wedge Azywx \wedge Azyxw))$.
\vspace{0.1 in}

	Upon a brief examination of the above schema, it is easy to see that 
for all elements of the universe if there is an $A$ that is true for a particular
set of four elements in a specified order, it is also true for any ordering.
Hence ``$Awxyz$'' implies all ``A$\phi$'' where $\phi$ is any permutation of $wxyz$.   \par
	It is also easy to see that by instantiating ``$Awxyz$'' with the various $\phi$, that any ``$A\phi$'' implies all others and hence the above
can be more expressive as a chain of biconditionals.  Hence this is 
equivalently: \par
 $\forall w \forall x \forall y \forall z (Awxyz  \leftrightarrow Awxzy \leftrightarrow Awyxz \leftrightarrow Awyzx \leftrightarrow Awzxy \leftrightarrow Awzyx \leftrightarrow Axwyz \leftrightarrow Axwzy \leftrightarrow Axywz \leftrightarrow Axyzw \leftrightarrow Axzwy \leftrightarrow Axzyw \leftrightarrow Aywxz \leftrightarrow Aywzx \leftrightarrow Ayxwz \leftrightarrow Ayxzw \leftrightarrow Ayzwx \leftrightarrow Ayzxw \leftrightarrow Azwxy \leftrightarrow Azwyx \leftrightarrow Azxwy \leftrightarrow Azxyw \leftrightarrow Azywx \leftrightarrow Azyxw)$. \par
	Viewing the problem in this manner, simplifying the symbolization reduces to an elementary problem in group theory.  That is what we want to find is
the minimal set of generator permutations for $S_{4}$ (i.e. the set of permutations of 4 elements). \par
	It is fairly elementary to conclude the the set of pairwise swaps
(i.e. \{(12), (13), (14), (23), (24), (34)\} [where (12) represents
the permutation that carries 1234 to 2134, and (13) carries 1234 to 3124, etc.]) is an adequate set from
which to construct all elemenst of $S_{4}$.  The basic question then reduces
to, ``is there a smaller such set of generators''. \par
	It is a subtler fact, but there is, in fact, a smaller set.  Particularly, the set \{(1234), (12)\} is adequate.  To see this, it is necessary simply to
note first that all of the pairwise swaps can be successively generated from
this set  (i.e. (1234)(12)(1234)$^{-1}$ = (14), (1234)(14)(1234)$^{-1}$ = (34), (1234)(34)(1234)$^{-1}$ = (23), etc. ).  From here, it is fairly easy to see
that this set of elements will actualy generate $S_{4}$ and that there is
no smaller such set (though there are other adequate sets of the same size).
\par
	Translating back into logical notation, all we have to do is implement
the minimal permutations as biconditionals from which all the others will
be constructable.  This then apears in logical form as: \par
 $\forall w \forall x \forall y \forall z (Awxyz  \leftrightarrow Axwyz \leftrightarrow Axyzw)$.\par


\end{document}
