Study your flashcards anywhere!

Download the official Cram app for free >

  • Shuffle
    Toggle On
    Toggle Off
  • Alphabetize
    Toggle On
    Toggle Off
  • Front First
    Toggle On
    Toggle Off
  • Both Sides
    Toggle On
    Toggle Off
  • Read
    Toggle On
    Toggle Off
Reading...
Front

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

image

Play button

image

Play button

image

Progress

1/58

Click to flip

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 a|b 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 = {x|xЄA \/ xЄB}
Intersection of A and B
The set A∩B ={x:xЄA /\ xЄB}
Difference of A and B
The set A-B ={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 = U-B.
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
Well-Ordering Principle
Every non-empty 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 R-related (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.
One-To-One
A function is said to be 1-1 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