Project 2001

Question 1: Enumerate various steps, which can be useful in translating statements arguments in English to corresponding statements or arguments in a formal language like Prepositional calculus (PC) or First Order Predicate Calculus (FOPC). Further translate the following arguments in arguments in English to corresponding arguments in a Formal Language (only PC/FOPC) and check in PC/FOPC the validity of the arguments:

a) If the parliament refuses to enact new laws, then the strike will not be over unless it lasts more than one year and the president of the firm resigns

Conclusion:

If either the parliament enacts new laws, then the strike is not over than the strike lasts more than one year.

b) No second-hand car dealer, buys a second-hand car for their families are absolutely dishonest. Then we conclude that some absolutely dishonest people are not second-hand car dealers.

Answer (a):Let P represents "Parliament enacts new laws"

SO represent "Strike is over"

L represents "Strike last more than one year"

PR represents "President resigns".

The above antecedent says:

ù (P) Þ (SO Þ ( L Ù PR))

The conclusion translates to:

( P Ú ù ( SO )) Þ L

The conclusion is not valid.

ù ( P ) Þ ( SO Þ ( L Ù PR))

ù ( ù ( P )) Ú ( SO Þ ( L Ù PR))

P Ú ( ù ( SO )) Ú ( L Ù PR))

P Ú ù ( SO ) Ú ( L ù R)

Clearly here P, ù (SO) can be true and L is false which would falsify the conclusion.

Answer (b): No second-hand car dealer buys a second hand car for their families are absolutely dishonest. Then we conclude that some absolutely dishonest people are not second-hand car dealers.

This means that:

No second-hand car dealer who buys a second-hand car for his/her family is absolutely dishonest. Then we conclude that some absolutely dishonest people are not second-hand car dealers.

P varies over all persons. SHCD(P) says person P is a second-hand car dealer, BSC(P) says that P buys a second-hand car for his/her family and DH(P) says P is absolutely dishonest.

So the statement translates to:

$ P (SHCD(P) Ù BSC(P) Þ ù (DH(P))

The conclusion translates to:

$ P DH(P) AND ù (SHCD(P))

The statement can be simplified as:

$ P ù ((SHCD(P)) Ú ù (BSC(P)) Ú ù (DH(P))

Perhaps $ P ù (DH(P)). This will be consistent with the statement but not with the conclusion.

Thus the conclusion is incorrect.

Question 2(a): Prove that in a complimented and distributive lattice [L, È , Ç ], the complement ` a of an element a of L is unique.

Answer: Let us suppose an element aÎ L has two elements say a1 and a2. Then by definition of complement

a Ç a1 = 0 and a È a1 = 1.

Also, a Ç a2 = 0 and a È a2 = 1.

Now, a1 = a1 Ç 1 = a1 Ç (a È a2)

= (a1 Ç a ) È ( a1 Ç a2 )

= 0 È ( a1 Ç a2 )

= ( a2 Ç a ) È ( a1 Ç a2 )

= ( a2 Ç a ) È ( a2 Ç a1 )

= a2 Ç ( a È a1)

= a2 Ç 1 = a2

Hence, a1 = a2, which contradicts the assumption that a Î L has two different complements a1 and a2.

\ The complement of any a Î L is unique.

Question 2(b): If we define a tree as a finite, undirected graph with no cycles, then prove that a graph with n vertices is a tree if and only if it is connected and has exactly (n – 1) edges.

Answer: By induction

If n = 1, then No. of vertices = 1, edges = 0.

Hence, the theorem is true for n = 1.

If n = 2, then No. of vertices = 2, edges = 1 = 2 – 1

The theorem is true for n = 2.

Let the theorem is true for n £ k also. Consider a tree with k + 1 vertices.

Let ep be an edge of the tree G, connecting vi and vj. Since, G is a tree, ep is the only path connecting vi and vj.

Hence, deleting ep will disconnect G into exactly two components. Each s such component has fewer than k + 1 vertices and hence each component is tree.

Let the two components have k1 and k2 vertices. Then the total number of edges will be

k1 – 1 + k2 – 1 = k1 + k2 –1 = k + 1 – 1, since, k1, k2 £ k

= k.

The theorem is true for n = k + 1 if it is true for n £ k.

Hence, by mathematical induction the proof follows.

i.e., If G is a tree with n vertices it has n – 1 edges. In other words any connected graph with n vertices and n – 1 edge is a tree.

Assume that G has a cycle of length P. Then there are P points and P lines on the cycle and for each of n – p points not on the cycle there is an incident line on an geodesic to a point of the cycle. Since, each such line is different, the total number of edges is n – p + p = n > n – 1 which is a contradiction.

Hence, the proof.