**MAIN OBJECTIVE:** to teach logical foundations of computer
science.

**MOTIVATION:** How can we make sure that a program computes what
the user want? Of course, we can (and we should) test the program on
several examples. However, if the program works well on several
example, there is no guarantee that it will always work well. Such
a guarantee cannot come from testing, it has to come from
*reasoning* about the program. The science of reasoning is
called *logic*. So, to make sure that our programs satisfy
the user specifications, we must use logic. In this class, we will
study different logical methods and techniques.

Reasoning about complex objects -- such as complex programs -- is not easy. Just as we human make mistakes when computing by hand and when coding, we often make mistakes when reasoning. Computing becomes easier (and less error-prone) when we make computers help us compute; for that, we need to describe the corresponding computational tasks in precise terms -- the terms that a computer can understand. Similarly, to make reasoning easier and less error-prone, we need to describe the corresponding logical problems in precise terms, terms a computer can understand and process. Thus, a significant part of this class will be devoted to a formal description of different logics, and to algorithms that help solve the corresponding logical problems.

**CONTENTS:** We start with the simplest logic --
*propositional* logic, a logic of "and", "or", and "not"
operations used in if-statements. We will learn how to
translate appropriate English phrases into this language, and
how to reason in propositional logic. Specifically, we will
first study so-called natural deduction -- a commonsense way of
reasoning about propositional formulas. As often happens in
computer science, the natural way is not always the most
efficient one, so we will study different ways to reason about
such formulas, some of which related to digital design (and its
normal forms), some related to Artificial Intelligence
(resolution).

Interestingly, often, once we have formulated the specifications in terms of propositional logic, we can automatically generate the corresponding program. In this class, we will describe the main ideas behind such logic-based automated program synthesis.

Not all statements can be expressed in propositional logic:
often, to check the program's correctness, we need to make sure
that it works correctly *for all* possible inputs.
Statements containing *quantifiers* such as "for all" and
"there exists" form *predicate* (*first-order*)
logic. Again, we will learn how to translate appropriate
English statements into this logic, and how to reason in this
logic.

The predicate logic is much more complex than the propositional logic: In propositional logic, there is an algorithm that solves all the problems; this algorithm may require too much computation time, but it exists. In contrast, for predicate logic, no such general algorithm is possible. It is therefore desirable to find practically important classes of problems which can be algorithmically solved. In this class, we will learn two such classes, that correspond to temporal logic (reasoning about changes) and modal logic (reasoning about what is possible and what is not). We will show how these logics can help, correspondingly, in program verification and in dealing with uncertainty (in particular, with interval uncertainty).

All the above techniques deal with situations where the
statements have an absolutely precise meaning. However, often,
the users are not precise. For example, if it is not possible
to always produce an exact solution to an optimization problem,
a user may want a program that will produce a solution which
is, in the vast majority of cases, *close* to the optimum
-- without specifying what "close" or "vast majority" mean. The
last topic that we will study -- multi-valued logics (such as
fuzzy logic) -- help to describe such statement inside the
computer, and to have a computer process such statements.
Interestingly, such logics also help to describe how we think
-- and thus, help computers emulate our informal reasoning.

**PROJECTS:** An important part of the class is a project.
There are three possible types of projects:

- If, as part of your current research project, you are interested in doing some research related to logical foundations, a research that will be useful for your future thesis, project, or dissertation, this will be an excellent project for the class.
- Another possibility is to participate in a hands-on advanced logic-related project, usually in collaboration with someone who is already working on a related topic. A list of such projects will be given shortly after the class starts. These projects will range from relatively easy to truly challenging ones -- ones which could eventually lead to a publication.

**PROJECTS:** An important part of the class is a project.
There are three possible types of projects:

- An ideal class project is if you do something related to logic which is useful for your future thesis or dissertation. Please check with your advisor about it, maybe he or she wants you to read and report on some logic-related paper, maybe you need to do some logic-related research, whatever your advisor recommends will be a very good project for this class, just let the class instructor know what exactly you plan to do.
- If you have not yet selected an advisor, but you already know what research area you want to work in, come talks to the class instructor, we will try to find some appropriate topic -- and if you have any proposals already, great.
- If you do not have a research topic or you have a one but your advisor cannot find anything logic-related that will be helpful for your future thesis or dissertation, come talk to the instructor too.
- Maybe you like logic and want to start doing a project in logic, then come and talk to the instructor, we will try to find something that will be of interest to you.

- reviewing and reporting on a related paper, or
- doing some independent research (not research as in high school, but research as in graduate school, i.e., trying to come up with something new), or
- programming something logic-related.

**TESTS AND GRADES:** There will be two tests and one final exam.
Each topic means home assignments -- both theoretical and programming.
Maximum number of points:

- first test: 10
- second test: 25
- home assignments: 10
- final exam: 35
- project: 20

A good project can help but it cannot completely cover possible deficiencies of knowledge as shown on the test and on the homeworks. In general, up to 80 points come from tests and home assignments. So:

- to get an A, you must gain, on all the tests and home assignments, at least 90% of the possible amount of points (i.e., at least 72), and also at least 90 points overall;
- to get a B, you must gain, on all the tests and home assignments, at least 80% of the possible amount of points (i.e., at least 64), and also at least 80 points overall;
- to get a C, you must gain, on all the tests and home assignments, at least 70% of the possible amount of points (i.e., at least 56), and also at least 70 points overall.

**STANDARDS OF CONDUCT:**
Students are expected to conduct themselves in a
professional and courteous manner, as prescribed by the
Standards of Conduct.
Students may discuss programming
exercises in a general way with other students, but the solutions must be
done independently. Similarly, groups may discuss project assignments with
other groups, but the solutions must be done by the group itself. Graded
work should be unmistakably your own. You may not transcribe or copy a
solution taken from another person, book, or other source, e.g., a web
page). Professors are required to - and will -
report academic dishonesty and
any other violation of the Standards of Conduct to the Dean of Students.

If you feel you may have a disability that requires accommodation, contact the The Center for Accommodations and Support Services (CASS) at 747-5148, go to Room 106 E. Union, or e-mail to cass@utep.edu. For additional information, please visit the CASS website.