Computational Thinking

Two Difficult Aspects of Programming

1. Programming language syntax and library usage

2. Logic (Hard Logic)

Soft Logic vs Hard Logic

• In everyday life

  • Soft Logic is useful because it is fast

  • Although logically imprecise expressions are used, there is an assumption that everyone already knows what they mean

• Programming uses Hard Logic

  • All expressions in programming languages originate from logic

  • Hard Logic is needed to understand the numerous algorithms used

1. Logic and Proof

Proposition

• A statement or sentence whose truth or falsity can be determined

• Expressed as p, q, r ...

  • If p -> q is true, then ~q -> ~p is also true (Contrapositive)

• ex)

  • Seoul is the capital of South Korea

  • 1 + 1 = 3

  • If two sides have equal length, then it is an isosceles triangle.

    -> If it is not an isosceles triangle, then no matter which two sides you choose, the lengths of the two sides are different

Truth Value

• Expresses true or false

• T, F or 1, 0

Tautology

: A proposition whose truth value is always true

Contradiction

: A proposition whose truth value is always false

Contingent Proposition

• A proposition that is neither a tautology nor a contradiction

• A proposition that varies depending on the situation

Conditional Proposition

• When p and q are propositions, a proposition where p is the condition (or cause) and q is the conclusion (or result)

• p -> q (if p then q)

• False only when p is True and q is False

Biconditional Proposition

• When p and q are propositions, a proposition where both p and q are conditions and conclusions

• p <-> q (if p then q, and if q then p)

• True when p and q have the same truth value

Propositional Operations (Connectives)

• Negation NOT

  • When p is a proposition, the truth value of the proposition is reversed

  • Denoted as ~p

    • Read as not p or the negation of p

• Conjunction AND

  • When p and q are propositions, a proposition that is true only when both p and q are true

  • p ^ q

    • p and q

• Disjunction OR

  • When p and q are propositions, a proposition that is false only when both p and q are false

  • p v q

    • p or q

• Exclusive Disjunction XOR

  • When p and q are propositions, a proposition that is true when only one of p or q is true

  • p ⊕ q

    • p xor q

Operator Precedence

• ~ > v , ^ > -> , <->

Proof

• A proof must be expressible as a propositional formula

• Usually the exact propositional formula is not written out, but fundamentally it can be converted into one

• Many misunderstandings about proofs arise from confusing p -> q with p <-> q

Mathematical Induction and Levels of Proof

• Basic form of mathematical induction

  • If P(1) is true and P(n) -> P(n+1) is true, then P(n) is true for all natural numbers n

• Strong form of mathematical induction

  • If P(1) is true and P(1) ^ P(2) ^ ... ^ P(n) -> P(n+1) is true (all cases are true), then P(n) is true for all natural numbers n

Vacuous Truth (pseudo-proposition) Logic

If you're the police chief, then I'm the president!

F -> () is always true

• If you assume a false proposition is true, then any proposition becomes true

  • ex) If you win the lottery, I'll buy you a car

    • If you don't win the lottery, not buying a car is not a lie, and buying one even without winning is also not a lie

    • By the same principle, if we say 2 is odd, then 5 being even or odd is not false

Only T -> F is definitively false

2. Numbers and Representation

• Computers represent numbers by collecting bits that can express 0/1

• Using k bits, it is possible to represent from 0 to 2^k -1 (from 1 to 2^k)

  • In fact, it is not necessarily that range!

  • It depends on the agreed-upon method, but in any case it is possible to represent up to 2^k different values

    • This is exactly the same process as using k digits in decimal to represent from 0 to 10^k -1

How many bits are needed to represent a value n?

• 2^k -1 >= n must hold

  • That is, 2^k >= n+1

  • Equivalently, k >= log(n+1)

    -> Approximately logn bits are needed

  • x = logn and 2^x = n refer to the same thing!

+

What is logn

1. The answer to "what power of 2 gives n"

2. The answer to "how many bits are needed to represent n"

3. The answer to "starting from 1 and continuously doubling, how many times until you reach n"

4. The answer to "when continuously dividing n by 2, how many divisions until you get approximately 1"

• When x = logn, comparing x and n, x is smaller, and as n grows, they diverge enormously

  • When you want to represent something that changes drastically in a smaller scale, use log!

• The value of a 100-digit decimal number is so large it's unreadable!

• In computer science, the base of log is always 2

• The address space of a 32-bit computer is 2^32 = approximately 4 billion addresses

• • When we reach the last (1+1+ ...)

    • n/ 2^k = 1

    • n = 2^k

    • k = logn

  • The total number of parentheses is logn

  • So when factoring the entire expression by n, we get nlogn

Big-O Complexity

Big O

Exercises

1. What is the range of numbers that can be represented with logn bits in binary representation?

   • With n bits -> 2^n values

   • With logn bits -> n values

2. If the game of 20 Questions proceeds ideally, how many possible answers can be guessed?

   • Each question can yield 2 possible answers

   • The total number of questions is 20

   • Therefore, the number of possible answers is 2^20

3. When n is sufficiently large, which value is greater?

   1. 2n < n^2

      • When the number is infinitely large, the constant in front of n can be ignored, and the growth rate of n^2 is much greater than n

   2. 2^(n/2) < sqrt(3^n)

      • sqrt(3^n) = 3^(n/2)

      • That is, comparing 2^n and 3^n, 3^n is greater

   3. 2^(nlogn) > n!

      • Assuming base 2,

      • n^n > n!

   4. log2^(2n) < n*sqrt(n)

      • 2n < n*sqrt(n)

4. When x = loga(yz), express x using logarithms with base 2. However, each logarithm function's argument must be a single letter.

5. Find the inverse functions of the following functions

   1. f(x) = log(x-3) -5

      • f^-1(x) = 2^(x+5) +3

   2. f(x) = 3 log(x+3) +1

   3. f(x) = 2 x 3^x -1

Sets and Combinatorics

Sets

• To prove that A is a subset of B for two sets A and B is equivalent to showing that any element of A is contained in B

  • ex) To prove that all multiples of 4 are multiples of 2, it suffices to show that 4k = 2(2k)!

• To prove that two sets A and B are equal, it suffices to prove that A is a subset of B and B is a subset of A

Combinations

• Combinatorics generally refers to problems that involve counting the number of cases

• The number of combinations is sometimes expressed using C, but the parenthetical notation such as (5 choose 2) = 10 is used more frequently

+

Mathematical Induction

One of the methods of mathematical proof, primarily used to show that a proposition holds for all natural numbers.

Mathematical induction consists of two steps.

First, show that the given proposition holds for 1 (or generally for k).

Next, show that if the proposition holds for any natural number n greater than or equal to 1 (or k), then it also holds for n+1.

Then, by mathematical induction, the given proposition holds for all natural numbers (or all natural numbers greater than or equal to k).

+

Proof by Contradiction

• When trying to prove a proposition, assume the negation of that proposition is true

• Show that this assumption leads to a contradiction, thereby demonstrating the original proposition is true

Exercises

4. Basic Formulas

master crm

5. Recursion

• Recursion is a function that calls itself

• (Can it ever terminate?)

  • A function has input, and if it calls itself with the same input, it obviously cannot terminate

  • It can terminate with different input!

• A function is something that codes a method to solve a problem

  • It does not solve just a single case of a problem!

    • If properly coded, it must solve all cases of the problem it addresses

• Mathematical induction can be used for proof

  1. The problem can be solved when n is 0

  2. If the problem can be solved for n-1, then it can also be solved for n

     • If the above two are true, then it is true that the problem can be solved for all possible n