CS 291 Exam One Terms and Concepts

Be familiar with truth tables and know how to use them to show the truth value of statements.
Know what makes a statement a well-formed formula (wff).
Understand the hierarchy of evaluation for the logical connectives and be able to unambiguously interpret wffs.
Know how to show that two wffs are logically equivalent by doing a step-by-step proof from one form to the other.
You should be familiar with the basic equivalences from Figure 6.2.6 on page 420.
Understand what it means for a wff to be a tautology, a contradiction or a contingency and be able to determine which of these any wff is using Quine's method.
Be familiar with Conjunctive Normal Form (CNF) and Disjunctive Normal Form (DNF). Be able to turn a wff into either form using equivalences and using truth tables.

Know how to do proofs using natural deduction.
For the you will have access to the Proof Rules on page 439 of your book. Know how to use them to do step-by-step proofs where each step is justified by previous steps and proof rules.
This includes being able to do nested Conditional Proofs (CP) and Indirect Proofs (IP).
You will also have access to the Derived Rules on page 450 of your book, but I will also not expect you to use them.

Know the definitions of soundness and completeness and how they differ.
Soundness: All proofs yield theorems that are tautologies. This means that everything we can prove is in fact true.
Completeness: All tautologies are provable as theorems. This means that everything that is true can be proven.