CS313K Logic, Sets, and Functions
- Catalog Description: Propositional and predicate logic; proof techniques,
including induction, sets, relations, and functions.
- Unique Id: 54095 – 54120
- Lecture Meets: TT 3:30 – 5:00, WEL 2.246
- Section Meetings:
|54095||Friday 9:00 – 10:00a||WRW 113||Vinod Venkataraman|
|54100||Friday 10:00 – 11:00a||JES A218A||Vinod Venkataraman|
|54105||Friday 10:00 – 11:00a||SZB 416||Xu Wang|
|54110||Friday 12:00 – 1:00p||RLM 5.122||Behnam Robatmili|
|54115||Friday 1:00 – 2:00p||CBA 4.344||Behnam Robatmili|
|54120||Friday 1:00 – 2:00p||JES A209A||Xu Wang|
- Supplemental Material Used in Lectures: Most of these ``lectures''
just contain the day's announcements. I do not post the Quiz Questions.
- Instructor: J Strother Moore
- Office: TAY 4.140A
- Email: < moore at cs dot utexas dot edu >
- Office Hours: Wednesday 2 pm – 3 pm, Thursday 2 pm – 3 pm, or by appointment
- TAs and Their Office Hours: To Be Determined
- Behnam Robatmili < beroy at cs dot utexas dot edu >
- Mon 1:30 – 3:30 pm, ENS 31NQ Desk 1
- Thu 9:00 – 10:00 am, ENS 31NQ Desk 1
- Vinod Venkataraman < vinodv at cs dot utexas dot edu >
- Mon 12:00 – 1:00 pm, ENS 31NQ Desk 6
- Wed 4:30 – 6:30 pm, ENS 31NQ Desk 6
- Xu Wang < wangxu at cs dot utexas dot edu >
- Mon 10:00 – 12:00 noon, ENS 31NQ Desk 3
- Thu 10:00 – 11:00 am, ENS 31NQ Desk 3
- Tutors: For best results, contact tutors in advance to insure that they will
be available. To Be Determined
- Young-suk Lee < youngsuklee at mail dot utexas dot edu >
Office: CS Micro Lab in ENS
- Wed 3:00 – 5:00 pm
- Thu 1:30 – 3:30 pm
- Google Group Discussion Forum: There is an optional
Discussion Forum you can join to
discuss the course with TAs and other students. Here is an
Introduction to Google Discussion Groups.
- Important Class Dates:
- Midterm 1: Thursday, Feb 11, 3:30 – 5:00 pm, Room: WEL 1.308 (not our usual room!)
- Midterm 2: Thursday, Apr 1, 3:30 – 5:00 pm, Room: WEL 2.224 (not our usual room!)
- Final Exam: Tuesday, May 18, 9:00 – 12:00 noon, Room: WEL 2.224
This course is designed to teach you to use the predominant mathematical
notations and systems in computer science, how to formalize ideas
mathematically, and how to prove that those formal concepts have certain
properties. This is a required course for CS majors. To find out why,
click here. For some advice on how to succeed in this
course, click here.
The second lecture will start with a quiz, so you must
accomplish all three of the following tasks before class on Thursday, Jan 21!
Do not procrastinate.
- Purchase CS313K
Notes — Spring, 2010, by J
Strother Moore, $12.94 at the UT Copy Center (see below). I strongly recommend you
buy a hardcopy to bring to class and mark-up, even though the link above will
give you a searchable pdf copy for free.
UT Copy Center
Welch Hall, WEL 2.228 (across the hall from the lecture room)
Hours: 7:30 am – 4:30 pm
Note: Mistakes in the notes will be corrected in class. You will be expected to be
there to hear the corrections and mark your books accordingly.
- Purchase an iClicker (a remote control device) from the Co-op bookstore, about $36
Beware: There may be several incompatible brands of
remote control devices on sale. Be sure you get the “iClicker” brand.
To find out more about iClickers, see the company's
The Co-op will buy back the iClicker for about half the current price. I recommend that you
put a piece of transparent tape across the serial number on the back of your iClicker to prevent it
from being rubbed off with use. That serial number is important when you register the
iClicker (see the next step) and you want it intact when/if you re-sell the iClicker.
- Register your iClicker (even if you think you already have!)
If you already have a iClicker and registered it to your EID in the past, you should be aware that
iClicker registrations do expire (each July, I believe). It doesn't hurt to re-register each term.
If you cannot read the serial number on your iClicker, see me.
- your first name
- your last name
- your UT EID (which they call your “student ID”)
- your clicker's ID (the serial number under the bar code on the back of the device)
Bring your notes, iClicker, some scratch paper, and a pen or pencil to every lecture.
Errata for the Notes
On page 5, the claim that
(f (g x y)) is ill-formed because it
contains an ``ill-formed interior term'' is wrong! It's not ill-formed at all.
(f (g x)) would be an example of the kind of ill-formed term
On page 22, Question 34 should ask ``what is the value of
x is a natural number?'' As phrased, the question is ill-formed
fn-q34 has arity 1 but the question talks about
(fn-q34 x y).
The notes list a number of homework problems due on Mar 16. That's during
Spring Break. Those homework problems are due Mar 23 instead.
See the (corrected) due dates in the Homework section below.
This is college. You must read ahead to know what is going on in the
lectures. The reading schedule is implicit in the notes. Each section is
marked with the date of the lecture at which that section will be discussed.
Every lecture — including the second — will start with an
iClicker quiz over the assigned reading and you will be graded on the
quizzes. I cannot stress enough the importance of your taking
responsibility for the reading.
We're going to cover roughly 240 pages of the notes. The course marches on
relentlessly, every lecture covering new material. Keep up!
I will not remind you of the reading from week to week. That is your responsibility! It will
sometimes take a day or two or read the material, so I recommend that after every class you
look ahead to see what the next reading assignment is and plan your time accordingly before
the next class. Do not wait until an hour before class! That won't be enough time.
I may have to change pace of the reading assignments. Changes will be announced in
class. Pay attention.
When you read the material, work some of the problems. Program up small
examples to test your understanding. Do not study passively! Just reading
— without thinking through the consequences of what you're reading
— is usually a waste of time.
The quizzes will often refer to the notes and I'll expect you to answer my
questions with your clickers. You will be graded on the answers. So
be sure you
- read the assigned material before class,
- bring your notes,
- bring your clickers, and
- bring paper and something to write with so you can work out
Last year (Spring, 2009) I had a rule that if more than half the students answered a quiz
question incorrectly, I did not count the question. I've decided that is a bad rule that
punishes the best students. This year (Spring, 2010), every question I ask will count.
Attendance is taken in every lecture via the iClicker quiz. It will be
necessary to attend class and take the quizzes to make a good grade.
Show up! And bring your clicker!
Please sit in the front.
There will be weekly homeworks.
Homework is always due on the Tuesday before class. All homework solutions
must be typed in plain ASCII and submitted via
facility. (Be sure to turn your homework into your CS313K folder and not some
other class! No credit will be given for homework turned in to another class!)
Your solution to the first homework should be
hw1.txt, the second
hw2.txt, etc. The text
file should start with your name, EID, and a title (e.g. “CS313K Spring 10
The official list of homework problems and due dates is given below. Remember: well formatted plain ASCII, via
turnin, before 3:30 pm,
on the Tuesdays listed below.
|1||Jan 26||14, 23, 24, 25, 29, 33|
|2||Feb 2||49, 50, 55, 57, 60, 65|
|3||Feb 9||89, 92, 93, 109, 112, 114, 115|
|4||Feb 23||125, 130, 131, 132, 133|
|5||Mar 2||135, 137, 146, 148, 151, 160, 164|
|6||Mar 9||167, 168, 169, 170, 174, 181|
|7||Mar 23||194, 199, 215, 216, 219|
|8||Mar 30||225, 226, 230, 235, 237|
|9||Apr 13||266, 268, 269, 270, 274, 281, 282, 283|
|10||Apr 20||289, 292, 293, 296, 314, 316|
|11||Apr 27||318, 320, 321, 322, 323, 324, 331, 337, 338, 355, 366, 372|
|12||May 4||379, 388, 393, 395, 403|
I reserve the right to change the homework assignments in response to the pace of the
lectures. Changes will be announced in class and the list above will be modified.
Check this list weekly if you want to be sure you're doing the right problems!
For your convenience, the printed copy of the textbook has the assigned homework problems
marked with stars
(★★★) along with the due date. Of course, if I change the assignments, the
starred problems in the book will no longer be current. I recommend that you mark your books
when I make announcements in class -- and check the list above weekly.
Some symbols we use in class and in the notes are not ASCII, e.g.,
∧, ∨, ¬, →, ↔, ∀, ∃, ∈, ⊆, ∩, ∪.
There is a table of ASCII substitutes in Appendix D of the notes. For example, you're
told there to type “
p --> q” for “p→q”, and
(all v p)” for “(∀ v : p)”.
Warning: You will get a 0 for any answer that violates the following rules.
Every “formula” must be syntactically well-formed. Nothing should extend beyond the
80th column -- lines should not be truncated or wrap around when viewed in a window 80 characters
wide. Finally, if the grader feels that insufficient effort has been made to display a formula
sensibly, he or she is free to assign a 0 for that answer even if it is correct! The book
discusses this at length in “Syntax” section of Chapter 4.
You may work on your homework in groups, but each person must prepare and
turn in his or her own write-up. Working in groups is an excellent way to
learn new material, but writing it down yourself is an great way to make sure
you understand it. Don't think that you understand because someone in
your group understands! And remember, you will work alone during the exams
and the only way to do well in the class is to master the material.
It is considered cheating to turn in somebody else's homework as your own. In
the CS department, cheating and facilitating cheating by others results in a
course grade of F.
Just to be clear:
- You can work together in groups or teams on homework.
- One person might take the lead and write out a proof, debugged by all the participants.
- You might take notes on how the team solved each problem.
- But then sit down by yourself and type your own homework solutions.
- If you realize you don't
understand a step in your notes, feel free to ask somebody.
- But what you must not do is copy somebody else's homework file or turn in somebody
else's work as your own.
You will be expected to define and run programs in the ACL2 programming language. ACL2 is probably
unfamiliar to you, but it is simple to learn.
The first homework assignment contains
explicit instructions to get you
started with the ACL2 system. It introduces an Eclipse interface to ACL2,
called ACL2s, written and maintained
by Peter Dillinger,
Pete Manolios and Harsh
Chamarthi, of Northeastern University, Boston. ACL2s is available on all the
CS department's public machines. You may wish
to install it on your own
laptop but that is not necessary.
If you do install ACL2s on your laptop, you might want to look at this
Do not be nervous about learning a new programming language. In your careers
as CS students and then as computer scientists you will learn new languages
regularly! Get used to it!
Note: ACL2 can be run under Emacs and directly from Windows or Unix.
You may see me using it that way in class from time to time. But the
preferred interface for novices is ACL2s, The ACL2 Sedan for Eclipse.
It's called the “sedan” for good reason. Driving full ACL2 is like driving
a race car: one mistake and you're in the ditch.
Exams and Scheduled Quizzes
There will be two midterms and a final. See above for the dates.
There will be a scheduled quiz in every lecture except the first one and the two lecture periods devoted to
Email and Discussion Forum
All students should become familiar with the University's official e-mail student
notification policy. I may occasionally use email to communicate with
the students in the class and it is your responsibility to keep your UT Direct
email address current and to check it frequently and regularly.
Discussion Forum To Be Determined (In Spring, 2009, online discussion
forums were organized. If that happens this time, I'll announce it here and
Grades are determined by the total number of points earned in each of several
activities: attendance at TA sessions, scheduled quizzes, homeworks, the two
midterm exams, and the final exam. The total available points is 1240, distributed
|total for course||1240
Your final score will be the total number of points earned divided by 12.40 and
rounded up to an integer. This gives an integer between 0 and 100.
Letter grades will be assigned in the conventional way:
|93 ≤ score ≤ 100||A
|90 ≤ score < 93||A-
|87 ≤ score < 90||B+
|83 ≤ score < 87||B
|80 ≤ score < 83||B-
|77 ≤ score < 80||C+
|73 ≤ score < 77||C
|70 ≤ score < 73||C-
|67 ≤ score < 70||D+
|63 ≤ score < 67||D
|60 ≤ score < 63||D-
| 0 ≤ score < 60||F
Each quiz is worth 10 points. But some quizzes may have as few as 2 questions
and others as many as 15 or so. The average number of questions per quiz will
be about 6.
Quiz, homework, and test scores are kept as integers between 0 and 10. When computed from fractions, they are rounded up.
For example if you answer 5 questions correctly on a quiz with 6 questions, you
will receive ceiling(10 × 5/6) = 9 points, not 8.3 points. Midterm and final exam scores are kept as
integers in the range 0 to 100.
Partial credit is not given on quiz answers.
Quiz scores are not curved.
If any student in a lecture is discovered with more than one clicker, the
clickers will be confiscated until the situation is sorted out by the
instructor. If it is determined that one student was taking quizzes for
another it will be considered cheating. The CS department penalty for
cheating is a course grade of F and referral to the Dean of
While discussion of the homework problems among students is encouraged, each
student must prepare his or her own homework submissions. Turning in
somebody else's work as your own is an example of cheating. The CS
department penalty for cheating is a course grade of F and
referral to the Dean of Students.
If you ever wonder whether some behavior you're contemplating would be considered cheating, don't do it!
If it's in this course, ask me. If it's in another course, ask the professor in charge.
Partial credit is not given on homework.
Failure to be in your TA session when attendance is taken, for any reason
other than an excused absence, results in a 0
that day. No partial credit is given for late arrivals.
Failure to turn in a homework on time, for any reason other than an excused absence, results in a 0 on that homework.
No partial credit is given for late homeworks.
Failure to take a midterm or the final exam will result in a score of 0.
Except for excused absences, make up exams
will not be scheduled.
No “slip points” are provided. However, it is possible to make an A
without perfect performance. See Effects of Various Coping Strategies.
If you are dissatisfied with a grade you receive on an assignment or test,
you must submit your complaint via email, along with supporting evidence or
arguments, to your TA within one week of the date the teaching staff first
attempted to return the assignment or test to you.
Questions about your homework grades are to be sent to your TA.
There are no opportunities for extra credit in this course.
Course grades may be adjusted with pluses and minuses at the instructor's
Effects of Various Coping Strategies
In this section I illustrate the implications of this grading scheme by
describing several hypothetical performance records and giving the resulting
First, note how expensive cheating is. A single quiz or homework assignment
is worth just 10 points out of 1240, less than 1% of your grade. But giving
your clicker to somebody to operate on your behalf, turning in somebody
else's work, or facilitating such behavior by another student results in a
course grade of F. That is, you're risking failing the entire
course to make less than 1% of the total available points.
If you miss one TA session and one Quiz (lecture) and fail to turn in one
homework, but you score 80% on the remaining quizzes, homeworks, midterms,
and the final exam, you'll make a B-.
But if you miss two TA sessions and two Quizes and otherwise perform as
above, you'll make a C+.
If you miss one TA session and one Quiz (lecture) and fail to turn in one
homework, but you score at least 90% on the remaining quizzes and homeworks and
you score 90 on two of the exams and 91 on the other, you'll make an A-.
Thus, it is possible to make an A- without perfect attendance or perfect
homework performance. Because of this, there are no “slip points.”
It is less risky to attend all the TA sessions and lectures.
If you have perfect attendance at the TA sessions and lectures and score 90
on every quiz, exam, and homework you turn in, you can afford to miss no more than 3
homeworks and still make an A-.
You could also make an A- by attending all the TA sessions and lectures,
make a 85% on the quizzes, average 95% on the homeworks and turn in all of them,
and make an 88 and 92 on the midterms and then a 90 on the final.
Finally, if you ace the exams, with three perfect 100s, and get perfect scores
on all the homeworks, but don't come to lectures or the TA sessions, you'll
make a D+! So you can't do well in this class without attending the
lectures and your TA sessions.
You can experiment with your own strategies using the following ACL2 function.
If you can't figure out how to use it after a couple of weeks, you won't pass.
To have ACL2 check that you're calling it with the right type of arguments,
:set-guard-checking t before you evaluate sample scenarios.
(defun score (tax qzx qzv hwx hwv mt1 mt2 fin)
:guard (and (and (natp tax) (<= tax 15))
(and (natp qzx) (<= qzx 27))
(and (rationalp qzv) (<= 0 qzv) (<= qzv 1))
(and (natp hwx) (<= hwx 12))
(and (rationalp hwv) (<= 0 hwv) (<= hwv 1))
(and (rationalp mt1) (<= 0 mt1) (<= mt1 1))
(and (rationalp mt2) (<= 0 mt2) (<= mt2 1))
(and (rationalp fin) (<= 0 fin) (<= fin 1)))))
; Returns the final score, between 0 and 100, of a student with
; the indicated performance, where the types of the arguments
; are as given above. Their meanings are:
; tax = number of TA sessions missed
; qzx = number of Quizzes missed
; qzv = average grade on quizzes taken
; hwx = number of Homeworks missed
; hwv = average grade on homeworks turned in
; mt1 = grade on midterm 1
; mt2 = grade on midterm 2
; fin = grade on final exam
; Note that the function requires fractional inputs between 0 and 1
; to represent the average scores on the quizzes, homeworks, and
; tests. I multiply those by the total number of points available
; for each category. In actual grading, we will just sum the number
; of points earned on the quizzes, the homeworks, and the tests.
(let ((TA 10)
(/ (+ (* (- 15 tax) TA)
(* (- 27 qzx) (* qzv QZ))
(* (- 12 hwx) (* hwv HW))
(ceiling (* mt1 M1) 1)
(ceiling (* mt2 M2) 1)
(ceiling (* fin FN) 1))
(+ (* 15 TA) (* 27 QZ) (* 12 HW) M1 M2 FN)))
For example, the outcome of the scenario
Suppose I miss 2 TA sessions and 1 lecture. I think I can score an
average of 73% on all the other quizzes. I haven't missed turning in any homework yet. I
can keep that up — it's easy since all the homeworks are marked in the book So my
missed homeworks will be 0.
I'm sure I can maintain an average
of 95% on the homeworks — I have a couple of
friends in the course who explain things to me. I got a 78% on the first
midterm. I think I can get an 85% on the next one and I'll assume I get just 80% on the
final exam. What will my final grade be?
is determined by
(score 2 1 73/100 0 95/100 78/100 85/100 80/100)
which computes to 81. The student will make a B-.
Religious Holy Days: A student who is absent from an examination or
cannot meet an assignment deadline due to the observance of a religious holy
day may take the examination on an alternate day, submit the assignment up to
24 hours late without penalty, or be excused from the examination or
assignment, if proper notice of the planned absence has been given. Notice
must be given at least fourteen days prior to the classes scheduled on dates
the student will be absent. For religious holy days that fall within the
first two weeks of the semester, notice should be given on the first day of
the semester. It must be personally delivered to the instructor and signed
and dated by the instructor, or sent via certified mail, return receipt
requested. Email notification will be accepted if received, but a student
submitting such notification must receive email confirmation from the
instructor. A student who fails to complete missed work within the time
allowed will be subject to the normal academic penalties.
Disability Related Needs: Please notify me of any
modification/adaptation you may require to accommodate a disability-related
need. You will be requested to provide documentation to the Office of the
Dean of Students in order that the most appropriate accommodations can be
determined. Specialized services are available on campus through Services for
Students with Disabilities, SSB 4th floor, A5800, 471-6259, TTY 471-4641
Emergencies and Illness: Documented emergencies and illnesses will be
dealt with by the instructor. For best results, communicate with me
before you miss a midterm or the final and be prepared to supply
written, verifiable evidence of the condition.
Code of Conduct: For important other advice about expectations and
conduct, see The Computer Sciences Department Rules to Live By.
I thank the following people for their help in preparing for this course: Bob
Boyer, Matt Kaufmann, Warren Hunt, Peter Dillinger, Pete Manolios, Harsh
Chamarthi, Sandip Ray, Morrie Schluman, Mike Scott, Bruce Porter, David
Rager, Behnam Robatmili, Ian Wehrman, Nathan Wetzler, Mark Reitblatt, and all
the TAs, tutors, departmental academic staff, and the ACL2 research
Why We Make CS Majors Take This Course
In science, mathematics is used to describe the world and to analyze the
behavior and interactions of objects in the world. Mathematics is necessary
because the objects we describe and analyze — planets, reactions, supernovas, molecular docking,
microprocessors, algorithms, networks — are so complicated that we cannot
keep all the interactions in mind at once. We need the precision and power
of mathematics to help us keep things straight in our heads.
In physics, for example, the dominant mathematical systems are calculus and
differential equations. But in computer science, the dominant mathematical
systems are mathematical logic, set theory, and the theory of functions and
relations. The difference is that physics deals mainly with continuous,
smoothly varying systems, while computer science deals with discrete, digital
systems. Continuous mathematics, like the Real Analysis and Calculus, is of
little use in analyzing a system that goes from one state to another without
any intermediate state.
Thus, the mathematical language of CS is often very different from that of physics.
In physics, your professors will use ∂ x/∂ y, ∫, and lots of
algebraic notation. In CS, your professors will use symbols you've never seen
before: ∧, ∨, ¬, →, ↔, ∀, ∃, ∈, ⊆, ∩, ∪,
etc. To understand your future CS courses and to speak clearly and precisely
to your computing colleagues, you need to learn the rudiments of these
mathematical systems. That's what this course is about.
Mathematical logic, set theory, and function theory are deep intellectual
subjects. Some of the greatest minds in computing — Godel, Turing, von
Neumann, Minsky, McCarthy, Dijkstra, Knuth, Newell, Rabin, Hoare, Cook, Karp,
Emerson, etc., — have made fundamental contributions that can only be
expressed in these terms. Some of the deepest insights mankind has had about
the nature of truth and the power of computation stem from these subjects.
Many of the basic ideas of programming languages and of system design — variables, objects,
methods, macros, modularity, recursion, types, interpreters, representation, abstraction —
were first explored in the context of mathematical logic.
How to Succeed in CS313K
You've probably never come across any form of mathematics quite like what you'll see here.
So it is going to seem really strange and hard to grasp.
But what are the skills you have as computer scientists? You can
These are the same skills it takes to master logic, sets, and functions.
- spot patterns
- understand the power of repetition
- solve puzzles
- decompose a problem into simpler steps
- describe precisely the decomposition and the assembly of their results, and
- use formal symbolic language for writing down such descriptions.
The secret to success is practice, practice, practice. You were not born
with the ability to ride a bike, hit a ball, dance, or play a musical
instrument. You picked up these and almost all your other skills by hard
work and practice. So too with proving theorems and reading set notation!
Nobody is born with an innate comprehension of mathematical logic, set theory, or
the theory of functions!
Everyone who knows how to do this stuff
learned it! We learned it by hard work and practice. You can too!
But you have to stay with it.
Here are the ten most important things to do to succeed in CS313K:
- never fall behind
- schedule time to do your reading in advance of every class
- think about the questions in the text
- spend way more time on this course than I do — I already know this stuff
- don't memorize; understand the new language you're learning
- come to every lecture and TA section
- answer every clicker question and compare your answers to the right ones
- ask questions when you don't understand
- visit me or the TAs or the tutors whenever you feel confused
- never fall behind