SBC_Lista_1.pdf

SBC_Lista_1.tex

\documentclass{article}

\usepackage{lmodern}
\usepackage[]{algorithm2e}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[portuguese]{babel}
\usepackage{mathtools}
\usepackage{enumitem}
\usepackage{listings}

\title{Lista 1 de Sistemas Baseados em Conhecimento}
\author{9410313 - Walter Perez Urcia}

\begin{document}

\maketitle

\section{Exercício 1}
	\subsection{Declaração}
		Essa questão envolve a formalização de algumas propriedades simples de conjuntos em lógica de primeira ordem. Considere os 3 seguintes fatos:
		\begin{itemize}
			\item Nenhum conjunto é elemento de si mesmo
			\item Um conjunto $x$ é subconjunto de um conjunto $y$ se e somente se todo elemento de $x$ é um elemento de $y$
			\item Algo é elemento da união de dois conjuntos $x$ e $y$ se e somente se ele é um elemento de $x$ ou um elemento de $y$
		\end{itemize}
		\begin{enumerate}[ label = (\alph*) ]
			\item Represente os fatos como sentenças de lógica de primeira ordem. Como símbolos não lógicos, use ${Sub}( x , y )$ para representar  "$x$ é um subconjunto de $y$", ${Elt}( e , x )$ para representar "$e$ é um elemento de $x$" e $u( x , y )$ para representar "a união de $x$ e $y$". Em vez de usar um predicado especial para afirmar que algo é um conjunto, você pode simplesmente assumir que no domínio (que assumimos não-vazio) tudo é um conjunto. Chame o conjunto resultante de sentenças $\tau$
			\item Mostre usando interpretações lógicas que "$x$ é subconjunto da uni˜åo de $x$ e $y$" é consequência lógica de $\tau$
			\item Mostre usando interpretações lógicas que "a união de $x$ e $y$ é igual à união $y$ e $x$" não é consequência lógica de $\tau$
			\item Seja $A$ um conjunto. Mostre usando interpretações lógicas que "existe um conjunto $z$ tal que a união de $A$ e $z$ é um subconjunto de $A$" é consequência lógica de $\tau$
			\item "Existe um conjunto $z$ tal que para qualquer conjunto $x$ a união de $x$ e $z$ é um subconjunto de $x$" é consequência lógica de $\tau$? Explique
			\item Escreva uma sentença que afirme a existência de conjuntos unitários, isto é, para qualquer $x$, o conjunto cujo único elemento é $x$. $\tau_1$ é $\tau$ com essa sentença adicionada
			\item Prove que $\tau_1$ não é finitamente satisfatível (novamente, assumindo que o domínio é não-vazio). Dica: Num domínio finito, considere $u$, o objeto interpretado como a união de todos os elementos do domínio
			\item Prove ou desprove que a existência de um conjunto vazio é consequência lógica de $\tau$
		\end{enumerate}
	\subsection{Solução a}
		O conjunto de sentenças $\tau$ contém:
		\begin{itemize}
			\item $\neg ( \exists_x ( {Elt}( x , x ) ) )$
			\item ${Sub}( x , y ) \equiv \forall_e [ {Elt}( e , x ) \land {Elt}( e , y ) ]$
			\item ${Elt}( e , u( x , y ) ) \equiv \forall_e [ {Elt}( e , x ) \lor {Elt}( e , y ) ]$
		\end{itemize}
	\subsection{Solução b}
		Temos $\alpha = {Sub}( x , u( x , y ) )$. Queremos mostrar $\tau \models \alpha$, então temos:
		\[ \tau \models {Sub}( x , u( x , y ) ) \]
		\[ \tau \models \forall e. {Elt}( e , x ) \land {Elt}( e , u( x , y ) ) \]
		\[ \tau \models \forall e. {Elt}( e , x ) \land \forall e. [ {Elt}( e , x ) \lor {Elt}( e , y ) ] \]
		\[ \tau \models \forall e. {Elt}( e , x ) \land [ {Elt}( e , x ) \lor {Elt}( e , y ) ] \]
		\[ \tau \models \forall e. {Elt}( e , x ) \land {Elt}( e , u( x , y ) ) \]
		\[ \tau \models {Sub}( x , u( x , y ) ) \]
		Dessa forma podemos mostrar que $\tau \models \alpha$
		
	\subsection{Solução c}
		Temos $\alpha = u( x , y ) = u( y , x )$. Para mostrar $\tau \models \alpha$ temos 
		\[ \tau \models {Elt}( e , u( x , y ) ) = {Elt}( e , u( y , x ) ) \]
		\[ \tau \models \forall e. {Elt}( e , x ) \lor {Elt}( e ,y ) = \forall e. {Elt}( e , y ) \lor {Elt}( e ,x )\]
		Pela propriedade comutativa da operação lógica $\lor$ podemos dizer que ambos termos são iguais e portanto $\tau \models \alpha$.
		
	\subsection{Solução d}
		Temos $\alpha = \exists z. Sub( u( A , z ) , A )$. Se tomamos o conjunto $z = \emptyset$, temos $u( A , \emptyset )$, mas pela segunda sentença em $\tau$ temos que $u( A , \emptyset ) = A$. Finalmente,
		\[ \tau \models Sub( u( A , z ) , A ) \]
		\[ \tau \models Sub( u( A , \emptyset ) , A ) \]
		\[ \tau \models Sub( A , A ) \]
		\[ \tau \models \forall e. [ {Elt}( e , A ) \lor {Elt}( e , A ) ] \]
		que sempre é verdadeiro. Portanto, $\tau \models \exists z. Sub( u( A , z ) , A )$.
	
	\subsection{Solução e}
		Temos $\alpha = \exists z. \forall x. Sub( u( x , z ) , x )$. Como no casso anterior, se tomamos o conjunto $z = \emptyset$, temos $u( x , \emptyset )$, mas pela segunda sentença em $\tau$ temos que $u( x , \emptyset ) = x$. Finalmente,
		\[ \tau \models Sub( u( x , z ) , x ) \]
		\[ \tau \models Sub( u( x , \emptyset ) , x ) \]
		\[ \tau \models Sub( x , x ) \]
		\[ \tau \models \forall e. [ {Elt}( e , x ) \lor {Elt}( e , x ) ] \]
		que sempre é verdadeiro. Portanto, $\tau \models \exists z. \forall x. Sub( u( x , z ) , x )$.
	
	\subsection{Solução f}
	\subsection{Solução g}
	\subsection{Solução h}
		Se tomamos um conjunto $x = \emptyset$ e um conjunto qualquer $y$ não vazio, podemos desprovar que $\alpha = \emptyset$ não é consequência lógica de $\tau$ fazendo:
		\[ \tau \models {Sub}( x , y ) \]
		\[ \tau \models \forall e. {Elt}( e , x ) \land {Elt}( e , y ) \]
		Mas como $x$ não tem elementos por ser o conjunto vazio, aquela conjunção não poderia ser verdadeira pelo fato que $y$ não verdadeiro. Portanto, $\alpha$ não é consequência lógica de $\tau$.
	
\section{Exercício 2}
	\subsection{Declaração}
		Considere os seguintes fatos sobre o Clube da Ponte da Elm Street:\\
		\textit{Joe, Sally, Bill e Ellen são os únicos membros do clube. Joe é casado com Sally. Bill é irmão de Ellen. O cônjuge de toda pessoa casada do clube também está no clube.}\\
		Desses fatos, a maioria das pessoas seria capaz de determinar que Ellen não é casada.
		\begin{enumerate}[ label = (\alph*) ]
			\item Represente esses fatos como sentenças em lógica de primeira ordem, e mostre semanticamente que apenas por elas não podemos concluir que Ellen não é casada
			\item Escreva em lógica de primeira ordem alguns fatos adicionais que podemos supor que a maioria das pessoas sabe, e mostre que esse conjunto de sentenças expandido agora nos permite concluir que Ellen não é casada
		\end{enumerate}
	\subsection{Solução a}
		Representando o problema como sentenças em lógica de primeira ordem temos:
		\begin{itemize}
			\item Membro( x )
			\item Casado( x , y )
			\item Irmão( x , y )
			\item $\forall$x,y $\equiv$ Membro( x ) $\land$ Membro( y )
		\end{itemize}
		Com domínio $D = \{ J , S , B , E \}$. Então para os fatos anteriores temos:
		\begin{itemize}
			\item Membro( J ), Membro( S ), Membro( B ), Membro( E )
			\item Casado( J , S )
			\item Irmão( B , E )
		\end{itemize}
		Tendo em consideração as sentenças temos que: Casado( x , E ) $\equiv$ Membro( x ) $\land$ Membro( E ) e do domínio $D$ podemos dizer quais são os possíveis valores para $x$. Portanto, existem membros do clube que poderiam estar casados com Ellen e não podemos afirmar que ela não esteja casada.
		
	\subsection{Solução b}
		Adicionando ao conjunto de sentenças o seguintes fato:
		\begin{itemize}
			\item $\forall$x,y Casado( x , y ) $\equiv$ Membro( x ) $\land$ Membro( y ) $\land \lnot$ Irmão( x , y ) $\land \lnot \exists$r[ Casado( r , x ) $\lor$ Casado( r , y ) $\land$ r $\not = $ x $\land$ r $\not =$ y] $\land$ x $\not =$ y
		\end{itemize}
		Podemos mostrar que agora permite concluir que Ellen não é casada porque não existem valores possíveis para $x$ em Casado( $x$ , E ).
\end{document}