\documentclass[12pt]{article}

\usepackage[spanish]{babel}
\usepackage[latin1]{inputenc}
\usepackage{stmaryrd}
\usepackage[usenames,dvipsnames]{color}

\usepackage{amssymb}
\usepackage{amsxtra}
\usepackage{amsmath}
\usepackage{amstext}
\usepackage{amsthm}
\usepackage{amsbsy}
\usepackage{latexsym}
\usepackage{mathrsfs}
\usepackage{eucal}
\usepackage{synttree}

\newcommand{\tf}{\ensuremath{\mathcal{\stackrel{\bigtriangledown}{\circ}}}}

\theoremstyle{definition}
\newtheorem{definition}{Definici\'on}[section]
\newtheorem{proposition}[definition]{Proposici\'on}
\newtheorem{lemma}[definition]{Lema}
\newtheorem{theorem}[definition]{Teorema}
\newtheorem{corollary}[definition]{Corolario}
\newtheorem{example}[definition]{Ejemplo}
\newtheorem{observation}[definition]{Observaci\'on}
\newtheorem{problem}[definition]{Problema}
\newtheorem{question}[definition]{Pregunta}

\def\proof{\noindent{\textbf{Demostraci\'on}}\\}
\def\endproof{\hfill{\ensuremath\square}}
\def\refname{Referencias}
\def\abstractname{Resumen}


\title{Probar tautologías por contradiccion \\
usando árboles \\
Lógica Matemática \\
Otoño de 2012\\
Sección 101}
\author{José de Jesús Lavalle Martínez}

\begin{document}
\maketitle

\begin{abstract}
Documento para aprender a demostrar por contradicción si una fórmula es una tautología usando árboles sintáctico-semánticos. De paso como dibujar árboles en \LaTeX.
\end{abstract}

Para poder dibujar árboles tendrá que usar el paquete \verb+synttree+ mediante el comando \verb+\usepackage{synttree}+.

\synttree[A[B][C]]

\begin{center}
\synttree[A[B][C]]
\end{center}

Suponer que la fórmula $(A \wedge ((\neg(A\wedge B))\wedge(C\supset B))) \supset \neg C$ es falsa.

\begin{center}
\synttree[$\supset,F$[$\wedge$ [$A$]
                                                  [$\wedge$[$\neg$ [$\wedge$[$A$][$B$]]]
                                                  [$\supset$[$C$][$B$]]]]
                                 [$\neg$ [$C$]]
               ]
\end{center}

Para que la $\supset$ sea falsa, el antecedente $A \wedge ((\neg(A\wedge B))\wedge(C\supset B))$ (hijo izquierdo) debe ser verdadero y el consecuente $\neg C$ (hijo derecho) falso.

\begin{center}
\synttree[$\supset,F$[$\wedge,T$ [$A$]
                                                               [$\wedge$[$\neg$ [$\wedge$[$A$][$B$]]]
                                                                                 [$\supset$[$C$][$B$]]]]
                                 [$\neg,F$ [$C$]]
               ]
\end{center}

Para que la conjunción sea verdadera sus dos hijos deben ser verdaderos $A$ y $\neg(A\wedge B)\wedge(C\supset B)$, para que la negación sea falsa su único hijo $C$ debe ser verdadero.

\begin{center}
\synttree[$\supset,F$[$\wedge,T$ [$A,T$]
                                                               [$\wedge,T$[$\neg$ [$\wedge$[$A$][$B$]]]
                                                                                 [$\supset$[$C$][$B$]]]]
                                 [$\neg,F$ [$C,T$]]
               ]
\end{center}

Como $A$ y $C$ son atómicos (hojas) propagamos a todas las hojas sus valores de verdad.

\begin{center}
\synttree[$\supset,F$[$\wedge,T$ [$A,T$]
                                                               [$\wedge,T$[$\neg$ [$\wedge$[$A,T$][$B$]]]
                                                                                 [$\supset$[$C,T$][$B$]]]]
                                 [$\neg,F$ [$C,T$]]
               ]
\end{center}

Para que la conjunción sea verdadera sus dos hijos, $\neg(A\wedge B)$ y $C\supset B$, deben ser verdaderos.

\begin{center}
\synttree[$\supset,F$[$\wedge,T$ [$A,T$]
                                                               [$\wedge,T$[$\neg,T$ [$\wedge$[$A,T$][$B$]]]
                                                                                 [$\supset,T$[$C,T$][$B$]]]]
                                 [$\neg,F$ [$C,T$]]
               ]
\end{center}

Para que la negación sea verdadera su único hijo $A\wedge B$ debe ser falso.

\begin{center}
\synttree[$\supset,F$[$\wedge,T$ [$A,T$]
                                                               [$\wedge,T$[$\neg,T$ [$\wedge,F$[$A,T$][$B$]]]
                                                                                 [$\supset,T$[$C,T$][$B$]]]]
                                 [$\neg,F$ [$C,T$]]
               ]
\end{center}

Para que la conjunción sea falsa, como el valor de $A$ es verdadero, nos obliga a que $B$ sea falsa.

\begin{center}
\synttree[$\supset,F$[$\wedge,T$ [$A,T$]
                                                               [$\wedge,T$[$\neg,T$ [$\wedge,F$[$A,T$][$B,F$]]]
                                                                                 [$\supset,T$[$C,T$][$B$]]]]
                                 [$\neg,F$ [$C,T$]]
               ]
\end{center}

Como $B$ es atómico (hoja), podemos propagar sus valor de verdad.

\begin{center}
\synttree[$\supset,F$[$\wedge,T$ [$A,T$]
                                                               [$\wedge,T$[$\neg,T$ [$\wedge,F$[$A,T$][$B,F$]]]
                                                                                 [$\supset,T$[$C,T$][$B,F$]]]]
                                 [$\neg,F$ [$C,T$]]
               ]
\end{center}

Pero que $C$ sea verdadera y $B$ falsa contradice que $C\supset B$ es verdadera.

\begin{center}
\synttree[$\supset,F$[$\wedge,T$ [$A,T$]
                                                               [$\wedge,T$[$\neg,T$ [$\wedge,F$[$A,T$][$B,F$]]]
                                                                                 [$\supset,T,F, \tf$[$C,T$][$B,F$]]]]
                                 [$\neg,F$ [$C,T$]]
               ]
\end{center}

Lo cual implica que es imposible falsificar la fórmula $(A \wedge ((\neg(A\wedge B))\wedge(C\supset B))) \supset \neg C$, por lo tanto es una tautología.

\begin{figure}[h]
\caption{Árbol sintáctico-semántico para la fórmula $(A \wedge ((\neg(A\wedge B))\wedge(C\supset B))) \supset_2 (\neg C)$, con la leyenda en la parte superior de la figura.}
\begin{center}
\synttree[$\supset,F$[$\wedge,T$ [$A,T$]
                                                               [$\wedge,T$[$\neg,T$ [$\wedge,F$[$A,T$][$B,F$]]]
                                                                                 [$\supset,T,F, \tf$[$C,T$][$B,F$]]]]
                                 [$\neg,F$ [$C,T$]]
               ]
\end{center}
\end{figure}

\begin{figure}[h]
\begin{center}
\synttree[$\supset,F$[$\wedge,T$ [$A,T$]
                                                               [$\wedge,T$[$\neg,T$ [$\wedge,F$[$A,T$][$B,F$]]]
                                                                                 [$\supset,T,F, \tf$[$C,T$][$B,F$]]]]
                                 [$\neg,F$ [$C,T$]]
               ]
\end{center}
\caption{Árbol sintáctico-semántico para la fórmula $(A \wedge ((\neg(A\wedge B))\wedge(C\supset B))) \supset_3 (\neg C)$, con la leyenda en la parte inferior de la figura.}
\end{figure}


\end{document}