Ferramentas do usuário
Valor booleano de fórmulas
É melhor você fazer essa lista antes desta.
1 Dentro de uma álgebra de Boole, mostre que $\inf \emptyset = 1$ e $\sup \emptyset = 0$.
O objetivo desta lista é determinar o valor $[\![ \varphi ]\!]$ para uma fórmula $\varphi$ da teoria dos conjuntos. Pense nisso como um algoritmo que, fixada uma fórmula, temos como calcular tal valor. Esse procedimento será feito por indução na complexidade das fórmulas. Assim, começamos com as atômicas (as mais simples). Outra coisa a se notar é que as fórmulas aqui não falarão mais sobre conjuntos, mas sim sobre nomes para conjuntos.
Vamos usar a seguinte notação para $a, b \in B$: $a \Rightarrow b = -a + b$.
Sejam $x, y$ nomes. Definimos:
- $\displaystyle [\![ x \in y ]\!] = \sup_{t \in \text{dom}(y)}y(t)[\![ x = t ]\!]$
- $\displaystyle [\![ x \subset y ]\!] = \inf_{t \in \text{dom}(x)} (x(t) \Rightarrow [\![ t \in y ]\!])$
- $[\![ x = y ]\!] = [\![ x \subset y ]\!] [\![ y \subset x ]\!]$
2 Mostre que $[\![ \emptyset = \emptyset ]\!] = 1$.
3 Considere o nome $x = \{(\emptyset, a)\}$ onde $a \in B$. Calcule $[\![ \emptyset \in x ]\!]$.
4 Seja $x$ um nome. Mostre que $[\![ x = x ]\!] = 1$. Atenção, neste resultado, você provavelmente vai querer usar o que chamamos de indução na complexidade do nome. Isto é, você mostra que vale $[\![ x = x ]\!] = 1$, supondo que vale $[\![ t = t ]\!] = 1$ para qualquer $t$ com rank menor que $x$.
5 Sejam $x, y$ nomes, com $y \in $dom$(x)$. Mostre que $x(y) \leq [\![ y \in x ]\!]$.
6 Sejam $a, b, c$ nomes. Mostre as seguintes afirmações:
- $[\![ a = b ]\!] [\![ b = c ]\!] \leq [\![ a = c ]\!]$
- $[\![ a \in b ]\!] [\![ a = c ]\!] \leq [\![ c \in b ]\!]$
- $[\![ a \in b ]\!] [\![ b = c ]\!] \leq [\![ a \in c ]\!]$
Dica: Mostre as três afirmações simultaneamente por indução em $a, b, c$.
Dada uma fórmula $\varphi(x_1, \ldots, x_n)$ onde $x_1, \ldots, x_n$ são as variáveis livres de $\varphi$ e dados $\sigma_1, \ldots, \sigma_n$ nomes, definimos $[\![ \varphi(\sigma_1, \ldots, \sigma_n) ]\!]$ por indução na complexidade de $\varphi$ da seguinte forma:
- Se $\varphi$ é da forma $x_1 = x_2$ ou $x_1 \in x_2$, procedemos como anteriormente.
- Se $\varphi$ é da forma $\neg \psi(x_1, \ldots, x_n)$, então $[\![ \varphi(\sigma_1, \ldots, \sigma_n) ]\!] = - [\![ \psi(\sigma_1, \ldots, \sigma_n) ]\!]$.
- Se $\varphi$ é da forma $\psi_1(x_1, \ldots, x_n) \land \psi_2(x_1, \ldots, x_n)$, então $[\![ \varphi(\sigma_1, \ldots, \sigma_n) ]\!] = [\![ \psi_1(\sigma_1, \ldots, \sigma_n) ]\!] [\![ \psi_2(\sigma_1, \ldots, \sigma_n) ]\!]$.
- Se $\varphi$ é da forma $\exists y \psi(y, x_1, \ldots, x_n)$, então $\displaystyle [\![ \varphi(\sigma_1, \ldots, \sigma_n) ]\!] = \sup_{\tau}[\![ \psi(\tau, \sigma_1, \ldots, \sigma_n) ]\!]$
7 Calcule $[\![ \varphi \lor \psi ]\!]$ em termos de $[\![ \varphi ]\!]$ e $[\![ \psi ]\!]$.
8 Calcule $[\![ \forall y \ \varphi(y) ]\!]$ em termos de $[\![ \varphi(\sigma) ]\!]$ para $\sigma$ nome.
9 Calcule $[\![ \exists x \ \forall y \ y \notin x ]\!]$.
10 Mostre que $[\![ \varphi ]\!] = 1$, onde $\varphi$ é o axioma da extensionalidade.
11 Mostre que $[\![ \varphi ]\!] = 1$, onde $\varphi$ é o axioma do par.
Ferramentas da página
