A specification says, “If a user is signed in, they can view the page.” Can we conclude that anyone who can view the page must be signed in? Not until we know that no other way to view it exists. Logic helps prevent this kind of reversal. The goal is to follow what is assumed and what can be concluded, rather than merely memorize symbols.
Propositions and logical connectives
A proposition is a statement that has a definite truth value. “7 is odd” is a proposition, whereas “x is odd” requires a value or domain for x. We write p∧q for “p and q,” p∨q for “p or q,” and ¬p for “not p.” In ordinary propositional logic, “or” includes the case where both statements are true. Distinguish it from the everyday expression “exactly one of the two.”
The same reasoning applies to program conditions. The negation of “A and B” is “not A, or not B,” rather than “not A and not B.” For example, people who do not satisfy “adult and member” include adults who are not members. When moving a negation inward, De Morgan’s laws also change the connective.
Check the direction of implication
p→q means “if p, then q.” It is false only when p is true and q is false. When p is false, the implication is true. This does not assert a causal relationship: it states that no object satisfying p is an exception to q. The statements p→q and q→p are different. When both hold, we write p↔q.
p q p → q
T T T
T F F
F T T
F F T“Every multiple of 4 is even” is true, but its converse, “Every even number is a multiple of 4,” has the counterexample 6. The equivalent statement is the contrapositive: “If a number is not even, it is not a multiple of 4.” Do not choose a converse or contrapositive by how its wording sounds. Write out the form ¬q→¬p to check it.
For all, there exists, and negation
∀x P(x) asserts that P holds for every object in the domain; ∃x P(x) asserts that it holds for at least one. The negation of ∀x P(x) is ∃x ¬P(x). Thus, the negation of “Every request succeeded” is “At least one request failed,” not “Every request failed.” Define the domain of x first, including how an empty domain is treated.
The order of quantifiers also changes the meaning. “Every user has a page they can read” is ∀u ∃p CanRead(u,p). The statement ∃p ∀u CanRead(u,p), “There is a page that every user can read,” is stronger. In the first statement, different users may choose different pages. This distinction matters when specifying access permissions or test conditions.
A proof connects assumptions to a conclusion
A direct proof derives the conclusion from assumptions and definitions. If an integer n is even, write n=2k. Then n²=4k²=2(2k²), so n² is even. For a proof by contraposition, suppose n is odd and write n=2k+1. We obtain n²=2(2k²+2k)+1, which is odd. This proves the contrapositive of “If n² is even, n is even.”
One counterexample is enough to refute a universal statement. By contrast, 100 passing tests do not prove a property for infinitely many inputs. Tests and proofs serve different purposes. Tests reveal specific defects in an implementation or execution environment; proofs establish general properties under explicit assumptions. Whether those assumptions match the implementation still needs checking.
Check your understanding
Can “Administrators can change the settings” imply “Non-administrators cannot change the settings”? No. The second statement is the inverse, equivalent to the converse rather than the original implication. An ordinary user who has permission to change settings is a counterexample.
Negate “Every element is at least 0.” The answer is “At least one element is less than 0.” Not being greater than or equal to 0 means being less than 0, not less than or equal to 0.
Prove by contraposition that, for an integer n, “If n² is odd, n is odd.” Prove instead that “If n is even, n² is even,” starting from n=2k.
Concepts in this unit: Implication · Quantifiers · Counterexample ·
Read next: Values, Types, Control Flow, Functions, and Modules