Logical Equivalence - A Proof with Predicates

Two statements involving quantifiers and predicates are logically equivalent if and only if they have the same truth values for every assignment of truth values, regardless which predicates are substituted into these statements and which domain is used.

If A and B are logically equivalent we write A ≡ B. Alternatively, A is logically equivalent to B if and only if A ↔ B is a tautology.

We can use this fact about the biconditional to prove two statements are logically equivalent

Example: Prove that ∀x(P(x)⋀Q(x)) ≡∀xP(x) ⋀∀xQ(x).

Proof:

To show that the statements are logically equivalent we need to show ∀x(P(x)⋀Q(x)) ↔ ∀xP(x) ⋀∀xQ(x) is a tautology.

So, we need to show
               ∀x(P(x)⋀Q(x)) → ∀xP(x) ⋀∀xQ(x) is a tautology
and         ∀xP(x) ⋀∀xQ(x) → ∀x(P(x)⋀Q(x)) is a tautology


First, we need to show∀x(P(x)⋀Q(x)) → ∀xP(x) ⋀∀xQ(x) is a tautology.

1.	∀x(P(x)⋀Q(x))	Premise
2.	P(x)⋀Q(x)	Universal Instantiation
3.	P(x)	Simplification
4.	Q(x)	Simplification
5.	∀xP(x)	Universal Generalisation
6.	∀xQ(x)	Universal Generalisation
7.	∀xP(x)⋀∀xQ(x)	Conjunction

Therefore, ∀x(P(x)⋀Q(x)) → ∀xP(x) ⋀∀xQ(x) is a tautology.

Similarly, we need to show∀xP(x) ⋀∀xQ(x) → ∀x(P(x)⋀Q(x)) is a tautology.

1.	∀xP(x)	Premise
2.	∀xQ(x)	Premise
3.	P(x)	Universal Instantiation
4.	Q(x)	Universal Instantiation
5.	P(x)⋀Q(x)	Conjunction
6.	∀x(P(x)⋀Q(x))	Universal Generalisation

Therefore, ∀x(P(x)⋀Q(x)) → ∀xP(x) ⋀∀xQ(x) is a tautology.

Therefore, ∀x(P(x)⋀Q(x)) ↔ ∀xP(x) ⋀∀xQ(x) is a tautology i.e.∀x(P(x)⋀Q(x)) ≡∀xP(x) ⋀∀xQ(x).

Is it time to start thinking about your "summer" break?

It may be time to start thinking about your "summer" break.  I say "summer" but I do acknowledge that depending on your location you may not necessarily refer to that May-August break from university as "summer". It may seem kind of early given that we're still wishing each other Happy New Year (all the best for 2014!) but now is the ideal time to starting thinking and even start setting some plans in motion for your break.

Before you know it the semester will begin and a month in the assignments would have surely started. As the semester progresses assignments and midterms will compete for your time and as the semester draws to a close you will be occupied with preparation for final exams and finally exams. Then ta-da, we'll be in the month of May. You've been here before, you know how time can fly.

Make use of your time now to explore your options, especially if you would like an internship or to work during that period. Check out the websites of notable companies in your field and check whether there are internship or "summer" work programmes. Your university may even have part-time employment options on campus. Start applying for these positions if possible. You may want to take courses (as part of your degree programme or to gain a new skill like learning a new language or cooking!) during this period, check which courses may be offered and note deadlines for registering for them. You don't want to leave these tasks for too late into the semester when there may be a lot on your plate.

Happy planning!