Neon-komputadór

Logical Sets and Procedures

The basis behind logical sets and digital logic are the rules known alternatively as Boolean algebra (after the nineteenth century English mathematician George Boole), discrete mathematics or propositional and predicate calculus. Regardless of the descriptive term used, learning about logical sets and procedures is helpful not just in programming, but anywhere where careful planning, distinction, organization and logic is required.

Logical sets or, in programming terms data types, consist of elements that share relevant common features. For example, the set of integers (1, 2, 3 ...), the set of characters (a, b, c ...), a set of real numbers (1.2456, 2343.452, -3327 etc). Elements may belong in multiple sets if they satisfy the conditions for membership and two sets are considered equal if they have the same elements. When we refer to the set of elements that are in Set A OR Set B, we describe it as the Union of A and B, or disjunction. When we refer to the set of elements that are in Set A AND Set B, we describe it as the Intersection of A and B, or conjunction. When we refer to the inverse of a set, we describe it as the negation of the set.

An important component in programming in the expression of an array. This is when a variable is declared of a particular data type but has a number of consecutive elements, for example the C declaration "int NumberList[10]", which is a declaration of an integer variable called NumberList that contains the numbers 0 through to 9 (ten numbers, must start at zero). To make matters more complex - and increasingly like a spreadsheet - arrays can have multiple dimensions, e.g., int Numberlist[10][10], which would include the variable elements 0-0, 0-1, 0-2, 0-3... 9-9.

Apart from elements and sets, logic has a language, rules of inference, semantic and syntax rules. Semantic rules are the associations of a language with elements of a set. Syntax refers to the proper use of signs in their recognized order. Rules of inference are used to produce formula. Propositions are statements about elements (e.g., the proposition "the goat is running" - "goat" is the element "is running" is the statement). An interpretation is the association of a proposition with an element. A denotation is as an associated proposition from a given interpretation. Predicates are further elaborations that make statements about propositions, that is, they raise a proposition to the level of an element.

The basic rule is that every proposition has a state which can be described as true or false (T or F), which is logically represented in binary as 1 or 0, or in electronics as 'high' or 'low' voltage. The relationship between operation and variables is described as AND, OR, XOR, and NOT. The AND operator returns true if all propositions are true, an OR operator returns true when any proposition is true, an XOR (exclusive OR) returns true if any proposition is true but false if all propositions are true, and a NOT operator inverts a result from true to false, or from false to true. Finally, it is also possible to have NAND and NOR operators, which operate like AND/OR operators but reverse the result. The following truth table summarizes the above discussion.

In addition to the truth table, there are certain basic Boolean laws, each of which has two expressions known as duality. This is achieved by converting all AND statements to OR statements, all OR statements to AND statements, all 1's to 0's and all 0's to 1's. These laws are known, in order, as the Identity Laws, Commutative Laws, Associative Laws, Distributative Laws, Redundance Laws and De Morgan's Theorem. In this example, we use the standard C programming language abbreviations for AND (&&), OR (||) and NOT (!)

Identity Laws
(i) A && A = A
(ii) A || A = A

Commutative Laws
(i) A && B = B && A
(ii) A || B = B || A

Associative Laws
(i) (A && B) && C = A && (B && C)
(iii) (A || B) || C = A || (B || C)

Distributative Laws
(i) A || (B && C) = A || B && A || C
(ii) A && (B || C) = A && B || A && C

Redundance Laws
(i) A && A || B = A
(ii) A || (A && B) = A

De Morgan's Laws
(i) !(A && B) = !A || ! B
(ii) !(A || B) = !A && !B

These truth tables and laws are implemented in computers through the electronic gates. The inputs are driven by voltages with nominal charges (e.g., 0V and 5V representing 0 and 1 or F and T) and the output is also represented by a nominal charge. NAND and NOR gates are called universal functions because with either one the AND, OR and NOT functions can be generated.

In addition to Boolean operations, there are also relational operators and arithmetic operators. Relational, or comparison, operators and their symbols in the C programming language include less than (<), greater than (>), equal to (==), less than or equal to (<=), greater than or equal to (>=) and not equal to (!=). Note that in the C programming language == is used for comparison and = is used for assignment. Finally, there are the arithmetic operators, addition (+), subtraction (-), division (/) and multiplication (*) and modulo reduction (%), the remainder from an integer division.

Regrettably, there is no universally accepted order of precedence in determining equations of mixed operators, although there is a general trend towards arithmetic, relational and finally logical operators. In the C programming language, multiplication, division, modulus are determined prior to addition and subtraction, then relational operators and finally Boolean operators NOT, AND and OR. In the Pascal programming language however, the Boolean operators are higher on the order of operations than relational operators. The logical AND has the same degree of precedence as multiplication and division and OR has the same precedence as addition and subtraction. In Visual Basic the arithmetic multiplication and division operators are determined first, followed by modulo, then addition and subtraction, then the comparison operators and finally logical NOT, AND, OR and XOR. In all cases, parentheses can override standard precedence and force part of an equation to be evaluated prior to others. Where operators have the same precedence evaluate from left to right.

Thus in the following expression:

x = (a + b) * c > d – e / f && g % h <= i

The sum of a and b would be calculated first, and then multiplied by c. This would be compared as greater than d minus the division of e and f. The truth statement of this result would be compared with the truth statement of whether the modulus of g divided by h is less than or equal to the variable i. If both these statements are true then x will also be true. Otherwise x will be false.

In addition to the precedence of operators within statements, control statements in a program alter the execution of statements themselves. Whilst all programs have a predefined order and will attempt to fulfill statements in that order, control statements can redirect the order in which statements are conducted. The concepts behind control statements are similar across all programming languages with minor changes in syntax being the main feature.

The IF-ELSE statement is the basic control statement. If an initial statement is true (IF) then the instructions are followed. If the statement is not true, then the alternative instructions are followed. IF-ELSE statements can have multiple nesting, so that alternatives to the alternative can be composed (IF – ELSE – IF – ELSE – IF – ELSE). A trivial example is given here from the C programming language:

If (result >= 85) printf ("Passed. High Distinction grade\n");
Else if (result >= 70) printf ("Passed. Distinction grade\n");
Else if (result >=60) printf ("Passed. Credit grade\n");
Else if (result >=50) printf ("Passed. Pass grade\n");
Else printf ("Failed.\n");

A common alternative to the ELSE-IF-ELSE-IF multiple alternative statement is the switch statement (in C), or Select Case (in Visual Basic) which is best used for a small number of definite, rather than relational, alternatives. An example is given below:

Switch ( smallnumber)
{
	case 0: print ("zero/n"); break;
	Case 1 : print ("ida/n"); break;
	Case 2 : print ("rua/n"); break;
	Case 3 : print ("tolu/n"); break;
	Default 4 : print ("barak! /n"); break;
}

Many control statements take the form of loops. Computers are particularly good at performing repetitive tasks and as such loops are a very efficient means of controlling program flow. In the C programming language there are three types of loops. The "while" until and associated test returns false. The "do ... while" loop is similar, except the test return is at the end of the statement, ensuring that the loop runs at least once. The "for" loop ensures that a certain action is performed as long as a counter value is set, incremented each time the block is executed and terminated when the upper limit is reached. The three examples are shown below:

while ( i <100 ) <>;
do { <>  ; } while { i < 100 } ;
for { i = 1; i <= 100; i++ }  <> ;

Understanding elements, sets, propositional and predicate logic, truth tables and control statements is a necessary and sufficient condition to understanding programming.