Anna University, Chennai
Sub. Code & Subject : MA2265 Discrete Mathematics (DM)
TWO MARK QUESTION & ANSWERS
1.Define negation?
UnitI&II




Example: P: madras is a city
~p:madras is not a city or it is not the case that madras is a city.
2.define conjunction?

Example : P : jack went up the hill
Q: jill went up the hill
P^Q: jack and jill went up the hill
3.define disjunction?
The disjunction of 2 statements P and Q is the statement P v Q which is read as “P or Q”. the statement P v Q has a truth value F only when both P and Q have truth value F otherwise it is true. The disjunction is defined by following table.
P Q P v Q
AkAsHViShAl
Example :
T T T T F T F T T F F F


2. there is something wrong with the bulb or wiring.
4.state molecular statements?
Those statements which contain one or more atomic statements and some connectives are called molecular statements.
Examples;
~P,P^~Q,P v Q.
5. Define conditional and biconditional?
If P and Q are any two statements then the statement P> Q which is read as “if P then Q “ is
called a conditional statement. Here P is called antecedent and Q is called consequent.
Truth table:
P  Q  P.> 
T T F F  T F T F  T F T T 
Example:
P: it is hot. Q: 5+3=8.
p> is false only when P is true and Q is false. Otherwise p>Q is true. Biconditional

6.define Tautology and Contradiction?
A statement formula which is true regardless of the truth values of the statements which replace the variables in it is called a universally valid formula or a tautology or a logical truth.
AkAsHViShAl


Contradiction:
A statement formula which is false regardless of the truth table values of the statements which replace variables in it is called a contradiction.
Example: P^~P

7.define Duality law?
Two formula A and A* are duals of each other if other if either one can be obtained from the other by replacing^ and v are also called duals of each other.
8.prove the following implications :
(i) (P^Q)=>(P>Q); (ii)P=>(Q>p)
Assume the consequent to be false (i.e)P>Q is false . by definition of conditional P is True and
Q is false
(ii) Assume Q>P is false Q is True but P is false. Therefore P is false.
9.define DNF and CNF
DNF:
A formula which is equivalent to a given formula and which consists of sum of elementary products is called a disjunctive normal form of the given formula.
CNF:
A formula which is equivalent to a given formula and which consists of product of elementary sums is called conjuctive normal form of the given formula.
10.state inference theory?
Rule P: a given premises may be introduced at any stage in the derivative.
Rule T: a formula S may be introduced in a derivation if S is tautologically implied by one or more of the preceding formula in to derivation.
Rule CP: if the conclusion is the form R>S then we include R is an additional premises and derive S from the given act of premises and R.this rule is called rule CP.
11.define PDNF and PCNF
PDNF: a formula which is equivalent to a given formula which is consists of sum its minterms is called PDNF.


12.construct the truth table for (q ^ (P>Q))>P)
Solution;
P  Q  P>Q  Q^(P>Q)  (Q^(P>Q))>P 
T T F F  T F T F  T F T T  T F T F  T T F T 
13 .construct the truth table for (P^Q)v()7p^Qv(P^7Q)v(7p^7Q)
Solution;
p  Q  7P  7Q  P^Q  7P^Q  p^7Q  7P^7Q  T  R  S 
T T F T  T F T F  F F T T  F T F T  T F F F  F F T F  F T F F  F F F T  T F T F  F T F T  T T T T 
14.construct the truth table for (PvQ)v7P

15.construct the truth table for (P>Q)^(q>P)

16.construct the truth table for(P>Q)<>(7PVQ)
Solution:
P  Q  7P  P>Q  7PVQ  (P>Q)<>(7PVQ) 
T T F F  T F T F  F F T T  T F T T  T F T T  T T T T 

Sol:
7pvQÃ³(7P^T)v(T^Q)
Ã³(7P^(Qv7Q))v((Pv7P)^Q)
Ã³(7P^Q)v(7P^7Q)v(P^Q)v(7P^Q)
Ã³(P^Q)v(7P^Q)v(7p^7Q)
18.obtain the PDNF for P>((P>Q)^7(7Qv7P))
Solution;
P>((P>Q^7(QV7P))
Ã³P>((7PVQ)^(Q^P))
Ã³7PV(7PVQ)^(Q^P))
Ã³7P^(QV7Q)V(F^Q)V(P^Q)
Ã³(7P^Q)V(7P^7Q)V(P^Q)
1.Define a simple statement function.
UNITIII&IV


Ex:
If “X is a teacher” is denoted by T(x),it is a statement function.if X is replased by John,then
“Johan is a teacher” is statement .
2.Define a compound statement function.
A compound stament function is obtained by combining one or more simple statement functions by logical connectives.
Ex: M(x)^H(x) M(x)>H(x)
M(x)Ñµ 7H(x)
An extension of this idea to the statement functions of two or more variables is straight
forward.
3.Define universal Quantifiers and existential Quantifiers. Universal Quantifiers:
The universal Quantification of P(x) is the proposition.”P(x) is true for all values of x in the
universe of discourse”.
The notation ¥x P(x) denotes the universal quantification of P(x).here ¥ is called the universal quantifier.
Existential Quantifier:
The existential Quantification of P(x) is the proposition.” There exists an element x in the universe of discourse such that P(x) is true”.
We use the notation ÆŽx P(x) for the existential quantification of p(x).here ÆŽ is called the existential quantifier.
4. what are the rules of Quantifier?
….

2.Rule UG (Universal generalization)
3.Rule ES (Existential Specification)
4.Rule EG (Existential Specification)
5.what are the rules of inference?
1. Rule P
A given premises may be introduced at any stage in the derivation.
2. Rule T
A formula S may be introduced in a derivation if S is tautologically implied by one or more of the proceeding formulae in the derivation .
3. Rule CP
If we can derive S from R and a set of given premises,then we can derive R>S from the set of premises alone.
6. symbolize the expression “x is the father of the mother of y”
P(x) : x is a person F(x,y) : x is a father of y M(x,y) : x is a mother of y
We symbolize this as(ÆŽz)(p(z)ÊŒF(x,z)ÊŒM(z,y))
7. Express the statement, ”Some people who trust others are rewarded” in symbolic form.
(ÆŽx)[P(x)ÊŒT(x)ÊŒR(x)] P(x) : x is aperson T(x) : x trusts others R(x) : x is rewarded
8. Give an example of free and bound variable in predicate logic.
(¥x) P(x,y) : x is a bound variable
Y is a free variable
9. Define statement function of one variable. When it will become a statement?
Statement function of one variable is defined to be an expression consisting of a predicate symbol and an individual variable. The statement function becomes a statement, when the variable is replaced by the name of an object.
10. Use quantifiers to express the associate law for multiplication of real numbers.
Universe of discourse: Set of real numbers. P(x,y,z): (x*y)*z
Q(x,y,z): x*(y*z) (x)(y)(z)(P(x,y,z)Ã³ Q(x,y,z))
11. Define simple statement function.
A simple statement function contains a predicate symbol followed by one (or) more variables. It gives the statement when the variables are replaced by objects from a designated set.

Q(x,y) : x+y=10

symbolic form.

13.Give an example to show that (ÆŽx) (A(x)ÊŒ B(x)) need not be a conclusion from(ÆŽx) a(x) B(x).
Let the universe of discourse be the set of all integers.

The statements (ÆŽx) A(x) and(ÆŽx)B(x) are true. The statement (ÆŽx)(A(x)ÊŒB(x)) is false,
because there is no integer ‘a’ such that 2a+1=5and
14.show that ~P(a,b)follows logically from (x),(y)(P(x.y)>W(x,y)and ~W(a,b)
(i) (x)(y)(P(x,y)>W(x,y) rule P (ii) (y)(P(a,y)>W(a,y)) US,(i) (iii) P(a,b)>W(a,b) US ,(ii)
(iv) ~W(a,b) rule P(v) ~P(a,b) rule T(iii,iv)



17.which of the following are statements?
i.(x)(P(x)vQ(x))^R. ii.(x)(P(x)^Q(x))^S(x) solution:
i.is not a statement ii.is a statement
18.using CP ot otherwise obtain the following implication: (x)(P(x)>Q(x)),
(x)(R(x)>7Q(x))=>(x)(R(x)>7P(x)) Sol:
(x)(P(x)>Q(x)) rule P
2.(x) R(x)>7Q(x) rule T
3.Q(x)>7R(x) rule T,,2,3
4.R(x)>7P(x) rule T,4
1.define function.
UnitV

2. define graph of a function.
With each function we can associate a graph ,which is a diagrammatic representation of a function.if the domain x and codomain Y of a function f are finite,we can represent such a function as follows
We draw a circle for each element x of X and each element y of Y and join x with y by a
directed line, directed from x to y ,if (x ,y)€f
.
3. define identity map
A mapping Ix:X>X is called an identify map if
Ix={(x,x){x€X}
4. define commutative property
A binary operation f:X x X >X is said to be commutative if for every x, y €X ,f(x, y)=f(y, x).
5 define distributive
A binary operation f: X*X>X denote by * is said to be , distributive over the operation g:X*X
>X, denoted by ⁰ if for every x, y, z €X. X*(y⁰z))=(x*Y)⁰(x*z)
6. define idempotent
Let * be a binary operation on X an element a €X is called idempotent with respect to * if



A function is called primitive recursive if and if it can be obtained from the initial functions by a finite number of operations of composition and recursion.
8. define onto (or) surjective (or)surjection
A mapping of f:X>Y is called onto if the range rf =Y; otherwise it is called into.
9.Define injective
A mapping f:X>Y is called oneto one if it is both onetoone .such a mapping is also called a one to one correspondence between X and Y.
10. define graph of functions
With each function ,we can associate a graph , which is a diagrammatic representation of a function if the domain X and codomain Y of a function f are finite , we can represent such a function as follows.
We draw a circle for each element x of X and for each element of Y and join x with y by a
directed line directed from x to y, if(x, y)€f.
11. define identity map
A mapping Ix=X>X is called an identity map if
Ix={(x, x){x€ X}
12. define inverse function
If it is a function from X to Y if f , the converse of f , given by (y, x)€f whenever (x, y) €f, need
not be a function from Y to X.
13.define binary and n ary operation
Let X be a set and f be a mapping f:X x X>X then f is called a binary operation on X. in general, a mapping f: Xn >Xis called an nary operation and n is called the order of the operation . for n=1,f:X>X is called a unary operation.
14 define primitive recursion
A function is called primitive recursive if and only if it can be obtained from the initial functions by a finite number of operations of composition and recursion.
15.Define permutation
A bijection from a set A to itself is called permutation of A.
16.define function.
Let x and Y be any two set. A relation F From X to Y is called a function if every X € there is a unique Y such that (X,Y) € F.
For a from F : X→ Y , if (X, Y)€ F, then Xs c argument and corresponding Y a X . The pair (X, Y)
€ F, is also written as Y=F ( X ), X is then said to be mapped into XY.
17.define into


then F is said to be a pinto be a into function from X into Y . Clear F : X → Y is an into function if ( X) = Y.
18.definr one to one
A mapping F : X → Y is called one (injection, or 11) if distinct element of X are mapped into element of Y .
In other ,F is one to one if
X1# F( X2) X1 = X2 .