Notes › MATH 2130: Discrete Mathematics Lecture 1
Propositional Logic
304 words 3 min Modified
Table of Contents
Proposition
- A declarative statement that is true or false
- Symbolized with propositional variables (typically $p, q, r, s$)
Compound Propositions
- Can be constructed with the use of logical connectives
- $\neg$ Negation (“not”)
- $\land$ Conjunction (“and”)
- $\lor$ Disjunction (“or”)
- $\implies$ Implication (“implies”)
- $\iff$ Biconditional (“iff”)
- The propositions that build a compound proposition are known as atomic propositions
Logical Connectives Truth Table
| p | q | $p \land q$ | $p \lor q$ | $p \implies q$ | $p \iff q$ | $p \oplus q$ |
|---|---|---|---|---|---|---|
| T | T | T | T | T | T | F |
| T | F | F | T | F | F | T |
| F | T | F | T | T | F | T |
| F | F | F | F | T | T | F |
Converse, Contrapositive, and Inverse
- From $p \implies q$, we can form other conditional statements:
- Converse: $q \implies p$
- Inverse: $\neg p \implies \neg q$
- Contrapositive: $\neg q \implies \neg p$
- “It raining is a sufficient condition for my not going to town.”
- Converse: “If I do not go to town, then it is raining.”
- Inverse: “If it is not raining, then I will go to town.”
- Contrapositive: “If I go to town, then it is not raining.”
Truth Tables for Compound Propositions
- The number of rows are $2^n$ for $n$ propositional variables
- Need a column for every part of a compound proposition that is itself a proposition
- Need a column at the end for the entire compound proposition
Example Truth Table
- Construct a truth table for $p \lor q \implies \neg r$
| $p$ | $q$ | $r$ | $\neg r$ | $p \lor q$ | $p \lor q \implies \neg r$ |
|---|---|---|---|---|---|
| F | F | F | T | F | T |
| F | F | T | F | F | T |
| F | T | F | T | T | T |
| F | T | T | F | T | F |
| T | F | F | T | T | T |
| T | F | T | F | T | F |
| T | T | F | T | T | T |
| T | T | T | F | T | F |
References
- Course slides §1.1: Propositions
Sources
- Course slides §1.1: Propositions