Ma 225

Front 1

Proposition

Back 1

A sentence that is either true or false

Front 2

Conjunction

Back 2

The conjunction of P and Q, denoted P /\ Q, is true exactly when both P and Q are true. "P and Q."

Front 3

Disjunction

Back 3

The disjunction of P and Q, denoted P \/ Q, is true exactly when at least 1 is true. "P or Q"

Front 4

Negation

Back 4

The negation of P, denoted ~P, is true exactly when P is false. "Not P."

Front 5

Propositional Form

Back 5

A finite number of propositions together with logical connections

Front 6

Tautology

Back 6

A propositional form that is always true.

Front 7

Contradiction

Back 7

A propositional form that is always false.

Front 8

Denial

Back 8

The denial of a propositional form, P, is any propositional form equivalent to ~P.

Front 9

Two propositional forms P and Q are equivalent iff

Back 9

P and Q have both the same truth tables.

Front 10

What's a conditional sentence?

Write out the truth table.

Back 10

A conditional sentence is "If P then Q" or P=>Q.

P Q P=>Q
T T T
F T T
T F F
F F T

Front 11

In the statement P=>Q or "if P then Q," what is the consqeuent and what is the antecedent?

Back 11

P is the antecedent and Q is the consequent.

Front 12

Converse

Back 12

Let P and Q be propositions.
The converse of P=>Q is Q=>P.

Front 13

Contropositive

Back 13

Let P and Q be propositions.
The contropositive of P=>Q is ~Q=>~P.

Front 14

What's a biconditional sentence?

Write out the truth table.

Back 14

For the propositions P and Q, the biconditional sentence P<=>Q is the proposition "P if and only if Q." P<=>Q is true when P and Q have the same truth tables.

P Q P<=>Q
T T T
F T F
T F F
F F T

Front 15

Open Sentence/Predicate

Back 15

A sentece that contains one or more varables and which becomes a proposition only when the varaibles are replaced by the names of particular objects.

Front 16

Universe

Back 16

The objects under consideration (or objects used to replace the variables).

Front 17

Existential Quantifier

Back 17

For an open sentence P(x), the sentence (╣Ex)P(x) is read there exists x such that P(x) or for some x, P(x), and is true iff the truth set of P(x) is nonempty.

Front 18

Universal Quantifier

Back 18

For an open sentence P(x), the sentence (\-/x)P(x)is read for all x, P(x) and is true iff the truth set of P(x) is the entire universe.

Front 19

Even

Back 19

An integer z is even iff there exists a k in the integers such that z=2*k.

Front 20

Odd

Back 20

An integer z is odd iff there exists a k in the integers such that z=2*k+1

Front 21

Divides

Back 21

Let a and b be integers. It's said that a divides b or a|b iff b=a*k for some k in the integers.

Front 22

Prime

Back 22

A natural number p is prime iff the only numbers that divide p are 1 and p.

Front 23

Absolute Value

Back 23

|x|={x if x>=0}
{-x if x<0}

Front 24

Proof by Contropositive

Back 24

Assume ~Q
:
:
~P
Therefore, ~Q=>~P
Thus P=>Q by controposition.

Front 25

Set

Back 25

A set is a collection of objects. Use brackets {} when defining a set.

Front 26

Elements

Back 26

The objects in a given collection (or members of the set). The symbol is the C with the dash through it.

Ex
B={1,2,3,4}
1 є B.

Front 27

Empty Set

Back 27

Φ or {} is the set with no elements in it.

Front 28

Subset

Back 28

Let A and B be sets. If all the elements of A are within B, we say that A is a subset of B<=>(\-/x)(xεA=>xεB)

Front 29

When does set A equal set B?

Back 29

Set A and B are equal iff A(_C)B and B(_C)A.

Front 30

Define A(_C)B

Back 30

We say that for every x in y is also contained in B.

Think of area which is the universe. An area B is contained within the universe. If A(_C)B, then an area A is contained within the area B.

A(C_)B iff (\-/x)(xЄA=>xЄB)

Front 31

Power Set

Back 31

Let A be a set. The power set of A is the set whose elements are the subsets of A is and is denoted with a funky P.

Front 32

Union of A and B

Back 32

The set AUB is = {x|xЄA \/ xЄB}

Front 33

Intersection of A and B

Back 33

The set A∩B ={x:xЄA /\ xЄB}

Front 34

Difference of A and B

Back 34

The set A-B ={x:xЄA /\ xЄ~B}

(except the mark goes on top of the B)

Front 35

Disjoint

Back 35

Two sets A and B are disjoint iff A∩B = Ø

Front 36

Complement

Back 36

If U is the universe and B(C_)U, then we define the complement of B to be the set of ~B = U-B.

Front 37

Universe

Back 37

The set of objects under consideration.

Front 38

Proof by Contradiction `

Back 38

Prove P
Pf: Suppose ~P
:
R
:
~R
(-><-)
Therefore by contradiction, P

Front 39

Pairwise Disjoint

Back 39

An indexed collection of sets {Aα: α є Δ} is said to be pairwise disjoint iff for all α and β in Δ, if Aα ≠ Aβ, then Aα∩Aβ = Ø

Front 40

Principle of Mathematical Induction

Back 40

If a set S is a nonempty subset of lN with the following 2 properties:
1) 1єS
2) \\-/n є lN if n є S, then n+1 є S
Then S=lN

Front 41

Inductive

Back 41

A set X is inductive iff X(C_)lN such that \\-/nєlN, if nєX, then (n+1)єX

Front 42

Well-Ordering Principle

Back 42

Every non-empty subset of lN has a least element.

Front 43

Cartesian Product

Back 43

Let A and B be sets. The sets of all ordered pairs having a first coordinate from A and a second coordinate from B is called the Cartestian Product of A and B is is written AxB.
Thus AxB={(a,b):aєA/\bєB}

Front 44

Relation from A to B

Back 44

Let A and B be sets. R is a relation from A to B iff R is a subset of A x B. If (a,b)єR, we write aRb and say a is R-related (or just related) to b.

Front 45

Domain

Back 45

The domain of the relation R from A to B is the set
Dom(R)={xєA:there exists yєB such that xRy)

Front 46

Range

Back 46

The range of the relationR is the set
Rng(R)={yєB: there exist xєA such that xRy).

Front 47

Inverse

Back 47

If R is a relation from A to B, then the inverse of R is R^-1={(y,x):(x,y)єR}.

Front 48

Composite

Back 48

Let R be a relation from A to B, and let S be a relation from B to C. The composite of R and S is
SoR={(a,c): there exists bєB such that (a,b)єR and (b,c)єS}

Front 49

function

Back 49

f is the relation from A to B such that
i. Dom(f)=A
ii. If f(x)=y and f(x)=z, then y=z

Front 50

Codomain

What is the master codomain?

Back 50

The codomain is any set B such that Rng(f) _C B.

The master codomain is ҐR.

Front 51

Equivalence Class

Back 51

If R is an equivalence relation from A to B
x/R={yєB:xRy}

Front 52

Set of all equivalence classes

Back 52

If R is an equivalence relation on A, then
A/R={x/R:xєA}

Front 53

Reflexive

Back 53

If R is a relation on A, then \-/xєA, xRx

Front 54

Symmetric

Back 54

If R is a relation on A, then \-/xєA and \-/yєA, if xRy, then yRx

Front 55

Transitive

Back 55

If R is a relation on A, then \-/xєA, \-/yєA, and \-/zєA, if xRy and yRz, then xRz.

Front 56

One-To-One

Back 56

A function is said to be 1-1 iff f(x)=f(y), then x=y.

Front 57

Onto

Back 57

A function is said to be onto B iff Rng(f)=B.

Front 58

Equivalence Relation

Back 58

R is a relation that is
i. Reflexive
ii. Symmetric
iii. Transitive