Open main menu
Home
Random
Log in
Settings
About The Portal Wiki
Disclaimers
The Portal Wiki
Search
Anisomorphism
Joined 24 January 2021
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
=== Gates === Typically you will see a logic gate defined by its values on all combinations of inputs as a "truth table": {| class="wikitable" style="margin:auto" |+ AND |- ! x !! y !! x AND y = AND(x,y) |- | 0 || 0 || 0 |- | 0 || 1 || 0 |- | 1 || 0 || 0 |- | 1 || 1 || 1 |} And statements written with logical connectives: <math> (x\and y)\or z = OR(AND(x,y),z) </math> <br> Along with distributive laws: <math> (x\and y)\or z = (x\or z)\and(y\or z) </math>, <math> (x\or y)\and z = (x\and z)\or(y\and z) </math> <br> De Morgan's laws: <math> \neg(x\and y) = (\neg x)\or (\neg y) </math>, <math> \neg(x\or y) = (\neg x)\and (\neg y) </math> <br> All of which apply to more complicated sentences rather than just individual variables. These laws along with commutative and associative laws are sufficient to evaluate and simplify any general logical expression, however we contend that this is the wrong language for computing and makes other important aspects - the dynamics and algebra - obscure. <br> There is one thing we can extract from logical connectives before moving on. The disjunctive normal form allows us to read truth tables and directly translate them into connective formulae which we can use later. Let us look at a different example which will help us escape the artificiality of AND and OR. {| class="wikitable" style="margin:auto" |+ XOR |- ! x !! y !! XOR(x,y) |- | 0 || 0 || 0 |- | 0 || 1 || 1 |- | 1 || 0 || 1 |- | 1 || 1 || 0 |} XOR is only "true" or 1 when x or y but not both, are 1. Disjunctive normal form says that we can view the x, y entries as unary operators which return the input with no change, combine these as given on the lines which evaluate to 1, and take the OR of all of them for the total connective form of the truth table. Here is the third line: <math> x\and\neg y</math>. <br> The total is: <math> \begin{align*} &(x\and\neg y)\or (\neg x\and y) \\ =&(x\or(\neg x\and y))\and(\neg y\or(\neg x\and y)) \\ =&(x\or\neg x)\and (x\or y)\and(\neg y\or\neg x)\and(\neg y\or y) \\ =&(x\or y)\and (\neg y\or\neg x) \\ =&(x\or y)\and\neg (y\and x) \end{align*} </math> <br> This process can be viewed as a sum of "elementary functions" which are only 1 on one line each, and building a general function/table.
Summary:
Please note that all contributions to The Portal Wiki may be edited, altered, or removed by other contributors. If you do not want your writing to be edited mercilessly, then do not submit it here.
You are also promising us that you wrote this yourself, or copied it from a public domain or similar free resource (see
The Portal:Copyrights
for details).
Do not submit copyrighted work without permission!
Cancel
Editing help
(opens in new window)