£199.99 £139.99 for one year of Unlimited learning. Offer ends on 14 November 2022 at 23:59 (UTC). T&Cs apply

Find out more
Logical equivalence: De Morgan’s law
Skip main navigation

Logical equivalence: De Morgan’s law

In this video, York student Salomé shows how we can test for logical equivalence using a truth-table, demonstrating De Morgan's law.
0
Let’s look at an example of logical equivalence. The example we’ll look at here has a name. It’s called De Morgan’s Law, after a famous logician, Augustus de Morgan. De Morgan’s Law says that ‘(P and Q)’ is logically equivalent to ‘not (not P or not Q)’. If it’s logically equivalent, then it should be that ‘(P and Q)’ entails ‘not (not P or not Q)’ and that ‘not (not P or not Q) entails ‘(P and Q)’. Let’s look at this using a truth table. We start by setting out the four ways things could be with the truth values of ‘P’ and ‘Q’.
49.7
Then we put: ‘(P and Q)’. The truth
58.4
values for that are: true, false, false, false. And now we going to have to do this, [ie. ‘not(not-P or not-Q)] which is a little more complicated. Let’s start with ‘not P’. ‘Not P’ is false, false, true, true. ‘Not Q’ is false, true, false, true. OK. Now,
81.9
not-P or not-Q: False and false [gives] false. False and true [gives] true. True and false [gives] true. True and true [gives] true. And now the last operator, the tilde there. If we have false for the plugged-in clause, we’ll get true under the tilde. If we have true for the clause, we’d get false under the tilde. So, that’s the truth table for this compound sentence. And look, ‘(P and Q)’ on the first line of the truth table is true, and so is our complex sentence. On the second row, they are both false. Third row, both false. On the final row, both false.
116
So you can see the ‘(P and Q)’ is true in exactly the same circumstances as ‘not (not P or not Q)’ and that means they are logically equivalent. Now there are several reforms of the De Morgan’s Law, and you can test some for yourself. One form says ‘(P or Q)’ is equivalent to ‘not (not P and not Q)’. You can see the pattern here. De Morgan’s Law says take a conjunction or a disjunction, change it to the other.
144.4
(If it’s a conjunction change it to a disjunction if it’s a disjunction, change it to a conjunction.) Put a tilde in front of the sentences either side, and then put a tilde in front of the whole clause, and you get something logically equivalent.

This video gives an example of testing for logical equivalence using a truth-table. In this case, we show that ‘(P & Q)’ is logically equivalent to ‘~(~P (vee) ~Q)’. This equivalence is called De Morgan’s Law.

This article is from the free online

Logic: The Language of Truth

Created by
FutureLearn - Learning For Life

Our purpose is to transform access to education.

We offer a diverse selection of courses from leading universities and cultural institutions from around the world. These are delivered one step at a time, and are accessible on mobile, tablet and desktop, so you can fit learning around your life.

We believe learning should be an enjoyable, social experience, so our courses offer the opportunity to discuss what you’re learning with others as you go, helping you make fresh discoveries and form new ideas.
You can unlock new opportunities with unlimited access to hundreds of online short courses for a year by subscribing to our Unlimited package. Build your knowledge with top universities and organisations.

Learn more about how FutureLearn is transforming access to education