Midterm Study Guide

Time: Tuesday, March 7th from 6pm-8pm
Location: CSI 437 and 430

• Midterm Practice Problems

• Midterm Definitions Sheet (subject to change)

Structure

• 6-7 Problems

• Shorter than HWs

• The hardest problems are the easier starred problems on the HWs.

• You will be given all definitions, equivalence laws, and inference rules.

• You will not be given proof strategies.

Topics

• Homeworks 2 through 7

• Propositional logic (not emphasized)

• Equivalence laws (not emphasized)

• First-order predicate logic

  • Including domains

• Formal (two-column) derivations

• Proofs

  • Universal generalizations ("Consider an arbitrary")

  • Existential generalizations (proof by example)

  • Direct proofs

  • Proof by cases

  • Proofs "in two directions"

  • Proof by contraposition

  • Proof by contradiction (not emphasized)

• Sets

  • Properties and their proofs: subset, equality.

  • Operations: union, intersection, set difference, cross product, powerset.

• No algebra (i.e. given x is even, prove x^4+2x+8 is even).

• No puzzles

Problem Types:

• Translate English into mathematical objects: i.e. translating specifications into logic, arguments into derivations.

• Translating mathematical claims into English 

• Define a mathematical object: i.e. defining a domain to make a statement true or false, or defining sets that satisfy a property

  • Figures are acceptable definitions of objects (i.e. sets).

• Informally draw conclusions from premises ("what can you conclude")

• Formal derivations (HW5, with inference rules)

• Find the flaw (in a proof or derivation)

• Write a proof:

  • Answers can use a "white-board" level of formality:

  • Bullet points are great.

  • Complete sentences optional.

  • Transitions are helpful, but not required.

  • You may skip small steps in arguments, i.e. "As A ⊆ B and x ∈ A, we know x ∈ B" can be shortened to "So x ∈ B".  

    1. However, partial credit is easier to award when they are included.

• Synthesis: apply knowledge in a new way.