Computer Science › Fundamentos da Ciência da Computação
O que distingue uma prova matemática de um exemplo convincente, um padrão observado ou um argumento persuasivo, e por que checar casos, por mais numerosos que sejam, nunca prova uma afirmação sobre um domínio infinito.
A definição precisa e por tabela-verdade de ¬, ∧, ∨, →, ↔, e por que uma hipótese falsa torna um condicional \"vacuamente\" verdadeiro, a propriedade exata que licencia o movimento básico da prova direta.
Provar que duas fórmulas sempre concordam, por tabela-verdade ou por uma cadeia de leis nomeadas (De Morgan, distributiva, dupla negação), e classificar uma proposição como tautologia, contradição ou contingência.
Traduzir afirmações em português para ∀/∃ sobre um domínio de discurso explícito, e por que a ordem entre um ∀ e um ∃ diferentes muda o significado: ∃y∀x é estritamente mais forte que ∀x∃y.
A definição formal de subconjunto como um ∀ implícito, provar igualdade de conjuntos por dupla inclusão, e por que |𝒫(A)| = 2^|A|: cada elemento é uma decisão binária independente de entrar ou não.
Por que |P(A)| = 2^|A| (duas provas: correspondência com strings de bits, e indução), por que A × B ≠ B × A, e como os dois se encontram na definição de relação como subconjunto de A × B.
Reflexiva, simétrica, antissimétrica e transitiva definidas com precisão por quantificadores, por que antissimétrica não é a negação de simétrica, e como as quatro propriedades classificam uma relação como grafo dirigido.
A definição formal de grafo como par (V, E), o teorema do aperto de mãos (Σdeg(v) = 2|E|), e a troca real de espaço por tempo entre matriz de adjacência e lista de adjacência conforme a densidade do grafo.
A fórmula de Euler V − E + F = 2 para grafos planares conexos, o limite E ≤ 3V − 6 que prova K₅ e K₃,₃ não planares sem precisar desenhar nada, e a plausibilidade do Teorema das Quatro Cores.
Árvore como grafo conexo e acíclico, a prova de que n vértices forçam exatamente n − 1 arestas, a garantia de pelo menos duas folhas, e o vocabulário adicional (pai, filho, profundidade, altura) que enraizar introduz.
Uma função é uma relação com totalidade e boa definição; injetora significa nenhuma colisão, sobrejetora significa todo elemento do contradomínio é atingido, e só uma bijeção garante que uma inversa exista.
P(n,k) = n!/(n−k)! e C(n,k) = P(n,k)/k! derivados do princípio multiplicativo, e o teste real pra distinguir os dois: trocar a ordem de dois elementos escolhidos produz um resultado diferente?
A correção precisa pra soma ingênua supercontar uniões de conjuntos sobrepostos: subtrair interseções aos pares, somar de volta interseções triplas, e assim por diante, com sinal alternado a cada nível.
Como provar que algo existe sem nunca construí-lo ou localizá-lo: n+1 objetos em n categorias forçam uma colisão, e a versão generalizada garante ⌈n/k⌉ objetos em alguma categoria. A dificuldade real está em escolher os pombos e as casas certos.
Uma relação reflexiva, antissimétrica e transitiva que captura \"vem antes\" sem exigir que todo par seja comparável, diferente de uma ordem total. Diagramas de Hasse tornam cadeias, anticadeias, elementos mínimos/máximos e limitantes visualmente imediatos.
Reflexiva + simétrica + transitiva induz uma partição em classes disjuntas e exaustivas, e toda partição induz de volta uma relação de equivalência: as duas descrições são o mesmo objeto visto de dois ângulos.
Por que um diagrama de Venn, por mais persuasivo que seja, nunca é uma prova de uma identidade geral de conjuntos, e como a técnica de dupla inclusão (herdada de subconjuntos) prova identidades para A, B, C arbitrários.
A regra mecânica ¬∀x P(x) ≡ ∃x ¬P(x) e ¬∃x P(x) ≡ ∀x ¬P(x), aplicada um quantificador de cada vez em afirmações aninhadas, e por que \"nem todo A é B\" não é o mesmo que \"todo A não é B\".
Todo subconjunto não vazio de ℕ tem um elemento mínimo, o método do menor contraexemplo que decorre disso, e por que boa ordenação é logicamente equivalente à indução matemática sobre os naturais.
Por que a indução é uma consequência lógica direta do princípio da boa ordenação, não um salto de fé separado, e como estruturar caso base e passo indutivo para somas, divisibilidade e desigualdades.
A identidade gcd(a, b) = gcd(b, a mod b) provada via a propriedade de linearidade da divisibilidade, e por que o algoritmo de Euclides roda em tempo logarítmico (Lamé) sem nunca fatorar nenhum dos números.
Congruência mod n como relação de equivalência cujas classes somam, subtraem e multiplicam de forma consistente, inversos modulares via Euclides estendido, e exponenciação rápida por elevação ao quadrado repetida em tempo logarítmico.
Por que indução forte e indução comum são logicamente equivalentes, mesmo a forte sendo mais conveniente sempre que o passo indutivo precisa alcançar valores que não estão a uma distância fixa de k+1, como em fatorações e recorrências tipo Fibonacci.
Definir um conjunto por caso base e regras construtoras, e provar propriedades sobre ele por indução estrutural, o espelho exato da recursão em código: a hipótese indutiva e o \"salto de fé recursivo\" são, formalmente, a mesma confiança.
Provar P → Q assumindo P e derivando Q, versus provar a contrapositiva logicamente equivalente ¬Q → ¬P quando a negação da conclusão é mais fácil de manipular, e por que a recíproca e a inversa não são equivalentes ao original.
Assumir ¬P, derivar uma impossibilidade, e concluir P por modus tollens, a técnica padrão para afirmações de não existência e irracionalidade, ilustrada pela prova de Euclides da infinitude dos primos e pela irracionalidade de √2.
Part of the Computer Science curriculum.
O que distingue uma prova matemática de um exemplo convincente, um padrão observado ou um argumento persuasivo, e por que checar casos, por mais numerosos que sejam, nunca prova uma afirmação sobre um domínio infinito.
A definição precisa e por tabela-verdade de ¬, ∧, ∨, →, ↔, e por que uma hipótese falsa torna um condicional \"vacuamente\" verdadeiro, a propriedade exata que licencia o movimento básico da prova direta.
Provar que duas fórmulas sempre concordam, por tabela-verdade ou por uma cadeia de leis nomeadas (De Morgan, distributiva, dupla negação), e classificar uma proposição como tautologia, contradição ou contingência.
Traduzir afirmações em português para ∀/∃ sobre um domínio de discurso explícito, e por que a ordem entre um ∀ e um ∃ diferentes muda o significado: ∃y∀x é estritamente mais forte que ∀x∃y.
A definição formal de subconjunto como um ∀ implícito, provar igualdade de conjuntos por dupla inclusão, e por que |𝒫(A)| = 2^|A|: cada elemento é uma decisão binária independente de entrar ou não.
Por que |P(A)| = 2^|A| (duas provas: correspondência com strings de bits, e indução), por que A × B ≠ B × A, e como os dois se encontram na definição de relação como subconjunto de A × B.
Reflexiva, simétrica, antissimétrica e transitiva definidas com precisão por quantificadores, por que antissimétrica não é a negação de simétrica, e como as quatro propriedades classificam uma relação como grafo dirigido.
A definição formal de grafo como par (V, E), o teorema do aperto de mãos (Σdeg(v) = 2|E|), e a troca real de espaço por tempo entre matriz de adjacência e lista de adjacência conforme a densidade do grafo.
A fórmula de Euler V − E + F = 2 para grafos planares conexos, o limite E ≤ 3V − 6 que prova K₅ e K₃,₃ não planares sem precisar desenhar nada, e a plausibilidade do Teorema das Quatro Cores.
Árvore como grafo conexo e acíclico, a prova de que n vértices forçam exatamente n − 1 arestas, a garantia de pelo menos duas folhas, e o vocabulário adicional (pai, filho, profundidade, altura) que enraizar introduz.
Uma função é uma relação com totalidade e boa definição; injetora significa nenhuma colisão, sobrejetora significa todo elemento do contradomínio é atingido, e só uma bijeção garante que uma inversa exista.
P(n,k) = n!/(n−k)! e C(n,k) = P(n,k)/k! derivados do princípio multiplicativo, e o teste real pra distinguir os dois: trocar a ordem de dois elementos escolhidos produz um resultado diferente?
A correção precisa pra soma ingênua supercontar uniões de conjuntos sobrepostos: subtrair interseções aos pares, somar de volta interseções triplas, e assim por diante, com sinal alternado a cada nível.
Como provar que algo existe sem nunca construí-lo ou localizá-lo: n+1 objetos em n categorias forçam uma colisão, e a versão generalizada garante ⌈n/k⌉ objetos em alguma categoria. A dificuldade real está em escolher os pombos e as casas certos.
Uma relação reflexiva, antissimétrica e transitiva que captura \"vem antes\" sem exigir que todo par seja comparável, diferente de uma ordem total. Diagramas de Hasse tornam cadeias, anticadeias, elementos mínimos/máximos e limitantes visualmente imediatos.
Reflexiva + simétrica + transitiva induz uma partição em classes disjuntas e exaustivas, e toda partição induz de volta uma relação de equivalência: as duas descrições são o mesmo objeto visto de dois ângulos.
Por que um diagrama de Venn, por mais persuasivo que seja, nunca é uma prova de uma identidade geral de conjuntos, e como a técnica de dupla inclusão (herdada de subconjuntos) prova identidades para A, B, C arbitrários.
A regra mecânica ¬∀x P(x) ≡ ∃x ¬P(x) e ¬∃x P(x) ≡ ∀x ¬P(x), aplicada um quantificador de cada vez em afirmações aninhadas, e por que \"nem todo A é B\" não é o mesmo que \"todo A não é B\".
Todo subconjunto não vazio de ℕ tem um elemento mínimo, o método do menor contraexemplo que decorre disso, e por que boa ordenação é logicamente equivalente à indução matemática sobre os naturais.
Por que a indução é uma consequência lógica direta do princípio da boa ordenação, não um salto de fé separado, e como estruturar caso base e passo indutivo para somas, divisibilidade e desigualdades.
A identidade gcd(a, b) = gcd(b, a mod b) provada via a propriedade de linearidade da divisibilidade, e por que o algoritmo de Euclides roda em tempo logarítmico (Lamé) sem nunca fatorar nenhum dos números.
Congruência mod n como relação de equivalência cujas classes somam, subtraem e multiplicam de forma consistente, inversos modulares via Euclides estendido, e exponenciação rápida por elevação ao quadrado repetida em tempo logarítmico.
Por que indução forte e indução comum são logicamente equivalentes, mesmo a forte sendo mais conveniente sempre que o passo indutivo precisa alcançar valores que não estão a uma distância fixa de k+1, como em fatorações e recorrências tipo Fibonacci.
Definir um conjunto por caso base e regras construtoras, e provar propriedades sobre ele por indução estrutural, o espelho exato da recursão em código: a hipótese indutiva e o \"salto de fé recursivo\" são, formalmente, a mesma confiança.
Provar P → Q assumindo P e derivando Q, versus provar a contrapositiva logicamente equivalente ¬Q → ¬P quando a negação da conclusão é mais fácil de manipular, e por que a recíproca e a inversa não são equivalentes ao original.
Assumir ¬P, derivar uma impossibilidade, e concluir P por modus tollens, a técnica padrão para afirmações de não existência e irracionalidade, ilustrada pela prova de Euclides da infinitude dos primos e pela irracionalidade de √2.