Propositional Logic gives us tools for precisely describing and analyzing logical statements. Real-world problems are usually given to us in English. In order to apply our new tool, we must first “formalize” the problem by translating the statement into Propositional Logic. Then, we can analyze it using tools such as truth tables or SAT solvers.
In this next topic, we will extend our knowledge of logic in a few ways. First, we will show the connection between Propositional Logic and circuits. Second, we will look at how to prove logical expressions (or circuits) equivalent without truth tables. Finally, we will extend our logic with the ability to talk about properties of objects, giving us Predicate Logic.
In this topic, we will learn a new way to reason about facts in logic. Previously, we saw how to show that various facts are equivalent. Here, we will see how to infer new facts from known ones. This includes equivalence as a special case (when we can infer either fact from the other) but is vastly more powerful.
We will begin by writing our proofs formally, which makes them easy to check. Formal proofs are built up using inference rules. Then, we will begin learning how to write English proofs by translating our formal proofs into English. As the course continues, we aim to get more confortable writing proofs directly in English, without working formally.
In the remainder of the course, we will look at different kinds of mathematical objects that show up frequently in computer science. In addition to learning about their properties, this will give us settings in which to practice the proof techniques we learned in Topic 3.
In this topic, we look at important properties of numbers. All data in a computer is stored as numbers and the only operations computers can do on their own are arithmetic calculations. For that reason, numbers arise everywhere in computer science, and we need to understand them well in order to make computers do interesting things for us.
In this next topic, we will extend our knowledge of number theory in a few ways. First, we will use our knowledge of congruences to show that we can solve for the variable that appears in a congruence (here, usually called a “modular equation”). Second, we will add two new inference rules that apply specifically to the domain of non-negative integers. These allow us to prove for-all claims over the non-negative integers in a new way. Finally, we will look at a few more applications of number theory that arise widely in computer science.
Our goal for the remainder of the course is to move beyond numbers to look at more interesting kinds of mathematical objects that show up in computer science. Such objects are usually described in the language of set theory, which will study in this topic.
In addition to their use throughout theoretical computer science, sets also arise in almost every area of programming. In Java, for example, Set and the closely related Map interfaces are two of the most widely used parts of the standard Java library.
In this topic, we begin our study of theoretical computer science by looking at two ways of defining “languages”, which are simply sets of strings. We will later connect these ways of defining languages to different types of computing machines, whereupon the fact that one way of defining languages has more expressive power tells us that one type of machine is more powerful than another.
Next, we see how to define a language by describing a “machine” that can recognize strings in the language. We will look at a few different kinds of machines and not only relate them to each other but also connect them to the ways of defining languages that we learned in Topic 9. This will eventually lead us to showing that our simple machines are not sufficiently powerful to define some languages we have seen before.
Are there problems that computers cannot solve? In the last topic, we saw that there are certain languages that cannot be described by any regular expression. What about a similar question for Java? Are there languages that cannot be recognized by any Java program?
Surprisingly, the answer is yes. We will discuss an important sense in which there are “more” languages than there are Java programs. Hence there must be some languages that are not described by any Java program. These languages are called “uncomputable” or “undecidable”. (To make this argument precise, we will need to define what it means for one infinite set to have “more” elements than another.) We will also see Turing's famous example of an uncomputable language: the Halting Problem.
That's all, folks!