
\documentclass[12pt]{article}
\usepackage{amsmath,amssymb, amsthm}
%\usepackage{latexcad}
%\pagestyle{plain}
\usepackage{latexsym, amsfonts, amsmath, amssymb, amscd, epsfig,amsthm}


\usepackage{graphicx}
%%%%%%%%%%%%%
% LAS MACROS
%%%%%%%%%%%%%
%\textwidth15.75cm \hoffset-1.1cm\textheight24cm \voffset-1.8cm

%\setlength{\parindent}{-3em} \setlength{\topmargin}{-1cm}

%\newcommand{\arc}{\,{\rm arc}}
%\newcommand{\cc}{{\bf C}}
%\newcommand{\rr}{{\bf R}}
%\newcommand{\qq}{{\bf Q}}
%\newcommand{\zz}{{\bf Z}}
%\newcommand{\nn}{{\bf N}}
%\newcommand{\mm}{{\bf M}}
%\font\go=eufm10 scaled\magstep1

\renewcommand{\P}{\mathbf{P}}

\usepackage[latin1]{inputenc}

%\renewcommand{\ni}{\noindent}
\input xy 
\xyoption{all} %%!!
\newcounter{problem}
\newcommand{\prob}{
{{\stepcounter{problem}\vspace{2ex}{\bf \theproblem.\ }}}}

\newcounter{letra}[problem]
\renewcommand{\theletra}{\alph{letra}}
\newcommand{\letra}{{\addtocounter{letra}{1}{\bf \theletra.\ }}}

%\documentclass[12pt,a4paper]{amsart}

\usepackage[latin1]{inputenc}

%\usepackage{latexcad}

%\usepackage{graphicx}



\newcounter{number}
\setcounter{number}{1}
\newcommand{\n}{\vspace{0.3cm}\noindent{\bf \arabic{number})\ }\addtocounter{number}{1}}

% apartados, nivel 1
\newcommand{\pr}[1]{\vspace{0.1cm}\hspace*{0.1cm} \textbf{#1) }}

% apartados, nivel 2
\newcommand{\prr}[1]{\vspace{0.1cm}\hspace*{0.5cm}\textbf{#1) }}


\newcommand{\df}{\mathop=\limits^{\sf def}}
\newcommand{\gfo}{G=(V,A)}
\newcommand{\gfop}{G^{\prime}=(V^{\prime},A^{\prime})}
\newcommand{\gfoc}{G^{\textsc{c}}=(V^{\textsc{c}},A^{\textsc{c}})}

% para combinar figuras y texto; probar ambos
%\usepackage{wrapfig}
%\usepackage{floatflt}

\setlength{\parindent}{0pt}

\newcommand{\esp}{\vspace{0.1cm}} % espacio entre ejercicios

\usepackage[hmargin=1.8cm,vmargin=2cm]{geometry}


\usepackage{graphicx}








\begin{document}

\thispagestyle{empty}

\pagestyle{empty}


\begin{center}
  \textsc{L\'ogica} \hfill \text{Hoja 5}
\end{center}

\


Para el Lunes 30/10/2017.
Se pueden entregar ejercicios individualmente o en grupo. Hacerlo
en grupo no penaliza.


\

Asumimos gen\'erica e informalmente la no trivialidad. Al escribir f\'ormulas, se permiten
las abreviaciones razonables. 

\n Usamos $\phi \models \psi$ como abreviaci\'on de  $\{\phi\} \models \psi$.  Probar o refutar:

a) $\exists x (\phi \vee \psi) \models (\exists x  \phi )\vee  (\exists x \psi)$.  Sugerencia: Probar.

b)  $(\exists x  \phi )\vee  (\exists x \psi) \models  \exists x (\phi \vee \psi) $.  Sugerencia: Probar.

c) $\exists x (\phi \wedge \psi) \models (\exists x  \phi )\wedge  (\exists x \psi)$.  Sugerencia: Probar.

d)  $(\exists x  \phi ) \wedge  (\exists x \psi) \models  \exists x (\phi  \wedge \psi) $.  Sugerencia: Refutar.

e) $\exists x (\phi \to \psi) \models (\exists x  \phi )\to  (\exists x \psi)$. Sugerencia: Refutar.

f)  $(\exists x  \phi )\to  (\exists x \psi) \models  \exists x (\phi \to \psi) $. Sugerencia: Probar.

g) $\exists x (\phi \to \psi) \models (\forall x  \phi ) \to  (\exists x \psi)$.  Sugerencia: Probar.

h)  $(\forall x  \phi ) \to  (\exists x \psi) \models  \exists x (\phi  \to \psi) $.  Sugerencia: Probar.


i)  $ \phi  \models  \forall x \phi$.  Sugerencia: Probar.

j) $\forall x (\phi \to \psi) \models (\forall x  \phi )\to  (\forall x \psi)$.  Sugerencia: Probar.

k)  $(\forall x  \phi )\to  (\forall x \psi) \models  \forall x (\phi \to \psi) $. Sugerencia: Refutar.


l)  $(\exists x  \phi ) \to  (\forall x \psi) \models  \forall x (\phi  \to \psi) $.  Sugerencia: Probar.

m) $\forall x (\phi \to \psi) \models (\exists x  \phi )\to  (\exists x \psi)$.  Sugerencia: Probar.


\n Tomando $\exists$ como abreviaci\'on de $\neg \forall \neg$, probar que el axioma de cuantificaci\'on para $\forall$
implica la siguiente vesi\'on para $\exists$:  si $t$ puede sustituir a $x$ en $\phi$, entonces $\phi (t/x) \to \exists x \phi(x)  $.
Del mismo modo, tomando $\forall$  como abreviaci\'on de $\neg \exists\neg$, probar que el axioma de cuantificaci\'on para $\exists$,
``si $t$ puede sustituir a $x$ en $\phi$, entonces $\phi (t/x) \to \exists x \phi(x)  $", implica el axioma para $\forall$.

\n Probar que la regla de generalizaci\'on para  $\forall$ es equivalente a la siguiente regla de generalizaci\'on para
$\exists$: si $x$ no aparece libre en $\phi$, de $\psi \to \phi$ deducimos $(\exists x \psi) \to \phi$.





\n  Usamos $\phi \vdash \psi$ como abreviaci\'on de  $\{\phi\} \vdash \psi$.  Probar (sin usar completitud):

a) $ \phi  \vdash   \forall x \phi$.

b)  $\exists x \forall y \phi (x,y)  \vdash   \forall y \exists x \phi (x,y)$.

c)  $ \vdash  \exists x \forall y \phi (x,y)  \to \forall y \exists x \phi (x,y)$.

d)   $  \forall x \forall y \phi (x,y) \vdash   \forall y \forall x \phi (x,y)$.

e)   Suponiendo que $y$ no aparece ligada en $\phi$, $  \forall x \forall y \phi (x,y) \vdash   \forall y \phi (y,y)$.



\end{document}

\




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


