MATH 213

呜呜呜，开学这种事情不要啊

………………………………………………………………………………………………………………………………

………………………………………………………………………………………………………………………………

………………………………………………………………………………………………………………………………

Logic and Mathematical Proofs

Propositional Logic

Proposition: a declarative sentence that is either true or false (not both).

• Conventional letters used for propositional variables are , , , , …
• Truth value of a proposition: true(T); false(F).

logical connectives: build compound propositions

• , , , , (Implication), (Biconditional).

Tautology and Logical Equivalences

Tautology: A compound propostion that is always true. ()

Contradiction: A compound proposition that is always false. ()

Logically equivalent: and are called logically quivalent (), if is a tautology

Predicate logic and Quantified Statements

Predicate Logic: make statements with variables: .

Quantified Statements: Universal quantifier ; Existential quantifier .

;

Validity of Argument Form

The argument form with premises and conclustion is valid, if is a tautology.

Sets and Functions

Sets

A set is an unordered collection of objects.

• listing (enumerating) the elements
• if enumeration is hard, use ellipses (…)
• definition by property, using the set builder

Cardinality: If there are exactly distinct elements in , where is a nonnegative integer, we say that is a finite set and n is the cardinality of , denoted by

Power Set: given a set , the power set of is the set of all subsets of the set , denoted by

Tuples: The ordered n-tuple is the ordered collection that has as its first element and as its second element and so on.

Cartesian Product: Let and be sets. The Cartesian product of and , denoted by , is the set of all ordered pairs , where and :

Set Operations

• Union:
• Intersection:
• Complement:
• Difference:

Function

Let and be two sets. A function from to , denoted by , is an assignment of exactly one emenet of to each element of .