Table of Contents

Previous: 3. Basic Computer Operations

Next: 5. Problem Solving with Computers

4  Logic Operations

ALU of a computer CPU is responsible arithmetic operations and logical operations. Logical operators are connectors such as AND, OR, and NOT that connect statements. In this chapter, we will explain basic logical operators and truth table. Both propositions and predicates are discussed. Then, we explain how to express predicates in C programming language as logical expressions. In addition to logical expressions in C, we also introduce bitwise logical operations. Finally, language constructs of conditional statement in C, including if-then-else statements and switch-case are included in the chapter.

4.1  Propositions and Predicates

In the mathematical theory of a logical system, a proposition is in one of three forms: a primitive statement, a unary connector, and a number of binary connectors. A primitive statement is a statement describing a fact and is denoted by an English letter. For example, the followings are primitive logical statements:

However, a question, an exclamation, or a command is not a logical primitive statement. For example the following sentences are not primitive statements:

The unary connector is the negation operator that transforms a statement p into Øp (NOT p). The binary connectors are conjunction, pÙq (p AND q), disjunction, pÚq (p OR q), exclusive or, pÅq (p XOR q),  implication, , pÞq (p implies q) and equivalence, pÛq (p if and only if q).

A primitive statement has a truth value of true or false, that is denoted as T or F, or as 1 or 0, respectively. The truth and falsity of the negation and other operations is given as the following truth tables:

Among these logical operators, negation (Ø) and disjunction (Ú) are sufficient to construct the other operators.

The above equivalent formulas can be proved by constructing the truth table of the expressions. We show verification of pÅq @ Ø(ØpÚq)ÚØ(pÚØq) and leave the other equivalent formulas as homework assignment.

To express an English statement into logical expressions, a statement is split into a number of primitive statements and is denoted as an English letter. The followings are examples of primitive statements:

We show examples of translating English sentences to logical expression as below:

A proposition can be generalized in two ways to construct a predicate:

1. In a proposition, a primitive statement is replaced by an expression, e.g., x<y and x=sqrt(y), where sqrt() is the square root  function.
2. The quantifier " meaning "for all" and $ meaning "there exists".

Examples of predicates are:

4.2 Relations and Logical Expressions in C

Predicates in C programming language are called logical expressions or conditions. The primitive statements of conditions are either relations or Boolean functions. A relation is a comparison of two arithmetic expressions of the following syntax:

In C programming language, conditions are connected by operators negation (!), conjunction (&&), and disjunction (||).

The truth values are represented as a number of any type. Value 0 is used to represent false and any value other than 0 is used to represent true. Often, value 1 is returned when a relation is evaluated to true. Program truthValues.c shows examples of conditions

Line 4 is the condition "one equals to one" that returns 1 for truth value true. Line 5 is the condition "one does not equal to one" that returns 0 for truth value false. Lines 6 to 8 illustrate conditions with negation, conjunction, and disjunction. 

4.3  Bitwise Operations in C

Another type of logical expressions in C is bitwise operations. A bitwise operator is a binary operator applying to corresponding bits of two expressions of the same length or applying to an expression and an integer. There are six bitwise operations defined in C programming language:

The expressions in bitwise operations must be of fixed length. For example, 8-bit long for the characters, 16-bit long for short integers, and 32-bit long for integers. In addition, for bitwise AND, bitwise OR, and bitwise XOR, the two expressions must have identical bit length. For right shift and left shift operations, the shift value is an integer value.

Bitwise NOT reverses the value of each individual bit of its operand, i.e., it performs one's complement of the operand. For example, in program bitwiseNot.c, variable x is set to 8-bit hexadecimal value 46₁₆=01000110₂, and then its negation is assigned to variable y in Line 6. We obtain the value of y to be 46₁₆=0100 0110₂=1011 1001₂=B9₁₆.

Bitwise AND, OR, and XOR perform AND, OR, and XOR operations on individual bits of the two operands. For example, program bitwiseAndOrXor.c shows the computational effect of bitwise AND, OR, and XOR operations. Variable x is initialized to hexadecimal value 46₁₆. In Line 6, the value of variable y is set to xÙ0 that sets all bits of x to 0's. In Line 9, the value of variable y is set to xÚ255 that sets all bits of x to 1's. In line 12, the value of variable y is set to xÅ255 that reverses all bits of x as bitwise NOT does.

A note about printf() in Lines 7, 10, and 14, the format specifier %02X will print two hexadecimal digits with leading zeros padded with 0. The output of program bitwiseAndOrXor.c is:

Bitwise shift is to shift the bits of its first operand to the right-hand-side or the left-hand-side a number of positions specified by its second operand. Program bitwiseShift.c illustrates the computation effect of bitwise shift operations. Variable x is initialized to hexadecimal value 46₁₆. In Line 6, the value of variable y is set to x after shifting to the right-hand-side four positions and the four bits on the left-hand-side are filled in with 0's. In Line 9, the value of variable y is set to x after shifting to the left-hand-side four positions and the four bits on the right-hand-side are filled in with 0's.

The output of bitwiseShift.c shows that after right shift 46₁₆ becomes 04₁₆ and after left shift 46₁₆ becomes 60₁₆.

Bitwise logical operations are often used in programs to efficiently perform certain arithmetic operations. For example, left shift an integer one position is equivalent to the product of multiplying this integer by 2; right shift an integer one position is equivalent to the quotient of dividing this integer by 2. Conjunction operation of an integer with 1 is equivalent to the remainder of dividing this integer by 2. The general rules are:

1. Left shift an integer k positions is equivalent to the product of multiplying this integer by 2^k.

2. Right shift an integer k positions is equivalent to the quotient of dividing this integer by 2^k.

3. Conjunction operation of an integer with 2^k-1 is equivalent to the remainder of dividing this integer by 2^k.

Program bitwiseArithmetic.c shows integer 3455 these operations with k=6, i.e., 2^k=64. Line 6 show sthat x<<6 and x*64 have the same computational result. Line 8 shows that x>>6 and x/64 have the same computational result. Line 10 show that x&63 and x%64 have the same computational result

The output of program bitwiseArithmetic.c is shown as below:

For two positive integers, if the non-zero bits of binary representation of these two integers do not overlap, their sum can be implemented as a bitwise OR operation of the two integers. For example, bitwiseSum.c adds 50432 and 125 using bitwise OR. Variable x is set to 50432₁₀=C500₁₆ and variable y is set to 125₁₀=7D₁₆. Since the non-zero bits of x and y do not overlap, bitwise OR of the two numbers is equivalent to an addition.

We conclude precedence and precedence rules and associativity rules of all operators in C programming language, including, parentheses, arithmetic operators, logical operators, bitwise operators, assignments, and access operators. Access operators are [], ->, and . that will be explained in details in Section 5.2, Section 6.3, and Section 7.3. Operator question-colon (?:) is a conditional expression that is explained in the Section 4.4. Common (, is a punctuation used in variable declarations and for loops in Section 5.2. The precedence rules are in the order that operators in the first row have the highest precedence and operators in the last row have the lowest precedence. Note that +, -, and * in the second row are unary operators and  +, -, and * in the third and fourth rows are binary operators.

4.4  Conditional Statements in C

C programming language supports two kinds of conditional statements: if-then-else statements and switch-case statements.

if-then-else statements

 The syntax of  if-then-else statements have two forms:

A statement in the then clause and else clause can be a block statement, i.e., a sequence of statements enclosed by a pair of curly brackets { }. The first syntactic form is also called an if-then statement. That is, the else clause in this case is the null statement. The semantics of if-then statements and if-then-else statement is:

1. if-then statement: if condition is evaluated to true (i.e., to a value other than 0), then statement in the then clause is executed; otherwise the if-then statement does nothing.

2. if-then-else statement: if condition is evaluated to true (i.e., to a value other than 0), then statement1 in the then clause is executed; otherwise, statement2 in the else clause is executed.

When execution of either the then clause or the else clause is completed, program execution continues to the next statement following the conditional statement.

Computational effect of a program can be specified using the operational semantics. We use a semi-formal notation to specify programs. In program specification (in orange color), we use an italicized  name to denote a mathematical function and the left arrow (¬) to represent assignment of a value to a variable. For example, assigning the absolution value of variable x to itself is expressed as:

where abs() is the mathematical function (in purple color) of absolute value. Function abs() can be defined as below:

If we substitute the definition of abs(x)in the above program specification, it is rewritten to:

The new specification can be implemented as an if-then-else statement as below:

Since the assignment statement x = x in the else clause does not have any computational effect, it can be omitted and the program is simplified to the if-then statement as below:

The above program shows a conditional statement without else clause. However, if we change the program specification to:

The program must be written with if-then-else because assignment y = x cannot be omitted in this case.

Note that the condition must be enclosed by a pair of parentheses. In this example, the then and else clauses have only one statement, they are not enclosed by a pair of curly brackets. We will consider another example computing maximum value of two variables. Let max() be a function that returns the maximum value of two variables and be defined as below:

Suppose the program specification is to assign the maximum value of x and y to variable ans:

The program that implements this specification is written as:

Ternary statements

C programming language provides a ternary operation (an operation with three operands) ?: to write a conditional statement in a brief way. Its syntax is:

The semantics of the ternary expression is that if condition is evaluated to true (values other than 0) then expression1 is executed; otherwise, expression2  is executed. With this ternary operation, we can rewrite the program computing maximum value to:

Nested conditional statements

Conditional statements can be enclosed in another conditional statements, i.e., they can be written as a nested conditional statements. For example, a possible form is to enclose two inner if-then-else statements in the then clause and the else clause of the outer if-then-else statement:

When writing a compound statement, it is important to place indentation in the program text so it is easier to read. Let consider function max3() which returns the maximum value of three variables x, y, and z. Function max3() can be defined as below:

If we expand the definition of function max3() in program specification ans¬max3() is written to the following formula:

The program specification can be implemented as the following C program:

Another form of if-then-else statements which is frequently used in C programs is called else-if construct:

If we rewrite the else-if construct with proper indentation, the exact syntax is:

We modify function max3() to the following definition:

and the program specification to:

The program is then implemented using the else-if construct:

switch-case statements

In C programming language, switch-case statements are used to implement a special form of the else-if construct when all of the conditions are equality tests of a given variable on a finite cases (usually a small number of cases) of discrete values. The syntax of switch-case statements is:

The number of case lines can be as many as needed and the default line is optional. The semantics of a switch-case statement is the value of variable is compared with values from the first to the last case in the specified order. Once one value of the case clause is matched, all statements following the case clause are executed unless a break statement is encountered. A switch-case statement is complete if the execution reaches a break statement or the last statement.

For example, program print_numbers_no_break.c uses a switch-case statement to print numbers of one, two, three, and four. Lines 9 to 15 make up a switch-case statement. Since the value of x is set to 2, statements starting from case 2: are executed. Hence, two, three, four, and others are output because there is not break statement after any case..

If only one number is going to be output, a break statement must be added after every printf() as in program print_number_with_break.c below: When x is set to 2, only two is output.

In fact, the switch-case statement from Line 9 to 27 can be written with the else-if construct as below:

In a switch-case statement, multiple values can be placed in consecutive case clauses without specific order. For example, if x is set to 12, the following program segment will output value two:

Table of Contents

Previous: 3. Basic Computer Operations

Next: 5. Problem Solving with Computers