MA121 Lecture Notes - Lecture 4: Subset, Empty Set, Contraposition

50 views2 pages
11 Feb 2019
School
Department
Course
Professor

For unlimited access to Class Notes, a Class+ subscription is required.

MA121 1 - Tutorial Fall 2018
I. Recall the truth tables of the following most basic logical operations on “simple” statements pand qwith connectives
,,and , respectively.
Negation
pp
T F
FT
Conjunction
p q pq
T T T
T F F
F T F
F F F
Disjunction
p q pq
T T T
T F T
F T T
F F F
Conditional
p q pq
T T T
T F F
F T T
F F T
Truth tables of all other compound statements involving two or more “simple” statements may be constructed using
the above basic ones.
II. Recall the following most frequently used nontrivial equivalence relationships:
Contrapositive
pq q→∼ p
Distributive Laws
p(qr)(pq)(pr)
p(qr)(pq)(pr)
De Morgans Laws
(pq)(p)(q)
(pq)(p)(q)
These equivalences, together with other more trivial equivalences such as p⇔∼ (p), may be used to verify other
equivalence relationships.
III. Let A,Band Cbe sets containing elements of the same non-empty universal set U. Recall the following definitions
and theorems from set theory.
Definition 1. The sets Aand Bare equal, denoted A=B, if Aand Bcontain exactly the same elements. Otherwise,
A6=B.
Denition 2. The set Ais a subset of B, denoted AB, if every element of Ais also an element of B; that is, if
xA, then xB. If ABbut A6=B, we say Ais a proper subset of B, denoted AB.
Denition 3. The union of Aand Bis the set
AB={xU:xAor xB}.
Denition 4. The intersection of Aand Bis the set
AB={xU:xAand xB}.
Denition 5. The set dierence Aminus Bis the set
AB={xU:xAand x /B}.
In particular, UB, denoted Bc, is called the complement of B(in U).
Theorem 1. (a) AU, where is the empty set and Ais any subset of the universal set U.
(b) If ABand BC, then AC.
(c) A=Bif and only if ABand BA.
Examples. Determine if each of the following statements is true or false, and try to understand the given justications
by the denitions and theorems listed above.
(a) {∅}. ( T rue /False)
Justication:By Theorem 1(a), is a subset of any set A. Thus, {∅} if we take Aas the set {∅}.
Remark. Here {∅} is also true because the set contains as its element.
Unlock document

This preview shows half of the first page of the document.
Unlock all 2 pages and 3 million more documents.

Already have an account? Log in

Get access

Grade+
$10 USD/m
Billed $120 USD annually
Homework Help
Class Notes
Textbook Notes
40 Verified Answers
Study Guides
1 Booster Class
Class+
$8 USD/m
Billed $96 USD annually
Homework Help
Class Notes
Textbook Notes
30 Verified Answers
Study Guides
1 Booster Class