This page gives information about the material covered each day in CSCE 235, as well as assigned reading.
Handed out the course policy sheet (PDF, TeX). Discussed section 1.1 through converses and contrapositives of implications. Assigned reading for the next class is sections 1.1 and 1.2.
Handed out the tentative course schedule (PDF, TeX). Discussed section 1.1 through the precedence of logical operators. Important points covered in section 1.1 so far include the following.
We also took the prerequisite test (PDF, TeX), which will be counted as a quiz. Solutions for the pretest are available (PDF, TeX). Grades for the pretest have been posted on Blackboard.
The first homework assignment will be handed out on Wednesday, January 17.
Returned the prerequisite tests; the solutions are available online (PDF, TeX). Handed out the first homework assignment (PDF, TeX) and a sheet listing some useful logical equivalences and implications (PDF). This homework assignment is due next Wednesday, January 24.
We discussed a few things to watch out for when translating English sentences into logical propositions, and talked some about bit operations; this concludes Section 1.1. Talked about Section 1.2: tautologies, contradictions, and contingencies; logical equivalence; and De Morgan's laws.
We also went through a direct formal proof, giving explanations for each step, like the eighth problem of the homework. This style of proof isn't discussed in the textbook, so be sure to ask me if you have questions about it. We'll go through a proof by contradiction in much the same way on Friday, and then talk about Section 1.3.
Went through a proof by contradiction, giving explanations for each step. Started Section 1.3; in particular, we talked about predicates and propositional functions, introduced the universal and existential quantifiers, discussed domains of discourse, and examined what is sufficient to prove a universal quantification false (a single counterexample is all that is needed) and what is sufficient to prove an existential quantification true (only a single example).
Read Section 1.3 if you haven't already.
I have exchanged my Tuesday and Thursday office hours, so that my office hours are now 1:30 to 3:00 on Tuesdays and 2:30 to 4:30 on Thursdays. Of course, you can always contact me to set up an appointment to meet at another time.
Finished Section 1.3, started Section 1.4. In detail, we talked about Table 1 on page 34 of the textbook, commented on vacuous truth (if the domain of discourse is empty, then a statement of the form ∀x P(x) is true no matter what P(x) is), mentioned the uniqueness quantifier (∃!), discussed a shorthand notation for restricting the domain, talked about what logical equivalence means for quantified statements, looked at De Morgan's laws for negating quantified expressions, translated a couple English sentences into logical expressions, and introduced the idea of nested quantifiers.
Don't forget that the first homework is due on Wednesday. Read Section 1.4 if you haven't already.
Finished Section 1.4. We discussed how the order of quantifiers is important, we translated between English sentences and logical statements, and we looked at a method for negating statements involving nested quantifiers.
Handed out the second homework assignment (PDF, TeX). This assignment is due on Monday, February 5.
Talked about Section 1.5. We discussed the definitions of words such as proof, argument, and valid. Remember that the validity of an argument is entirely independent of the truth values of its premises and its conclusion. We examined several argument forms; see Table 1 on page 66 of the textbook for a list of eight argument forms, and see how they mirror the logical equivalences on the handout from class (PDF). We briefly looked at some logical fallacies and rules of inference for quantified statements.
On Monday we will begin Section 1.6, "Introduction to Proofs". Read through the end of Section 1.6 if you have not done so already.
Discussed Section 1.6. Defined terms such as theorem, proposition, proof, premises, conclusion, lemma, corollary, and conjecture. Described direct proofs and proofs by contraposition, and gave some examples of each. Mentioned vacuous and trivial proofs.
Began by talking about proofs by contradiction. Gave two famous examples of proofs by contradiction, which show that √2 is irrational and that there are infinitely many prime numbers. Talked briefly about how to prove bijections of the form p ↔ q (one method is to split the proof into two parts, one of which proves p → q and the other of which proves q → p). Described how many statements can be disproved by finding a single counterexample.
Started Section 1.7, "Proof Methods and Strategy". The first part of this section talks about exhaustive proofs and proofs by cases; we covered a couple examples like this. We then spent a little time talking about the concept of making assumptions without loss of generality.
Continued Section 1.7 with some examples of existence proofs to prove statements of the form ∃x P(x), including both constructive existence proofs, which explicitly give some example of an element x for which P(x) is true, and nonconstructive existence proofs, which prove that such an element must exist but do not actually give an example of one. Briefly discussed the idea behind uniqueness proofs. Discussed some proof strategies, including forward and backward reasoning, adapting existing proofs, and looking for counterexamples.
The first quiz was handed out (PDF, TeX); solutions are available (PDF, TeX). The due date for the first homework assignment has been postponed to Wednesday, February 7.
Handed back the quiz from Friday and the first homework assignment.
Discussed Section 2.1 about sets. Defined many terms, including set, element, the concept of equality of two sets, subset, proper subset, cardinality, finite set, infinite set, and power set. Went over some common notation used for sets; the symbols N, Z, Q, R, and C; and the related symbols Z+, Q+, and R+. Introduced the empty set, and emphasized that the empty set, written ∅, is not the same as the set containing the empty set, written {∅}. Stated the fact that for every set S, we have both ∅ ⊆ S and S ⊆ S. Gave an important method for proving that A = B: First prove that A ⊆ B, and then prove that B ⊆ A.
Talked a little about power sets. If a set S has cardinality n, then the power set of S has cardinality 2n. Concluded by examining how to represent subsets with bit strings.
Introduced Cartesian products and ordered n-tuples. Mentioned the use of set notation with quantifiers and the idea of a truth set of a predicate. This concludes Section 2.1.
In Section 2.2, "Set Operations", we defined the union, the intersection, and the difference of two sets, and defined what it means for two sets to be disjoint. We also defined the complement of a set. The set identities from Table 1 on page 124 of the textbook will be important; read these and convince yourself that they are true. Finally, we generalized the concepts of union and intersection to apply to more than two sets.
We began talking about relations, beginning with Section 8.1. A relation from A to B is simply a subset of A × B. We looked at a couple examples of relations. We will start from here on Friday; the goal is to finish discussing Sections 8.1 and 8.5 by the end of class on Friday.
The first exam is scheduled for Friday, February 16. It will cover all we have talked about up through Section 8.5.
Homework 3 is available online (PDF, TeX). It is officially due on Monday, February 12. If you turn it in by Monday, I will try my best to get it back to you by Wednesday so that you can use it to study for the exam. If you aren't able to get it in on Monday, you can turn it in to me on Tuesday or at the beginning of class on Wednesday. The absolute latest you can turn in Homework 3 will be 12:30 p.m. on Wednesday, February 14.
Discussed notation used for relations, the idea of relations on a set, and two ways to visualize a relation graphically. Defined the terms reflexive, symmetric, and transitive, which describe properties a relation on a set may have; also defined equivalence relation, which is a relation that is reflexive, symmetric, and transitive. Gave several examples of equivalence relations. Described equivalence classes and partitions of sets, and mentioned how equivalence classes and partitions are essentially different ways to think about the same thing.
Proved the following theorem, found on page 560 of the textbook.
Let R be an equivalence relation on a set A. The following statements for elements a and b of A are equivalent.
- a R b (that is, a ∼ b);
- [a] = [b]; and
- [a] ∩ [b] ≠ ∅.
As a corollary, we saw that the equivalence classes of a relation on a set form a partition of the set.
Handed out my answers to the three homework assignments that have been given so far. These are available online.
Began talking about Section 2.3, which discusses functions. We defined the terms function, domain, codomain, image, preimage, range, onto (surjective), one-to-one (injective), and bijection (one-to-one correspondence). Looked at some examples of functions, and examined their properties.
I also answered a few questions about the exam. Remember, the exam will be given during the normal class time on Friday, February 16.
Exam 1.
Introduced inverse functions (denoted f−1) and compositions of functions, and gave some examples. Also described three important functions: the floor function, denoted ⌊x⌋; the ceiling function, denoted ⌈x⌉; and the factorial function, denoted x!.
Began to discuss the idea of mathematical induction (Section 4.1), illustrating the idea with the concept of an infinite ladder.
Handed out the fourth homework assignment (PDF, TeX) and the first programming assignment (PDF, TeX). The homework assignment is due on Friday, March 2, and the programming assignment is due on Monday, March 5.
Discussed mathematical induction in more detail, and went through an inductive proof of the formula 1 + 2 + 3 + … + n = n(n + 1)/2.
No class today; instead the College of Arts and Sciences conducted a focus group for the computer science majors enrolled in the course.
Covered the idea of strong induction (Section 4.2), and used it to prove that every integer greater than 1 is a possible score in football. We also proved, using strong induction, that every integer greater than 1 can be written as the product of primes.
Talked about recursion and recursive definitions (Section 4.3), with an example of a recursively defined sequence and a recursive definition of the factorial function.