Lógica Matemática e Teoria dos Conjuntos

Em 1891, Georg Cantor demonstrou algo que chocou o mundo matemático: existem diferentes «tamanhos» de infinito. O conjunto dos números inteiros é infinito, o conjunto dos números reais é infinito — mas o segundo é inimaginavelmente maior que o primeiro. A prova usou o célebre «argumento diagonal de Cantor» — pura lógica, sem cálculo. A resposta da comunidade matemática foi tão hostil que Cantor passou os últimos anos da vida em sanatórios, em depressão. Hoje, a teoria dos conjuntos que ele fundou é a linguagem em que toda a matemática é escrita.

Proposições e Conectivos Lógicos

Uma proposição é uma afirmação que pode ser verdadeira (V) ou falsa (F) — não ambas.

«7 é primo» — proposição verdadeira.
«Lisboa é a capital de Espanha» — proposição falsa.
«Que horas são?» — não é proposição (é uma pergunta).

Conectivos Fundamentais

| Símbolo | Nome | Leitura | |---|---|---| | $\neg p$ | Negação | «Não p» | | $p \land q$ | Conjunção | «p e q» | | $p \lor q$ | Disjunção | «p ou q» | | $p \Rightarrow q$ | Condicional | «Se p, então q» | | $p \Leftrightarrow q$ | Bicondicional | «p se e só se q» |

Tabelas de Verdade

Negação

| $p$ | $\neg p$ | |---|---| | V | F | | F | V |

Conjunção e Disjunção

| $p$ | $q$ | $p \land q$ | $p \lor q$ | |---|---|---|---| | V | V | V | V | | V | F | F | V | | F | V | F | V | | F | F | F | F |

A conjunção é verdadeira apenas quando ambas as proposições são verdadeiras. A disjunção é falsa apenas quando ambas são falsas.

Condicional

| $p$ | $q$ | $p \Rightarrow q$ | |---|---|---| | V | V | V | | V | F | F | | F | V | V | | F | F | V |

⚠O condicional com hipótese falsa

O condicional $p \Rightarrow q$ só é falso quando $p$ é verdadeiro e $q$ é falso. Quando $p$ é falso, a condicional é verdadeira por vacuidade — «ex falso quodlibet». Isto é contraintuitivo mas fundamental.

Tautologias e Equivalências Lógicas

Uma tautologia é uma proposição sempre verdadeira, independentemente dos valores de verdade das proposições simples.

Exemplos de tautologias importantes:

Terceiro excluído: $p \lor \neg p$
Modus Ponens: $(p \land (p \Rightarrow q)) \Rightarrow q$

Duas proposições são logicamente equivalentes ( $\equiv$ ) se têm a mesma tabela de verdade.

Leis de De Morgan

\neg (p \land q) \equiv (\neg p) \lor (\neg q)

\neg (p \lor q) \equiv (\neg p) \land (\neg q)

Tradução: A negação de «p e q» é «não p ou não q». A negação de «p ou q» é «não p e não q».

Contrapositiva

A condicional $p \Rightarrow q$ é equivalente à sua contrapositiva $\neg q \Rightarrow \neg p$ :

(p \Rightarrow q) \equiv (\neg q \Rightarrow \neg p)

💡Provar por contrapositiva

Muitas demonstrações matemáticas são mais fáceis de fazer provando a contrapositiva. Se queres provar «se n² é par, então n é par», prova a contrapositiva: «se n é ímpar, então n² é ímpar» — que é mais direta.

Quantificadores

Para proposições com variáveis, usam-se quantificadores:

Quantificador universal $\forall$ : «para todo o...». $\forall x \in R : x^{2} \geq 0$ (verdadeiro).
Quantificador existencial $\exists$ : «existe...». $\exists x \in R : x^{2} = 2$ (verdadeiro).

Negação de Proposições com Quantificadores

\neg (\forall x, P (x)) \equiv \exists x, \neg P (x)

\neg (\exists x, P (x)) \equiv \forall x, \neg P (x)

Teoria dos Conjuntos

Um conjunto é uma coleção bem definida de objetos (os elementos).

Operações com Conjuntos

Dados $A$ e $B$ subconjuntos de um universo $U$ :

União: $A \cup B = {x : x \in A ou x \in B}$
Interseção: $A \cap B = {x : x \in A e x \in B}$
Complementar: $A^{c} = {x \in U : x \in / A}$
Diferença: $A ∖ B = {x : x \in A e x \in / B}$

Leis de De Morgan (para Conjuntos)

(A \cup B)^{c} = A^{c} \cap B^{c}

(A \cap B)^{c} = A^{c} \cup B^{c}

Completamente análogas às leis lógicas — não é por acaso: há uma correspondência profunda entre lógica e conjuntos.

Produto Cartesiano e Cardinalidade

O produto cartesiano de $A$ e $B$ é:

A \times B = {(a, b) : a \in A, b \in B}

Exemplo: Se $A = {1, 2}$ e $B = {a, b, c}$ :

A \times B = {(1, a), (1, b), (1, c), (2, a), (2, b), (2, c)}

Cardinalidade

A cardinalidade $# A$ (ou $∣ A ∣$ ) é o número de elementos de $A$ .

Fórmulas úteis:

# (A \cup B) = # A + # B - # (A \cap B)

# (A \times B) = # A \times # B

Exemplo: Se $# A = 30$ , $# B = 25$ e $# (A \cap B) = 10$ :

# (A \cup B) = 30 + 25 - 10 = 45

O Argumento Diagonal de Cantor

Cantor provou que o conjunto dos números reais em $[0, 1]$ é não numerável — não pode ser posto em correspondência biunívoca com os naturais.

Ideia da prova (por absurdo): Suponha que podemos listar todos os reais de $[0, 1]$ :

$r_{1} = 0, 314159 \dots$
$r_{2} = 0, 718281 \dots$
$r_{3} = 0, 577215 \dots$
...

Constrói um número $d$ cujo $n$ -ésimo dígito difere do $n$ -ésimo dígito de $r_{n}$ . Este $d$ pertence a $[0, 1]$ mas não está na lista — contradição! Logo, a lista não pode existir.

🔬Infinitos de diferentes tamanhos

Cantor classificou os infinitos: o cardinal dos naturais é $ℵ_{0}$ («aleph-zero»), o dos reais é $c = 2^{ℵ_{0}}$ . A Hipótese do Contínuo — se existe um cardinal entre $ℵ_{0}$ e $c$ — foi provada indecidível em 1963 por Paul Cohen: nem se pode provar nem refutar dentro da matemática padrão.

Para o Exame

Nas tabelas de verdade, o condicional $p \Rightarrow q$ só é falso numa situação: p verdadeiro e q falso.
As leis de De Morgan são testadas frequentemente na negação de afirmações: «não (A e B)» é «(não A) ou (não B)».
A fórmula $# (A \cup B) = # A + # B - # (A \cap B)$ aparece em problemas de probabilidade e combinatória.
O produto cartesiano $A \times B$ está na base da definição de função como subconjunto de $A \times B$ .