9. Set, Symmetric Difference and Propositional Logic
Set, Symmetric Difference and Propositional Logic are kind of heart and soul of Discrete Mathematics, as well as Computer Science. These concepts are immersed in data structures and algorithm, too. Without understanding these key concepts, we cannot move forward. Our knowledge of data structures and algorithm will remain incomplete.
In the previous chapters, we have seen a few implementations of Sets in various programming languages. We have also found out that sets are basically statements, just like we use the term statement within the coding paradigm.
Let us write a discrete mathematical Set of even numbers like this:
1 A = {2, 4, 6, 8}
We can read the Set of this even numbers as a statement – it is an even number. In discrete mathematical concepts, numerical sets are considered as a collection of discrete numbers that will not contain duplicate numbers. Yet, this statement will come into possession of something else if we replace the words ‘numbers’ with ‘things’. We will come to that point in a minute.
If two different sets contain duplicate numbers, the symmetric difference will easily point out those numbers. Set uses XOR symbol to express the inequality, and this Boolean concept is implemented in every programming language.
Here comes Propositional Logic. We cannot find Symmetric Difference of two Sets without implementing Propositional Logic.
Propositional Logic is concerned with statements that are governed by ‘truth values’; true and false. These truth values are assigned to analyze these statements either individually or in a composite manner.
These discrete mathematical concepts are not only interrelated, they also help each other clandestinely, within the coding paradigms.
We have found out in the previous chapter, in Java Collection framework, a Set is a Collection that cannot contain duplicate elements. It models the mathematical Set abstraction, Symmetric difference and Propositional logic one behind the other.
The concepts of Propositional logic plays a key role in some special cases, such as where the Set Collection defines behaviors like ‘equals’ or ‘hashCode’ operations. Let us consider an example, where we have two Set instances. If we want to compare them, we need to model the discrete mathematical Set abstractions, as well as Symmetric difference and propositional logic. Only if two Set instances are equal, when they contain the same elements.
A simple discrete mathematical example will clarify the concept.
1 A = {1, 5, 8, 9} and B = {5, 9, 11, 45}
2 A Symmetric Difference B = {1, 8, 11, 45}
Here numbers 1, 8, 11 and 45 are in each Set. However, 5 and 9 are in both Sets.
While we are not going to the details of the discrete mathematical representations, nevertheless we need to understand why implementations of Set abstractions are necessary in Data Structures.
So far, we have seen some mathematical Set implementations with numerical sets. But it could be of ‘things’. Even mathematically when we define a Set, we say, a Set is a Collection. Collection of what? Collection of things. And, of course, these things should have a common property. We can imagine a Set of biking gears, such as helmet, gloves, goggles, shoes, etc. In another example of Set we can think of our two eyes – left eye and right eye.
We have already learned the Set notations, so we can write these two examples this way:
1 {helmet, gloves, goggles, shoes, ... }
2 {left-eye, right-eye}
In the first example, we have used three dots, they are called ellipsis. It means, the biking gear list is endless,or infinite. On the contrary, we have second example, where we have exact two elements.
We call the first one ‘infinite set’ and the second one is a ‘finite set’.
Set abstractions may seem pointless as far as Mathematics is concerned, but this statement is contextual. In many situations Sets can become building blocks of highly complicated mathematical concepts, such as Graph Theory, Abstract Algebra, Linear Algebra, Number theory, etc. Furthermore, Set abstractions are building blocks of Data Structures, of which we are interested at present.
Why Set is important in Data Structures
The Set abstraction has some special characteristics. While we organize our data, we need to implement those special characteristics of Set abstraction. By organizing data we mean creation, retrieval, modification, and removal of data. In such operations, the implementations of Set abstraction comes to our help. Let us try to understand this part.
An element can exist only once in a Set. This Collection does not allow duplication. Particularly, this trait makes Set different from others in Java Collection framework. When we organize our data structures, we can plan it in that way.
We can store unique elements. Since, by default, Set abstraction does not care about order, in some cases, we can take advantage of that character also.
Based on such characteristics, we can store discrete elements without duplication, and we need not care about the order of the elements always. Although Set does not care about order, in some cases, we do not need chaos, but order. In such cases, we have the general-purpose Set implementation ‘TreeSet’. It maintains the order of elements based on their values. But implementation of ‘TreeSet’ comes at a higher cost. It is slower than the other Set implementation ‘HashSet’, which stores data in a hash table. As long as the order of iteration is concerned, the ‘HashSet’ implementation does not guarantee that.
Let us take a look at the both implementations.
1 //code 9.1
2
3 package chapternine;
4
5 import java.util.HashSet;
6 import java.util.Set;
7 import java.util.TreeSet;
8
9 public class FirstCodeSample {
10
11 public static void main(String[] args) {
12
13 int countingIntegers[] = {25, 44, 78, 1, 65, 3};
14 Set<Integer> hashSet = new HashSet<Integer>();
15 try {
16 for(int i = 0; i < 5; i++) {
17 hashSet.add(countingIntegers[i]);
18 }
19 System.out.println("HashSet does not sort the order: " + hashSet);
20
21 TreeSet sortedTreeSet = new TreeSet<Integer>(hashSet);
22 System.out.println("TreeSet sort the order based on values :");
23 System.out.println(sortedTreeSet);
24 }
25 catch(Exception e) {}
26 }
27 }
We have implemented both, the ‘HashSet’ and the ‘TreeSet’. We can see the difference in the following output:
1 //output 9.1
2
3 HashSet does not sort the order: [1, 65, 25, 44, 78]
4 TreeSet sort the order based on values :
5 [1, 25, 44, 65, 78]
There is another implementation, called ‘LinkedHashSet’, which is implemented as a hash table with a linked list running through it. This implementation maintains the order in a different way. As we insert new element, the insertion-order is maintained.
We have started this section with a question, why Set is important in data structures?
A one-line answer is, we can take any Collection containing duplicate elements and convert it to another Collection removing all the duplicate elements. We can do that by implementing the Set discrete mathematical abstraction.
How Symmetric Difference and Propositional Logic combine
The very conception of Symmetric Difference does not exist without the Set abstraction.
Based on that, we can easily implement that abstraction in our Java code.
In general, the symmetric difference of two Sets mean a new Set, where duplication is nonexistent.
1 //code 9.2
2
3 package chapternine;
4
5 import java.util.HashSet;
6 import java.util.Set;
7
8 public class SecondCodeExample {
9
10 public static void main(String[] args) {
11
12 Set<String> uniqueSet = new HashSet<String>();
13 Set<String> duplicateSet = new HashSet<String>();
14
15 String[] ourArguments = {"I", "saw", "Mary", "I", "left", "Mary", "stayed"};
16 for (String a : ourArguments){
17 if (!uniqueSet.add(a)){
18 duplicateSet.add(a);
19 }
20 }
21
22 System.out.println("Applying Symmetric Difference abstraction : ");
23 uniqueSet.removeAll(duplicateSet);
24
25 System.out.println("Unique words in unique Set: " + uniqueSet);
26 System.out.println("Duplicate words in unique set: " + duplicateSet);
27
28 }
29 }
What kind of output we can expect here? The arguments we have passed possess unique words, as well as duplicate words. We have tried to identify both the unique words, and the duplicate words. After that, we have produced them in the following output.
1 //output 9.2
2
3 Applying Symmetric Difference abstraction :
4 Unique words in unique Set: [left, stayed, saw]
5 Duplicate words in unique set: [I, Mary]
We have implemented the symmetric difference abstraction in a different way. Implementing the same abstraction in a different way, may have produced only the discrete words, without duplication.
We can use a few other Set Symmetric Difference; however, we need to understand other Set algebraic operations. To do that, we can write a simple Java code that will show us how the implementation of Set abstraction does not allow duplication.
1 //code 9.3
2
3 package chapternine;
4
5 import java.util.HashSet;
6 import java.util.Set;
7
8 public class ThirdCodeExample {
9
10 public static void main(String[] args) {
11
12 Set<String> hashSetExample = new HashSet<String>();
13 hashSetExample.add("Sanjib");
14 hashSetExample.add("Sanjib");
15 hashSetExample.add("Sanjib");
16 hashSetExample.add("Sanjib");
17 hashSetExample.add("Sanjib");
18 System.out.println("HashSet does not allow duplication, we will get one outp\
19 ut: ");
20 System.out.println(hashSetExample);
21 }
22 }
The output is quite expected. The Set will not allow duplication. Therefore, repeated entry of same element will not be stored.
1 //output 9.3
2
3 HashSet does not allow duplication, we will get one output:
4 [Sanjib]
In discrete mathematical paradigms, Set abstraction is basically chaotic, and unordered. But it makes the difference in one area. No duplicate element is allowed in the world of Set. The next code snippet and its output will show you the same property.
1 //code 9.4
2
3 package chapternine;
4
5 import java.util.HashSet;
6 import java.util.Set;
7
8 public class ThirdCodeExample {
9
10 public static void main(String[] args) {
11
12 Set<String> hashSetExample = new HashSet<String>();
13 hashSetExample.add("Sanjib");
14 hashSetExample.add("Json");
15 hashSetExample.add("John");
16 hashSetExample.add("Sanjib");
17 hashSetExample.add("Austin");
18 hashSetExample.add("Bob");
19 System.out.println("HashSet is an unordered list: ");
20 System.out.println("HashSet also does not allow duplication; we will get one\
21 Sanjib: ");
22 System.out.println(hashSetExample);
23 }
24 }
25
26
27 //output 9.4
28
29 HashSet is an unordered list:
30 HashSet also does not allow duplication; we will get one Sanjib:
31 [Bob, John, Json, Austin, Sanjib]
For the Java enthusiasts we will write the same code again,to show that different types of output can be produced. In fact, every high level language has many ways to produce an output.
1 //code 9.5
2
3 package chapternine;
4
5 import java.util.HashSet;
6 import java.util.Set;
7
8 public class ThirdCodeExample {
9
10 public static void main(String[] args) {
11
12 Set<String> hashSetExample = new HashSet<String>();
13 hashSetExample.add("Sanjib");
14 hashSetExample.add("Json");
15 hashSetExample.add("John");
16 hashSetExample.add("Sanjib");
17 hashSetExample.add("Austin");
18 hashSetExample.add("Bob");
19 System.out.println("HashSet is an unordered list: ");
20 System.out.println("HashSet also does not allow duplication; we will get one\
21 Sanjib: ");
22 System.out.println(hashSetExample);
23 System.out.println();
24 for (String name : hashSetExample){
25 System.out.println(name);
26 }
27 System.out.println();
28 hashSetExample.forEach(System.out::println);
29 }
30 }
31
32
33 //output 9.5
34
35 HashSet is an unordered list:
36 HashSet also does not allow duplication; we will get one Sanjib:
37 [Bob, John, Json, Austin, Sanjib]
38
39 Bob
40 John
41 Json
42 Austin
43 Sanjib
44
45 Bob
46 John
47 Json
48 Austin
49 Sanjib
When the implementation type is ‘HashSet’, there is no guarantee that the order will be maintained. However, if we want the list in alphabetical order, we can always use the ‘TreeSet’ implementation along with the ‘HashSet’. Changing the implementation makes our Set abstraction more robust.
1 //code 9.6
2
3 package chapternine;
4
5 import java.util.HashSet;
6 import java.util.Set;
7 import java.util.TreeSet;
8
9 public class FourthCodeExample {
10
11 public static void main(String[] args) {
12
13 Set<String> hashSetExample = new HashSet<String>();
14 hashSetExample.add("Sanjib");
15 hashSetExample.add("Json");
16 hashSetExample.add("John");
17 hashSetExample.add("Sanjib");
18 hashSetExample.add("Austin");
19 hashSetExample.add("Bob");
20 System.out.println("Unordered HashSet output of names: ");
21 System.out.println(hashSetExample);
22 System.out.println();
23 TreeSet sortedTreeSet = new TreeSet<String>(hashSetExample);
24 System.out.println("TreeSet has sorted the order based on values :");
25 System.out.println(sortedTreeSet);
26 }
27 }
28
29
30 //output 9.6
31
32 Unordered HashSet output of names:
33 [Bob, John, Json, Austin, Sanjib]
34
35 TreeSet has sorted the order based on values :
36 [Austin, Bob, John, Json, Sanjib]
When a Set is not equal to another Set, in mathematics we use a special symbol. This inequality symbol is a representation of XOR, which is actually inequality on Boolean.
Here, in this part of Set implementation, the Propositional Logic is also implemented. It is a part of Set mathematical abstraction, just like Symmetric Difference.
I write regularly on Algorithm and Data Structure in
QUIZZ on Chapter Nine
Question 1: We cannot find Symmetric Difference of two Sets without implementing Propositional Logic.
Option 1: True
Option 2: False
Answer: Option 1
========================
Question 2: If two different Sets contain duplicate numbers, the symmetric difference will easily point out those numbers.
Option 1: It is true only for Discrete Mathematics.
Option 2: It is true only for Discrete Mathematics, and as well as all programming languages.
Option 3: It is neither true for Discrete Mathematics, nor for any programming language.
Option 4: None of the above statement is true.
Answer: Option 2.
=======================
Question 3: We can take any Collection containing duplicate elements and convert it to another Collection removing all the duplicate elements.
Option 1: True
Option 2: False
Answer: Option 1
========================
Question 4: In Java Collection framework, a Set is a Collection that cannot contain duplicate elements.
Option 1: The above statement does not make any sense because Set is completely different concept.
Option 2: The above statement is partly true.
Option 3: It models the mathematical Set abstraction, Symmetric difference and Propositional logic one behind the other.
Option 4: None of the above statement is true.
Answer: Option 3
=======================
Challenge 1 : Why the Set implementation ‘HashSet’ is better than the general-purpose Set implementation ‘TreeSet’? Can you compare and prove that?
Solution to Challenge 1 :
Language Used: Java
1 //code
2
3 package chapternine;
4
5 import java.util.HashSet;
6 import java.util.Set;
7 import java.util.TreeSet;
8
9 public class FirstCodeSample {
10
11 public static void main(String[] args) {
12
13 int countingIntegers[] = {25, 44, 78, 1, 65, 3};
14 Set<Integer> hashSet = new HashSet<Integer>();
15 try {
16 for(int i = 0; i < 5; i++) {
17 hashSet.add(countingIntegers[i]);
18 }
19 System.out.println("HashSet does not sort the order: " + hashSet);
20
21 TreeSet sortedTreeSet = new TreeSet<Integer>(hashSet);
22 System.out.println("TreeSet sort the order based on values :");
23 System.out.println(sortedTreeSet);
24 }
25 catch(Exception e) {}
26 }
27 }
28
29
30 // We have implemented both, the ‘HashSet’ and the ‘TreeSet’. We can see the differe\
31 nce in the following output:
32
33
34 //output 9.1
35
36 HashSet does not sort the order: [1, 65, 25, 44, 78]
37 TreeSet sort the order based on values :
38 [1, 25, 44, 65, 78]
’’’’’’’’’'’EXPLANATION ‘’’’’’’’’’’’
Although the ‘TreeSet’ maintains the order of elements based on their values. But implementation of ‘TreeSet’ comes at a higher cost. It is slower than the other Set implementation ‘HashSet’, which stores data in a hash table and maintains the time complexity.
’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’
Challenge 2 : Can you combine Symmetric Difference and Propositional Logic in one program? You can write it in any programming language.
Solution to Challenge 2 :
Language Used: Java
1 //code
2
3 package chapternine;
4
5 import java.util.HashSet;
6 import java.util.Set;
7
8 public class SecondCodeExample {
9
10 public static void main(String[] args) {
11
12 Set<String> uniqueSet = new HashSet<String>();
13 Set<String> duplicateSet = new HashSet<String>();
14
15 String[] ourArguments = {"I", "saw", "Mary", "I", "left", "Mary", "stayed"};
16 for (String a : ourArguments){
17 if (!uniqueSet.add(a)){
18 duplicateSet.add(a);
19 }
20 }
21
22 System.out.println("Applying Symmetric Difference abstraction : ");
23 uniqueSet.removeAll(duplicateSet);
24
25 System.out.println("Unique words in unique Set: " + uniqueSet);
26 System.out.println("Duplicate words in unique set: " + duplicateSet);
27
28 }
29 }
30
31 //output
32
33 Applying Symmetric Difference abstraction :
34 Unique words in unique Set: [left, stayed, saw]
35 Duplicate words in unique set: [I, Mary]
’’’’’’’’’’’’’'’EXPLANATION’’’’’’’’’’’’’’’’’’’’’’’’
The arguments we have passed possess unique words, as well as duplicate words. We have tried to identify both the unique words, and the duplicate words. The symmetric difference of two Sets mean a new Set, where duplication is nonexistent. The implementation of Set abstraction does not allow duplication.
’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’’
Challenge 3 : In discrete mathematical paradigms, Set abstraction is basically chaotic, and unordered. However, no duplicate element is allowed in the world of Set. Can you prove it?
Solution to Challenge 3 :
Language Used: Java
1 //code
2
3 package chapternine;
4
5 import java.util.HashSet;
6 import java.util.Set;
7
8 public class ThirdCodeExample {
9
10 public static void main(String[] args) {
11
12 Set<String> hashSetExample = new HashSet<String>();
13 hashSetExample.add("Sanjib");
14 hashSetExample.add("Json");
15 hashSetExample.add("John");
16 hashSetExample.add("Sanjib");
17 hashSetExample.add("Austin");
18 hashSetExample.add("Bob");
19 System.out.println("HashSet is an unordered list: ");
20 System.out.println("HashSet also does not allow duplication; we will get one\
21 Sanjib: ");
22 System.out.println(hashSetExample);
23 }
24 }
25
26
27 //output
28
29 HashSet is an unordered list:
30 HashSet also does not allow duplication; we will get one Sanjib:
31 [Bob, John, Json, Austin, Sanjib]