Study your flashcards anywhere!
Download the official Cram app for free >
 Shuffle
Toggle OnToggle Off
 Alphabetize
Toggle OnToggle Off
 Front First
Toggle OnToggle Off
 Both Sides
Toggle OnToggle Off
 Read
Toggle OnToggle Off
How to study your flashcards.
Right/Left arrow keys: Navigate between flashcards.right arrow keyleft arrow key
Up/Down arrow keys: Flip the card between the front and back.down keyup key
H key: Show hint (3rd side).h key
A key: Read text to speech.a key
58 Cards in this Set
 Front
 Back
Proposition

A sentence that is either true or false


Conjunction

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


Disjunction

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


Negation

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


Propositional Form

A finite number of propositions together with logical connections


Tautology

A propositional form that is always true.


Contradiction

A propositional form that is always false.


Denial

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


Two propositional forms P and Q are equivalent iff

P and Q have both the same truth tables.


What's a conditional sentence?
Write out the truth table. 
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 

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

P is the antecedent and Q is the consequent.


Converse

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

Contropositive

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

What's a biconditional sentence?
Write out the truth table. 
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 

Open Sentence/Predicate

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.


Universe

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


Existential Quantifier

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.


Universal Quantifier

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.


Even

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


Odd

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


Divides

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


Prime

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


Absolute Value

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

Proof by Contropositive

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

Set

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


Elements

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. 

Empty Set

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


Subset

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)


When does set A equal set B?

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


Define A(_C)B

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) 

Power Set

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.


Union of A and B

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


Intersection of A and B

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


Difference of A and B

The set AB ={x:xЄA /\ xЄ~B}
(except the mark goes on top of the B) 

Disjoint

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


Complement

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


Universe

The set of objects under consideration.


Proof by Contradiction `

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

Pairwise Disjoint

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


Principle of Mathematical Induction

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 

Inductive

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


WellOrdering Principle

Every nonempty subset of lN has a least element.


Cartesian Product

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} 

Relation from A to B

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 Rrelated (or just related) to b.


Domain

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

Range

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

Inverse

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


Composite

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} 

function

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 

Codomain
What is the master codomain? 
The codomain is any set B such that Rng(f) _C B.
The master codomain is ҐR. 

Equivalence Class

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

Set of all equivalence classes

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

Reflexive

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


Symmetric

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


Transitive

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


OneToOne

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


Onto

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


Equivalence Relation

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