 (Upload on Apirl 13 2016) [ 日本語 | English ]

Computer science (計算機科学)

Mount Usu / Sarobetsu post-mined peatland
From left: Crater basin in 1986 and 2006. Cottongrass / Daylily

Principle of optimality (最適性原理)
= Bellman equation, discovered by Richard Bellman (1953)
= dynamic programming equation
Bellman, Richard Ernest (1920–1984)

Boolean algebra (ブール代数)

Boole George (1815-1864, England)

differential equations and algebraic logic
Boolean algebra, introduced in the Laws of Thought (1854)

Boolean algebra

Axiom
1. a + b = b + a
2. (a + b) + c = a + (b + c)
3. a + 0 = a
4. a + a = a
5. ab = ba
6. (ab)c = a(bc)
7. a•1 = a
8. aa = a
9. aa' = 0
10. a + a' = 1
11. a(b + c) = ab + ac
Prove:
1' = 0 → 1' = 1'•1 = 1•1' = 0
a + 1 = 1 → a + 1 = a + (a + a') = (a + a) + a' = a + a' = 1
a•0 = 0•a = 0 → a•0 = 0•a, a•0 = a(aa') = (aa)a' = aa' = 0
a + ab = aa + ab = a•1 + ab = a(1 + b) = a•1 = a
a(a + b) = aa(a + b) = aa + ab = a + ab = a
a(a + b + c) = aaa + ab + ac = (aa + ab) + ac = a + ac = a
a + bc = (a + b)(a + c) →

a + bc = a(a + b + c) + bc = a(a + b) + ac + bc = a(a + b) + c(a + b) //

Q Solve simultaneous equation a + x = 1, ax = 0
A (x = a') is a root because of axiomatic system (a + a' =1)

set x0 as a root
x0 = x0•1 = x0(a + a') = x0a + x0a' = 0 + x0a'
= aa' + x0a' = (a + x0)a' = 1•a' = a'
only a' is the root //

Law. De Morgan's law (1)
→ (ab)' = a' + b'
Pr. (a' + b') + ab = (a' + b' + a)(a' + b' + b) = (b' + 1)(a' + 1) = 1•1 = 1

while (a' + b')ab = a'ab + b'ab = 0•b + 0•a = 0 + 0 = 0
(x = (ab)') is the only root that msut satisfy (x + ab = 0) and (xab = 0)
∴ (ab)' = a' + b //

Law. de Morgan's law (2)
→ (a + b)' = a'b'
Pr. (a + b)' = [(a')' + (b')']' = [(a'b')']' = a'b' //
Table. Case that Boolean algebra that has only specific factors (0, 1)
+  0  1    •  0  1    '
-------    -------    ----
0  0  1    0  0  0    0  1
1  1  1    1  0  1    1  0

Table. Set {a, b} → subset φ, U = {a, b}, {a}, {b}
0 = π, 1 = U, 2 = {a}, 3 = {b}

+  0  1  2  3    •  0  1  2  3    '
-------------    -------------    ----
0  0  1  2  3    0  0  0  0  0    0  1
1  1  1  1  1    1  0  1  2  3    1  0
2  2  1  2  1    2  0  2  2  0    2  3
3  3  1  1  3    3  0  3  0  3    3  2

UNIX (Unix)

 1969 Thompson K: developing the OS for mini-computer PDP-7 (DEC) = beginning of UNIX greatly-simplified functions system files distributed by ASCII format - can be modified by users → causes of developing various UNIX local languages Ex. ATT System V, UCB BSD, IBM AIX 1973 Richie D: unix kernel re-written by C language 1991.10.5 Linus T (Finland): opned Linux distributed freely, independent of unix-OS system → becoming popular EWS (engineering workstation) Past: high-spec computer for business use (the most of OS are UNIX) → system (computer) = EWS (hardware) + UNIX (OS) + Application software office computer = EWS ↔ personal computer (PC) Present: ≈ general-purpose computer (PC), because of upgrading PC BSD, Barkeley Software Distribution one of the UNIX OSs, developed by Univercity of Carfornia, Berkeley functions of C Shell, vi, termcap, virtual memory, TCP/IP network characterzied by high-spec job control adopted by standard UNIX (= SVR4, UNIX System V Release 4) COSE, Common Open Software Environment projects and standards of six computer items, including desktop and network environments, drawn up common API proposed by UNIX vendors