Logic
What is Logic?
A declarative statement that is either true or false.
Key formula / rule: Conjunction (AND)
Key points
- Understand the concept of propositions and logical connectives.
- Construct and interpret truth tables.
- Identify tautologies, contradictions, and contingencies.
- Apply logical equivalences and laws (e.g., De Morgan's laws).
Common exam trap
Confusing implication (P → Q) with its converse (Q → P) or inverse (¬P → ¬Q).
Definitions
- Term
Proposition
- Meaning
A declarative statement that is either true or false.
- Term
Truth Table
- Meaning
A table that shows all possible truth values of a compound proposition based on the truth values of its atomic propositions.
- Term
Tautology
- Meaning
A compound proposition that is true for all possible truth assignments of its variables.
- Term
Contradiction
- Meaning
A compound proposition that is false for all possible truth assignments of its variables.
- Term
Logical Equivalence
- Meaning
Two compound propositions are logically equivalent if they have the same truth value for all possible truth assignments.
- Term
Quantifier
- Meaning
A symbol (like ∀ for 'for all' or ∃ for 'there exists') used in predicate logic to specify the quantity of elements for which a predicate holds.
Learning objectives
Understand the concept of propositions and logical connectives.
Construct and interpret truth tables.
Identify tautologies, contradictions, and contingencies.
Apply logical equivalences and laws (e.g., De Morgan's laws).
Understand the basics of predicate logic and quantifiers.
Formulae
- Name
Conjunction (AND)
- Note
True if and only if both P and Q are true.
- Expression
P ∧ Q
- Name
Disjunction (OR)
- Note
True if and only if at least one of P or Q is true.
- Expression
P ∨ Q
- Name
Negation (NOT)
- Note
True if P is false, and false if P is true.
- Expression
¬P
- Name
Implication (IF...THEN)
- Note
False if and only if P is true and Q is false. Equivalent to ¬P ∨ Q.
- Expression
P → Q
- Name
Biconditional (IF AND ONLY IF)
- Note
True if and only if P and Q have the same truth value. Equivalent to (P → Q) ∧ (Q → P).
- Expression
P ↔ Q
- Name
De Morgan's Law 1
- Note
The negation of a conjunction is the disjunction of the negations.
- Expression
¬(P ∧ Q) ≡ ¬P ∨ ¬Q
- Name
De Morgan's Law 2
- Note
The negation of a disjunction is the conjunction of the negations.
- Expression
¬(P ∨ Q) ≡ ¬P ∧ ¬Q
- Name
Contrapositive
- Note
An implication is logically equivalent to its contrapositive.
- Expression
P → Q ≡ ¬Q → ¬P
Prerequisites
Basic understanding of mathematical statements and their truth values.
Familiarity with set theory concepts can be helpful.
Common mistakes
Confusing implication (P → Q) with its converse (Q → P) or inverse (¬P → ¬Q).
Incorrectly applying De Morgan's laws.
Assuming that if a conclusion is true, the premises must also be true (fallacy of affirming the consequent).
Errors in constructing or interpreting truth tables for complex statements.
Keywords
Logic
Propositional Logic
Predicate Logic
Truth Table
Connectives
Tautology
Contradiction
Logical Equivalence
Quantifiers
Deductive Reasoning
Argumentation
Practice preview
Consider the statement: "If it rains, then the ground is wet." Which of the following statements is logically equivalent?…
easy
What is the negation of the statement: "All students like mathematics and some students like physics"?…
easy
In a group of 100 students, 70 students like Physics, 45 students like Chemistry, and 30 students like both. How many students like neither Physics nor Chemistry?…
medium