Lista 01: Logica e Teoria dos Conjuntos
Missão: resolver os exercícios de algebra com passos detalhados, explicando cada etapa do raciocínio e os cálculos envolvidos. O objetivo é fornecer uma compreensão clara e completa de como chegar à resposta correta, utilizando conceitos fundamentais da álgebra e lógica. Cada exercício será abordado de forma meticulosa, garantindo que todas as etapas sejam compreendidas e que o processo de resolução seja transparente.
Parte 1 — Lógica Proposicional
1. Lei da Contrapositiva: \((P \to Q) \leftrightarrow (\neg Q \to \neg P)\)
O que significa: uma implicação é logicamente equivalente à sua contrapositiva. Provar \(P \to Q\) é exatamente a mesma coisa que provar \(\neg Q \to \neg P\).
Conceitos necessários antes de começar
Implicação (\(P \to Q\)): “Se P então Q.” É falsa somente quando P é verdadeiro e Q é falso. Em todos os outros casos é verdadeira.
| P | Q | \(P \to Q\) |
|---|---|---|
| V | V | V |
| V | F | F |
| F | V | V |
| F | F | V |
Bicondicional (\(A \leftrightarrow B\)): “A se e somente se B.” É verdadeira quando A e B têm o mesmo valor lógico.
Construção da tabela-verdade passo a passo
Vamos construir coluna por coluna, justificando cada passo.
Passo 1 — Colunas base (todas as combinações possíveis de P e Q):
| P | Q |
|---|---|
| V | V |
| V | F |
| F | V |
| F | F |
Passo 2 — Calcular \(P \to Q\) (falsa só quando P=V e Q=F):
| P | Q | \(P \to Q\) |
|---|---|---|
| V | V | V |
| V | F | F |
| F | V | V |
| F | F | V |
Passo 3 — Calcular \(\neg Q\) (inverter Q):
| P | Q | \(P \to Q\) | \(\neg Q\) |
|---|---|---|---|
| V | V | V | F |
| V | F | F | V |
| F | V | V | F |
| F | F | V | V |
Passo 4 — Calcular \(\neg P\) (inverter P):
| P | Q | \(P \to Q\) | \(\neg Q\) | \(\neg P\) |
|---|---|---|---|---|
| V | V | V | F | F |
| V | F | F | V | F |
| F | V | V | F | V |
| F | F | V | V | V |
Passo 5 — Calcular \(\neg Q \to \neg P\) (falsa só quando \(\neg Q\)=V e \(\neg P\)=F):
Linha 1: \(\neg Q\)=F, \(\neg P\)=F → implicação com antecedente falso → V
Linha 2: \(\neg Q\)=V, \(\neg P\)=F → antecedente V e consequente F → F
Linha 3: \(\neg Q\)=F, \(\neg P\)=V → antecedente falso → V
Linha 4: \(\neg Q\)=V, \(\neg P\)=V → ambos V → V
| P | Q | \(P \to Q\) | \(\neg Q\) | \(\neg P\) | \(\neg Q \to \neg P\) |
|---|---|---|---|---|---|
| V | V | V | F | F | V |
| V | F | F | V | F | F |
| F | V | V | F | V | V |
| F | F | V | V | V | V |
Passo 6 — Calcular o bicondicional \((P \to Q) \leftrightarrow (\neg Q \to \neg P)\):
É verdadeiro quando as duas colunas marcadas têm o mesmo valor:
| P | Q | \(P \to Q\) | \(\neg Q \to \neg P\) | \((P \to Q) \leftrightarrow (\neg Q \to \neg P)\) |
|---|---|---|---|---|
| V | V | V | V | V |
| V | F | F | F | V |
| F | V | V | V | V |
| F | F | V | V | V |
Conclusão: a coluna final é sempre V — isso significa que \((P \to Q) \leftrightarrow (\neg Q \to \neg P)\) é uma tautologia: verdadeira para qualquer valor de P e Q.
2. Lei de De Morgan para a Negação da Disjunção: \(\neg(P \lor Q) \leftrightarrow (\neg P \land \neg Q)\)
O que significa: negar “P ou Q” é o mesmo que dizer “não P e não Q”.
Exemplo concreto: “Não é verdade que (está chovendo ou está frio)” equivale a “não está chovendo E não está frio.”
Construção passo a passo
Passo 1 — Colunas base:
| P | Q |
|---|---|
| V | V |
| V | F |
| F | V |
| F | F |
Passo 2 — Calcular \(P \lor Q\) (verdadeiro quando ao menos um é V):
| P | Q | \(P \lor Q\) |
|---|---|---|
| V | V | V |
| V | F | V |
| F | V | V |
| F | F | F |
Passo 3 — Calcular \(\neg(P \lor Q)\) (inverter a coluna anterior):
| P | Q | \(P \lor Q\) | \(\neg(P \lor Q)\) |
|---|---|---|---|
| V | V | V | F |
| V | F | V | F |
| F | V | V | F |
| F | F | F | V |
Passo 4 — Calcular \(\neg P\) e \(\neg Q\):
| P | Q | \(\neg(P \lor Q)\) | \(\neg P\) | \(\neg Q\) |
|---|---|---|---|---|
| V | V | F | F | F |
| V | F | F | F | V |
| F | V | F | V | F |
| F | F | V | V | V |
Passo 5 — Calcular \(\neg P \land \neg Q\) (verdadeiro somente quando ambos são V):
| P | Q | \(\neg(P \lor Q)\) | \(\neg P\) | \(\neg Q\) | \(\neg P \land \neg Q\) |
|---|---|---|---|---|---|
| V | V | F | F | F | F |
| V | F | F | F | V | F |
| F | V | F | V | F | F |
| F | F | V | V | V | V |
Passo 6 — Bicondicional final:
As colunas \(\neg(P \lor Q)\) e \(\neg P \land \neg Q\) são idênticas → o bicondicional é sempre V:
\[\boxed{\neg(P \lor Q) \leftrightarrow (\neg P \land \neg Q) \text{ é uma tautologia}}\]
Parte 2 — Teoria dos Conjuntos
3. Complementar de um conjunto: \(A' = \{x : (x \in X) \land (x \notin A)\}\)
Contexto: temos um conjunto universo \(X\) e um subconjunto \(A \subseteq X\).
Definição: o complementar de \(A\) em relação a \(X\), denotado \(A'\) (ou \(A^c\)), é o conjunto de todos os elementos de \(X\) que não pertencem a \(A\).
Passo 1 — Leitura da notação:
\[A' = \{x : (x \in X) \land (x \notin A)\}\]
Lê-se: “A linha é o conjunto de todos os \(x\) tais que \(x\) pertence a \(X\) e \(x\) não pertence a \(A\).”
Passo 2 — Exemplo concreto:
Seja \(X = \{1, 2, 3, 4, 5\}\) e \(A = \{1, 3, 5\}\).
Verificando cada elemento de \(X\):
| \(x\) | \(x \in X\)? | \(x \notin A\)? | \(x \in A'\)? |
|---|---|---|---|
| 1 | V | F | F |
| 2 | V | V | V |
| 3 | V | F | F |
| 4 | V | V | V |
| 5 | V | F | F |
Portanto: \(A' = \{2, 4\}\)
Passo 3 — Propriedades imediatas:
- \(A \cup A' = X\) (juntos cobrem tudo)
- \(A \cap A' = \emptyset\) (não têm elementos em comum)
- \((A')' = A\) (o complementar do complementar é o original)
4. Pertinência na Interseção: \(x \in (A \cap B) \leftrightarrow (x \in A) \land (x \in B)\)
O que significa: um elemento pertence à interseção de dois conjuntos se e somente se ele pertence aos dois simultaneamente.
Passo 1 — Definição formal:
\[A \cap B = \{x : (x \in A) \land (x \in B)\}\]
Passo 2 — Exemplo:
Seja \(A = \{1, 2, 3, 4\}\) e \(B = \{3, 4, 5, 6\}\).
Para cada elemento candidato:
| \(x\) | \(x \in A\)? | \(x \in B\)? | \((x \in A) \land (x \in B)\) | \(x \in A \cap B\)? |
|---|---|---|---|---|
| 1 | V | F | F | F |
| 2 | V | F | F | F |
| 3 | V | V | V | V |
| 4 | V | V | V | V |
| 5 | F | V | F | F |
| 6 | F | V | F | F |
Portanto: \(A \cap B = \{3, 4\}\)
Passo 3 — Analogia com a lógica:
A condição \((x \in A) \land (x \in B)\) é uma conjunção — assim como na tabela-verdade da lógica, ela só é verdadeira quando ambas as condições são verdadeiras simultaneamente.
5. Pertinência na União: \(x \in (A \cup B) \leftrightarrow (x \in A) \lor (x \in B)\)
O que significa: um elemento pertence à união se pertence a pelo menos um dos conjuntos.
Passo 1 — Definição formal:
\[A \cup B = \{x : (x \in A) \lor (x \in B)\}\]
Passo 2 — Usando os mesmos conjuntos \(A = \{1,2,3,4\}\) e \(B = \{3,4,5,6\}\):
| \(x\) | \(x \in A\)? | \(x \in B\)? | \((x \in A) \lor (x \in B)\) | \(x \in A \cup B\)? |
|---|---|---|---|---|
| 1 | V | F | V | V |
| 2 | V | F | V | V |
| 3 | V | V | V | V |
| 4 | V | V | V | V |
| 5 | F | V | V | V |
| 6 | F | V | V | V |
Portanto: \(A \cup B = \{1, 2, 3, 4, 5, 6\}\)
Passo 3 — Analogia com a lógica:
A condição \((x \in A) \lor (x \in B)\) é uma disjunção — verdadeira quando pelo menos uma das condições é verdadeira.
6. Lei de De Morgan para Conjuntos — Interseção: \((A \cap B)' = A' \cup B'\)
O que significa: o complementar da interseção é igual à união dos complementares.
Analogia com a lógica: esta lei é o espelho exato de \(\neg(P \land Q) \leftrightarrow (\neg P \lor \neg Q)\).
Demonstração por dupla inclusão (passo a passo)
Estratégia: para provar que dois conjuntos \(S\) e \(T\) são iguais, mostramos que \(S \subseteq T\) e \(T \subseteq S\).
Parte A — Mostrar que \((A \cap B)' \subseteq A' \cup B'\):
Tomamos um elemento \(x\) qualquer de \((A \cap B)'\) e mostramos que ele pertence a \(A' \cup B'\).
Passo 1 — \(x \in (A \cap B)'\) significa, por definição de complementar: \[x \notin (A \cap B)\]
Passo 2 — Por definição de interseção, \(x \notin (A \cap B)\) significa que não é verdade que (\(x \in A\) e \(x \in B\)). Em lógica: \[\neg(x \in A \land x \in B)\]
Passo 3 — Pela Lei de De Morgan lógica: \(\neg(P \land Q) \leftrightarrow \neg P \lor \neg Q\): \[x \notin A \quad \lor \quad x \notin B\]
Passo 4 — Isso significa que \(x \in A'\) ou \(x \in B'\), ou seja: \[x \in A' \cup B' \checkmark\]
Parte B — Mostrar que \(A' \cup B' \subseteq (A \cap B)'\):
Tomamos \(x \in A' \cup B'\) e mostramos que \(x \in (A \cap B)'\).
Passo 1 — \(x \in A' \cup B'\) significa: \[x \in A' \quad \lor \quad x \in B'\]
Passo 2 — Ou seja: \(x \notin A\) ou \(x \notin B\).
Passo 3 — Pela Lei de De Morgan lógica ao contrário: \[\neg(x \in A \land x \in B)\]
Passo 4 — Isso significa que \(x \notin (A \cap B)\), ou seja: \[x \in (A \cap B)' \checkmark\]
Conclusão: como \((A \cap B)' \subseteq A' \cup B'\) e \(A' \cup B' \subseteq (A \cap B)'\), temos:
\[\boxed{(A \cap B)' = A' \cup B'}\]
Verificação com exemplo numérico:
Seja \(X = \{1,2,3,4,5,6\}\), \(A = \{1,2,3,4\}\), \(B = \{3,4,5,6\}\).
| Expressão | Cálculo | Resultado |
|---|---|---|
| \(A \cap B\) | elementos em ambos | \(\{3,4\}\) |
| \((A \cap B)'\) | elementos de X fora de \(A\cap B\) | \(\{1,2,5,6\}\) |
| \(A'\) | elementos de X fora de A | \(\{5,6\}\) |
| \(B'\) | elementos de X fora de B | \(\{1,2\}\) |
| \(A' \cup B'\) | união dos complementares | \(\{1,2,5,6\}\) |
\((A \cap B)' = \{1,2,5,6\} = A' \cup B'\) ✓
7. Lei de De Morgan para Conjuntos — União: \((A \cup B)' = A' \cap B'\)
O que significa: o complementar da união é igual à interseção dos complementares.
Analogia com a lógica: espelho de \(\neg(P \lor Q) \leftrightarrow (\neg P \land \neg Q)\) — exatamente o item 2 desta lista!
Demonstração passo a passo
Parte A — Mostrar que \((A \cup B)' \subseteq A' \cap B'\):
Passo 1 — Tome \(x \in (A \cup B)'\). Por definição: \[x \notin (A \cup B)\]
Passo 2 — Por definição de união, isso significa que não é verdade que (\(x \in A\) ou \(x \in B\)): \[\neg(x \in A \lor x \in B)\]
Passo 3 — Pela Lei de De Morgan lógica: \(\neg(P \lor Q) \leftrightarrow \neg P \land \neg Q\): \[x \notin A \quad \land \quad x \notin B\]
Passo 4 — Portanto \(x \in A'\) e \(x \in B'\), ou seja: \[x \in A' \cap B' \checkmark\]
Parte B — Mostrar que \(A' \cap B' \subseteq (A \cup B)'\):
Passo 1 — Tome \(x \in A' \cap B'\). Por definição de interseção: \[x \in A' \quad \land \quad x \in B'\]
Passo 2 — Ou seja: \(x \notin A\) e \(x \notin B\).
Passo 3 — Pela De Morgan lógica ao contrário: \[\neg(x \in A \lor x \in B)\]
Passo 4 — Isso significa \(x \notin (A \cup B)\), ou seja: \[x \in (A \cup B)' \checkmark\]
Conclusão:
\[\boxed{(A \cup B)' = A' \cap B'}\]
Verificação com o mesmo exemplo:
| Expressão | Cálculo | Resultado |
|---|---|---|
| \(A \cup B\) | elementos em pelo menos um | \(\{1,2,3,4,5,6\}\) |
| \((A \cup B)'\) | elementos de X fora da união | \(\emptyset\) |
| \(A'\) | \(\{5,6\}\) | — |
| \(B'\) | \(\{1,2\}\) | — |
| \(A' \cap B'\) | elementos em ambos os complementares | \(\emptyset\) |
\((A \cup B)' = \emptyset = A' \cap B'\) ✓
Neste caso particular a união cobriu todo o universo \(X\), então o complementar é vazio — e de fato \(A' \cap B' = \{5,6\} \cap \{1,2\} = \emptyset\).
Resumo: A conexão profunda entre Lógica e Conjuntos
| Lógica | Conjuntos | Significado |
|---|---|---|
| \(P \land Q\) | \(A \cap B\) | “e” / interseção |
| \(P \lor Q\) | \(A \cup B\) | “ou” / união |
| \(\neg P\) | \(A'\) | negação / complementar |
| \(\neg(P \land Q) \leftrightarrow \neg P \lor \neg Q\) | \((A \cap B)' = A' \cup B'\) | De Morgan |
| \(\neg(P \lor Q) \leftrightarrow \neg P \land \neg Q\) | \((A \cup B)' = A' \cap B'\) | De Morgan |
| \(P \to Q \leftrightarrow \neg Q \to \neg P\) | — | Contrapositiva |
As Leis de De Morgan funcionam identicamente na lógica e na teoria dos conjuntos porque as operações \(\cap\), \(\cup\) e \('\) foram construídas para espelhar exatamente \(\land\), \(\lor\) e \(\neg\).