Implication, equivalence and negation

Begin with a condition and its claim

If an integer is divisible by 4, then it is even. Try 4, 2 and 1: 4 meets both conditions, 2 is even without being divisible by 4, and 1 meets neither. Divisible by 4 means n = 4k for some integer k; even means n = 2j for some integer j. These definitions include negative integers and zero.

Let P(n) mean ‘n is divisible by 4’ and Q(n) mean ‘n is even’. The arrow ⇒ reads ‘if … then …’: P(n) ⇒ Q(n). In the complete finite domain D = {−4, −2, −1, 0, 1, 2, 4}, predict whether any member has P true and Q false. Also predict whether reversing the arrow changes the result. T means true and F means false.

The diagram groups every member of D by its two conditions. There is no P-only member, but −2 and 2 are Q-only members. Thus the forward claim holds on D and its converse fails there. For all integers, a separate argument proves the forward claim: if n = 4k, then n = 2(2k), and 2k is an integer. The finite diagram alone does not cover all integers.

Substitution from Variables, expressions and substitution helps with the examples. Integer divisibility is defined above. Statements and truth tables supply the logical notation, which we introduce here as it is needed. The later nested-quantifier section builds on Quantifiers and precise mathematical claims; on a first reading, learn the two-condition examples now and return to that section after studying domains and witnesses.

One implication fails only when its condition holds and its claim fails

For two defined classical truth values P and Q, the material implication P ⇒ Q is false exactly when P is T and Q is F. P is the antecedent, the if-part; Q is the consequent, the then-part. The other three pairs make the implication true. Read this definition as excluding a successful condition with a failed conclusion.

When P is false, the implication is true whether Q is true or false. This does not claim that P occurs, that Q occurs, or that one causes the other. It says the prohibited pair P true and Q false has not occurred at this instance. An implication’s truth also does not tell us whether we know its component values.

The symbols ¬, ∧ and ∨ mean not, and and inclusive or. Inclusive or permits both parts to be true. The expression ¬P ∨ Q has exactly the same column as P ⇒ Q: it is false only when P is true and Q false. The notation A ≡ B states logical equivalence under the stated assumptions; the complete table establishes (P ⇒ Q) ≡ (¬P ∨ Q) for every classical valuation of P and Q.

A domain-wide implication must cover every permitted object

For total predicates P(x) and Q(x) on a declared domain D, the universal statement ∀x ∈ D, (P(x) ⇒ Q(x)) means that no allowed x has P true and Q false. A predicate is total here when it gives one defined classical truth value at every allowed input. The symbol ∀ means ‘for every’.

One true instance cannot prove this universal claim. On a finite domain, check every distinct allowed member. On an infinite domain, prove the conclusion for an arbitrary allowed x satisfying P, or give another argument covering the whole domain. A single allowed member with P true and Q false refutes the universal claim.

Write the satisfying sets as S_P = {x ∈ D: P(x)} and S_Q = {x ∈ D: Q(x)}. The universal implication holds exactly when S_P is a subset of S_Q. In one direction, every member satisfying P must satisfy Q. In the other, inclusion prevents any P-only member. This is a two-way argument about the full sets, not a conclusion drawn from their appearance in a sampled picture.

If D is empty, the universal implication is true because there is no allowed counterexample. It creates no object or antecedent instance. The same claim can be true on a nonempty domain where every antecedent is false. Keep existence separate from the absence of a failing implication.

Necessary and sufficient name different directions

If P implies Q throughout the declared domain, P is sufficient for Q: having P guarantees Q. Q is necessary for P: P cannot hold without Q. In our integer example, divisibility by 4 is sufficient for evenness, and evenness is necessary for divisibility by 4.

The phrase ‘P only if Q’ means P ⇒ Q. Read only if as naming a requirement for P. By contrast, ‘P if Q’ means Q ⇒ P. Thus ‘P is necessary for Q’ also means Q ⇒ P. Start by writing the arrow, then attach the words necessary and sufficient to its direction.

A condition can be necessary without being sufficient. Being nonzero is necessary for a real number to be positive, but the nonzero real number −1 is not positive. A condition can be both: for an integer, being even and having an even square are necessary and sufficient for each other, as the parity proof later shows.

The contrapositive preserves an implication’s meaning

Starting from P ⇒ Q, its converse is Q ⇒ P, its inverse is ¬P ⇒ ¬Q, and its contrapositive is ¬Q ⇒ ¬P. The contrapositive reverses the direction and negates both parts. The inverse negates both parts without reversing them.

The complete four-row table proves (P ⇒ Q) ≡ (¬Q ⇒ ¬P) and (Q ⇒ P) ≡ (¬P ⇒ ¬Q). The original and contrapositive fail at exactly the pair P true and Q false. The converse and inverse fail at exactly the pair P false and Q true. The two pairs of formulas generally differ.

The integer n = 2 refutes the converse ‘even implies divisible by 4’ and the inverse ‘not divisible by 4 implies not even’. It does not refute the original or its contrapositive. At every integer, ‘not even implies not divisible by 4’ follows from the already proved original implication.

Treat a compound or quantified part as a whole when forming the contrapositive. For a total predicate A on D and a defined statement B, the contrapositive of (∀x ∈ D, A(x)) ⇒ B is ¬B ⇒ ¬(∀x ∈ D, A(x)), equivalently ¬B ⇒ (∃x ∈ D, ¬A(x)). The quantifier’s domain remains D; ∃ means ‘there exists’.

If and only if requires both arrows

The biconditional P ⇔ Q reads ‘P if and only if Q’. At one valuation it is true when P and Q agree, including when both are false. Equivalently, both P ⇒ Q and Q ⇒ P hold. To prove ∀x ∈ D, (P(x) ⇔ Q(x)), establish both domain-wide directions on the same domain.

Distinguish three scopes: equality at one selected row, equivalence of two predicates on a stated domain, and a logical equivalence of formulas for every permitted valuation of their atoms. P and Q can happen to agree at one input without agreeing elsewhere. A complete truth table proves a propositional equivalence; a finite input list proves only its own declared finite claim.

For every real x, x² = 1 if and only if x = −1 or x = 1. Forward: x² − 1 = (x − 1)(x + 1) = 0, so the real zero-product property gives x = 1 or x = −1. Reverse: either value squares to 1. At x = 0 both conditions are false, so their biconditional is still true.

Each algebraic step needs its original hypotheses. Dividing by a quantity that might be zero can lose solutions; squaring can add solutions. A reversible chain is an equivalence only where every transformation works in both directions. Otherwise separate the implications and check candidates in the original condition.

Negation identifies exactly how a statement fails

The negation of P ⇒ Q is P ∧ ¬Q: the condition holds and the claim fails. It is not Q ⇒ P or ¬P ⇒ ¬Q. The complete truth definition gives both directions: a false implication has that exact pair, and that pair makes the implication false.

The negation of P ⇔ Q is (P ∧ ¬Q) ∨ (¬P ∧ Q): exactly one part holds. De Morgan’s laws are ¬(P ∧ Q) ≡ (¬P ∨ ¬Q) and ¬(P ∨ Q) ≡ (¬P ∧ ¬Q). An and fails when at least one component fails; an inclusive or fails when both components fail. These explanations establish both directions for defined classical values.

Negate the entire consequent as one unit. The negation of P ⇒ (Q ∧ R) is P ∧ (¬Q ∨ ¬R), because at least one required conclusion fails. The negation of (P ∧ R) ⇒ Q is P ∧ R ∧ ¬Q: both antecedent conditions must hold. Parentheses identify which condition the negation belongs to.

A universal implication’s negation supplies one counterexample

With total predicates on the same domain, ¬(∀x ∈ D, (P(x) ⇒ Q(x))) ≡ ∃x ∈ D, (P(x) ∧ ¬Q(x)). If the universal statement fails, an allowed failing member exists; at that member P is true and Q false. Conversely, such a member makes the universal false. The two predicates refer to the same witness x.

Also ¬(∃x ∈ D, (P(x) ⇒ Q(x))) ≡ ∀x ∈ D, (P(x) ∧ ¬Q(x)). Existence of a true implication can be weak: an allowed input with P false already witnesses it, whether Q is true or false. It is not equivalent to existence of an input satisfying both P and Q. Empty D makes the existential false and its negation true.

Keep expressions defined before applying truth rules. For real reciprocal comparisons, first choose D = ℝ ∖ {0}. On that domain the negation of 1/x > 0 is 1/x ≤ 0. At zero neither comparison has a real value. Placing x ≠ 0 in a material implication does not itself define 1/0, even when the antecedent is false. A separately specified total extension would be a different predicate.

A counterexample can concern the whole witness choice

For a total relation R(x, y) on X × Y, ∀x ∈ X, ∃y ∈ Y, R(x, y) permits a different y for each x. Its complete negation is ∃x ∈ X, ∀y ∈ Y, ¬R(x, y): there is one allowed x for which every reply fails. The order remains x then y; each quantifier switches, and the inner condition is negated.

Let X = Y = {0, 1} and R(x, y) mean x = y. Predict whether each x has a reply and whether one fixed y works for both inputs.

The complete matrix has true entries on its diagonal. Each row has a witness, while no column works for every row. Thus the dependent claim is true and the uniform claim is false. The uniform claim is ∃y ∈ Y, ∀x ∈ X, R(x, y). Its negation is ∀y ∈ Y, ∃x ∈ X, ¬R(x, y): each proposed fixed reply has some failing input. A uniform witness always gives dependent witnesses by reusing that y. The reverse fails in the equality matrix.

For every integer x, choosing the integer y = x + 2 proves ∀x ∈ ℤ, ∃y ∈ ℤ, y = x + 2. A fixed y for all x would have to be both 2 at x = 0 and 3 at x = 1, which is impossible. This rule and contradiction prove the integer-wide claims; the finite equality matrix does not.

Empty domains require the same reading. If X is empty, the dependent universal is true; a uniform y still requires Y to contain a member. If X is nonempty and Y empty, the dependent claim is false because its required reply does not exist. The transformed negations retain these cases through vacuous inner universals.

Choose a route that keeps the hypotheses visible

For a direct proof of a domain-wide implication, take an arbitrary allowed object satisfying the antecedent and derive its conclusion. For a contrapositive proof, take an arbitrary allowed object failing the conclusion and derive failure of the antecedent. The complete truth-table equivalence justifies changing routes; reversing the arrow alone does not.

For an integer n, prove that an even square forces n to be even by contraposition. If n is not even, integer parity gives n = 2k + 1 for an integer k. Then n² = 4k² + 4k + 1 = 2(2k² + 2k) + 1, which is odd. This proves ‘n not even implies n² not even’, and hence the desired implication for every integer.

The reverse direction is direct: if n = 2k, then n² = 4k² = 2(2k²), which is even. Thus an integer is even if and only if its square is even. The proof uses integer parity and integer closure, including negative k and zero, rather than successful numerical samples.

Before finishing, check the domain, both directions if claimed, and the original expression at every candidate used. A converse can be false even when the original is proved, and an inverse can be false with it. The counterexample n = 2 to the divisibility converse explains why those extra directions need their own arguments.

Predict, compare and reveal the complete finite result

The tables scene offers eight formula comparisons, including an implication and its converse. Select a valuation and predict the two values before revealing whether the complete columns agree. All four P, Q pairs are retained, so equality at the selected row is separate from equivalence for every valuation.

The conditions scene offers eight finite domains. It groups every allowed input by P and Q and reports forward and reverse implications separately, together with necessary and sufficient directions. The reciprocal cases distinguish a restricted nonzero domain from a retained undefined zero: the zero row and complete classical domain verdict remain unassigned, while the defined rows are retained.

The negations scene offers three unary claims and five complete equality matrices. Read the original formula and its whole transformed negation, then distinguish a dependent reply from a uniform one. Empty domains have no invented evaluation. The tables give every finite witness and counterexample; the written semantic arguments and arbitrary-integer proofs establish the broader conclusions.

Worked examples

Try it yourself

1. At P = F and Q = T, evaluate the original, converse, inverse, contrapositive, biconditional and negation of the original. Does this row prove equivalence of the original and converse?

   Show the answer and reasoning

   The values are T, F, F, T, F and F respectively. This row actually refutes equivalence of the original and converse; one agreeing row would not establish it either.

   Apply the failure pair to each ordered arrow. P ⇒ Q has a false antecedent, while Q ⇒ P has a true antecedent and false consequent. The inverse has that same failing pair; the contrapositive has a false antecedent. The biconditional fails because P and Q differ, and negating the true original gives F.

2. Translate ‘a real number is positive only if it is nonzero’. Identify the necessary and sufficient conditions and test its converse.

   Show the answer and reasoning

   Write x > 0 ⇒ x ≠ 0 on ℝ. Positivity is sufficient for being nonzero, and being nonzero is necessary for positivity. The converse fails at −1, which is nonzero but not positive.

   The condition after only if is a requirement for the preceding condition. Every positive real number differs from zero, proving the original direction. The allowed input −1 satisfies the proposed converse’s antecedent and fails its conclusion, so nonzero alone is insufficient.

3. Prove that an integer is even if and only if its square is even, covering every integer rather than testing a list.

   Show the answer and reasoning

   If n = 2k, n² = 2(2k²) is even. For the other direction use the contrapositive: an odd integer n = 2k + 1 has n² = 2(2k² + 2k) + 1 odd. Integer parity covers every integer, so both directions hold.

   Keep k an arbitrary integer in both calculations. Integer closure makes both displayed coefficients of 2 integers. Every integer is either even or odd; the odd calculation rules out an odd input with even square, proving the forward implication by its equivalent contrapositive.

4. Is ∀x ∈ ℝ, (x² = 9 ⇒ x = 3) true? Negate it. What changes if the domain is the nonnegative reals?

   Show the answer and reasoning

   It is false on ℝ because −3 has square 9 and is not 3. Its negation is ∃x ∈ ℝ, (x² = 9 ∧ x ≠ 3), witnessed by −3. Factoring gives exactly −3 and 3 as real square roots; restricting to nonnegative reals excludes −3 and makes the universal true.

   The real zero-product property applied to (x − 3)(x + 3) = 0 yields exactly two candidates, and both satisfy the original square equation. Only −3 is a P-only input. A restriction changes the domain of the statement, not the earlier claim’s truth; on x ≥ 0 the sole permitted candidate is 3.

5. For total P, Q and R on D, negate ∀x ∈ D, (P(x) ⇒ (Q(x) ∧ R(x))).

   Show the answer and reasoning

   The equivalent negation is ∃x ∈ D, (P(x) ∧ (¬Q(x) ∨ ¬R(x))). A witness must satisfy P and fail at least one required conclusion, all at the same allowed input.

   Negate the outer every to some on the same D, then the implication to its successful antecedent and failed consequent. An and-consequent fails if Q or R fails, including if both fail. The existential witness remains one x rather than separate inputs for P and the failing conclusion.

6. On D = ℝ ∖ {0}, prove x > 0 if and only if 1/x > 0. Explain why zero supplies no truth-table row for these original predicates.

   Show the answer and reasoning

   The real product x(1/x) equals 1 and is positive. The two nonzero factors therefore have the same sign, proving both positivity directions. Zero is excluded from D and 1/0 is undefined; an antecedent involving x ≠ 0 does not define the reciprocal comparison there.

   Use the nonzero domain before reasoning about signs. A positive product of two nonzero real factors requires matching signs. Thus positivity of either factor gives positivity of the other, while negative inputs give two negative factors. None of these original operations defines a value at the excluded zero.

7. For X = Y = {1, 2} and R(x, y): x = y, decide the dependent and uniform claims and give their full negations.

   Show the answer and reasoning

   ∀x ∈ X ∃y ∈ Y R(x,y) is T, using y = x. Its negation ∃x ∈ X ∀y ∈ Y ¬R(x,y) is F. ∃y ∈ Y ∀x ∈ X R(x,y) is F: y = 1 fails at x = 2 and y = 2 fails at x = 1. Its negation ∀y ∈ Y ∃x ∈ X ¬R(x,y) is T, using the other member as x.

   All four equality values are T, F in the first row and F, T in the second. Each row’s true entry proves the dependent claim, and each proposed column’s false entry refutes the uniform claim. Switching each quantifier and negating equality retains the original finite domains and gives opposite whole-claim values.

What to carry forward

• For defined classical values, P ⇒ Q fails exactly when P is true and Q false.
• A universal implication excludes every allowed P-only counterexample; a true selected instance does not prove it.
• P sufficient for Q means P ⇒ Q; P necessary for Q means Q ⇒ P.
• An implication is equivalent to its contrapositive. Its converse and inverse form a separate equivalent pair.
• A domain-wide biconditional needs both directions on the same domain, and permits both conditions to be false at an input.
• Negate the whole statement: not every implication means some allowed input satisfies P and fails Q.
• Retain total predicates, domains and quantifier order; finite tables prove their complete finite claims, while infinite claims need full arguments.