cmpsc360notesAsOf2/13

EVERYTHING FROM THE CLASS THE WHOLE SEMESTER THE DOCUMENT~~~~~~~~~~~~~
Day 1: HW: 1.1 1-37 odds + 1.2 1-7 odd

Discrete Objects vs. Continuous Objects
1. Discrete means it's segremented.. not continuous
	(That's kinda broad isn't it?)
	1.1. Why is discrete math important to Comp Sci?
		1.1.1 Logic! (Booleans and what not / Circuit gates / program flow)
		1.1.2 Algorithms (Time Complexity / Storage Space + memory / Validity)
			1.1.1.1 Validity means .. it does what it needs to all the time
				Justification (ie. Proofs) that it is valid is DMath
		1.1.3 Objects and Terminology used in Algorithms and Analysis

FIRST TOPIC!!!!!!!!!!!!!!!!!______________________________________________________
****************************LOGIC*************************************************
Defintion of Propositional Logic - is a declaration that is (True or False)

EXAMPLES

Sun Sets in the North (FALSE)
Bob has Purple Hair (??? Whos is Bob... I guess he could but it is either True or False)
Jane got up at 8am Today (Same as above)

you can do it with math too.. and not sentences

1 + 3 = 4 (True)
2 < 1 (False)

x < 3 (Not a well defined truth value.. this is relevant currently but it will be)

LOGICAL OPERATORS
let p == "Jane got up before 8am today"
let q == "Jane is tired"

Logical Operator - NEGATION
~P = NOT P - "Jane did not get up before 8am"

Logical Operator - CONJUNCTION
p ^ q - P and Q - "Jane got up before 8am and Jane is tired"

Logical Operator - DISJUNCTION
p v q - P or Q - "Jane got up before 8am or Jane is tired"
(This means Either one or the other, or BOTH)

TRUTH TABLES
p|~p|q|~q|p v q|p + q|p->q|p^q|
-------------------------------
T| F|T| F|  T  |  F  | T  | T |
-------------------------------
F| T|F| T|  F  |  F  | T  | F |
-------------------------------
T| F|F| T|  T  |  T  | F  | F |
-------------------------------
F| T|T| F|  T  |  T  | T  | F |

Show all possible truth values

Logical Operator - Exclusive Disjunction (exclusive Or)
p + q (p xor q)
"Jane got up before 8am or Jane is tired... but not both"
P = False & Q = False - P+Q = False
P = True & Q = TRUE - P+Q = False
P = True & Q = False - P+Q = True
P = False & Q = True - P+Q = True

Logical Operator - Conditional (if then)
p -> q
"If jane got up before 8am then jane is tired"
NOTE: If the p is false then q could be true (see truth table)
ie. Only is false if q is false... true is p is false

EXPRESS THE FOLLOWING IN SYMBOLIC FORM
r - "Bob takes the stairs"
s - "The elevator is working"
t - "It is over 90 degrees"

"It is over 90 degrees or the elevator is working" - Disjunction (t ^ s)
"If the elevator is not working then Bob takes the stairs" - Conditional (~s -> r)
"Bob takes the stairs only if it is not over 90 degrees" - Conditional (r -> ~t)

__________________________________________________________________________________________
RELATED IMPLICATIONS
P - "You clean your room"
Q - "I will give you candy"

Original - (P -> Q) - "If you clean your room then I will give you candy"
Converse - (Q -> P) - "If I give you candy then you cleaned your room"
Inverse -  (~P -> ~Q) - "If you didn't clean your room then I won't give you candy"
ContraPositive - (~Q -> ~P) - "If I won't give you candy then you didn't clean your room"

NOTE: Then does not imply conrological events.. it's only an implication

Converse is not the same as the original (Original != Converse)

P|Q|P->Q|Q->P|
---------------
T|T|  T | T  |
---------------
F|T|  T | F  |
---------------
T|F|  F | T  |
---------------
F|F|  T | F  |

SEE! Not the same!

Logical Operator - Biconditional (if and only if)
p <-> q  (Can be written as (p->q) ^ (q->p) but no ones does cus that's gay)
"I will give you candy if and only if you clean your room"

TRUTH TABLE FOR ~(p->q) ^ ~q

P|~P|Q|~Q|(P->Q)|~(P->Q)|~(P->Q) ^ ~Q|
--------------------------------------
T| F|T| F|  T   |   F   |     F      |
--------------------------------------
T| F|F| T|  F   |   T   |     T      |
--------------------------------------
F| T|T| F|  T   |   F   |     F      |
--------------------------------------
F| T|F| T|  T   |   F   |     F      |
--------------------------------------

TRUTH TABLE FOR (p ^ q) <-> r

P|Q|R|(P^Q)|(P^Q)<->R|
----------------------
T|T|T|  T  |    T    |
----------------------
T|T|F|  T  |    F    |
----------------------
T|F|T|  F  |    F    |
----------------------
T|F|F|  F  |    T    |
----------------------
F|T|T|  F  |    F    |
----------------------
F|T|F|  F  |    T    |
----------------------
F|F|T|  F  |    F    |
----------------------
F|F|F|  F  |    T    |
----------------------


DAY 2: HW: 1.3 1-15 odds + 61
ASSIGNMENT 1: DUE THURSDAY Jan. 18
DAILY REMINDER: Attendance + Particiaption is a big thing in this class

HW REVIEW:
1.1 15B
P = "Grizzly bears have been seen in the area"
q = "Hiking is safe on the trail"
r = "Berrys are ripe along the trail"
15B) Grizzly bears have not been seen in the area and hiking is safe... but berrys are ripe along the trail
(~p ^ q) ^ r

1.1 23D
"It is necessary to walk 8 miles to get to the top of Long's Peak"
P = "walking 8 miles"
Q = "To get to long's peak"
Q -> P
If you were to get to the top of long's peak then you walked 8 miles
______________________________________________________________________________________________________________
NEW TOPIC: Compound Proposition
definition: that is always true is called a "Tautology"
definition: that is always false is called a "Contradiction"
definition: that is sometimes true & sometimes false is called a "Contingency"
definition: that is true in AT LEAST one case is "Satisfiable" (ie. is a Tautology or a Contingency)
EXAMPLES:
Tautology - (P v ~P)
Contradiction - (P ^ ~P)
Contingency - (P ^ Q) v R *****MOST COMPOUND PROPOSITIONS ARE LIKE THIS*******

Truth Table for Tautology and Contradiction

P|~P|(Pv~P)|(P^~P)|
-------------------
T|F|   T   |   F  |
-------------------
F|T|   T   |   F  |
-------------------

Is the following a tautology, contradiction or contigency: r v (r -> ~s)
Start with a truth table

r|s|~s|(r->~s)|rv(r->~s)|
-------------------------
T|T|F |   F   |    T    |
-------------------------
T|F|T |   T   |    T    |  EVERYTHING IN THE FINAL LINE IS *TRUE* ERGO: IT'S A TAUTOLOGY
-------------------------
F|T|F |   T   |    T    |
-------------------------
F|F|T |   T   |    T    |
-------------------------

LOGICAL EQUIVILENCE:
U and Z are logically equivilent iff U <-> Z is a tautology!
Remember... When is a biconditional (<->) always true: When both things (U&V) have the same truth values
Represented by Three lines like an equals sign and I can't type that so... I'll denote it as =-
	(Just imagine that the left line is jammed in the middle of the equalsign)
EXAMPLE: (P->Q) =- (~Q -> ~P)

P|Q|~P|~Q|(P->Q)|(~Q -> ~P)
---------------------------
T|T|F | F|   T  |    T    |
--------------------------
T|F|F | T|   F  |    F    |   Both are the same in the last column..
--------------------------
F|T|T | F|   T  |    T    |         ERGO: (P->Q) =- (~Q->~P)
---------------------------
F|F|T | T|   T  |    T    |
---------------------------

COMMON LOGICAL EQUIVELENCIES (Table in text)

IDENTITY LAWS
P ^ T = P
P v F = P

DOMINATION LAWS
p v T = T
p ^ F = F

IDEMPOTENT LAWS
P v P = P
P ^ P = P

DOUBLE NEGATION LAWS
~(~P) = P

COMMUNITATIVE LAWS
P v Q = Q v P
P ^ Q = Q ^ P

ASSOCIATIVE LAWS
(P v Q) v R = P v (Q v R)
(P ^ Q) ^ R = P ^ (Q ^ R)

DISTRIBUTIVE LAWS
P v (Q ^ R) = (P v Q) ^ (P v R)
P ^ (Q v R) = (P ^ Q) v (P ^ R)

DEMORGANS LAWS
~(P ^ Q) = ~P v ~Q
~(P v Q) = ~P ^ ~Q

ASBORPTION LAWS
P v (P ^ Q) = P
P ^ (P v Q) = P

NEGATION LAWS
P v ~P = T
P ^ ~P = F

CONDITONAL
P -> Q = ~P v Q

CONTRAPOSITIVES
P -> Q = ~Q -> ~P

NEGATION OF CONDITIONAL
~(P -> Q) = (P ^ ~Q)

BICONDITIONAL LAW
P <-> Q = (P -> Q) ^ (Q -> P)

INVERSE OF BI CONDITIONAL
P <-> Q = ~P <-> ~Q

Show using identities:
(P v ~Q) -> r =- (~P v R) ^ (Q v R)
~(P v ~Q) v R (Conditional)
(~P ^ Q) v R (deMorgans) - *NOTE* You used a (double negation) here too on the Q
(~P v R) ^ (Q v R) (Distributive)
DONE!

Identities can help simplify expressions too! *'Nam Flashbacks from Trig*
SHOW (P ^ ~Q) -> (P v Q)  is a tautlogy using identities

~(P ^ ~Q) v (P v Q) - Conditional
(~P v Q) v (P v Q) - deMorgans - and double negation
~P V P V Q V Q - Associative
Q v ~P v P - Impodent
Q v (T) - Negation
T - Domination

_________________________________________________________________________________________________________
PROPOSITONAL SATISFIABILITY!!!!
def: A propsition is satisfiable iff it is true in at least one case!
You can determine it in 2 different ways:
1. Truth Table.. the tried and true method! *BRUTE FORCE METHOD!* *VERY SYSTEMATIC* ... but takes ages as it gets                 a larger number of variables
2. Show one case where the statement is true! (more coming next time!)

__________________________________________________________________________________________________________
Day 3:
HW: 1.4 1-25 odds - REMINDER Assignment #1 is due next class

Note: Whenever you are doing identities with conditionals.. USUALLY 99% of the time you will use the conditional laws
PROPOSITONAL SATISFIABILITY CONTINUED:
	a proposition must be true in at least one case
The ideal methods for these is to find one case on your own without a truth table that would make the expression true

EXAMPLE:
	determine whether the following is satisfiable and justify your answer
p^~q
[the insite approach] ... Well.. we know it will be true when P is true and ~Q is True... therefore the expression will be true when P is true and Q is false

p^~p
Not satisfiable by the Negation laws

~(pvq) ^ ~(~p->r) *this would be a pain in the ass to do normally.. so lets do identities
(~p ^ ~q) ^ (~p ^ ~r) // Demorgans and Negation of conditional
(~p ^ ~p) ^ (~q ^ ~r) // Associative & communitiy
(~p) ^ (~q ^ ~r) // idempotent identity
If p = F and q = F and r = F then the statement is true.. Therefore the expression is satisfiable
_____________________________________________________________________________________________________________
NEW TOPIC: Section 1.4!!!!
Predicate Logic!
"Student X is Twenty years old"
---------  -------------------
SUBJECT          PREDICATE

X > 3 .. x is the subject .. 3 is predicate

Propositional Function: EXAMPLE
Let P(x) denote "x > 3"
Let Q(x,y) denote "y = x^2"

P(2) = False
P(8) = True
Q(2,4) = True
Q(4,2) = FALSE!

QUANTIFIERS
∀(x) - Universal - "For all x *in the domain* P(x) holds"
∃(x) - Existence - "There exists an x *in the domain* such that P(x) is true"
∃!(x)- Uniqueness - "There exists exactly one x *in the domain* such that P(x) is true"

EX.
∃x(x>3) - There exists an X that is greater than 3
∀x(x + 1 > x) - For all X there is a number greater than it
A Propositional Function should have a DOMAIN! So there are *right* but too general
	Sometimes... The domain is implicit if it is obvious.. But sometimes you just have to
	specify to make it True
EXAMPLE OF WHY THIS IS IMPORTANT:
∃x (x = pi) - Domain is Integers: False
∃x (x = pi) - Domain is all real numbers: True
∀x (x^2 >= x) - Domain is Integers: True
∀x (x^2 > = x) - Domain is all reals: False

Symbolic to English Translations
P(x) = "x is enrolled in CMPSC360"
Q(x) = "x knows C++"
R(x) = "x likes basketball"
DOMAIN: Students at PSU harrisburg
∃xP(x)  - "At least one student at penn state harrisburg is enrolled in 360" = True
∀xQ(x) - "All students at PSH know c++" = FALSE
∃!x(P(x) ^ R(x)) = "There exists only one student enrolled in cmpsc360 and likes basketball" = Probably true there can't be more than 1 non-autistic cunt
"There is a student at psh who does not like basketball" - ∃x(~R(x))
"There is a student and PSH who knows C++ but is not enrolled in CMPSC 360" - ∃x(Q(x) ^ ~P(x))

RESTRICTING THE DOMAIN via DOMAIN NOTATION
∃x<0,(x^2=2) - "There is a negative real number that is equal to 2 when squared"
∀y!=0, (y^2 > 0) - "For all Y's that aren't 0, y^2 is greater than 0"

Existence and Uniqueness are restricted by adding AND
∃x[(x < 0) ^ (x^2 = 2)]
There exists and X that is less than 0 and it's square is equal to 2

Universals are restricted by adding the restriction as a premise to an implication
∀y[(y!=0) -> (y^2 > 0)]
"For all y, if y != 0 then y^2 > 0"

EXAMPLE:
"Every student at PSH enrolled in CMPSC360 knows C++"
∀x[(P(x)) -> (Q(x))]
"There is a student in psh who is enrolled in CMPSC360 who does not like basketball"
∃x[p(x) ^ ~R(x)]
________________________________________________________________________________________________________
Thursday Jan. 25 - HW 2 Due! First Quiz too! All information from before and today!
HW: 1.4 33 37 39 53 && 1.5 1-15 odd 19-27 odd 31 33

HW review: 1.4 19E
Suppose domain contains {1,2,3,4,5}
display (FOR ALL)x (x != 3) -> P(x)) v (THERE EXISTS)x(~P(x))
	(P(1) ^ P(2) ^ P(4) ^ P(5)) v (P(1) v P(2) v P(3) v P(4) v P(5))
________________________________________________________________________________________________________
NEW TOPICS: Negation of Quantifiers
DeMorgans
~(∀x(P(x))) =- ∃x(~P(x))
~(∃x(P(x))) =- ∀x(~P(x))

Examples:
P(x) = "x has purple hair"
S(x) = "x has a smart phone"
Y(x) = "x is a new yorker"
domain is everyone in class

∀x(S(x)) = Everyone in class has a smart phone
~(∀x(S(x))) = ∃x(~S(x)) = someone in class does not have a smart phone
∃x(Y(x) ^ P(x)) = "Someone in class is a new yorker and has purple hair"
~(∃x(y(x) ^ (P(x)))) = ∀x(~y(x) v ~p(x)) = All people in class are not a new yorker or do not have purple hair

Negate and simplify the following (all negations  directly precede predicates)
(∀x(R(x))) ^ (∃x(Q(x)))
~((∀x(R(x))) ^ (∃x(Q(x)))) == ∃x(~R(x)) v ∀x(~Q(x)) // I used demorgans 2x on this one

Binding variables:
∀x(Q(x,y)) ... the x after the ∀ is the 'scope'
					     note how variable y exists... x is bound and y is free
							 The expression is called a "Propositional Function of Y"
∃x(x =1) ^ ∃x(x = 2) = TRUE
											 It is true because each x is a different scope that's why it can be both 1 && 2
∃x(x = 1 ^ x = 2) = FALSE
				            is false because X cannot be 1 and 2 at the same time
Nested Qualifying statements
	∃y∀x(Q(x,y)) <--- you can do this shit
EXAMPLE
Let P(x,y) denote "Student x has used computer y"
x = all students, y = computers
∀x∃y(P(x,y)) = "For every student x, there exists a computer student x has used"
						 = "Every student has used a computer" - almost certainly true
∃y∀x(P(x,y)) = "there exists a computer y, that all students x has used"
			       = "There is a computer that all students have used" - certainly false
The point of these 2 statements is that just because you flip the qualifiers doesn't mean it's equal
EXAMPLE:
Express the following in symbolic form...
	P(x,y) "Student x has taken course y"
	Q(y) "y is a programming course"
	R(x) "x has blond hair"
	*x is the domain of students && y is the domain of all courses*
	"Every course has been taken by at least one student" = ∀y(∃x(P(x,y)))
	"Every student has taken exactly one programming course" = ∀x(∃!y(Q(y) ^ P(x,y)))
	"No course has been taken by all students" = ~∃y(∀x(P(x,y))) // think of "No course" is ~∃y

SOLVE AND SHARE EXAMPLE:
	A(x) = "x likes apricots"
	B(x) = "x likes bread"
	C(x,y) = "x has called y"
	x & y domains = all people
translate the following:
	∃y∃x(A(x) ^ C(x,y)) = There exists Someone who likes apricots and has called someone // logically equivlent
			    = There is a person called by someone who likes apricots // more proper english edition
	"There is someone who has called everyone" = ∃x∀y(C(x,y))
Negate and simplify
∀x(Q(x) ^ ∃y(R(x,y)))
∃x(~(Q(x) ^ ∃y(R(x,y))))
∃x(~Q(x) v ∀y(~R(x,y)))

Why are Qualifiers important?: Many properties and theorems are expresable as quantified statement
Communative property of addition ∀x∀y(x + y = y + x)
Existence of a multiplicate identity : ∃x∀y(x*y = y = y * x)
Existance of multiplicate inverse: ∀x((x!=0) -> ∃y(xy = 1)) (recipricols exist)
__________________________________________________________________________________________________________
Day: Already lost track of the Days: First day in the box
HW Questions: 1.5
QUIZ AND HW NEXT CLASS: Quiz is up til 1.5 (ie. EVERYTHING ABOVE THE LINE ABOVE)

Intoduction to Proofs:
Rules of Inference and Logical Arguments:
"You eat mushrooms... Then you will get sick"
So... "You eat mushrooms" Therefore you will get sick

MODUS PONENS
p -> q
p
therefore q

MODUS TOLLENS
~q
p -> q
therefore ~p

HYPOTHETICAL SYLLOGISM
p->q
q->r
therefore p->r

DISJUNCTIVE SYLLOGISM
p v q
~p
therefore q

ADDITION
p
therefore p v q

SIMPIFICATIONS
p ^ q
therefore p (or q)

CONJUNCTION
p
q
therefore p ^ q

RESOLUTION
p v q
~p v r
therefore q v r

PRACTICE: Identify the rule of inference in the following argument
"I win or my name is mud"
"I do not win"
therefore "My name is mud"
Disjunctive Syllogism

"I like playing checkers"
"I like playing chess"
therefore "I like playing checkers and chess"
Conjunction

r -> u
s v r
~u
therefore s

We will justify this via a step reson table

step         |        reason
----------------------------------------------
r -> u       |    Premise (Given assumed true)
~u           |    Premise (Given assumed true)
~r           |    True due to modus tolens
s v r        |    Premise (given assumed true)
s            |    True due to Disjunctive Syllogism

"If Herb plays guitar then he joins a band" (p -> q)
"Herb gets a tattoo, but does not join a band" (r ^ ~q)
therefore: "Herb gets a tattoo and does not play guitar" (r ^ ~p)

step       |       reason
-----------------------------------------
p -> q     |  Premise
r ^ ~q     |  Premise
~q         | Simplification
~p         | Modus Tollens
r          | Simplification
r ^ ~p     | Conjunction

FALACIES:
"If he was innocent then he would say he is innocent"
"He says he is innocent"
therefore he is innocent
It's a fallacy known as "Affirming the conclusion"

AFFIRMING THE CONCLUSION
p -> q
q
therefore p (FALSE)



7 = 9
-8  -8
-1 = 1
square both sides
1 = 1
Once again affirming the conclusion

Solve and Share:
"Alice is a programmer or a tester" (p v q)
"Bob is a programmer but not a tester" (r ^ ~s)
"Either alice or bob is not a programmer" (~p v ~r)
therefore: Either alice or bob is a tester  (q v s)

step       |    reason
-----------------------------------------
p v q      |  Premise
r ^ ~s     |  Premise
~s         |  Simplification  // This is Extranious... You can omitt this
r          |  Simplfication
~p v ~r    |  Premise
~p         |  Disjunctive syllogism
q          |  Disjunctive syllogism
q v s      |  Addition

RULES OF INFERENCE FOR QUANTIFIED STATEMENTS
UNIVERSAL INSTANTIATION
∀xP(x)
therefore P(c)

UNIVERSAL GENERALIZATION
P(c)
therefore ∀xP(x)

EXISTENTIAL INSTANTIATION
∃xP(x)
therefore P(c) // for some element C

EXISTENTIAL GENERALIZATION
P(c) // for some element of C
∃xP(x)

PRACTICE
R(x) - x has read War and Peace
L(x) - x has had a Literature Class

∀x(R(x) v ~L(x))
∃x(~R(x))
therefore ∃x(~L(x))

step                |    reason
-------------------------------------------
∀x(R(x) v ~L(x))    | Premise
∃x(~R(x))           | Premise
~R(c))              | Existential Instantiation (2)
R(c) v ~L(c)        | Universal Instantiation (1)
~L(c)               | Disjunctive Syllogism (3 and 4)
∃x(~L(x))           | Existential Generalization (5)

Oh and guess what.. you gotta know all the names boi

INTRO TO PROOFS:
Definition: An integer is Even iff
					  n = 2K (ie. is a multiple of 2)
Definition: An integer is odd iff
			      n = 2K + 1 (ie. is a multiple of 2 plus 1)
Definition: Every integer is even or odd but not both
____________________________________________________________________________________________________________
Day 2 in the box  - Proofs continued
Normal Theorem Structure:
∀x(P(x) -> Q(x)) - P is the premises Q is the conclusion
example:
∀x(x > 0 -> |x| = x)
---------------------------------------------------------------------------------------------
Direct Proof: Assume P(x), show: Q(x)

Proposition: If N is even then 3n + 4 is even
∀n(n is even -> 3n+4 is even)
Assume n is even, so n = 2k for some integer k
TO SHOW: 3n + 4 is even 3n + 4 = 2()
3n + 4 = 3(2k) + 4 = 6k + 4 = 2(3k + 2)
where 3k + 2 = j
therefore 2(j)
so 3n + 4 is even[] <--- use the silly box thing at the end of the proof
---------------------------------------------------------------------------------------------
Proof by Contraposition
Assume: ~Q(x)
show: ~P(x)
∀x(~Q(x) -> ~P(x)) =- ∀x(P(x) -> Q(x)) (remember)

Proposition: For an integer n, if 3n+4 is even then n is even
Proof: Proof by contraposition, assume n is odd
to show: 3n+4 is odd
so... n = 2k + 1 for some integer k
Notice: 3(2k + 1) + 4 = 6k + 7 = 2(3k + 3) + 1
As 3k + 3 is an integer, so 3n + 4 is odd.  By contraposition, 3n + 4 is even implies n is even
------------------------------------------------------------------------------------------------
Proof by Contradiction
Assume: P(x) and also ~Q(x)
Show: a contradiction follows (R(x) ^ ~R(x))
Proposition: For integers p and q if pq = 800 then p is even or q us even
Proof: Assume pq = 800 Assume for sake of contradiction that both p and q are odd
so that p = 2k + 1 and q = 2l + 1
so that (2k + 1)(2l + 1) = 4kl + 2k + 2l + 1 = 2(2kl + k + l) + 1
as 2kl + k + l is an integer so pq is odd.. but 2(400) = 800 is even
-><- So by contradiction p or q must be even
-----------------------------------------EXAMPLE--------------------------------------------
Definition:
A Real Number is rational iff there exists integer p and q != 0 so that r = p/q if a real number is not rational it's called irrational
Proposition: The sum of two rational numbers is rational
Prof: Let r and s be two rational numbers so that
r = p1/q1 and s = p2/q2 for some integers p1, p2, q1, q2
r + s = p1/q1 + p2/q2 = (p1*q2)/(q2*q1) + (p2*q1)/(q1*q2) = (p1*q2 + p2*q1)/(q1*q2)
Both the top and bottom are integers and as q1 !=0 and q2 != 0 so that q1*q2 != 0 therefore r + s is rational
-----------------------------------------EXAMPLE--------------------------------------------------
Prop: for an integer n, n is even iff n^2
for all (n is even) <-> n^2 is even
so...
n is even -> n^2 is even     and          n^2 is even -> n is even
We have to do both

n is even -> n^2 is even
assume n is even, n = 2k for for some integer k
such that n^2 = (2k)^2 = 4k^2 = 2(2k^2) where 2k^2 = j so that 2(j) .. therefore n^2 is even if n is even

n^2 is even -> n is even
proof contrapositive
n is odd -> n^2 is odd and n is some integer
n = (2x + 1)
n^2 = (2x + 1)^2
n^2 = 4x^2 + 4x + 1 = 2(2x^2 + 2x) + 1 where an integer k = 2x^2 + 2x = 2k + 1 = n^2
therefore
by contraposition if n^2 is even then n is even

n is even -> n^2 is even
direct proof
n is even -> n^2 is even and n is some integer
n = 2x
n^2 = (2x)^2 = 4x^2 = 2(2x^2) let some integer k = 2x^2 such that n^2 = 2k
therefore
by direct proof is n is even then n^2 is even
-----------------------------------------------------------------------------------------------------------------------
The following are equivlent - if one is true all the others are true
i)
ii)
iii)
i -> iii  and i -> ii and iii -> i (and the rest ie. ii -> iii is via hyper syllogism)
it can get even simpler.. using hyper syllogism
________________________________________________________________________________________________________________________
Prove if x is irrational then 1/x is irrational
pf: Assume x is irrational assume for sake of contradiction that 1/x is rational
So 1/x = p/q for some integers p and q where q!= 0
Reciprocating both sides gives x/1 = q/p, so x = q/p
NOTE: if p = 0 then 1/x = 0/q = 0... but multiplying this by x would return 1 = 0*x = 0 so p != 0
so x is rational if x = q/p
CONTRADICTION -><- we assumed x is irrational therefore by contradiction if x is irrational then 1/x is irrational
_________________________________________________________________________________________________________________________
Proof by classes!!!
Prop: if m and n are integers and even then |m - n| is even
pf: assume m and n are even integers so m = 2k and n = 2l for some integers k and l
2k - 2l = 2(k-l)
you need 2 cases: if m-n >= 0 and if m-n < 0 because absolute value
case 1:
if m-n is >= 0 then |m-n| = 2(k-l) where some integer o = (k-l) so that |m-n| = 2o so that |m-n| is an even integer as k-l is an integer
case 2:
if m-n is < 0 then |m-n| = -2(k-l) = 2(-k + l) which is even as -k + l is an integer such that an integer o = -k + l |m - n| = 2o

in all cases |m-n| is even
--------------------------------------------------------------------------------------------------------------------------
Prop: for two integers m and n if one is even and the other is odd then m+n is odd
pf. without loss of generality, assume m is even and n is odd, so m = 2k and n = 2l + 1
notice that m+n = 2k + 2l + 1 where sume integer o = k + l such that m+n = 2(o) + 1
therefore m+n is odd when m is even and n is odd
_________________________________________________________________________________________________________________________________
END OF CHAPTER 1!!!!!!!!
Set Theory!!!!!
A Set is an unordered collection of objects
Ex.
A = {1,2,3} // Roster Method.. good for finite small sets but.. sucks ass for big / infinite ones

Let B be the set of all students // Verbally define the collection

C = {x | x is an odd integer} // Set builder notation ... | is "such that"
D = {x^2 | x is an integer}
E = {C,D} // You can have sets inside sets

Special Mathematical Sets:
Natural Numbers = {0,1,2,3,....INFINITY} = ℕ
Integers = {-INFINITY... -1, 0, 1 ... INFINITY} = ℤ
Positive Integers = {1,2,3,4...INFINITY} = ℤ+
Quotient = {p/q | p,qϵℤ, q!= 0 } = ℚ
 ℝ = Real Numbers  ->  ℝ+ = {xϵℝ | x > 0}
 Complex Numbers = basically a cent symbol
 ∅ = Empty set = {}

 Cardinality (Size) of a set
 If S is a finite set then |S| = n where n is the number of elements in S
 ex.
 E = {C,D} therefore the Cardinality is 2.. ez pz niga
 -------------------------------------------------------------------------------------------------------------------
 Subsets:
 Def: A Set of A is a subset of a set B such that A ⊆ B  iff every element of A is an element of B
 			∀x((XϵA) -> (xϵB))
			fun fact: ∀x((Xϵ∅) -> (xϵℝ))  is true because Xϵ∅ is always false
						which means an empty set is a subset of the reals
Example: Let S = {xϵℤ | x^2 <= 100}
					is S a subset of ℤ? - No! because of negatives S !⊆ ℤ+

__________________________________________________________________________________________________________________--
Power Sets: For all sets S, the power set P(x) is the set of all subsets of S
Ex: S={1,2}
P(S) = {∅,{1},{2},{1,2}}
Cardinality of a Power Set ...
	Note: if |S| = n (ie. is finite) then |P(S)| = 2^n
_________________________________________________________________________________________
We are still in the box.. Assignment #4 due thursday Feb8  and Quiz #2 Feb8 too
Cartisian Products: 2 sets
	Set A
	Set B
	A x B = {(a,b)|aϵA, bϵB}
	EX: R = {a,b}, S = {1,2,3}
	    R x S = {(a,1),(a,2),(a,3),(b,1),(b,2),(b,3)}
	    NOTE: (a,3) ϵ R x S  BUT (3,a) !ϵ R x S ... BUT (3,a) ϵ S x R

	A^2 = A x A  && A^n = A x A x A .... x A
	so.. from earlier.. R^2 = {(a,a),(a,b),(b,a),(b,b)}
Relations of sets and Quantifiers and Predicate logic:
	∀xϵℝ, x^2 >= 0  AND ∀xϵℤ, x^2 >= x
	They are used to specify the domain

	Definition: The Truthset of a predicate P on domain D is {xϵD | P(x)}
	Example: P(x) donates "3x >= x"
	         What is the truth set of P(x) over ℝ?
					 3x >= x ---> 2x >= 0 -----> x >= 0
					 A: [0, INFINITY) so ∀xϵℝ, 3x >= x is FALSE
					 	                so ∃xϵℝ, 3x >= x is TRUE
Operations on Sets:
	Union - A u B = {x | xϵA or xϵB}
					---------------------  u would be everything in box
					|      |     |      |
					|   A  | both|    B |
 					|______|_____|______|
	Intersection - A n B = {x | xϵA and xϵB}
					---------------------  n would be everything in BOTH box
					|      |     |      |
					|   A  | both|    B |
					|______|_____|______|
	Difference - A - B = {x | xϵA and x!ϵB}
					---------------------  - would be everything in A box
					|      |     |      |
					|   A  | both|    B |
					|______|_____|______|
	Complement à = U - A
						 NOTE: U is the universe.. IE .. everything inside AND outside of the box
					 ---------------------  Ã would be everything outside of A box
					 |      |     |      |
					 |   U  | A   |    U |
					 |______|_____|______|

		Example: A = {1,3,6} B = {1,2,4} U = All positive integers
						 A u B = {1,2,3,4,6}
						 A n B = {1}
						 A - B = {3,6}
						 Ã = {2,4,5,7,8,9.....}

Big Union
		n
		⋂ Ai = A1 n A2 n A3 ... An
	 i = 1

	  n
		⋃ Ai = A1 u A2 u A3 ... An
	 i = 1
	 Think of these as effectively Sigma or Pi Summation and Products

Example:
	5
	⋃{i} = {1} u {2} u {3} u {4} u {5} = {1,2,3,4,5}
 i = 1
	3
	⋂{i} = {1}n{2}n{3} = {EMPTY SET}
 i=1

  3
  ⋂[0,i] = {0,1}n{0,1,2}n{0,1,2,3} = {0,1}
 i=1

Proving Set Inclusion:
		(P ⊆ Q) ∀x[(xϵP) -> (xϵQ)] "P is a subset of Q.. if X is in P then X is in Q"
	Ex. If A⊆B then AuC ⊆ BuC
	Proof: Assume A⊆B . Let xϵAuC
	to show: xϵBuC --> xϵB or XϵC
	By definition of union, xϵA or xϵC
		Case1: xϵA
				A⊆B .. Therefore xϵB by definition of Subset
							 so if XϵB then it is in BuC  by definition of union
		Case2: xϵC
						Well if xϵC then xϵ(BuC) by definition of union
		So in either case AuC ⊆ BuC[]

	Prop: An(BnC) = (AnB)nC
	Pf: Let xϵAn(BnC)
	Show: xϵ(AnB)nC, xϵ(AnB) and xϵC
	By Intersection.. xϵA and xϵ(BnC) so xϵB and xϵC
	so..By intersection again.. xϵ(AnB) and we know xϵC.. therefore xϵ(AnB)nC
		Therefore: An(BnC) ⊆ (AnB)nC
	===================================================
	Pf: Let xϵ(AnB)nC
	Show: xϵAn(BnC), xϵ(BnC) and xϵA
	By intersection.. xϵAnB and xϵC so xϵA, xϵC and xϵB
	so.. By intersection again.. xϵ(BnC) and xϵA .. therefore xϵAn(BnC)
		Therefore: (AnB)nC ⊆ An(BnC)
	therefore because each are a subset of either
	An(BnC) = (AnB)nC[]

Example 2:
EmptySet -A = Empty Set
Pf. Assume for sake of contradiction EmptySet - A != EmptySet so that there exists an element xϵEmptySet-A
		So by Set difference x belongs to emptySet but not A..
		CONTRADICTION =><= . Something cannot belong to the emptySet
		therefore emptySet -A = emptySet

Functions:
	A Function from A to B is an assignment of exactly one element of B for each element of A
	f: A ----> B where A is the domain and B is the codomain..
		 The Set of images of all elements of A is called the range or image of f
EXAMPLE:
	g: ℝ->ℝ, Where g(x) = x^2 .. Domain: ℝ, codomain: ℝ, Range: [0,infinity)
	h: ℝ->ℝ, Where h(x) = 2x + 3 .. Domain: ℝ, codomain: ℝ, Range: ℝ

	If a function is...
		A->B it's called "INJECTIVE" or "One to One" iff for all a,b (f(a) = f(b)) -> (a = b) (same input = same output)
	If a function is...
		"Surjective" or "on to" for all elements of the codomain,  there exists an element on the domain
			Every element of the codomain is attained as the output of at least one input
	https://en.wikipedia.org/wiki/Bijection,_injection_and_surjection <--- Pictures of these are here

_________________________________________________________________________________________________________________________________________________________
Feb. 6th Class - Quiz next time up to 2.2 (Rules of inference to set theory)
								 HW is also due next time
HW review 2.2
9)
A U Ã = u
show: x belongs to u
Let x be an element of A u Ã
So by definition of Union.. x belongs to A or Ã
Case 1: X belongs to A
Then since A is a subset of U then x belongs to U!
Case 2: X belongs to Ã
Then since à is u - A, X belongs to U by definition of Set difference and Compliment

Let x be an element of u
show: x belongs to A U Ã or x belongs to A or Ã
Case 1: if x belongs to A
Then by union x belongs to A U Ã
Case 2: if x DOES NOT belong to A
Then by definition of compliment, x belongs to à therefore belongs to A U Ã

In either case x belongs to A U Ã  since subset in both directions is shown equality follows []
___________________________________________________________________________________________________________________________________________________________________
Back to Functions:
F: A -> B f is INJECTIVE
∀x∀y[(F(x) = F(y)) -> (x=y)]

F: A -> B f is Surjective
∀b belongs to B, ∃a That belongs to A , f(a) = b

Bijective iff f is both injective and surjective

H(x) = 2x + 3
Prop: H is injective
Prof. Let x,y be elements of all real numbers, Such that h(x) = h(y)
Show: x = y
2x + 3 = 2y + 3
-3         -3
2x = 2y
/2    /2
x = y
therefore H is injective

Prop: H is surjective
Prof. Let b be an element of the reals
Show: find an a such that H(a) = b
Such that a = (b - 3) / 2  which is a member of the reals
H(a) = 2a + 3 = 2((b-3)/2) + 3 = (b-3) + 3 = b

therefore h is bijective
---------------------------------------------------------------------------------------------------
Let f be an element of all positive integers such that Z+ -> Z+
f(n){	n/2 if n is even /// 3n + 1 if n is odd

Prop: f is surjective
Prof. Let b be an element of Z+
Set a = 2b
	Note: a still belongs to Z+ and is even by definition of even
f(a) = f(2b) = 2b/2 = b therefore f(a) = b []
___________________________________________________________________________________________________________________
Composition of Functions:
For f:A -> B and g:B -> C then the composition is A -> C ... gof(a) = g(f(a))
EX. h R -> R h(x) = 2x + 3
	  g R -> R g(x) = x^2

		goh(x) = (2x + 3)^2
		hog(x) = 2x^2 + 3

Images and Preimages:
f: A -> B .. S is a subset of A
						 T is a subset of B
f(S) = {b belongs to B | b = f(S) for some s that belongs to S}
     = {f(s) | s belongs to S}

f(T) = {a belongs to A | f(a) belongs to T}

Example:
g: R -> R
g(x^2)

g([0,2]) = [0,4]
g^-1([0,2]) = [(-sqrt(2), sqrt(2))]
g([-1,3]) = [0,9]

Prop: Let f: A->B
if u is a subset of v are both subsets of A then f(u) is a subset of f(v)
prof:
Let x be subset of f(u) so x =f(a)
for some a that exists in u
therefore a belongs to v
_________________________________________________________________________________________________________________________
Prop: Suppose F A -> B and f(u) belongs to V, then u belongs to f^-1(V)
let x be an arbitary element of u
show: x exists of f^-1(V) therefore f(x) belongs to V
f(x) belongs to f(u) by defintion of images
therefore a F(u) belongs to v so by subset f(x)) belongs to u
therefore x belongs to f^-1(V) so u is a subset of f^-1(V)[]
_______________________________________________________________________________________________________________________________________________
Sequences an ORDERED list of numbers
a1, a2, a3, .. an
an Infinite sequence can be viewed as a function from Z+ to S
an = n^2 = {an}n=0 -> infinity = 0,1,4,9,16.....
bn = 1+n = {bn}n=1 -> infinity = 2,3,4,5,6,7......

Ex. Let a0 = 1 and an = n*an-1 for n>=1
a1 = 1
a2 = 2
a3 = 6
a4 = 24
.... (basically n!)

ex2. Let f0=1 and f1=1 and fn = fn-1 + fn-2
f2 = 2
f3 = 3
f4 = 5
f5 = 8
f6 = 13
f7 = 21
f8 = 34
... Fibonacci numbers
___________________________________________________________________________________________________________________________________________________
Cardinality:
	Cardinality means SIZE!
	Q: What is the size of the following sets
			Z+ = infinite, Z = infinite, R = infinite, [0.1) = infinite....
			THEY'RE ALL INFINITE BUT THEY HAVE DIFFERENT SIZES
	Sets A and B have the same cardinality if and only if there is a bijection from A to B
	|A|=|B|
	A = {a,b,c}
	B = {1,2,3}
	f: A -> B
	f(a) = 1
	f(b) = 2
	f(c) = 3
	BIJECTIVE, each output has exactly 1 input
	If there is an injection from A->B - |A| <= |B|
	if there is a surjection from A->B - |A| >= |B|

	Example... Let C = {n exist on Z | n>=5}
						 Prop: |N| = |C| // you have to show there is a bijection
						 Pf: Define f: N -> C such that f(n) = n+5
						 Well defined: Assume n exists on N so n exists on Z and and n>=0
						 Notice, f(n) = n+5 is an integer and n+5 >= 0+5
						 so that f(n) exists on C
						 Injective: So let x,y exits on N such that f(x) = f(y) so x+5 = y + 5 ---> x = y therefore injective
						 Surjective: let b exist on C let a = b - 5 note that b exists on C so b exits on Z and b >=5 so b-5 >= 5-5 = 0
						 						  so that f(a) = a + 5 = (b - 5) + 5 = b  so f is surjective
						 Therefore f  bijective therefore |N| = |C|

	Definition: COUNTABLE: A is countable iff it is finite or |A| is the same as |Z+|
	_________________________________________________________________________________________________________-
	Let E = {Positive Odd numbers}
	is E countable? .. yes.. 1,3,5,7 .. how do i show E and Z
	F: Z+ -> E
	f(k) = 2k - 1... then prove it

	is Z countable? .. yes - f(k) = {k is even - -k/2, k is odd (k-1)/2}

	is Q countable? Yes!

	Prop: [0,1) is not countable
	Proof: Assume for sake of contradiction [0,1) is countable so there is a squence such that [0,1) = union from 1 - infinity ({rn})
	_____________________________________________________________________________________________________________________________________
	2.3 5a - Domain and range
	a) the function that assigns to each bit string the number of 1s in the string - the number of zeros in the string
		  Domain - set of all bit strings  ---> range - Z

  b) The function that assigns to each bit string twice the number of zerosin the string
			domain - set of all bit strings ---> range - {n exists on Z | n is even and n >= 0}
	___________________________________________________________________________________________________________________