Introduction to set theory/Lecture 1
< Introduction to set theoryIntroduction
We will start the course by introducing Propositional Logic. Even though this is a set theory class and not a logic course, most of notations from the logic courses can be used in set theory. Furthermore, logic is important in various proofs we will encounter in this course.
Notations
Here are the notations and what they mean:
| Symbols | Meaning |
|---|---|
 |
and (conjunction) |
 |
or (nonexclusive disjunction) |
 |
not (negation) |
 |
if then/implies |
 |
if and only if |
Truth Table
Truth tables are used to analyze formulae of propositional logic.
Example
Truth table for 
 |
 |
 |
|
|---|---|---|---|
| T | T | T | T |
| T | F | T | T |
| F | T | F | T |
| F | F | T | T |
Tautology
Definition
A formula 
of propositional logic is a tautology if only T's occur in the column of the truth table.
Examples
Truth table for 
| |
 |
 |
|
|---|---|---|---|
| T | F | F | T |
| F | T | T | T |
Truth table for 
| |
|
 |
 |
 |
|
|
|---|---|---|---|---|---|---|
| T | T | F | F | F | F | T |
| T | F | T | F | F | F | T |
| F | T | F | F | T | T | T |
| F | F | T | F | T | T | T |
Truth table for 
| |
|
|
 |
 |
|
|---|---|---|---|---|---|
| T | T | F | T | T | T |
| T | F | F | F | F | T |
| F | T | T | T | T | T |
| F | F | T | T | T | T |
Tautological Equivalence
Definition
The proposition formulas 
and are tautologically equivalent if 
is a tautology.
Examples
Contraposition: 
is tautologically equivalent to 
.
| |
|
|
|
|
|
 |
|---|---|---|---|---|---|---|
| T | T | F | F | T | T | T |
| T | F | T | F | F | F | T |
| F | T | F | T | T | T | T |
| F | F | T | T | T | T | T |
de Morgan's Law I: 
is tautologically equivalent to 
.
| |
|
|
|
 |
|
|
|
|---|---|---|---|---|---|---|---|
| T | T | F | F | T | F | F | T |
| T | F | F | T | T | F | F | T |
| F | T | T | F | T | F | F | T |
| F | F | T | T | F | T | T | T |
de Morgan's Law II: 
is tautologically equivalent to 
.
Truth table for Assignment #1
Related Resources
The materials in this course overlap with Introductory Discrete Mathematics for Computer Science, particularly Lesson 1.