Mathematical Foundation of Computer Science
DHARM 144 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE Hence argument is valid. Consider another argument, II. “India is democrat ...
DHARM PROPOSITIONAL LOGIC 145 For example, consider an argument, I. “All dogs are barking. Some animals are dogs. Therefore, som ...
DHARM 146 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE We can prove above equivalence formulas. For example, to prove the (iii) e ...
DHARM PROPOSITIONAL LOGIC 147 5.2 Let R be “He is richer” and let C be “He has a car”. Write each of the following statements in ...
DHARM 148 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE 5.9 For the given premises determine a suitable conclusion so that the arg ...
LATTICE THEORY 6.1 Introduction................................................................................................. ...
6.1 INTRODUCTION In this chapter we shall first discuss what is meant by a partial ordered set and how partial ordered set is re ...
DHARM LATTICE THEORY 151 Similarly the relation “less than” or relation “greater than” are also partial ordered relation over s ...
DHARM 152 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE Thus, a simplified poset will be, ≤ = {(2, 4), (2, 6), (3, 6), (4, 8), (6, ...
DHARM LATTICE THEORY 153 Thus, the Hasse diagram is shown in Fig. 6.3. {, ,}abg {, }bg {}g {, }ab {}a Ø {}b {,}ag {, ,}abg {, }b ...
DHARM 154 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE Hence the Fig. 6.5 shows the Hasse diagram for poset (S, ≤) 24 12 18 9 9 4 ...
DHARM LATTICE THEORY 155 Lower Bound Let (X, ≤) be a poset and Y ⊆ X, then an element x ∈ X be the lower bound for Y if and only ...
DHARM 156 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE {α, β}}. Then, poset (P(X), ⊆) in which each pair have a unique LUB & ...
DHARM LATTICE THEORY 157 From the definition of GLB(x, y), we have GLB(x, y) ≤ x. Hence, x ≤ y ⇒ GLB(x, y) = x. Further assume, ...
DHARM 158 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE Again using equality (i) we obtain, GLB(y, z) ≤ GLB (LUB(x, y), LUB(x, z)) ...
DHARM LATTICE THEORY 159 Therefore, x ≤ GLB(x, LUB(x, y)); Conversely, from the definition of GLB, we have GLB(x, LUB(x, y) ≤ x. ...
DHARM 160 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE Example 6.8. Show that lattice of Fig. 6.7 is not a distributive lattice. ...
DHARM LATTICE THEORY 161 Example 6.10. Consider the poset (X, ≤) where X = {1, 2, 3, 5, 30} and the partial ordered relation ≤ i ...
DHARM 162 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE a b c d f e Fig. 6.10 Let x = c then LUB(c, f) = c and GLB(c, f) = f and L ...
DHARM LATTICE THEORY 163 Then we can find the complement of the elements that are listed in the table shown in Fig. 6.12. No. El ...
«
4
5
6
7
8
9
10
11
12
13
»
Free download pdf