# 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
\
### 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
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://chloe-codes1.gitbook.io/til/programming-101/computational_thinking.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.