From Individual Statements to Compound Statements
In True and False Mathematical Statements, we evaluated complete claims and distinguished their truth values from our knowledge of those values. We now consider how complete claims can be combined. The statements “\(3+2=5\)” and “\(4<4\)” have different truth values. Joining them with “and” produces a different assertion from joining them with “or.”
We will use lowercase letters \(p\), \(q\), and \(r\) to stand for complete propositions. These are placeholders for statements, not numbers. This differs from the earlier notation \(P(x)\) or \(Q(x)\), which describes a predicate with an input.
Throughout this tutorial, the components are meaningful propositions in a specified context. As before, classical logic assigns each proposition exactly one of the two truth values: true or false.
Negation: “Not”
The negation of \(p\), written \(\neg p\), means “not \(p\)” or “it is not the case that \(p\).” It is true when \(p\) is false and false when \(p\) is true. Negation acts on one statement.
Worked Example: Negating an Inequality
Let \(p\) be the statement “\(4<4\).” Then \(\neg p\) says “It is not the case that \(4<4\).” Since \(p\) is false, \(\neg p\) is true.
In the ordering of real numbers, “not less than” means “greater than or equal to.” Thus the negation can also be written \(4\geq4\). It cannot be replaced by \(4>4\), which is false. The equality case must be included.
Negating a statement denies its assertion; it does not merely replace a word with a plausible opposite. For example, the negation of “\(0\) is even” is “\(0\) is not even.” The original statement is true by the definition of evenness, so its negation is false.
Proof. There are exactly two possibilities. If \(p\) is true, then \(\neg p\) is false, so \(\neg(\neg p)\) is true. If \(p\) is false, then \(\neg p\) is true, so \(\neg(\neg p)\) is false. In both cases, the double negation has the same truth value as \(p\). These cases exhaust the possibilities in classical logic.
For instance, “It is not the case that \(3+2\neq5\)” has the same truth value as \(3+2=5\). Double negation does not add a stronger claim; it returns to the original truth value.
Conjunction: “And”
The conjunction of \(p\) and \(q\), written \(p\land q\), means “\(p\) and \(q\).” It is true exactly when both components are true. If either component is false, including the case where both are false, the conjunction is false.
To establish a conjunction, both assertions must be justified. To show that a conjunction is false, one false component is enough.
Worked Example: Two Requirements
Let \(p\) be “\(-6\) is even” and let \(q\) be “\(-6>0\).” The statement \(p\) is true because \(-6=2(-3)\), with integer multiplier \(-3\). The statement \(q\) is false because \(-6\) is negative.
Therefore \(p\land q\), meaning “\(-6\) is even and \(-6\) is positive,” is false. Verifying evenness does not establish the conjunction: positivity is a separate requirement.
The word “but” usually has the same truth conditions as “and.” The assertion “\(-6\) is even, but \(-6\) is not positive” is a conjunction of two true statements. The word “but” suggests a contrast in ordinary language; that contrast does not change the logical truth conditions.
Disjunction: Inclusive “Or”
The disjunction of \(p\) and \(q\), written \(p\lor q\), means “\(p\) or \(q\).” It is true when at least one component is true, including when both are true. It is false exactly when both components are false.
For example, “\(6\) is even or \(6>0\)” is true. Both components are true: \(6=2\cdot3\), and \(6\) is positive. Inclusive “or” does not require us to discard one of these facts.
Using the same components, the exclusive assertion “\(6\) is even or \(6>0\), but not both” is false. We can express exclusive disjunction using the connectives already introduced:
The first part requires at least one component to be true. The second rules out both being true. Together they require exactly one true component.
Worked Example: Combining Earlier Instances
Retain the real-domain predicate \(Q(x): x^2=x+2\). The previous tutorial established that \(Q(-1)\) is true and \(Q(0)\) is false. Indeed, \((-1)^2=(-1)+2=1\), whereas \(0^2=0\) is not \(0+2=2\).
- \(Q(-1)\land Q(0)\) is false because \(Q(0)\) is false.
- \(Q(-1)\lor Q(0)\) is true because \(Q(-1)\) is true.
- \(Q(-1)\land\neg Q(0)\) is true because both displayed components are true.
These expressions combine specified instances, each of which is a complete proposition. They do not assert that \(Q(x)\) holds for every real number.
Implication: “If … Then …”
The implication, or conditional, \(p\to q\) means “If \(p\), then \(q\).” The statement \(p\) is its antecedent, and \(q\) is its consequent. This connective is also called material implication.
In particular, if \(p\) is false, \(p\to q\) is true whether \(q\) is true or false. Such a conditional is often described as vacuously true. It has no true antecedent paired with a false consequent.
This definition does not say that a false antecedent makes the consequent true. The truth of the conditional and the truth of its consequent are different matters.
Worked Example: Checking a Conditional
For specified real values \(x\), consider:
- At \(x=3\), both components are true, so the implication is true.
- At \(x=1\), the antecedent is false and the consequent is true, so the implication is true.
- At \(x=-1\), both components are false, so the implication is still true.
Now reverse the direction. At \(x=1\), the statement \((x>0)\to(x>2)\) has a true antecedent and a false consequent. It is false. Reversing the arrow can change the truth value.
A general conditional claim requires more than checking these instances. For example, the theorem proved in the previous tutorial says that, for every integer \(n\), if \(n\) is even, then \(n^2\) is even. By that theorem, no integer has a true antecedent and a false consequent in this assertion.
A counterexample to a claim of the form “For every allowed input, if \(p\), then \(q\)” must therefore satisfy the antecedent and fail the consequent. An input at which the antecedent is false is not a counterexample.
Material implication concerns truth values, not causation or timing. It does not assert that one event causes another, and the arrow by itself is not a proof. A mathematical argument must still justify any conditional it claims to establish.
The Biconditional: “If and Only If”
The biconditional \(p\leftrightarrow q\) means “\(p\) if and only if \(q\).” It is true exactly when \(p\) and \(q\) have the same truth value: either both are true or both are false. It is false when one is true and the other is false.
A biconditional asserts both directions. It can be expressed as
To verify this description, first suppose \(p\) and \(q\) are both true. Both implications are then true. If both are false, each implication has a false antecedent, so both are again true. If their truth values differ, the implication from the true component to the false component is false, making the conjunction false. These are exactly the stated truth conditions for the biconditional.
Worked Example: Two Ways to State an Equality
For any specified real number \(x\), consider
Both directions are justified by arithmetic. If \(x+2=5\), subtracting \(2\) gives \(x=3\). If \(x=3\), adding \(2\) gives \(x+2=5\).
At \(x=3\), both components are true. At \(x=1\), both are false, and the biconditional is still true. A true biconditional does not require its components to be true; it requires their truth values to agree.
In mathematical wording, “\(p\) only if \(q\)” means \(p\to q\), while “\(p\) if \(q\)” means \(q\to p\). Thus “if and only if” includes both directions. It is often abbreviated “iff.”
The Five Connectives at a Glance
| Connective | Reading | When it is true |
|---|---|---|
| \(\neg p\) | Not \(p\) | When \(p\) is false. |
| \(p\land q\) | \(p\) and \(q\) | When both are true. |
| \(p\lor q\) | \(p\) or \(q\) | When at least one is true. |
| \(p\to q\) | If \(p\), then \(q\) | When \(p\) is false or \(q\) is true. |
| \(p\leftrightarrow q\) | \(p\) if and only if \(q\) | When their truth values agree. |
These definitions separate the meaning of a compound statement from the work needed to evaluate its components. A component might require a calculation, a witness, or a general proof. Once its truth value is known, the connective determines how that value contributes to the whole.
Parentheses and the Scope of a Connective
A compound statement can itself become a component of a larger statement. Parentheses specify which parts are grouped together. In particular, the scope of a negation is the statement it negates.
Compare
The first denies the entire conjunction. The second denies only \(p\) and also asserts \(q\). They are not interchangeable. If both \(p\) and \(q\) are false, then \(p\land q\) is false, so \(\neg(p\land q)\) is true. But \((\neg p)\land q\) is false because its second component is false.
Similarly, \((p\lor q)\land r\) need not have the same truth value as \(p\lor(q\land r)\). If \(p\) is true and both \(q\) and \(r\) are false, the first expression is false because \(r\) is false. The second is true because \(p\) is true. Use parentheses rather than relying on an ambiguous string of symbols.
Check that each is complete and meaningful in the stated context.
Locate the outermost connective and the smaller statements it joins or negates.
Evaluate each component, then apply the connective definitions to the grouped parts.
A true disjunction need not have two true components, and a true conditional need not have a true consequent.
Connectives also do not automatically bind free variables. For example, \((x>0)\land(x<2)\) remains a predicate on the real numbers until the input is specified or the statement is completed with appropriate wording such as “there is a real number \(x\).” Logical structure and the scope of the variables must both be read carefully.
Check Your Understanding
Give a reason for each answer using the definitions of the connectives.
- Let \(p\) be “\(3+2=5\)” and \(q\) be “\(4<4\).” Determine the truth values of \(\neg p\), \(p\land q\), \(p\lor q\), \(p\to q\), \(q\to p\), and \(p\leftrightarrow q\).
- Explain why “\(0\) is even or \(0\geq0\)” is true with inclusive “or” but false with exclusive “or.” Verify both component statements.
- For the real-domain predicate \(Q(x): x^2=x+2\), evaluate \(Q(2)\land\neg Q(0)\) and \(Q(2)\leftrightarrow Q(-1)\).
- Give a real value of \(x\) that makes \((x>0)\to(x>2)\) false. Explain why \(x=-1\) is not a counterexample to the corresponding claim about every real number.
- Write the negation of \(5<5\) as an inequality. Then explain why \(\neg(p\land q)\) and \((\neg p)\land q\) have different truth values when \(p\) and \(q\) are both false.
- Prove that \(p\land q\) and \(q\land p\) always have the same truth value. Account for both the case where both components are true and the case where at least one is false.