Lecture 9 - Proofs (Part 1)

These flashcards cover key terminology and concepts related to mathematical proofs in logic and algorithms.

Axiom

A statement that is assumed to be true.

Theorem

A statement that can be proven to be true.

Proof

A valid argument that establishes the truth of a theorem.

Universal Statement

A statement that asserts something is true for every element in a particular domain.

Proof by Exhaustion

Proving a universal statement by checking if the statement is true for each element in a small domain.

Direct Proof

A method of proof that begins by assuming the antecedent of a conditional statement and derives the consequent.

Counterexample

An example that disproves a universal statement.

Divisibility

A term used to indicate that one integer is divisible by another without leaving a remainder.

Quod Erat Demonstrandum (QED)

A Latin phrase meaning 'what was to be shown,' often used at the end of a proof.

Pythagorean Theorem

A theorem in mathematics that states that in a right triangle, the square of the length of the hypotenuse is equal to the sum of the squares of the lengths of the other two sides.

Prime Number Theorem

A theorem that describes the asymptotic distribution of prime numbers.

P vs NP Problem

A major unsolved problem in computer science regarding the efficiency of solving problems and verifying solutions.