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!

Software for students

For new computing students finding affordable, legitimate software and tools to get started with course content, personal projects and solutions for software development competitions (e.g. Imagine Cup and Teleios Code Jam) may be a challenge. Nigel Sammy has compiled a list of options for Microsoft software and tools on his blog:

Nigel Sammy - Blog: Free Microsoft Software and Tools: Before you get too excited this isn't a situation where I am giving away any software. It also is not a promotion or a scam, it is about legitimate sites and programs that offer Microsoft software and tools for various time periods...

Learn about industry

When students are studying full-time they may not necessarily think about the industry or job market they will be entering. The primary focus is usually the immediate future and the immediate future is usually some deadline for an assignment or exam. It can be useful to be aware of what roles exist, have a sense of the responsibilities of each role, have an idea of which roles appeal to you and what are the skills employers typically request. It also helps to know about recent developments are in your field.

There are convenient ways to get this information. If you are a user of social media, then let social media work for you. On Facebook, Twitter and LinkedIn you can like and follow thought leaders, groups, agencies and companies in your field. Subscribe to job alerts on recruitment websites or companies for which you would like to work. Some companies even offer programmes for recent graduates, so do a bit of research to see what opportunities may become available to you upon graduation. Of course there's always the traditional route of browsing your daily newspaper.

The suggestions may seem pretty obvious to some but they are often overlooked by many students simply because it's not the current focus. For my IT students here are a few recommendations to get started:

• Microsoft Trinidad and Tobago
• Trinidad and Tobago SQL Server User Group
• Trinidad and Tobago Computing Society
• Caribbean Jobs
• Government Human Resource Services

Why would you leave an exam early?

As a student, and more so now as an instructor, it baffles me when I see students leave an examination early. Did they suddenly take ill? No. Did they get a perfect score? Negative. Is there some prize for leaving early? None. Then why did they leave?

Even when you think you've answered every question to the best of your ability, the remaining time can still be used to review your work, as many times as your time allows. Reviewing your work begins with the question, not with your solution. Reread the questions and ensure that they were interpreted correctly. Then review the solutions, redoing calculations where applicable. Mistakes can be made when using a calculator too! In some cases it is even possible to verify that the answer found is correct (e.g. by using another method or substituting the results to ensure that they satisfy all parts of the question.) Maybe in your haste your penmanship deteriorated. In this case you can use the time to rewrite parts of your solution more legibly.

Even when you draw a complete blank in an exam, it is in your best interest to stay. Take a few deep breaths and calm your nerves, then try the question again. You never know what you can remember unless you take the time to try to remember.

If you are a student who has left an exam early please share your reasons in the comments below.