Chapter Ii

Chapter-II MATHEMATICAL LOGIC Contents: 2.1

Basic concepts of Mathematical logic

2.2

Propositions or Statements

2.3

Combining Propositions

2.4

Truth Table

2.5

Conditional and Biconditional Propositions

2.6

Reverse, Converse, Inverse, and Contrapositive of an implication

2.7

Tautology

2.8

Logical Equivalence

2.9

Switching circuits

MATHEMATICAL LOGIC 2.1 Basic concepts of Mathematical logic: Mathematical logic is the application of mathematical techniques to logic. Logic is commonly known as the science of reasoning. The emphasis here will be on logic as a working tool. We will develop some of the symbolic techniques required for computer logic. Some of the reasons to study logic are the following: • •

At the hardware level the design of ’logic’ circuits to implement instructions is greatly simplified by the use of symbolic logic. At the software level a knowledge of symbolic logic is helpful in the design of programs.

Logic is a language for reasoning. It is a collection of rules we use when doing logical reasoning. Human reasoning has been observed over centuries from at least the times of Greeks, and patterns appearing in reasoning have been extracted, abstracted, and streamlined. The foundation of the logic we are going to learn here was laid down by a British mathematician George Boole in the middle of the 19th century, and it was further developed and used in an attempt to derive all of mathematics by Gottlob Frege, a German mathematician, towards the end of the 19th century. A British philosopher/mathematician, Bertrand Russell, found a flaw in basic assumptions in Frege’s attempt but he, together with Alfred Whitehead, developed Frege’s work further and repaired the damage. The logic we study today is more or less along this line. In logic we are interested in true or false of statements, and how the truth/falsehood of a statement can be determined from other statements. However, instead of dealing with individual specific statements, we are going to use symbols to represent arbitrary statements so that the results can be used in many similar but different cases. The formalization also promotes the clarity of thought and eliminates mistakes. There are various types of logic such as logic of sentences (propositional logic), logic of objects (predicate logic), logic involving uncertainties, logic dealing with fuzziness, temporal logic etc. Here we are going to be concerned with propositional logic and predicate logic, which are fundamental to all types of logic.

2.2 Propositions or Statements: The smallest unit we deal with in propositional logic is a sentence. We do not go inside individual sentences and analyze or discuss their meanings. We are going to be interested only in true or false of sentences, and major concern is whether or not the truth or falsehood of a certain sentence follows from those of a set of sentences, and if so, how. Propositional logic is a logic at the sentential level. Thus sentences considered in this logic are not arbitrary sentences but are the ones that are true or false. This kind of sentences is called propositions. If a proposition is true, then we say it has a truth value of “true”; if a proposition is false, its truth value is “false”. A proposition is any meaningful statement that is either true or false, but not both e.g. p:1+1=3 to define p to be the proposition 1 + 1 = 3: The truth value of a proposition is true, denoted by T, if it is a true statement and false, denoted by F, if it is a false statement. Statements that are not propositions include questions and commands.

2.3 Combining Propositions: Simple sentences which are true or false are called basic propositions. Larger and more complex sentences are constructed from basic propositions by combining them with connectives. Thus propositions and connectives are the basic elements of prepositional logic. In English, we can modify, combine, and relate propositions with words such as “not”,“and”, “or”, “implies”, and “if then”.For example, we can combine three propositions into one like this:

If all humans are mortal and all Indians are human, then all Indians are mortal The propositions and connectives are the basic elements of prepositional logic. A few of connectives are as follows: Mathematics Symbol or

¬

Meaning not and or implies if and only if exclusive or

p

truth variable

T

true

F

false

Example Consider the following propositions p : It is Friday: q : It is raining: Construct the propositions p ^ q and p v q: Solution. The conjunction of the propositions p and q is the proposition p ^ q : It is Friday and it is raining: The disjunction of the propositions p and q is the proposition p v q : It is Friday or It is raining: A truth table displays the relationships between the truth values of propositions. Next, we display the truth tables of p ^ q and p v q: pqp^q

Let p and q be two propositions. The exclusive of p and q; denoted p © q;

is the proposition that is true when exactly one of p and q is true and is false otherwise. The truth table of the exclusive ’or’ is displayed below

2.4 Truth Table : A truth table is a mathematical table used in logic—specifically in connection with Boolean algebra, Boolean function and propositional calculus—to compute the functional values of logical expressions on each of their functional arguments Example: Constructing a Truth Table Construct the truth table for ~ (p q). Solution: Whenever we encounter a complex formula like this, we work from the inside out, just as we might do if we had to evaluate an algebraic expression, like - (a+b). Thus, we start with the p and q columns, then construct the p q column, and finally, the ~ (p q) column:

p T T F F

q T F T F

p q ~(p q) T F F T F T F T

2.5 Conditional and Biconditional Propositions : Let p and q be propositions. The implication p q is the the proposition that is false only when p is true and q is false; otherwise it is true. p is called the hypothesis and q is called the conclusion. The connective is called the conditional connective. Example: Construct the truth table of the implication p Solution The truth table is

q:

2.6 Reverse, Converse, Inverse, and Contrapositive of an implication

By definition, the reverse of an implication means the same as the original implication itself. Each implication implies its contrapositive, even intuitionistically. In classical logic, an implication is logically equivalent to its contrapositive, and, moreover, its inverse is logically equivalent to its converse. Comparisons: name

form

description

implication

if P then Q

first statement implies truth of second

inverse

if not P then not Q negation of both statements

converse

if Q then P

reversal of both statements

contrapositive if not Q then not P reversal of negation of both statements Take the statement "All quadrilaterals have four sides," or equivalently expressed "If a shape is a quadrilateral, then it has four sides." • • • •

The Contrapositive is "If a shape does not have four sides, then it is not a quadrilateral." This follows logically, and as a rule, contrapositives share the truth value of their conditional. The Inverse is "If a shape is not a quadrilateral, then it does not have four sides." In this case, unlike the last example, the inverse of the argument is true. The Converse is "If a shape has four sides, then it is a quadrilateral." Again, in this case, unlike the last example, the converse of the argument is true. The Contradiction is "There is at least one quadrilateral that does not have four sides."

Since the statement and the converse are both true, it is called a biconditional, and can be expressed as "A shape is a quadrilateral if, and only if, it has four sides." That is, having four sides is both necessary to be a quadrilateral, and alone sufficient to deem it a quadrilateral. 2.7 Tautology : A formula of propositional logic is a tautology if the formula itself is always true regardless of which valuation is used for the propositional variables. There are infinitely many tautologies. Examples include: •

• • • • •

("A or not-A"), the law of the excluded middle. This formula has only one propositional variable, A. Any valuation for this formula must, by definition, assign A one of the truth values true or false, and assign A the other truth value. ("if A implies B then not-B implies not-A", and vice versa), which expresses the law of Contraposition. ("if not-A implies both B and its negation not-B, then not-A must be false, then A must be true"), which is the principle know as reduction ad absurdum. , which is know as de Morgan’s law ("if A implies B and B implies C, then A implies C"), which is the principle know as syllogism. (if A or B is true and both implies C, then C must be true), which is the principle know as proof by cases..

The problem of determining whether a formula is a tautology is fundamental in propositional logic. The definition suggests one method: proceed by cases and verify that every possible valuation does satisfy the formula. An algorithmic method of verifying that every valuation causes this sentence to be true is to make a truth table that includes every possible valuation. For example, consider the formula

There are 8 possible valuations for the propositional variables A, B, C, represented by the first three columns of the following table. The remaining columns show the truth of subformulas of the formula above, culminating in a column showing the truth value of the original formula under each valuation. A T T T T F F F F

B T

C T

T

T

T

T

T

T

F

T

F

F

F

T

F F T T F F

T F T F T F

F F F F F F

T T T T T T

T T T F T T

T T T T T T

T T T T T T

Because each row of the final column shows T, the sentence in question is verified to be a tautology.

Example:

Example:

2.8 Logical Equivalence: Two propositions whose truth tables have the same last column are called logically equivalent. This means that no matter what truth values the primitive propositions have, these two propositions are either both true or both false. To test whether or not two propositions are logically equivalent we make a truth table for each of them and compare their last columns. Example: The proposition (p ^ q) ^ r is logically equivalent to p ^ (q ^ r). This is why the expression p ^ q ^ r is invalid, wherever the parentheses go the result is equivalent. p T T T T

q T T F F

r T F T F

p^q T F F F

(p ^ q) ^ r T F F F

p T T T

q

r

T T F

T F T

q^r T F F

p^ (q ^ r) T F F

F F F F

T T F F

T F T F

F F F F

F F F F

T F F F F

F T T F F

F T F T F

F F F F F

F F F F F

Similarly, the proposition (p ^ q) ^ r is logically equivalent to p ^ (q ^ r) so the expression p ^ q ^ r is invalid. Wherever the parentheses go the result is equivalent. De Morgan's Laws state that

(p ^ q) is logically equivalent to

(p V q) is logically equivalent to

p^

p V q and that

q.

2.9 Switching Circuits: A switching network is an arrangement of wires and switches which connect two terminals. A switch can be either closed or open. A closed switch permits and an open switch prevents flow of current. The simplest kind of network in which there is a single wire containing a single switch p is shown in the figure: P If P denotes a switch, then p' denotes that switch which is open when p is closed, and is closed when p is open. Let P be the statement: "switch p is closed", then lp will be the statement: "switch p is open." If x denotes the state of the switch p, then x' will be the state of the switch p', x will be called the state variable or Boolean variable. It is a binary variable.

If the value x=l denotes that the switch is closed or the current flows. Then value x=O denotes that the switch is open or the current stops. , Switch p Proposition Truth State of p Boolean Value of x al Value Variable Variable Closed x P T 1 (on) Open x ⌐P F 0 (off) Let 'in series' connection be represented by /\ [i.e. a/\b denotes' switches a and bare connected in series']. Also let aV b denote 'switches a and b are connected in parallel'. Consider the system ({O,l} /\, V ); B={O,1} Then B is a non-empty set and /\ and V are two binary compositions on B, by tables: /\ 0 1 v 0 1 0 0 0 0 0 1 1 0 1 1 1 1 The conditions of idempotency, commutativity, associativity and absorption are clearly seen

to be satisfied, Hence B is a distributive lattice in which each element has a complement, i.e., it is a Boolean algebra. Thus the system ({O,l} /\, V, `) is usually called switching algebra. Representation of Circuits We now illustrate how a given Boolean function can represent a circuit and how a circuit can be represented by a Boolean function. Simplification of Circuits Simplification of a circuit would normally mean the least complicated circuit with minimum cost and best (convenient) results. This would be governed by various factors like cost of equipment, positioning and number of switches, type of material used etc. Simplification of circuits would mean lesser number of switches, which we achieve by qsing different properties of Boolean algebras. Example Draw the circuit representing the Boolean functions: (i) a/\b,

(ii) aVb,

(iii) a/\(bVc) .

Solution

Example: Find the Boolean function representing the circuit:

Solution The Boolean function for the given circuit is a/\[(b/\c)v(d/\(e/\f))]

Design of Circuits Here we explain with the help of examples how with given requirements, corresponding circuits are designed. Example In a committee of three members, each member indicates his agreement by closing a switch. A bulb is lighted when a majority agrees. Construct a suitable arrangement. Solution Let A, B, C denote agreement by member number 1, 2, 3 respectively. The bulb is lighted when current flows. Current flows when at least two members agree. Hence the logic statement describing agreement is f = (A/\B/\C)V(A/\B/\¬C)V(A/\⌐B/\C)V(¬A/\B/\C)........................(i) The circuit diagram- for the Boolean function: [here a stands for A, b stands for B and c stands for C]