Lab 03 - Computational Logic

In this assignment, you will write a series of functions for the C++ set class to allow us to treat it more like a mathematical set.

Assignment

Begin with the following starter code:

#include <iostream>
#include <set>

using std::cout;
using std::endl;
using std::set;
using std::ostream;

// Print a set (Don't change this)
ostream & operator << (ostream & out, set<int> theSet) {
    out << "{";

    set<int>::iterator it;
    for(it = theSet.begin(); it != theSet.end(); it++) {
        if(it != theSet.begin())
            out << ", ";

        out << *it;
    }

    out << "}";

    return out;
}

// Print a set of sets (Don't change this either)
ostream & operator << (ostream & out, set< set<int> > theSet) {
    out << "{ ";

    set< set<int> >::iterator it;
    for(it = theSet.begin(); it != theSet.end(); it++) {
        if(it != theSet.begin())
            out << ", ";

        out << *it;
    }

    out << " }";

    return out; 
}

// This function should create a new set that is the union 
// of sets A and B
set<int> setUnion(set<int> & A, set<int> & B) {

    set<int> C;

    // ...

    return C;
}

// This function should create a new set that is the intersection 
// of sets A and B
set<int> setIntersection(set<int> & A, set<int> & B) {

    set<int> C;

    // ...

    return C;
}

// This function should create a new set that is the difference 
// of sets A and B
set<int> setDifference(set<int> & A, set<int> & B) {
    set<int> C;

    // ...

    return C;
}


// This function indicates if the integer x is an element of set A.
bool isElementOf(int x, set<int> & A) {

    // ...
    return false;
}

// This function indicates if set A is a subset of set B.
bool isSubsetOf(set<int> & A, set<int> & B) {

    // ...  
    return false;
}

// This function returns the power set of set A, that is
// the set of all subsets of A.
set< set<int> > powerSet(set<int> & A) {

    set< set<int> > P;

    // ...

    return P;
}


int main() {

    // Build A
    set<int> setA;
    setA.insert(3);
    setA.insert(1);
    setA.insert(4);

    cout << "Should be A = {1, 3, 4}" << endl;
    cout << "A = " << setA << "\n---------" << endl;

    // Build B
    set<int> setB;
    setB.insert(5);
    setB.insert(1); 

    cout << "Should be B = {1, 5}" << endl;
    cout << "B = " << setB << "\n---------" << endl;

    // Union
    set<int> setC = setUnion(setA, setB);
    cout << "Should be: A \u222A B = {1, 3, 4, 5}" << endl;
    cout << "A \u222A B = " << setC << "\n---------" << endl;

    // Element of B
    cout << "Should be 5 is an element of B" << endl;
    if(isElementOf(5, setB))
        cout << "5 is an element of B." << "\n---------" << endl;
    else
        cout << "THIS SHOULDN'T PRINT" << "\n---------" << endl;    

    // Intersection
    set<int> setD = setIntersection(setA, setB);
    cout << "Should be: A \u2229 B = {1}" << endl;
    cout << "A \u2229 B = " << setD << "\n---------" << endl;

    // Difference
    set<int> setE = setDifference(setA, setB);
    cout << "Should Be A - B = {3, 4}" << endl;
    cout << "A - B = " << setE << "\n---------" << endl;

    // Subsets
    cout << "Should be E \u2286 A " << endl;
    if(isSubsetOf(setE, setA))
        cout << "E \u2286 A" << "\n---------" << endl;
    else 
        cout << "THIS SHOULDN'T PRINT" << "\n---------" << endl;


    // Powerset
    // Order doesn't matter, but note the empty set
    set< set<int> > setP = powerSet(setA);
    cout << "Should be P(A) = { {}, {1}, {3}, {4}, {1, 3}, {1, 4}, {3, 4}, {1, 3, 4} }" << endl;
    cout << "P(A) = " << setP << endl;

}

You need to implement the setUnion, setIntersection, isElementOf, isSubsetOf, and powerSet functions. You should not change main.

Grading:

Out of 100 points:

setUnion works: 20 Points
setIntersection works: 30 Points
isElementOf works: 10 Points
isSubsetOf works: 30 Points
powerSet works: 10 Points

Hints

Pay attention to the output statements, they'll help you know how close you are.

Don't copy code from the internet. I'll know.

You can iterate over a set (or any C++ container) using this syntax:

// Create an iterator
set<int>::iterator it;

// Start at the beginning of the set, loop until the iterator points to the end
// and move the iterator forward by one location each run through the loop
for(it = theSet.begin(); it != theSet.end(); it++) {
    // Dereference the iterator with a * to access the thing it points to 
    // (the element of the set in this case).
    cout << *it << endl;
}

The following references might come in handy:

Submission

To submit your assignment, zip the cpp file and upload it to mySVU.

CSC 240