Bitwise manipulation is when we perform a logical operation against each individual bit of a binary number. The logical connectives a.k.a. the bitwise operatorsAND, OR, and XOR can be used as masks that can affect the specific bits.
What is the point of Bitwise manipulation?
Human readability is certainly not the point, but speed and efficiency are. Bitwise operations are primitive actions that can be executed directly on the CPU meaning that they stake up less temporary/persistent storage and require less pre-processing overhead to compute. You can think of them like shortcuts.
AND
The AND logical operation can be used to turn off certain bits of a binary number, because:
1 AND 0 is 0
0 AND 0 is 0
Consider you have an input of 1101 1011 and a bitwise mask of 1111 1000. Examine the function table below:
Input
1
1
0
1
1
0
1
1
Mask
1
1
1
1
1
0
0
0
Result
1
1
0
1
1
0
0
0
Bitwise AND Mask Results
Notice that the mask only applies to the last three digits. The third to last digit is unchanged only because it was already 0.
OR
The AND logical operation can be used to turn off certain bits of a binary number, because:
1 AND 0 is 0
0 AND 0 is 0
Consider you have an input of 1001 1011 and a bitwise mask of 1110 0000. Examine the function table below:
Input
1
0
0
1
1
0
1
1
Mask
1
1
1
0
0
0
0
0
Result
1
1
1
1
1
0
1
1
Bitwise OR Mask Results
Notice that only the first three digits changed (except the first digit which was already a 1). The OR switch changed all the 0 bits to 1’s.
XOR
The XOR (Exlusive OR) logical function can be used to reverse certain bits of a binary number, because:
0 XOR 1 is 1
1 XOR 1 is 0
Consider you have an input of 1011 1001 and a bitwise mask of 0000 1111. Examine the function table below:
Input
1
0
1
1
1
0
0
1
Mask
0
0
0
0
1
1
1
1
Result
1
0
1
1
0
1
1
0
Bitwise XOR Mask Results
Notice that all four of the bits aligned with the mask are now the opposite of what they once were without exceptions. The bits have essentially been “flipped”.
Logical Shift Left
Performing a logical shift one bit to the left on a binary number means:
Moving all the bits of the number one place to the left
Discarding the most significant bit
Putting a 0 into the empty place on the right
Interestingly this is equivalent to multiply our binary number by 2. Notice that performing a logical shift three bits to the left on a binary number is the same as multiplying the number by 23 = 8.
Example:
If we start with the decimal number 14, three logical shifts to the left of its binary form results in the decimal number 112:
128
64
32
16
8
4
2
1
1410
0
0
0
0
1
1
1
0
2810
0
0
0
1
1
1
0
0
5610
0
0
1
1
1
0
0
0
11210
0
1
1
1
0
0
0
0
Logical Shift Left Results
Logical Shift Right
Performing a logical shift one bit to the right on a binary number means:
Moving all the bits of the number one place to the right
Discarding the least significant bit
Putting a 0 into the empty place on the left
As you might have guessed, this is equivalent to dividing our number by 2. Notice that performing a logical shift two bits to the right on a binary number is the same as dividing the number by 22 = 4.
Example:
If we start with the decimal number 112, two logical shifts to the right of its binary form results in the decimal number 28:
As discussed in the previous post, compound predicates are built from other predicates and propositions using logical connectives (¬, ∧, ∨, ⇒, ↔). The truth value of the compound predicate depends on the truth values of its components.
Truth tables can be used to define the meaning of logical operators and to investigate compound expressions. By investigating the truth values of compound expressions, you can establish new logical concepts. This is especially useful when it comes to rewrite rules which we will discuss a little bit later on.
Components of a Truth Table
Truth tables consists of a header and a body. When defining the meaning of a logical connective, the leftmost column lists the variable you are evaluating and the rightmost column lists the connective.
Example:
This truth table defines the conjunction connective. By looking at this truth table we can see that if P and Q both have a truth value of TRUE then the expression P ∧ Q also has a truth value of TRUE, but any other combination of P and Q means that the truth value of P ∧ Q is FALSE.
When investigating the truth value for a compound expression, the left most column headers list the variables and the rightmost header lists the compound expression.
The Body of a truth table always contains one row for every possible combination of the variables involved.
Note: The variables in a truth table are propositional variables. This allows you to work with the most simplified form of possible combinations and outcomes.
Here are truth tables for all of the logical connectives:
Note: Regarding the truth table for the Disjunction connective, this table shows the truth values for what is referred to as the inclusive or. This means that the proposition evaluates to TRUE if P and Q are both TRUE. You may encounter times when the exclusive or is specified (sometimes called XOR or EOR). This simply means that one of the criterion must be true but not both.
Equivalence and Implication
These two connectives may not be as immediately apparent or intuitive and the others so I think they warrant a bit more discussion.
Equivalence
This one isn’t too bad. It’s basically the same as the = operator (Note to self: check thesaurus for “same as”). It evaluates to TRUE if and only if the two involved propositional variables evaluate to the same truth value (either both TRUE or both FALSE).
Implication
This one is a bit more confusing because of the way “implies” is used informally versus its mathematical logical meaning. To better explain what the Implication connective means, I think it would be easier to start with what it doesn’t mean:
It doesn’t mean “suggests”.
It doesn’t mean “causes”.
The following sentence is completely logical under the mathematical definition of Implication:
“The sky is blue implies January is a month”
This does not mean “Since the sky is blue January is a month” or “January is a month because the sky is blue”
Note: Always remember that the ONLY time that an implies statement is FALSE is if the Antecedent (P) is TRUE but the Consequent (Q) is FALSE.
So let’s take a closer look at the Implication truth table again:
To better understand this, it might be better to evaluate the conditions in stages. We will start by examining the truth values for P. If the truth value for P is FALSE, we aren’t even going to check what the truth value for Q is because we already know that the expression is TRUE. If P is TRUE then we have to go on to evaluate if Q is TRUE, if it is the expression is TRUE, but if it isn’t then the expression is FALSE.
I like to think of this as “Innocent until proven guilty” or “True until proven false”.
Example:
Proposition: If your pet is a dog, then your pet is a male.
Suppose my pet is a dog… ok now I can check the gender… it turns out my dog is male… the statement must be true
Suppose my pet is a dog… ok now I can check the gender… it turns out my dog is female… I’ve proven the statement false
Suppose my pet is a cat… ok I could check the gender but it doesn’t really matter because the statement only applies to dogs so I wouldn’t be proving anything even if my cat was female… without evidence to prove that the statement wrong, I must assume that it is true.
Suppose my pet is a bird… same logic applies as if my pet was a cat… without evidence to prove that the statement wrong, I must assume that it is true.
Implication is probably the least intuitive of all the connectives and some of that probably comes from how we think about “implications” outside of mathematics. Let’s consider for a moment why this is.
Consider the following scenario:
I have a bag of 10 marbles. One is blue and nine are yellow.
I ask you to pick one marble out of the bag without looking and offer the following implication:
“If you pick a blue marble, the next will be yellow”
So you pick a marble:
Suppose I pick a blue marble… ok now I can pick another marble… it turns out it is yellow… The statement must be true. (T ⇒ T) = T
Suppose I pick a blue marble… ok now I can pick another marble… it turns out it is blue… The statement must be false. (T ⇒ F) = F
Those two seem pretty intuitive right? So let’s look at the tricky ones:
Suppose I pick a yellow marble… ok now I can pick another marble… it turns out it is also a yellow marble… ok so I don’t have enough information to know if the original statement is true or not. In real life if a friend asked me to do this and draw a conclusion I would say that there isn’t enough information to determine if it is TRUE or FALSE because the first marble I drew wasn’t blue so can’t actually test the hypothesis. Ahhh but let’s remember our definition of a proposition: a declarative sentence that when evaluated is either TRUE or FALSE, but not both.
By definition, our implication proposition MUST evaluate to either TRUE or FALSE, it cannot be both or neither. So now the question really becomes given this scenario, do we assume FALSE or do we assume TRUE? When it comes to implication, we always assume TRUE. This is why I use the phrase “innocent until proven guilty”. Just like in a court of law, the defendant is innocent until they can be proven guilty. Likewise when it comes to an implication, we assume that the overall statement (P ⇒ Q) is TRUE unless we can definitively prove that it is FALSE.
Predicate Strength
You can think about Implication as “ordering” the predicates that make up its operands. This order is referred to as the strength of the predicate. The “strongest” predicate is the one that implies the other. Consider P ⇒ Q, in this situation P is the stronger predicate and Q is the weaker.
Example:
The variable x is defined with a type of integer.
Consider the predicate: x > 5 ⇒ x > 0
To state that x is greater than 5 implies that x is greater than 0. This implication is TRUE regardless of the value of x, and the predicate x > 5 is the stronger predicate while x > 0 is the weaker one.
The only time that both predicates are of equal strength is when P ⇒ Q and Q ⇒ P. When the predicates are of equal strength they are equivalent: ↔
In my last blog post we discussed propositions and predicates. To summarize, a proposition is a declarative sentence that can be proven TRUE or FALSE. Similarly, a predicate takes the form of a declarative sentence but contains at least one embedded variable (parameter) and cannot be evaluated as TRUE or FALSE unless input for said parameters is provided.
A logical connective is an operator that is used to form more complex predicates by combining predicates together. The most well-known of these logical connectives are conjunction (logical AND), disjunction (logical OR), and negation (logical NOT). Probably less commonly known are implication and equivalence.
Symbol
Meaning
Terminology
¬
NOT
Negation
∧
AND
Conjunction
∨
OR
Disjunction
⇒
IMPLIES
Implication (if…then…)
↔
IS EQUIVALENT TO
Equivalence (if and only if)
Note: If you take a course in mathematical logic, you will have a formal discussion of proofs. You start with a formal language, which describes the symbols you're allowed to use and how to combine them, and the rules of inference, which describe the valid ways of making steps in a proof. This is important because natural languages like English are informal and imprecise, as a consequence, the meaning of words sometimes depends on context; this kind of ambiguity is why formal language and symbols exist. However, throughout my writings I will use a mix of formal and informal language and syntax for the sake of learning.
Simple and Compound Predicates
If a logical connective is regarded as a logical operator, we can say that it takes one or more predicates as its operand and returns another predicate.
Example:
Consider the logical operator ∧
Consider the predicates x = 11 and y = 15 as the operands
The compound predicate would be (x = 11) ∧ (y = 15)
In informal language this reads as: I propose that x equals 11 and y equals 15.
With an AND operator, the compound predicate only evaluates to TRUE if both the simple predicates also individually evaluate to TRUE.
Note: The simple predicates that make up the operands of the logical operator are also sometimes referred to as components of the compound predicate. Isn’t natural language fun?
Propositional Variables
Let’s consider another kind of compound predicate. Consider the following:
P ∧ Q ⇒ P ⇒ Q
This looks a bit different than the predicates we’ve looked at so far. That’s because this example uses the propositional variables P and Q. If you consider that a variable is a “holder” for a value, then you can think of a propositional variable as a “holder” for a proposition.
An assertion that contains at least one propositional variable is referred to as a propositional form. If you substitute all propositional variables (of the given propositional form) with a proposition the propositional form is transformed into a proposition in and of itself.
Phew, even reading that back to myself that is a tricky sentence. You may think at this point that a propositional form seems very similar to a predicate. So what’s the difference? Well, let’s recall that a predicate takes the form of a declarative sentence (just like a proposition) but has embedded variables. A predicate cannot be evaluated to TRUE or FALSE until values are substituted for these variables. Meanwhile a propositional form uses propositional variables which themselves represent a truth value (TRUE or FALSE).
This means that we can treat propositional variables as arbitrary predicates with truth values without having to fully express the details of the underlying proposition
Example:
Let P represent 3 + 5 = 8
Let Q represent 1 + 1 = 2
Consider the propositional form P ∧ Q
If we replace the proposition variables (P,Q) the propositional form is transformed to the following proposition:
3 + 5 = 8 ∧ 1 +1 = 2
Which evaluates to TRUE.
Similarly, we can use letters like P,Q,R, ect. In expressions like this:
P(x), Q(y), R(s,t)
These represent arbitrary predicates with parameters.
Example:
Let P represent 3 + 2x = 9
What is the value of P(x) given that x = 3
You would evaluate this by substituting P(3) which means to pass 3 as the value for parameter x to the predicate 3 + 2x = 9 which forms the proposition 3 + (2*3) = 9 which evaluates to TRUE and thus P(x) evaluates to TRUE
If we pass any other value for x, the resulting proposition evaluates to FALSE.
Logical Operator Precedence and Parentheses
I’m sure everyone remembers PEMDAS (Parentheses, Exponents, Multiplication, Division, Addition, Subtraction), the order of operations from your middle school math class. Just like algebraic expressions follow the order of operations, logical expressions follow an order of precedence. And just like the algebraic expressions, you can override this order using parentheses.
Note: Even though formal rules of the syntax do not always strictly require parentheses, it is a good idea to add them even if redundant to avoid any confusion or misinterpretation. It increases readability and is just as valid.
Here are the Logical Connective Precedence Rules:
Rank
Connective
1
¬
2
∧, ∨
3
⇒, ↔
Note that some operators have the same rank.
Example:
Given P ∧ Q ⇒ R the precedence rules state that this is equivalent to (P ∧ Q) ⇒ R rather than P ∧ (Q ⇒ R)
For operations with equal rank, formal rules state that you should read operations from right to left. This is called the associative rule.
Example:
Given P ⇒ Q ⇒ R, the associative rule states that this should be equivalent to P ⇒ (Q ⇒ R) rather than (P ⇒ Q) ⇒ R
This is an important rule to keep in mind, but for the sake of clarity I will most often use parentheses in my posts.
Regardless of your background, you probably have at least some idea about what the terms values and variables mean. However, when talking about them in a technical context it is important to be precise as they are often used interchangeably when they ought not be.
A value is an individual constant which is well-defined. Being a constant means that it is fixed and well-defined means that it is unambiguous. For example, the integer 42 is a value (and the answer to the ultimate question of life, the universe, and everything). You cannot update or change a value because if you did it would no longer be the same value. A value can be represented in many different ways (through encoding) but it always represents the same thing.
A variable is a holder or a container for a value. As such the value of a variable is not fixed. Or put another way, which value the variable is holding can change. Variables have a name, which can be used to reference them without the requirement of knowing what value (or set of values) it contains. Given x = 1 + 3 as an example, x is a variable and it holds the value 4 which is the result of the operation (1+3).
A variable’s type is the entire set or range of values that a variable is allowed to hold.
Propositions and Predicates
In logic, the primary components we will deal with are propositions and predicates.
A proposition (also sometimes referred to as a statement) is a declarative sentence that when evaluated is either TRUE or FALSE, but not both.
Example:
In English, the sentence “The sky is beautiful” is NOT a proposition because while it does make an assertion, it is a subjective one since it is a matter of opinion. Some would evaluate the this assertion as TRUE while others would deem it FALSE. Thus it is ambiguous and thus not a proposition.
The sentence “Is it raining?” is not a proposition because it is a question rather than an assertion or a declaration.
The sentence “Right now, it is 5:00PM Pacific Time in Seattle, Washington” is a proposition because it makes a well-defined assertion which either is or is not.
Some sentences that are mathematical in nature often are not statements because we may not know precisely what a variable represents.
Example:
Consider the equation (2x)+5 = 15. This is NOT a proposition because we do not know what the variable represents. Remember that in order for something to be a proposition it must be either true or false but not both.
Consider the equation 4 + 1 = 5. This is a proposition because without any additional information we can evaluate this as either TRUE or FALSE. In this case it is TRUE.
Note: It is a common mistake to only consider TRUE sentences as valid propositions but propositions can also be FALSE; the important consideration when defining a proposition is that it cannot be both.
A predicate is something which has the form of a declarative sentence but which includes at least one embedded variable whose value is unknown and which you cannot determine to be TRUE or FALSE without knowing the value of said variable(s). We will refer to these embedded variables as the parameters of the predicate.
Example:
Using the same example as from above, the equation (2x)+5 = 15 is a predicate because without additional information, we don’t know what the value of x is and so we cannot determine if it is TRUE or not.
A predicate with n parameters is referred to as an n-place predicate. If you substitute one of the parameters in an n-place predicate with a value, it becomes an (n-1)-place predicate.
Example:
Consider the equation x + y = 5
This is a 2-place predicate; it has two parameters x and y.
Now, consider the same equation with the variable x substituted with the value 4:
4+ y = 5
This is a 1-place predicate; it has one parameter y.
So you may be wondering, if n = 1, wouldn’t an (n-1)-place predicate be a 0-place predicate? The answer is yes. Given the same equation from the previous example, if we replace the last remaining parameter y with a literal value such as 1, the equation becomes:
4 + 1 = 5
You may have noticed that this is the exact same equation as the example given for a proposition. That’s because a 0-place predicate is a proposition. In this way, a proposition can be thought of as a special case of predicates. You can transform a predicate into a proposition by replacing all of its parameters with values. This process is called instantiating the predicate with the given values.
The parameters of a predicate are also referred to as the free variables of a predicate. There is another way to convert predicates into propositions; binding them to a quantifier. Free variables then turn into what are referred to as bound variables. This process is called Quantification (over a set) and it is an important concept in logic and an especially important when it comes to data management.
Bonus:
Consider the following two sentences:
This statement is false.
I’m lying.
These are both self-referential sentences; meaning that they tell us something about themselves. Sentences like these have the potential to cause logical contradictions. The second sentence is called the Liar’s paradox. If you begin an evaluation of the sentence with the assumption that it is TRUE, you will reach the conclusion that it is in fact FALSE. However, if you begin an evaluation of the sentence with the assumption that it is FALSE, you will come to the conclusion that it is in fact TRUE. Because of this you are unable to determine if the sentence is TRUE or FALSE, despite the fact that there are no variables or parameters. The solution is to disregard the statement as a valid proposition.
Similarly, you must discard “ill-formed” expressions as predicates.
Consider the following:
2 is an element of 7
This is an ill-formed predicate because 7 is not a set, it is a value. The expression just doesn’t make any sense and so it should be disregarded. This assumes at least a familiarity with the concept of sets, but I’ll be covering basic set theory in a future post.
We use cookies on our website to give you the most relevant experience by remembering your preferences and repeat visits. By clicking “Accept”, you consent to the use of ALL the cookies. You can review our cookie policy here.
This website uses cookies to improve your experience while you navigate through the website. Out of these, the cookies that are categorized as necessary are stored on your browser as they are essential for the working of basic functionalities of the website. We also use third-party cookies that help us analyze and understand how you use this website. These cookies will be stored in your browser only with your consent. You also have the option to opt-out of these cookies. But opting out of some of these cookies may affect your browsing experience.
Necessary cookies are absolutely essential for the website to function properly. This category only includes cookies that ensures basic functionalities and security features of the website. These cookies do not store any personal information.
Any cookies that may not be particularly necessary for the website to function and is used specifically to collect user personal data via analytics, ads, other embedded contents are termed as non-necessary cookies. It is mandatory to procure user consent prior to running these cookies on your website.
