Representation of data.html (5900B)
1 <?xml version="1.0" encoding="UTF-8"?> 2 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> 3 <html><head><link rel="stylesheet" href="sitewide.css" /><meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/><meta name="exporter-version" content="Evernote Mac 6.13.1 (455785)"/><meta name="altitude" content="2.24882698059082"/><meta name="author" content="Alex Balgavy"/><meta name="created" content="2017-11-06 1:44:00 PM +0000"/><meta name="latitude" content="52.33300989593394"/><meta name="longitude" content="4.865525107085234"/><meta name="source" content="desktop.mac"/><meta name="updated" content="2017-11-06 3:31:32 PM +0000"/><title>Representation of data</title></head><body><div><span style="font-weight: bold;">Representing data</span></div><div>Binary circuits in computers</div><div>Unit of information: bit (binary digit) — 0 or 1 (data values or boolean)</div><div>Bit strings: multiple bits together, which can be given a specific meaning (such as natural numbers)</div><div><br/></div><div><span style="font-weight: bold;">Computing — boolean algebra</span></div><div>we want a computer that can calculate (expression string -> result string(s))</div><div><br/></div><div>operations:</div><div><ul><li>x.y (or x ^ y) — “AND", class of objects with both properties</li><ul><li>x.x— no further information</li><ul><li>x*x = x² = x</li></ul><li>0.x = 0 (annihilator)</li><li>1.x = x (identity)</li></ul><li>x+y (or x v y) — “OR”, merges independent objects</li><li>x+x — no further information</li><ul><li>x+x = x</li><li>0+x = x (identity)</li><li>1+x = 1 (annihilator)</li></ul></ul></div><div><br/></div><div>complements:</div><div><ul><li>if x, then complement is 1-x</li><li>x(1-x) = x-x² = x-x = 0</li><li>1-x = x̄</li></ul><div><br/></div></div><div>therefore, any function ƒ(x) can be written as ƒ(x) = a ⋅ x + b ⋅ (1-x)</div><div>really? let’s try one:</div><blockquote style="margin: 0 0 0 40px; border: none; padding: 0px;"><div>ƒ(x) = a₀ + a₁x</div><div>let b = a₀, a = a₀ + a₁</div><div>∴ ƒ(x) = a ⋅ x + b ⋅ (1-x)</div><div>ƒ(1) = a</div><div>ƒ(0) = b</div><div>ƒ(x) = ƒ(1) ⋅ x + ƒ(0) ⋅ x̄</div><div><br/></div></blockquote><div><b>Truth tables</b><br/></div><div>Binary addition — XOR</div><div>x ⨁ y = x ⋅ ȳ + y ⋅ x̄</div><div><table style="border-collapse: collapse; min-width: 100%;"><colgroup><col style="width: 130px;"/><col style="width: 130px;"/><col style="width: 130px;"/></colgroup><tbody><tr><td style="border: 1px solid rgb(219, 219, 219); width: 130px; padding: 8px;"><div>x</div></td><td style="border: 1px solid rgb(219, 219, 219); width: 130px; padding: 8px;"><div>y</div></td><td style="border: 1px solid rgb(219, 219, 219); width: 130px; padding: 8px;"><div>⨁</div><div>(carry result)</div></td></tr><tr><td style="border: 1px solid rgb(219, 219, 219); width: 130px; padding: 8px;"><div>0</div></td><td style="border: 1px solid rgb(219, 219, 219); width: 130px; padding: 8px;"><div>0</div></td><td style="border: 1px solid rgb(219, 219, 219); width: 130px; padding: 8px;"><div>0 0</div></td></tr><tr><td style="border: 1px solid rgb(219, 219, 219); width: 130px; padding: 8px;"><div>0</div></td><td style="border: 1px solid rgb(219, 219, 219); width: 130px; padding: 8px;"><div>1</div></td><td style="border: 1px solid rgb(219, 219, 219); width: 130px; padding: 8px;"><div>0 1</div></td></tr><tr><td style="border: 1px solid rgb(219, 219, 219); width: 130px; padding: 8px;"><div>1</div></td><td style="border: 1px solid rgb(219, 219, 219); width: 130px; padding: 8px;"><div>0</div></td><td style="border: 1px solid rgb(219, 219, 219); width: 130px; padding: 8px;"><div>0 1</div></td></tr><tr><td style="border: 1px solid rgb(219, 219, 219); width: 130px; padding: 8px;"><div>1</div></td><td style="border: 1px solid rgb(219, 219, 219); width: 130px; padding: 8px;"><div>1</div></td><td style="border: 1px solid rgb(219, 219, 219); width: 130px; padding: 8px;"><div>1 0</div></td></tr></tbody></table></div><div>Binary multiplication — AND</div><div>x ⨂ y = x ⋅ y</div><table style="border-collapse: collapse; min-width: 100%;"><colgroup><col style="width: 130px;"/><col style="width: 130px;"/><col style="width: 130px;"/></colgroup><tbody><tr><td style="border: 1px solid rgb(219, 219, 219); width: 130px; padding: 8px;"><div>x</div></td><td style="border: 1px solid rgb(219, 219, 219); width: 130px; padding: 8px;"><div>y</div></td><td style="border: 1px solid rgb(219, 219, 219); width: 130px; padding: 8px;"><div>⨂</div><div>(carry result)</div></td></tr><tr><td style="border: 1px solid rgb(219, 219, 219); width: 130px; padding: 8px;"><div>0</div></td><td style="border: 1px solid rgb(219, 219, 219); width: 130px; padding: 8px;"><div>0</div></td><td style="border: 1px solid rgb(219, 219, 219); width: 130px; padding: 8px;"><div>0</div></td></tr><tr><td style="border: 1px solid rgb(219, 219, 219); width: 130px; padding: 8px;"><div>0</div></td><td style="border: 1px solid rgb(219, 219, 219); width: 130px; padding: 8px;"><div>1</div></td><td style="border: 1px solid rgb(219, 219, 219); width: 130px; padding: 8px;"><div>0 1</div></td></tr><tr><td style="border: 1px solid rgb(219, 219, 219); width: 130px; padding: 8px;"><div>1</div></td><td style="border: 1px solid rgb(219, 219, 219); width: 130px; padding: 8px;"><div>0</div></td><td style="border: 1px solid rgb(219, 219, 219); width: 130px; padding: 8px;"><div>0 1</div></td></tr><tr><td style="border: 1px solid rgb(219, 219, 219); width: 130px; padding: 8px;"><div>1</div></td><td style="border: 1px solid rgb(219, 219, 219); width: 130px; padding: 8px;"><div>1</div></td><td style="border: 1px solid rgb(219, 219, 219); width: 130px; padding: 8px;"><div>1 0</div></td></tr></tbody></table><div><br/></div></body></html>