逻辑门/二进制

We will start with the basic units, the $0$ and the $1$. $0$ is used to represent "false" and $1$ is used to represent "true." A boolean variable is a variable takes the value either $0$ or $1$. A boolean operation is a function that takes in some number of boolean variables and outputs either $0$ or $1$. By this definition, boolean operations can easily be written out using truth tables, in which we list every possible input and then write what the operation gives for each one.

There are three main operators on boolean variables: NOT ($\neg$), AND ($\land$), OR ($\lor$). They are described in the following truth tables below. Essentially, NOT flips the value, AND checks if both are true, and OR determines if at least one of them are true.

Here we will show a proof by truth table that $\neg((\neg x)\land(\neg y))$ and $x\lor y$ are logically equivalent, which means these two functions give the same value for all inputs.

Binary is a very convenient system for working with logical statements. To convert a binary number to base $10$ (decimal), we sum up the $k$th digit times $2^k$, so if the number is $11011001$ then we sum up $1\cdot2^0+0\cdot2^1+0\cdot2^2+1\cdot2^3+1\cdot2^4+0\cdot2^5+1\cdot2^6+1\cdot2^7=217$.

To convert from decimal to binary, we continually subtract the largest power of $2$ less than the number and try to reverse engineer the above definition. So for $100$, subtract $64=2^6$, then from $100-64=36$ subtract $32=2^5$, then $36-32=4=2^2$. So $100=2^6+2^5+2^2=1100100$. There is also another way that involves finding the number mod 2, 4, 8, etc but this gets complicated.