D421 Discrete Math: Functions and Relations - Set 2 - Part 2

Correct Answer: Proving ¬q → ¬p to establish p → q

Since a conditional equals its contrapositive, proving ¬q → ¬p establishes the original p → q.

Correct Answer: Disproving a universal statement

A single counterexample disproves a universally quantified statement by exhibiting one case where it fails.

Correct Answer: Statements about all natural numbers

Mathematical induction proves a statement holds for all natural numbers by establishing a base case and an inductive step.

Correct Answer: Base case and inductive step

Induction requires proving the base case (usually n = 1) and the inductive step (if it holds for n = k, it holds for n = k + 1).

Correct Answer: The statement holds for n = k (the inductive hypothesis)

The inductive step assumes the inductive hypothesis, that the statement holds for some n = k, and then proves it for n = k + 1.

Correct Answer: n(n + 1)/2

The sum of the first n positive integers is n(n + 1)/2, a classic result often proven by induction.

Correct Answer: 55

Using n(n + 1)/2 with n = 10 gives 10 × 11 / 2 = 55.

Correct Answer: ¬(¬p) is equivalent to p

Double negation states that negating a proposition twice returns the original: ¬(¬p) = p.

Correct Answer: Always true

The expression p ∨ ¬p, called the law of the excluded middle, is a tautology because either p or its negation must be true.

Correct Answer: Always false

The expression p ∧ ¬p is a contradiction, always false, since a proposition and its negation cannot both be true.

Correct Answer: ¬p ∨ q

The conditional p → q is equivalent to ¬p ∨ q, a frequently used identity in logic.

Correct Answer: A statement involving variables that becomes a proposition when values are assigned

A predicate is a statement containing variables, such as P(x), that has a truth value once the variables are given specific values.

Correct Answer: From p and p → q, conclude q

Modus ponens allows concluding q when both p and the conditional p → q are known to be true.

Correct Answer: From ¬q and p → q, conclude ¬p

Modus tollens allows concluding ¬p when the conditional p → q holds and q is false.

Correct Answer: The set of values that variables can take

The domain of discourse (universe) is the set of all values over which the quantified variables range.

Correct Answer: A conditional whose hypothesis is always false

A conditional with a false hypothesis is vacuously true, since p → q is automatically true when p is false.

Correct Answer: Exclusive or (XOR)

The symbol ⊕ denotes exclusive or, which is true when exactly one of the two operands is true.

Correct Answer: When exactly one of p, q is true

Exclusive or is true precisely when the two operands have different truth values.

Correct Answer: ¬p → ¬q

The inverse of p → q is ¬p → ¬q, negating both the hypothesis and conclusion without swapping them.

Correct Answer: Logically equivalent to each other

The converse (q → p) and inverse (¬p → ¬q) are contrapositives of each other, so they are logically equivalent.