MCS 013 Discrete Mathematics

 MCS-013 

Discrete Mathematics

2016-17

2.

(a) Write down suitable mathematical statement that can be
represented by the following symbolic properties.
(i)

sol.   (There exist value of x) for ( for all values of y) for ( all exist value of z).

where x,y,z belong to the real value

.

(ii)

sol.   (for all value of x ) for (There exist values of y)  for ( all exist value of z).

where x,y,z belong to the real value 

.

(b) Write the following statements in the symbolic form.

(i) Some birds can not fly

B : are birds

F : are fly

B->F all birds are flying 

And at least one bird are flying 

So

Neglect of above sentence 

(~B) - >F

(ii) Nothing is correct

A : all things

B : correct 

A->B

All things is correct 

And neglected of sentence 

(A) - > (~B) all things are not correct

So nothing is correct. 

(c) What is modus ponen and modus tollen? Write one
example of each.

In propositional logic, modus tollens (or modus tollendo tollensand also denying the consequent) (Latin for "the way that denies by denying") is a valid argument form and a rule of inference. It is an application of the general truth that if a statement is true, then so is its contra-positive.

Consider the following argument...

• "If you have a current password, then you can log on to the network"
• "You have a current password"
  
  Therefore:
  
  
• "You can log on to the network"

This has the form:

p→q
p

---

∴ q

This form of argument is calls Modus Ponens (latin for "mode that affirms")


Note that an argument can be valid, even if one of the premises is false. For example, the argument above doesn't say whether you do or don't have a current password. Maybe you do, and maybe you don't . But either way, the argument is still valid.


Consider this argument:

• You can't log into the network
• If you have a current password, then you can log into the network
  
  Therefore
  
  
• You don't have a current password.

Now, in real life, we might say: that's not a valid argument. For example, maybe you can't log into the network because your Ethernet cable is bad, or because the network is down for maintenance, or any one of a zillion other reasons.

But in fact, this is a valid argument in logic. If we accept the two premises, then the conclusion follows. One of the premises is "If you have a current password, you can log into the network". There are no ifs, ands, or buts. 

So, this illustrates an important point: when working with logic problems it is important to take the statements literally and at face value. Don't read things into the problems that aren't there. 

We sometimes use problems that seemto be about the real world—we do this to make the problems more interesting and relevant, and to give us some insight into what the symbols mean. But the problems, ultimately are not in the real world—they are about amathematical model of the real world, where we make a lot of simplifying assumptions. For example, the hard and fast absolute statement:

• If you have a current password, then you can log into the network

According to this statement, a current password is sufficient for you to be able to log in.

So, if we assume this to be true, as we do in the argument below, and we assume that you can't log into the network, then we can definitely conclude: you don't have a current password. So here it is again:

• You can't log into the network
• If you have a current password, then you can log into the network
  
  Therefore
  
  
• You don't have a current password.

This is an argument of the form:

¬q
p→q

---

∴ ¬p

This form of argument is called modus tollens (the mode that denies).

Both modus ponens and modus tollens have "universal forms":

Universal modus ponens:

∀x((P(x)→Q(x))
P(a), where a ∈ {domain of the predicate P}

---

∴Q(a)

E.g. All fish have scales. This salmon is a fish. Therefore, this salmon has scales.

Universal modus tollens:

∀x((P(x)→Q(x))
¬Q(a), where a ∈ {domain of the predicate P}

---

∴¬P(a)

E.g. All surfers are hot. Conrad is not hot. Therefore Conrad is not a surfer.

(d) What is relation? Explain equivalence relation with the
help of an example.

A relation between two sets is a collection of ordered pairs containing one object from each set. If the object x is from the first set and the object y is from the second set, then the objects are said to be related if the ordered pair (x,y) is in the relation.

A function is a type of relation. But, a relation is allowed to have the object x in the first set to be related to more than one object in the second set. So a relation may not be represented by a function machine, because, given the object x to the input of the machine, the machine couldn't spit out a unique output object that is paired to x.

Equivalence Relation

An equivalence relation on a set is a subset of , i.e., a collection of ordered pairs of elements of , satisfying certain properties. Write "" to mean is an element of , and we say " is related to ," then the properties are

1. Reflexive: for all ,

2. Symmetric: implies for all

3. Transitive: and imply for all ,

where these three properties are completely independent. Other notations are often used to indicate a relation, e.g., o