COT 3100 (Section #7094X) Topic #1:
Fundamentals of Logic

This topic covers the basic elements of propositional and predicate logic. In general, by logic we mean the mathematical language that permits us to concisely yet unambigiously express complex statements, and to accurately define and reason about the conditions under which those statements are true or false.

In a later topic, Formal Proofs, we will show how to use these fundamental elements of logic as building blocks for constructing precise, complete proofs of logical statements. Such formal proofs are useful because they can easily be checked carefully by other people (or even automatically by computer proof-verification systems), and so they provide a way to convince even the most die-hard skeptics that a very complex argument is indeed correct.

In another later topic, Probability, we will show how to extend logic beyond the realm of the true and false, to deal with shades of uncertainty.

Propositional Logic (2 lectures)

Propositional logic deals with building compound logic statements out of simpler statements using standard connectives such as AND and OR. It is covered in sections 1.1 and 1.2 of the text. It has many immediate, practical applications:

Applications of propositional logic:

For computer engineers, propositional logic is important because it is the fundamental principle underlying the design of all digital computing hardware.
For programmers, propositional logic is important because its constructs are a critical part of all general-purpose computer programming languages.
For anyone working in information systems, propositional logic concepts are useful for composing sophisticated queries to databases and search engines.
Understanding how to use propositional logic is a generally useful tool for thought, because it allows you to extend your innate logical reasoning abilities to the realm of long, complex ideas.

Objectives:

After completing propositional logic, the student should be able to:

Explain in terms understandable by anyone (a) what an atomic or compound "proposition" is, (b) what the basic ideas of propositional logic are, and (c) what are its primary applications.
Give examples of English sentences that are propositions, and examples of ones that are not.
Write from scratch the symbols and truth tables for the operators NOT, AND, OR, XOR, IMPLIES, and IF-AND-ONLY-IF.
Explain to any college student the meaning of any of these connectives.
Generate the truth tables for small compound propositions.
Correctly translate small compound statements from English to propositional logic, or vice-versa.
Also translate propositions involving NOT, AND, OR, and XOR to and from logic-level circuit diagrams.
Rapidly and accurately determine the truth value of any compound proposition given the truth values of its atomic propositions.
Evaluate bitwise logic expressions on bit strings.
Convert compound propositions to other equivalent propositions.
Determine using either truth tables or symbolic derivation whether a small compond proposition is a tautology or a contradiction.
Determine for any pair of small compound propositions whether the two are equivalent.
Explain to any bright college student the general infeasibility of determining satisfiability or equivalence of very long propositions.

Predicate Logic (1 lecture)

Predicate logic is logic language that includes propositional logic, and additionally adds the ability to precisely express statements that are explicitly about particular objects, all objects, or some objects of a given class. It is covered in Rosen §1.3.

Predicate logic has widespread applications in all areas of mathematics and theoretical computer science (for precisely expressing and proving complex statements), in program verification (proving that programs or parts of programs are correct in all cases), and in some database query languages and advanced programming languages. It is also a powerful tool for improving one's general-purpose reasoning abilities.

Objectives

Objectives for Predicate Logic - still under construction.

Homework Assignments