Glossário de Matemática Discreta

Definições

prova

Derivação de uma afirmação à partir de hipóteses utilizando regras de dedução lógicas.

axioma

Afirmação considerada evidente, que não precisa de provas.

teorema

Afirmação que foi provada baseada em certas hipóteses e que possui certa importância.

afirmação, asserção, resultado, fato

Afirmação provada, mas sem muita importância. Usada para provar um teorema ou proposição.

proposição

Afirmação de importância intermediária entre um teorema e um resultado/fato.

lema

Afirmação usada na prova de um longo teorema. A prova é dividida em partes, os lemas.

corolário

Afirmação com prova curta baseada em um teorema ou proposição. Consequência imediata de fatos recém provados.

hipótese/conjectura

Afirmação que não foi provada.

Técnicas de Demonstração

demonstração direta

Sequência de passos lógicos que levam de p → q, por transitividade, à implicação desejada. Cada passo é um axioma ou um teorema demonstrado previamente.

demonstração pela contrapositiva

Contrapositiva de p → q é ¬q → ¬p.

demonstração por contradição

Suposição absurda de que a afirmação demonstrada é falsa a fim de se obter, através de deduções válidas, uma conclusão contraditória.

demonstração por casos

A afirmação é particionada em um conjunto finito de casos, e a afirmação de cada caso é demostrada em separado.

contra-exemplo

Um contra exemplo é um exemplo que expõe a falsidade de uma afirmação.

Teoria dos Números

divisibilidade

Para todo número natural n e d (n ∈ N, d ∈ N*), existem e são únicos os números q e r ∈ N tais que:

n = dq + r

• d é o divisor

• q é o quociente

• r é o resto da divisão de n por d.

É possível estender a proposição para inteiros (Z).

m divide n se existe k tal que: n = km Notação: m|n (m divide n), m⟊n (m não divide n)