Which of the following logical expressions are equivalent:

1.        p && ( q && r)
2.        (p && !q) || (p && !r)
3.        (p || (!q && !r) )
4.        (p && q) && r
5.        (p && q) && (p &&r )
6.        (p || q) && r
7.        p || (q && r)
8.        p || !(q || r)
9.        p || ( q && ! r) 

============
MY SOLUTION:
============

// This can be done through visual inspection, but writing a program for it
// as well is just that much more awesome, and I couldn't resist.
// 
// By visual inspection, each statement can be reduced to the following:
// 1) PQR
// 2) PQ'+PR' = P(Q'+R') = P(QR)'
// 3) P+(Q'R')
// 4) PQR
// 5) PQR
// 6) R(P+Q)
// 7) P+QR
// 8) P+(Q'R')
// 9) P+QR'
// 
// Statements 1, 4, and 5 are the same expression, as are 3 and 8.
// But why mess around with boolean algebra when a computer can do it for you?

#include <iostream>
using namespace std;

bool eval(int statement, int p, int q, int r) {
	switch (statement) {
		case 1: return (p && (q && r)); break;
		case 2: return ((p && !q) || (p && !r)); break;
		case 3: return (p || (!q && !r)); break;
		case 4: return ((p && q) && r); break;
		case 5: return ((p && q) && (p && r)); break;
		case 6: return ((p || q) && r); break;
		case 7: return (p || (q && r)); break;
		case 8: return (p || !(q || r)); break;
		case 9: return (p || (q && !r)); break;
	}
}

// a very simplistic exponentiation function that works only with positive integers
unsigned int pow(int base, int power) {
	if (power == 0) { return 1; }
	unsigned int result = base;
	for(int i = 1; i < power; i++) { result = result * base; }
	return result;
}

int main() {
	// the truth table for each of the nine statements can be represented linearly,
	// but because there is also a 1-to-1 mapping of a specific sequence of 1's and 0's
	// to an integer, it'll be easier to simply note this one integer as a sort of
	// compressed truth table
	// e.g. '11' is actually 00001011, which is true for P'Q'R, P'QR', and P'QR

	int truth[9] = { 0 };

	// crank out truth tables
	for (int s = 0; s < 9; s++) {
		for (int p = 0; p <= 1; p++) {
			for (int q = 0; q <= 1; q++) {
				for (int r = 0; r <= 1; r++) {
					truth[s] += (int)eval(s+1, p, q, r) * pow(2, 4*p + 2*q + r);
	}	}	}	}
	
	// see if any two are the same
	for (int i = 0; i < 8; i++) {
		for (int j = i+1; j < 9; j++) {
			if (truth[i] == truth[j]) { cout << "Statements " << i+1 << " and " << j+1 << " are equivalent.\n"; }
	}	}
	
	return 0;
}