**Chapter 4 Discrete Mathematics**

**Discrete Mathematics Long Answer Type Questions (8 Marks)**

Question 1.

How are characters created by Binary Numbers? What are its different codes? Explain with examples. (UP 2011)

Answer:

Computer Code: Computer codes are used to convert data into binary form to make the computer understand it. Apart from this, they are responsible for error-free signal flow in the computer. Three popular computer codes are:

BCD (Binary Coded Decimal): It is one of the earliest developed memory codes. In this, every digit is converted into binary form separately:

e.g.,

But four-bit code can handle only 2^{4} = 16 dIfferent characters that are why it is extended to 6-bit code and It can handle 2^{6} = 64 different characters. It is 6-bit code and divided into two parts i.e., zone bit and character code.

Zone bit consists of Z bits and character zone consists of 4 bits.

To understand more look at the table given below:

EBCDIC (Extended Binary Coded Decimal Interchange Code): BCD can convert only 64 characters but we use more than 64 characters in computer to represent data. To overcome this problem, 2 more bits have been added to the zone bit to develop new 8-bit code and, that is why it is known as extended binary coded decimal interchange code. EBCDIC is 8- bit code which can encode 2^{8} = 256 different characters. It is similar to BCD in working but it has 4 bits in bit zone. To understand more table is given below:

ASCII (American Standard Code for Information Interchange): This code is the most popular and widely accepted computer code. It is the standard code for computers, developed by the American National Standards Institute in the year 1963 for encoding different characters in the computer. It is used by almost every manufacturing company. ASCII codes are of two types:

(a) 7-bit Code: To encode 2^{7} = 128 characters with 3 bits in zone bit and four in character zone.

(b) 8-bit code: To encode 2^{8} = 256 characters with 4 bits in bit zone and 4 bits in character zone.

Question 2.

Define character representation in computers. (UP 2008)

Or

What is meant by “character representation”? Explain one such code in detail. (UP 2009)

Or

What is meant by character coding? Explain one coding methods in detail. (UP 2016)

Or

What is Character Representation? (UP 2018)

Answer:

Character Representation: Physical devices used to store and process data in computers are two-state devices. A switch, for example, is a two-state device. It can be either ON or OFF. Electronic devices such as transistors used in computers must function reliably when operated as switches. Thus, all data to be stored and processed in computers are transformed or coded as strings of two symbols, one symbol to represent each state.

Coding of characters has been standardized to facilitate the exchange of recorded data between computers. The most popular standard is known as ASCII. Each letter is a unique combination of Binary Digits (BITS). That is, each letter is a group of charged and uncharged transistors and it is grouped in such a way that a particular combination represents a specific character. A group of 8 BITS which is used to represent a character is called a byte. The length of 1 word is called word length which ranges from 1 byte to 64 bytes.

The internal code representation of string HARSH is:

Question 3.

Explain the Number System.

Answer:

Number System: Number systems are very important to understand because the design and organization of a computer system depend on it.

Number systems are basically of two types:

1. Non-positional Number System: In this number system, each symbol represents the same value regardless of its position in the number and the symbols are simply added to find out the value of a particular number. Since it is very difficult to perform arithmetical operations with such a number system, positional number systems have been developed.

2. Positional Number System: In a positional number system, there are only a few symbols called digits, and these symbols represent different values depending on the position they occupy in the number.

The value of each digit in such a number is determined by three considerations :

- The digit itself

Face Value: The face value of a digit always remains the same regardless of its position in the number, e.g., the face value of 4 in 554, 40567 etc. is 4. - The position of the digit in the number.

Place Value: Place value of a digit changes due to change in its position, e.g., place value of 2 in 4210 is 2 hundred, in 32,450 it is 2 thousand, etc. - The base of the number system (where the base is defined as the total number of digits available in the number system), e.g., Decimal number system has base 10 since it includes only 10 digits 0, 1, 2, ….., 9, to represent any number.

The various positional systems in use are:

- Binary number system
- Octal number system
- Decimal number system
- Hexadecimal number system.

Question 4.

What are the logical operators? What are their different types? Explain operators making their Truth Table. (UP 2007, 08, 10)

Answer:

Logical Operators: AND, OR, and NOT are logical operators. Since these operators are operated on logical values 0 and 1, that is why these operators are called logical operators.

AND Operator: An AND operator is represented by the symbol ‘.’. Basically AND operator is used to performing logical multiplication. A, B, and C are three logical variables, where A, B, are input variables and C is the output variable. We can define the AND operator by listing all possible combinations of A and B and the resulting value of C in the operation A.B = C.

It may be noted that since the variables A and B can have only two possible values (0 or 1) so only four (22) combinations of inputs are possible as shown in the following table. The resulting output values for each of the four input combinations are given in the table. Such a table is known as the truth table. Thus, the table is the truth table for the logical AND operator.

As we can observe from the truth table that in AND operation, the output will be 1 when all inputs are 1 else output will be 0.

OR Operator: An OR operator is represented by the symbol V. Basically an OR operator is used to perform logical addition. As in the previous example, A and B are input variables and C its output variable. We can define the OR operator by listing all possible combinations of A and B and the resulting value of C in the equation A + B = C. The truth table for Logical OR operator is shown in the following Table:

As we can observe from the truth table that in logical addition, the output will be 1 when any one input is 1. It means if all inputs are 0 then the output will be 0.

NOT Operator: The two operators (AND and OR) are binary operators because they operate on two variables. NOT operator denoted by is a Unary operator because it operates on a single variable. NOT operator is also known as complementation operator or inverse operator.

Thus, complement of A is [latex]\bar { A } [/latex]. Complement of (A + B) is [latex]\bar { (A+B } )[/latex]. If value

of [latex]\bar { A } [/latex] is 0 then value of A is 1 and if value of A is 1 then value of [latex]\bar { A } [/latex] is 0. The truth table for logical NOT operator is shown in table.

Question 5.

Write about the postulates of Boolean Algebra.

Answer:

Postulates of Boolean Algebra: Boolean Algebra is an algebraic structure defined on a set of elements B together with two binary operators + and . provided the following postulates are satisfied:

(1) (a) Closure with respect to the operator +

(b) Closure with respect to the operator.

(2) (a) An identity element with respect to +, designated by

0 : X + 0 = 0 + X = X.

(b) An identify element with respect to designated by

1 : X . 1 = 1 . X = X.

(3) (a) Commutative with respect to + : X + Y = Y + X

(b) Commutative with respect to . : X . Y = Y . X

(4) (a) . is distributive over : : X . (Y + Z) = (X . Y) + (X . Z)

(b) + is distributive over . : X + (Y . Z) = (X + Y) . (X + Z)

(5) For every element X ∈ B, there exists an element [latex]\bar { X } [/latex] ∈ B such that:

(a) X × [latex]\bar { X } [/latex] = 1

(b) X . [latex]\bar { X } [/latex] = 0

The postulates listed above are called Huntington (1904) Postulates and need no proof. They are used to prove the theorems of Boolean Algebra.

Question 6.

What are the different Gates in Boolean Algebra? (UP 2004, 05, 07)

Or

What is ‘Truth Table’? How is it helpful in understanding GATES? (UP 2006)

Or

Explain the working of a NAND Gate. Give its two application. (UP 2009, 10)

Or

How can you show that NAND is a Universal Gate? Explain with diagrams and truth tables. (UP 2011, 19)

Answer:

Truth Table: A table that shows all the input-output possibilities of a logic circuit is called a truth table.

There are several types of the truth table. AND, OR, NOT, NAND, NOR, XOR, XNOR Gates are described below:

(a) AND Gate: In English language, Input A is ANDed with Input B to get output Y.

The truth table illustrates four ways to express the logical ANDing of A and B.

The AND Gate works on the principle that output will be high when all the inputs are high otherwise output will be low.

(b) OR Gate: In OR Gate, input A is ORed with input B to get output Y.

The OR Gate works on the principle that, if anyone input is high, the output will be high. Thus, the only case when output will be low is when all inputs are low i.e., 0.

(c) NOT Gate: The NOT Gate is an electronic circuit that generates an output signal which is the reverse of the input signal. A NOT gate is also known as an inverter because it inverts the input.

(d) NAND Gate: A NAND Gate is a complemented AND gate. That is, the output of NAND Gate will be 1 if anyone of the inputs is 0 and will be 0 when all the inputs are 1.

(e) NOR Gate: A NOR Gate is a complemented OR Gate. That is, the output of a NOR Gate will be 1 only when all inputs are 0 and will be 0 if any input represents a 1.

(f) XOR Gate (Exclusive-OR Gate): XOR Gate is a combination of AND, OR, and NOT Gates. symbol denotes XOR operation. This Gate works on the principle that if an odd number of inputs are 1, the output will be 1 otherwise output will be 0.

As observed from the truth table, the output is 1 when odd numbers of inputs are 1.

(g) XNOR Gate (Exclusive-NOR Gate): Similarly, XNOR gate is also formed with a combination of AND, OR, and NOT gates. symbol denotes XNOR operation. Since this gate is the inverse of XOR gate, the output will be 0 when odd numbers of inputs are 1 otherwise output will be 1.

Question 7.

Explain the basic features of ASCII Code. (UP 2005, 08, 09, 10)

Or

Explain in detail the features of the ASCII character code. (UP 2007)

Answer:

ASCII: Binary numbers are coded to represent characters in the computer memory. Several codes are used for this purpose. One most commonly used code is the American Standard Code for Information Interchange (ASCII). ASCII has been adopted by several American computer manufacturers as their computer’s internal code. This code is popular in data communications, is used almost exclusively to represent data internally in microcomputers, and is frequently found in the larger computers produced by some vendors.

ASCII is of two types: ASCII-7 and ASCII-8. ASCII-7 is a 7-bit code that represents 128 (27) different characters.

ASCII-8 is an extended version of ASCII-7. It is an 8-bit code that represents 256 (28) different characters rather than 128.

e.g. (i) A is given ASCII code 65.

Now if we convert 65 into Binary form we get 01000001 → 1 byte

In the same way, every character has its own ASCII value after converting into binary code stored on the computer.

Question 8.

Describe various Binary Arithmetic Operations. (UP 2008, 09, 11)

Or

What is binary arithmetic? Explain with suitable example. (UP 2017)

Answer:

Four basic arithmetic operations are performed inside a computer using binary numbers. These are addition, subtraction, multiplication, and division. Since binary numbers are made up of 0’s and 1’s, results of arithmetic operations are also in 0’s and 1’s only.

Binary Addition: Binary addition is performed in the same manner as decimal addition. However the binary system has only two digits, the addition table for binary arithmetic is very simple, consisting of only four entries. The complete table for binary addition is as follows:

0 + 0 = 0

0 + 1 = 1

1 + 0 = 1

1 + 1 = 0

Plus a carry of 1 to next higher column. Carryovers are performed in the same manner as in decimal arithmetic. Since 1 is the largest digit in the binary system, any sum greater than 1 requires that a digit be carried over.

Example:

Binary Subtraction: From the following table, it is clear that the lower digit is subtracted from the upper digit. If the lower digit is larger than the upper digit, it is necessary to borrow from the column to the left which equals to 2 (10).

0 – 0 = 0

1 – 0 = 1

1 – 1 = 0

0 – 1 = 1

with borrow from the next column. Thus, the only case in which it is necessary to borrow is when 1 is subtracted from 0.

Example

Binary Multiplication: Multiplication in the binary system also follows the same general rules as decimal multiplication. The table for binary multiplication is as follows:

0 × 0 = 0

0 × 1 = 0

1 × 0 = 0

1 × 1 = 1

Example:

Binary Division: Binary division is, again, very simple. As in the decimal system (or in any other system), division by zero is meaningless, here too. Hence, the complete table for the binary division is as follows:

0/1 = 0

1/1 = 1

The division process is performed in a manner similar to the decimal division.

Example:

**Discrete Mathematics Short Answer Type Questions (4 Marks)**

Question 1.

What is the order of precedence in Boolean Algebra? (UP 2007, 09, 19)

Answer:

In a Boolean expression, many operators are used. The order in which they are operated is known as precedence. The precedence of Boolean operators is as follows:

- The expression is scanned from left to right.
- Expressions enclosed within parentheses are evaluated first.
- All complement (NOT) operations are performed next.
- All ‘.’ (AND) operations are performed after that.
- Finally, all ‘+’ (OR) operations are performed in the end.

Question 2.

Define the Principal of Quality. (UP 2016)

Answer:

The Huntington Postulates have been listed in two parts: (a) and (b). One part may be obtained from the other if ‘+’ is interchanged ‘+’ with ‘.’ and ‘0’ in interchanged with ‘1’ and vice-versa. This important property of Boolean Algebra is called Principle of Quality. This principle ensures that, if a theorem is proved using the postulates, then a dual theorem obtained interchanging ‘+’ with ‘.’ and ‘0’ with ‘1’ automatically holds and need not be proved separately.

The table below lists theorems and their corresponding dual theorems.

Question 3.

Write a note on De Morgan’s Theorems to prove it.

Answer:

Theorem (a): De Morgan’s Theorems: (x + y)’ = x’. y’

Proof: The truth table for proving this theorem is given below:

From the truth table, it is clear that both sides of the theorem are equal. Hence, the theorem is proved.

Theorem (b): (x + y)’ = x’ + y’

Proof: The truth table for proving this theorem is given below:

From the truth table, It is clear that both sides of the theorem are equal. Hence, the theorem is proved.

Theorems 6(a) and 6(b) are very important and useful. They are known as De Morgan’s theorems. They can be extended to n variables as given below:

(X_{1} + X_{2} + X_{3} + ………. + X_{n})’ = X_{1}‘ . X_{2}‘ . X_{3}‘ …….. X_{n}‘

(X_{1} . X_{2} . X_{3}. …… X_{n})’ = X_{1}‘ + X’_{2} + X_{3}‘ + ……….. + X_{n}‘

Question 4.

Write AND and OR LAWS of Discrete mathematics.

Answer:

AND LAWS: AND LAWS are the laws which work on logical multiplication. They are:

1. x . 1 = x

2. x . x’ = 0

3. x . x = x

4. x . 0 = 0

“The tabular representations of truth values of a compound statement based on the truth values of the prime connective ness of statements is called TRUTH TABLE.”

Truth table consists of horizontal lines (rows) and vertical lines (columns). If a compound statement consists of N statements, the number of rows will be 2^N. The number of columns in a truth table depends upon the number of relationships between these statements.

**Discrete Mathematics Very Short Answer Type Questions (2 Marks)**

Question 1.

Discuss De-Morgan’s Theorem. (UP 2014)

Answer:

First Theorem: This theorem states that the complement of a sum of the binary variable is equal to the product of the complement of the binary variables.

Second Theorem: The theorem states that the complement of a product of binary variable is equal to the sum of the complement of the binary variable

Question 2.

What is the full form of ASCII? (UP 2014)

Answer:

The full form of ASGII is American Standard Code for Information Interchange.

Question 3.

If A = 0 and B = 1, then find the value of y from the following expression:

Y = (A . B)

Answer:

Y = [latex]\bar { (0.1 } )[/latex] = [latex]\bar { (0 } )[/latex] = 1

Question 4.

Give the name of the Boolean operators. (UP 2014)

Answer:

AND Operator, Or operator and NOT operator.

Question 5.

Write a full form of EBCDIC. (UP 2017)

Answer:

Extended Binay Coded Decimal Interchange Code.

**Discrete Mathematics Objective Type Questions (1 Marks)**

There are four alternative answers for each part of the questions. Select the correct one and write in your answer book:

Question 1.

Each letter is a unique combination of:

(a) Bits

(b) Bytes

(c) Word length

(d) Binary.

Answer:

(a) Bits

Question 2.

A group of 8 bits which is used to represent a character is called :

(a) Bits

(b) Bytes

(c) Integer

(d) None of these.

Answer:

(b) Bytes

Question 3.

The most popular standard is known as:

(a) BCD

(b) ABC

(c) ASC

(d) ASCII

Answer:

(d) ASCII

Question 4.

In the hexadecimal number system, the base :

(a) 8

(b) 10

(c) 16

(d) None of these.

Answer:

(c) 16

Question 5.

The binay equivalent of the number (15)_{10}. (UP 2014)

(a) (1101)

(b) (1110)_{2}

(c) (1111)_{2}

(d) (1000)_{2}.

Answer:

(a) (1101)

Question 6.

Which logic gate has only one input and one output? (UP 2015)

(a) NOT

(b) NOR

(c) OR

(d) AND.

Answer:

(a) NOT

Question 7.

The value of the binary number (1010)_{2} would be?

(a) (14)_{10}

(b) (12)_{10}

(c) (10)_{10}

(d) (11)_{10}

Answer:

(c) (10)_{10}

Question 8.

What is binary equivalent of [31]_{10}. (UP 2017)

(a) 10000

(b) 11111

(c) 100000

(d) 11110.

Answer:

(b) 11111

Question 9.

Which of the following is a single input logic gate? (UP 2018)

(a) NAND

(b) AND

(c) NOT

(d) NOR.

Answer:

(c) NOT