STEP-BY-STEP LESSON · §2.1
Logical Form and Logical Equivalence
Check logical form on every truth assignment.
Before you begin
Variables
In x+y=0, each variable keeps its chosen value throughout the statement. If x=3, only y=−3 satisfies this condition.
x+y=0; x=3 ⇒ y=−3
The condition x>0 depends on the permitted values of x. Specify the domain: integers.
x∈ℤ
Symbols
- ¬
- not
- ∧
- and
- ∨
- or
- ≡
- logical equivalence
- ⊤ / ⊥
- true / false constants
Definitions and notation for this topic
True / false
T / F; ⊤ / ⊥
T and F denote true and false. The symbols ⊤ and ⊥ are truth and falsity constants in the stated logical notation.
In digital logic, 1 and 0 encode these values. They do not make the logical operation OR the same as ordinary integer addition: 1∨1=1.
Separate glossary example
The statement 3 = 3 has truth value T.
Negation / NOT
¬ ~
Reverses the truth value of a statement.
Read negation as: it is not the case that…
Epp commonly writes ~p for negation. In a~b the same-looking mark may instead name a relation; read the whole construction.
Separate glossary example
¬(2 < 3) is false.
Conjunction / AND
∧
True exactly when both statements are true.
One false part makes the conjunction false.
Separate glossary example
(2<3) ∧ (4<5) is true.
Disjunction / OR
∨
True when at least one statement is true, including when both are true.
Logical OR is inclusive unless stated otherwise.
Separate glossary example
(2<3) ∨ (4<3) is true.
Exclusive OR / XOR
⊕
True exactly when one of the two statements is true.
Unlike inclusive OR, XOR is false when both parts are true.
Separate glossary example
T ⊕ T = F
Logical equivalence
≡
Two formulas have the same truth value for every allowable assignment.
The sign ≡ also has a different use in modular arithmetic.
Logical ≡ is different from a≡b (mod m), which compares integer remainders. State the context before reading the sign.
Separate glossary example
¬(p ∧ q) ≡ ¬p ∨ ¬q
De Morgan’s laws for propositions
¬(p∧q)≡¬p∨¬q; ¬(p∨q)≡¬p∧¬q
For classical propositions p and q, negating a conjunction gives a disjunction of the negations, and negating a disjunction gives a conjunction of the negations.
Negate the complete parenthesized expression and each component, including the strictness of inequalities. ≡ says the two formulas agree under every truth assignment.
Separate glossary example
For real x, ¬(x>0 ∧ x<1) is equivalent to x≤0 ∨ x≥1.
Statement / proposition
A declarative sentence that is either true or false, but not both.
A question such as “How many?” is not a statement.
Separate glossary example
The statement 2 < 3 is true.
Truth table
Lists every truth-value assignment to the input propositions and the resulting values of the formula; intermediate columns can show its parts.
A table with n independent propositional inputs has 2^n rows. T… is not a mathematical symbol for a truth table.
Separate glossary example
For ¬p: when p=T, ¬p=F; when p=F, ¬p=T.
For p and q: TT, TF, FT, FF.
Tautology
A formula that is true for every assignment of truth values.
At least one of these two parts is always true.
Separate glossary example
p ∨ ¬p
Contradiction
A formula that is false for every assignment of truth values.
A statement and its negation cannot both be true.
Separate glossary example
p ∧ ¬p
Evaluate
Find the value of an expression using the given values of its variables.
The inputs are supplied and the requested result is a value. Solving instead asks which inputs satisfy a stated condition.
Separate glossary example
Evaluate p∨q when p=F and q=T: the value is T.
Evaluate 2x+1 at x=3: 2×3+1=7.
Simplify
Rewrite an expression in a simpler equivalent form, respecting its domain.
Distribute A∩ over the union and use B∪Bᶜ=U. The rewritten expression has the same value under the stated universe; this is not solving for A.
Separate glossary example
Simplify (A∩B)∪(A∩Bᶜ), with A,B⊆U: it equals A.
2x+3x=5x
Step by step
Step 1 / 6
Distinguish a statement from an open condition
“7 is odd” has a definite truth value. “x is odd” has no determined truth value until a value or a quantifier is supplied. Logical letters p,q name whole statements.
p: 7=2·3+1
Truth-table operations apply to truth values, so identify what each input statement says before calculating.
Worked example
Compare ¬(p∨q) and ¬p∧¬q for every assignment of p,q.
- For TT: p∨q=T, so its negation is F; ¬p∧¬q=F∧F=F.
- For TF and FT, OR is still T, while at least one negated input of AND is F. Both formulas give F on each row.
- For FF: OR is F, so its negation is T; ¬p∧¬q=T∧T=T.
- Both complete columns are F,F,F,T. Every assignment has been checked, establishing equivalence.
Optional self-check
Does one matching row establish equivalence?
Show answer
No, every truth assignment is required.