Logical Operations
The five logical connectives, the syntax of compound formulas, and the duality between predicate operations and set operations.
Start Learning
Learning Objectives
On completing this unit, the student will be able to:
- State the truth conditions of negation, conjunction, disjunction, implication, and equivalence.
- Distinguish between necessary and sufficient conditions in a conditional statement, and identify the converse, inverse, and contrapositive of an implication.
- Parse a compound formula into its sub-formulas using operator precedence and parentheses.
- Construct the truth table of a propositional formula in any number of variables.
- Classify a formula as a tautology, a contradiction, or a contingent formula on the basis of its truth table.
- Establish logical equivalence either by truth table or by appeal to the standard equivalence laws (commutativity, associativity, distributivity, De Morgan, contrapositive, double negation, etc.).
- Apply the connectives to predicates and translate the resulting formulas into the language of sets, exploiting the duality between propositional and set operations.
About This Course Unit
Building on the language of Unit 1, this unit develops propositional logic as a calculus. We define the five connectives — negation, conjunction, disjunction, implication, and equivalence — by their truth conditions, and use them to build compound formulas of arbitrary complexity. The truth table is introduced as the canonical decision procedure: it lets us test whether a formula is a tautology, a contradiction, or contingent, and it lets us prove logical equivalence between formulas. Finally, we lift the connectives from propositions to predicates and discover a structural correspondence with the operations of set theory: conjunction matches intersection, disjunction matches union, negation matches complement. This duality is one of the central insights of the course.