Chapter 00	Chapter 06
Chapter 01 Part 1	Chapter 07
Chapter 01 Part 2	Chapter 08
Chapter 01 Part 3	Chapter 09
Chapter 02	Chapter 10
Chapter 03	Chapter 11
Chapter 04	Chapter 12
Chapter 05	Chapter 13

Sources

Past Exams

Spring 2002 - Exam 1

Spring 2002 - Exam 2

Spring 2011 - Exam 1 (Exam, Solution)

Spring 2011 - Exam 2 (Part I, Part II, Solution)

Spring 2011 - Final (Exam, Solution)

Spring 2015 - Exam 2

Spring 2016 - Exam 2

Math 521

Notes on Math 521: Analysis I @ University of Wisconsin-Madison Your comments and criticism are greatly welcomed.

Course Website

Homepage

Syllabus

Textbook

Rudin, W. Principles of Mathematical Analysis. Third Edition

Lecture Notes

Download PDF

Week 1
1/24	Number Systems, Irrationality of √2
1/26	Sets, Gaps in Q, Field
Week 2
1/29	Field, Order, Upper Bound and Lower Bound
1/31	Infimum and Supremum, Ordered Field
2/2	Ordered Field, Archimedean Property, Density of Q in R
Week 3
2/5	n-th Root of Real Number, Complex Numbers
2/7	Complex Numbers, Euclidean Spaces
2/9	Quiz
Week 4
2/12	Schwarz Inequality, Function, Cardinality
2/14	Finite and Infinite, Sequence
2/16	Set Operations, Countable and Uncountable
Week 5
2/19	Metric Space, Interval, Cell, Ball, Convex
2/21	Definitions in Metric Space
2/23	Neighborhood, Open and Closed, De Morgan's Law
Week 6
2/26	Open and Closed, Closure
2/28	Convergence and Divergence, Range, Bounded
3/2	Important Properties of Convergent Sequences
Week 7
3/5	Algebraic Limit Theorem
3/7	Convergence of Sequences in R^n, Compact Set
3/9	Exam 1
Week 8
3/12	Compact Subset, Cantor's Intersection Theorem
3/14	Nested Intervals Theorem, Compactness of k-cell
3/16	Heine-Borel, Weierstrass, Subsequence
Week 9
3/19	Cauchy Sequence, Diameter
3/21	Cauchy Sequence, Complete Metric Space, Monotonic
3/23	Upper and Lower Limits
Week 10
4/2	Some Special Sequences
4/4	Series, Cauchy Criterion for Series, Comparison Test
4/6	Convergence Tests for Series
Week 11
4/9	Power Series, Absolute Convergence, Rearrangement
4/11	Rearrangement, Limit of Functions
4/13	Exam 2
Week 12
4/16	Continuous Function and Open Set
4/18	Continuity and Compactness, Extreme Value Theorem
4/20	Uniform Continuity and Compactness
Week 13
4/23	Connected Set, Intermediate Value Theorem
4/25	Derivative, Chain Rule, Local Extrema
4/27	Mean Value Theorem, Monotonicity, Taylor's Theorem
Week 14
4/30	Riemann-Stieltjes Integral, Refinement
5/2	Fundamental Theorem of Calculus
5/4	Sequence of Functions, Uniform Convergence

Math 541

Notes on Math 541: Modern Algebra @ University of Wisconsin-Madison Your comments and criticism are greatly welcomed.

Course Website

Homepage

Syllabus

Textbook

Abstract Algebra, by Dummit and Foote, Third Edition, 2004

Lecture Notes

Download PDF

Week 1
1/24	Divides, Equivalence Relations
1/26	Well-ordering of Z
Week 2
1/29	Division Algorithm, gcd
1/31	Euclidean Algorithm
2/2	Equivalence Class, Z/nZ, Group
Week 3
2/5	Group, Well-definedness, Z/nZ
2/7	(Z/nZ)*, Properties of Group
2/9	Order, Symmetric Group
Week 4
2/12	Symmetric Group, Cycle
2/14	Homomorphism, Isomorphism
2/16	Order, Homomorphism, Subgroup
Week 5
2/19	Dihedral Groups, Subgroup
2/21	Cyclic Group, lcm, Order of g^a
2/23	Cyclic Subgroup, Generating Set of a Group
Week 6
2/26	Finitely Generated Group
2/28	Coset, Normal Subgroup
3/2	Exam 1
Week 7
3/5	Quotient Group, Index, Lagrange's Theorem
3/7	Corollaries of Lagrange's Theorem
3/9	The First & Second Isomorphism Theorems
Week 8
3/12	The Third Isomorphism Theorem
3/14	Transposition, Sign of Permutation
3/16	Homework 6, The Correspondence Theorem
Week 9
3/19	Sign of Permutation, Alternating Group
3/21	Subgroups of A_4, Group Action, Orbit, Stabilizer
3/23	Orbit, Stabilizer, Cayley's Theorem
Week 10
4/2	Conjugacy Class, The Class Equation
4/4	Cauchy's Theorem, Recognizing Direct Products
4/6	Homework 8, Properties of Finite Abelian Group
Week 11
4/9	Fundamental Theorem of Finite Abelian Groups
4/11	Definition of Ring
4/13	Exam 2
Week 12
4/16	Properties of Ring, Zero-Divisor, Unit
4/18	Field, Product Ring, Integral Domain
4/20	Product Ring, Finite Domain and Field, Subring
Week 13
4/23	Polynomial Ring, Ideal, Principal Ideal
4/25	Examples of Ideals, Quotient Ring
4/27	Isomorphism Theorems for Rings
Week 14
4/30	Generating Ideal, Maximal Ideal, Prime Ideal
5/2	Prime Ideal, Euclidean Domain
5/4	Review, Galois Theory

1.3 Propositional Equivalences

Tautologies, Contradictions, and Contingencies • Tautology ○ A tautology is a proposition which is always true. ○ Example: p∨¬p • Contradiction ○ A contradiction is a proposition which is always false. ○ Example: p∧¬p • Contingency ○ A contingency is a proposition which is neither a tautology nor a contradiction ○ Example: p Logically Equivalent • Two compound propositions p and q are logically equivalent if p↔q is a tautology. • We write this as p⇔q or as p≡q where p and q are compound propositions. • Two compound propositions p and q are equivalent if and only if the columns in a truth table giving their truth values agree. • Example p q ¬p ¬p∨q p→q T T F T T T F F F F F T T T T F F T T T De Morgan’s Laws • ¬(p∧q)≡¬p∨¬q • ¬(p∨q)≡¬p∧¬q • Truth Table p q ¬p ¬q p∨q ¬(p∨q) ¬p∧¬q T T F F T F F T F F T T F F F T T F T F F F F T T F T T Key Logical Equivalences • Identity Laws ○ p∧T≡p ○ p∨F≡p • Domination Laws ○ p∨T≡T ○ p∧F≡F • Idempotent Laws ○ p∨p≡p ○ p∧p≡p • Double Negation Law ○ ¬(¬p)≡p • Negation Laws ○ p∨¬p≡T ○ p∧¬p≡F • Commutative Laws ○ p∧q≡q∧p ○ p∨q=q∨p • Associative Laws ○ (p∨q)∨r=p∨(q∨r) ○ (p∧q)∧r=p∧(q∧r) • Distributive Laws ○ p∨(q∧r)≡(p∨q)∧(p∨r) ○ p∧(q∨r)≡(p∧q)∨(p∧r) • Absorption Laws ○ p∨(p∧q)≡p ○ p∧(p∨q)≡p • Logical Equivalences Involving Conditional Statements ○ p→q≡¬p∨q ○ p→q≡¬q→¬p ○ p∨q≡¬p→q ○ p∧q≡¬(p→¬q) ○ ¬(p→q)≡p∧¬q ○ (p→q)∧(p→r)≡p→(q∧r) ○ (p→r)∧(q→r)≡(p∨q)→r ○ (p→q)∨(p→r)≡p→(q∨r) ○ (p→r)∨(q→r)≡(p∧q)→r • Logical Equivalences Involving Biconditional Statements ○ p⟷q≡(p→q)∧(q→p) ○ p⟷q≡¬p⟷¬q ○ p⟷q≡(p∧q)∨(¬p∧¬q) ○ ¬(p⟷q)≡p⟷¬q Constructing New Logical Equivalences • We can show that two expressions are logically equivalent by developing a series of logically equivalent statements. • To prove that A≡B we produce a series of equivalences beginning with A and ending with B. ○ A≡A_1≡A_2≡…≡A_n≡B • Keep in mind that whenever a proposition (represented by a propositional variable) occurs in the equivalences listed earlier, it may be replaced by an arbitrarily complex compound proposition. Propositional Satisfiability • A compound proposition is satisfiable if there is an assignment of truth values to its variables that make it true. • When no such assignments exist, the compound proposition is unsatisfiable. • A compound proposition is unsatisfiable if and only if its negation is a tautology. Questions on Propositional Satisfiability • (p∨¬q)∧(q∨¬r)∧(r∨¬p) ○ p∨¬q=T⇒set p=T ○ q∨¬r=T⇒set q=T ○ r∨¬p=T⇒set r=T ○ One solution: p=q=r=T • (p∨¬q)∧(q∨¬r)∧(r∨¬p)∧(p∨q∨r)∧(¬p∨¬q∨¬r) ○ Not satisfiable. ○ Check each possible assignment of truth values to the propositional variables and none will make the proposition true. Notation • ⋁24_(j=1)^n▒p_j ≡p_1∨p_2∨…∨p_n • ⋀24_(j=1)^n▒p_j ≡p_1∧p_2∧…∧p_n Sudoku • A Sudoku puzzle is represented by a 9×9 grid made up of nine 3×3 subgrids, known as blocks. • Some of the 81 cells of the puzzle are assigned one of the numbers 1,2, …, 9. • The puzzle is solved by assigning numbers to each blank cell so that every row, column and block contains each of the nine possible numbers. • Example • Encoding as a Satisfiability Problem ○ Let p(i,j,n) denote the proposition that is true when the number n is in the cell in the ith row and the jth column. ○ There are 9×9×9 = 729 such propositions. ○ In the sample puzzle p(5,1,6) is true, but p(5,j,6) is false for j = 2,3,…, 9 ○ For each cell with a given value, assert p(i,j,n), when the cell in row i and column j has the given value. ○ Assert that every row contains every number. § ⋀24_(i=1)^9▒⋀24_(n=1)^9▒⋁24_(j=1)^9▒p(i,j,n) ○ Assert that every column contains every number. § ⋀24_(j=1)^9▒⋀24_(n=1)^9▒⋁24_(i=1)^9▒p(i,j,n) ○ Assert that each of the 3×3 blocks contain every number. § ⋀24_(r=0)^2▒⋀24_(s=0)^2▒⋀24_(n=1)^9▒⋀24_(i=1)^3▒⋁24_(j=1)^3▒p(3r+i,3s+j,n) ○ Assert that no cell contains more than one number. Take the conjunction over all values of n, n’, i, and j, where each variable ranges from 1 to 9 and n≠n′ of § p(i,j,n)→¬p(i,j,n′) • Solving Satisfiability Problems ○ To solve a Sudoku puzzle, we need to find an assignment of truth values to the 729 variables of the form p(i,j,n) that makes the conjunction of the assertions true. ○ Those variables that are assigned to yield a solution to the puzzle. ○ A truth table can always be used to determine the satisfiability of a compound proposition. ○ But this is too complex even for modern computers for large problems. ○ There has been much work on developing efficient methods for solving satisfiability problems as many practical problems can be translated into satisfiability problems.

1.2 Applications of Propositional Logic

Translating English Sentences • Steps to convert an English sentence to a statement in propositional logic ○ Identify atomic propositions and represent using propositional variables. ○ Determine appropriate logical connectives • Example: “If I go to Harry’s or to the country, I will not go shopping.” ○ p: "I go to Harry’s." ○ q: "I go to the country." ○ r: "I will go shopping." ○ p∨q→¬r • Example: “You can get an extra piece of pie if you have completed your homework or if you are extremely hungry” ○ p: You have completed your homework ○ q: You are extremely hungry ○ r: You can get an extra piece of pie ○ p∨q→r System Specifications • System and Software engineers take requirements in English and express them in a precise specification language based on logic. • Example: “The automated reply cannot be sent when the file system is full” ○ p: “The automated reply can be sent” ○ q: “The file system is full.” ○ q→¬ p Logic Puzzles • An island has two kinds of inhabitants, knights, who always tell the truth, and knaves, who always lie. • You go to the island and meet A and B. ○ A says “B is a knight.” ○ B says “The two of us are of opposite types.” • What are the types of A and B? ○ Let p and q be the statements that A is a knight and B is a knight, respectively. ○ So, then Øp represents the proposition that A is a knave and Øq that B is a knave. ○ If A is a knight, then p is true. Since knights tell the truth, q must also be true. Then (p ∧Øq)∨(Øp∧q) would have to be true, but it is not. So, A is not a knight and therefore Øp must be true. ○ If A is a knave, then B must not be a knight since knaves always lie. So, then both Øp and Øq hold since both are knaves. Logic Circuits • Electronic circuits; each input/output signal can be viewed as a 0 or 1. ○ 0 represents False ○ 1 represents True • Complicated circuits are constructed from three basic circuits called gates. ○ The inverter (NOT gate) takes an input bit and produces the negation of that bit. ○ The OR gate takes two input bits and produces the value equivalent to the disjunction of the two bits. ○ The AND gate takes two input bits and produces the value equivalent to the conjunction of the two bits. • More complicated digital circuits can be constructed by combining these basic circuits to produce the desired output given the input signals by building a circuit for each piece of the output expression and then combining them.

Shawn Zhong

Shawn Zhong

Math 240

Course Website

Textbook

Lecture Notes

Lecture Slides

Past Exams

Math 521

Course Website

Textbook

Lecture Notes

Math 541

Course Website

Textbook

Lecture Notes

1.3 Propositional Equivalences

1.2 Applications of Propositional Logic

Search

WeChat Account