SUNY Geneseo Department of Computer Science

Logic

Return to List of Lectures

Questions?

Reasoning about Conditionals

Sections 5.1 through 5.5

• Or, And, Exclusive-Or
  • Truth tables
  • Proofs
  • Combining boolean operations
  • Simplifying combinations, optimizing code
• Implication?
  • p implies q
  • If p is true, then q is true too
  • aka "whenever p is true, q is true too"
  • Truth table

• "q is true when p is true"
  • Equivalent to "if p then q"
  • vs "q is true only when p is true"
  • vs "q is true when and only when p is true"
  • Substitute "if" for "when" above
• Proof by case
• Performance analysis of conditionals
  • 2n vs n...?
    • Hypothetical example
    • Suppose some algorithm with input n...
      • Has worst case running time 2n
      • Has best case running time of n
    • Note worst case is bigger than best case
      • Twice as much work in worst case
    • But both proportional to n, maybe difference doesn't matter that much
  • Worst case, best case to narrow expected case...

Examples

• Pseudocode for reading a digit from a user:

        read character c
        until c >= '0' and c <= '9'
            print error message
            read character c

• But "while" loops are more common in actual programming languages than "until," so translate this into a form that uses "while"

        read c
        while ! ( c >= '0' && c <= '9' )
            print error message
            read c

• or (being very careful about "or," deMorgan's Law)

        read c
        while c < '0' || c > '9'
            print error message
            read c

• Prove that a "not and" operation is sufficient to define and, or, and not (and thus all logical expressions)
  • Commonly called "nand"
  • a nand b = not ( a and b )

• Proof that this computes "not a"
• Suppose a is false. Then the "nand" computes "not (a and a )" = "not ( false and false )" = "not false" = true
• Suppose a is true. Then the "nand" computes "not ( a and a )" = "not ( true and true )" = "not true" = false

Hand out problem set 3

Next

Recursion review

Read section 6.1