
Mathematical Logic Fundamentals
Mathematical logic provides the formal language for reasoning about statements, their truth values, and the relationships between them. Mastering the fundamentals—such as propositions,…

What is the truth value of the negation of a true proposition?
When is the conjunction P ∧ Q true?
When is the disjunction P ∨ Q false?
What is the negation of the implication P → Q?
What is the contrapositive of P → Q?
When is the biconditional P ↔ Q true?
What does the universal quantifier ∀x∈E P(x) assert?
What is the negation of the existential statement ∃x∈R : x+1<0?
In a direct proof, if P is true and P → Q is true, what can be concluded?
Introduction to Mathematical Logic
Mathematical logic provides the formal language for reasoning about statements, their truth values, and the relationships between them. Mastering the fundamentals—such as propositions, logical connectives, and quantifiers—lays the groundwork for advanced topics in mathematics, computer science, and philosophy. This course breaks down each concept, explains common pitfalls, and offers examples that mirror typical quiz questions.
Truth Values and Propositions
What is a truth value?
In classical logic every proposition is assigned a truth value of either true or false. These values are often represented numerically as 1 for true and 0 for false. Understanding this binary system is essential because all logical connectives operate on these values.
- True proposition → truth value 1
- False proposition → truth value 0
For example, the statement "2 is an even number" is true, so its truth value is 1.
Negation and its effect on truth values
The negation operator ¬ flips the truth value of a proposition. If P is true (1), then ¬P is false (0), and vice‑versa. This simple rule is the basis for many logical equivalences.
Quiz example: What is the truth value of the negation of a true proposition? The correct answer is 0.
Logical Connectives
Conjunction (∧)
The conjunction P ∧ Q is true only when both P and Q are true. In all other cases—if either component is false—the conjunction evaluates to false.
- True ∧ True → True (1)
- True ∧ False → False (0)
- False ∧ True → False (0)
- False ∧ False → False (0)
Quiz reference: "When is the conjunction P ∧ Q true?" The answer is Only when both P and Q are true.
Disjunction (∨)
The disjunction P ∨ Q is true if at least one of the propositions is true. It is false only when both are false.
- True ∨ True → True
- True ∨ False → True
- False ∨ True → True
- False ∨ False → False
Quiz reference: "When is the disjunction P ∨ Q false?" The correct condition is Only when both P and Q are false.
Implication (→)
An implication P → Q is false only when P is true and Q is false; otherwise, it is true. This sometimes counter‑intuitive truth table is crucial for constructing proofs.
- True → True → True
- True → False → False
- False → True → True
- False → False → True
The negation of an implication, ¬(P → Q), is equivalent to P ∧ ¬Q. This equivalence appears frequently in proof by contradiction.
Quiz reference: "What is the negation of the implication P → Q?" Answer: P ∧ ¬Q.
Contrapositive
The contrapositive of an implication swaps and negates both parts: ¬Q → ¬P. Importantly, an implication and its contrapositive are logically equivalent—they share the same truth value in every possible scenario.
Quiz reference: "What is the contrapositive of P → Q?" Answer: ¬Q → ¬P.
Biconditional (↔)
The biconditional P ↔ Q asserts that P and Q have the same truth value. It is true when both are true or both are false, and false otherwise.
- True ↔ True → True
- False ↔ False → True
- True ↔ False → False
- False ↔ True → False
Quiz reference: "When is the biconditional P ↔ Q true?" Answer: When P and Q have the same truth value.
Quantifiers
Universal Quantifier (∀)
The universal quantifier ∀x ∈ E P(x) states that the predicate P(x) holds for every element x in the domain E. If even a single element violates the predicate, the whole statement is false.
Example: "∀x ∈ ℝ, x² ≥ 0" is true because every real number squared is non‑negative.
Quiz reference: "What does the universal quantifier ∀x∈E P(x) assert?" Answer: P(x) holds for every element of E.
Existential Quantifier (∃) – brief overview
Although not directly covered in the provided quiz, the counterpart to the universal quantifier is the existential quantifier ∃x ∈ E P(x), which claims that at least one element in E satisfies P(x). Understanding both quantifiers together enables you to translate natural‑language statements into precise logical form.
Putting It All Together: Common Logical Equivalences
Recognizing patterns among connectives and quantifiers helps simplify complex statements. Below are several key equivalences that frequently appear in proofs and exam questions.
- De Morgan’s Laws: ¬(P ∧ Q) ≡ ¬P ∨ ¬Q and ¬(P ∨ Q) ≡ ¬P ∧ ¬Q.
- Implication as Disjunction: P → Q ≡ ¬P ∨ Q.
- Contrapositive Equivalence: P → Q ≡ ¬Q → ¬P.
- Biconditional Expansion: P ↔ Q ≡ (P → Q) ∧ (Q → P) ≡ (¬P ∨ Q) ∧ (¬Q ∨ P).
Applying these rules systematically can turn a seemingly intricate formula into a manageable expression.
Study Tips for Mastering Logical Foundations
- Practice truth tables for each connective; they provide a visual confirmation of how truth values combine.
- Translate everyday sentences into symbolic form. For instance, "If it rains, the ground gets wet" becomes R → W.
- Use counterexamples to test universal statements. Finding a single element that falsifies P(x) disproves ∀x P(x).
- Review equivalences regularly; they are the shortcuts that save time during problem solving.
Conclusion
By mastering truth values, logical connectives, and quantifiers, you gain the language needed to articulate and verify mathematical arguments rigorously. The concepts covered in this course—truth assignments, negation, conjunction, disjunction, implication, contrapositive, biconditional, and universal quantification—form the core toolkit for any student of mathematics, computer science, or philosophy. Continue practicing with varied examples, and soon these logical structures will become second nature.
