Logic on Numbers
Contents
Logic on Numbers¶
Boolean Logic is the study of things that can be either True or False. Computer bits can also take only two values 0 or 1. All the concepts developed in Boolean Logic can be immediately applied to binary values.
We will look at 4 operations from Boolean Logic and how they can be applied to binary numbers. The operations are Conjunction, Disjunction, Negation, and Exclusive Or.
The operations are listed here in precedence order of evaluation. Operators with a lower precedence number are evaluated before higher values.
Precedence |
Name |
English |
Symbol |
|---|---|---|---|
1 |
Negation |
not |
\(\neg\) |
2 |
Conjunction |
and |
\(\wedge\) |
3 |
Disjunction |
or |
\(\vee\) |
4 |
Exclusive Or |
either … or … |
\(\oplus\) |
Negation¶
The Negation Operator is used to find opposites. In English, we say not. The operator symbol for negation is \(\neg\). The negation only applies to one input and gives the opposite.
If you said “It is not raining” that tells us the opposite of raining is happening. The Truth Table for negation is show below.
In logic, we describe how operators work by using a Truth Table. The Truth Table describes the output of the operator for every possible input.
x |
\(\neg x\) |
|---|---|
1 |
0 |
0 |
1 |
This operator can only be applied to a number in binary.
\( \begin{align} \neg 25_{10} =& 230_{10} \\ \neg(0001 1001) =& 1110 0110 \end{align} \)
The negation operator can be used for the bit flip stage of Two’s Complement.
Conjunction¶
The Conjunction Operator is used when we want two things to be True. In English, the conjunction operation is the word and. The logic symbol we use for conjunction is \(\wedge\). Imagine someone said “It is raining and cold out today.” We understand that they mean both things are True. It is raining is True. It is cold out is also True. How do we apply this to bits? If we say \(x \wedge y\) we are saying both \(x\) and \(y\) are equal to 1. There are four possible ways to use the conjunction on a single bit.
\( \begin{align} 1 \wedge 1 =& 1 \\ 1 \wedge 0 =& 0 \\ 0 \wedge 1 =& 0 \\ 0 \wedge 0 =& 0 \end{align} \)
The Truth Table for the Conjunction is shown below.
\(x\) |
\(y\) |
\(x \wedge y\) |
|---|---|---|
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
We can apply this concept to an entire numbers, we just use the table on each column of the Binary Number. We can compute \(93_{10} \wedge 38_{10}\)
\( \begin{align} & 0101 1101 & 93 \\ \wedge & 0010 0110 & \wedge 38 \\ & = & = \\ & 0000 0100 & 4 \\ \end{align} \)
Only the columns where both bits are 1 result in a 1. Other columns are zeroed. We can use this to determine if a bit in the number is set to 1. The only bit that appears in both \(93_{10}\) and \(38_{10}\) is \(4\).
If \(x \wedge 4_{10}=0\) then the bit for \(2^2\) is 0.
If \(x \wedge 4_{10}=4\) then the bit for \(2^2\) is 1.
The number \(12_{10} =8_{10}+4_{10}\). It does have a 1 in the bit for \(2^2\).
\( \begin{align} & 0000 1100 & 12 \\ \wedge & 0000 0100 & \wedge 4 \\ & = & = \\ & 0000 0100 & 4 \\ \end{align} \)
The number \(10_{10} = 8_{10} + 2_{10}\). It does not have a 1 in the bit for \(2^2\).
\( \begin{align} & 0000 1010 & 10 \\ \wedge & 0000 0100 & \wedge 4 \\ & = & = \\ & 0000 0000 & 0 \\ \end{align} \)
Disjunction¶
The Disjunction Operator is used when either of two things can be true. In English, this would be the word or. The logic symbol for disjunction is \(\vee\).
If someone told you “it is raining or cold” that doesn’t tell you it is raining. You know at least one of the two things is True. It may be the case that both are True. This is conveyed in the following Truth Table.
\(x\) |
\(y\) |
\(x \vee y\) |
|---|---|---|
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
The disjunction operator can be used to find which bits appear in either of two numbers.
\( \begin{align} & 0001 1100 & 28 \\ \vee & 0000 1010 & \vee 10 \\ & = & = \\ & 0001 1110 & 30 \\ \end{align} \)
Exclusive Disjunction¶
The Exclusive Disjunction is similar to the disjunction, but it is either but not both. We would write it as xor and uses the symbol \(\oplus\). The Truth Table is shown below.
\(x\) |
\(y\) |
\(x \oplus y\) |
|---|---|---|
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
We can use it to find the bits that are different between two numbers. If \(a \oplus b=0\) then the numbers are the same. If it gives us any other number, it tells us what bits are different.
\( \begin{align} & 0110 0000 & 96 \\ \oplus & 0010 0000 & \oplus 32 \\ & = & = \\ & 0100 0000 & 64 \\ \end{align} \)
The xor operator is very useful for detecting changes. For example, if you had two copies of a file and ran an xor on the bits, it would tell you where the changes are.