## CS 291 Exam One Terms and Concepts

#### Hein Section 6.2 Propositional Calculus

• 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.

#### Hein Section 6.3 Formal Reasoning

• 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.

#### Hein Section 6.4 Formal Axiom Systems

• 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.