Okay, so second and last lecture of the week's material, and we are going to be looking more at logical equivalences, and we're going to look at a very almost complete list of logical equivalences, and the rest of them are generated from these, but they correspond very nicely with the same laws of Boolean. algebra that we saw earlier. So I will just what we will do is I will remind you of what a logical equivalence is and then we shall look at a few of the laws of propositional logic and you can see that they really are going to correspond very nicely with those from billion algebra. Recall that two propositions and we'll call them R and S are logically equivalent so logically equiv propositions if They have the same truth value no matter what the input.
So no matter the truth value of any propositions they might depend on. So one of the most important, because it connects a symbol that we have introduced in propositional logic for kind of allowing us to move from the truth of one statement to another, namely the conditional. So we can actually relate the conditional back to something just involving or. and not.
And we might have gone through this, but let's have another look at it. So if you look at P implies Q and not P or Q. So if that's my R and that's my S, then these two are logically equivalent.
So R and S are logically equivalent. And how do we check whether they're logically equivalent? Well, we just write out their truth tables, and then we look at the...
So there could be, in this case, there were two things that they depend on, but there could be three and... or more. And, uh...
We will just list out all the different possible P's and Q's, truth values of P and Q, and then see whether they agree on each one of them. Well, we can kind of do this a little bit quicker in a truth table if we remember that this is only false if P is true and Q is false. So, recall, p implies q is only false when p is true, but q is false.
Okay, well, let's look at the other side here. So, the only time that... if you have something or something is false, the only time that happens is when they're both false.
But what happens when they're both false? Well, we get that P is true and Q is false. So not P or Q is only false.
when not P is true and Q, so not P is false and Q is false. And that happens exactly when not P is true. So if and only if P is true. But Q is false, which is the same statement as we've written above. So, with that in mind, we can now have a look at the laws of propositional logic.
And we can hopefully notice quite a few similarities between the laws of Boolean logic. And the first that you notice is the commutative law. So, P and Q is the same as Q and P. And you might ask why is that?
Well, fundamentally it comes down to what happened when we defined the truth table of P and Q. And that doesn't depend on which way round P and Q are. And neither does P or Q. These are both the same, no matter which way round you put them.
you get the same truth table. So these are logically equivalent. The idempotent laws should not be too surprising.
If you want p to be true and you want p to be true, that's the same thing as saying that p is true. Similarly, saying p is true or q is true is the same thing as saying p is true. The associative laws... we would need to, we would actually need to write down the truth table of these.
But if you think of this, and so the notation is made to be quite similar because they are supposed to be similar. If you think about what happens when you're looking at a Venn diagram of three things, it doesn't matter what order you... say that you want to do the intersections in, you always end up at the same place. So let's just have a look at that quickly.
So another example of the connection between... We'll just call it subsets and propositions. So if I take the intersection of P and Q and R, it doesn't matter if I take the intersection of Q and R to start with, and then I intersect with P, I end up with this middle bit.
Or if I do the intersection of P and Q to start with, in which case I will get this bit. And then if I take the intersection with R, I will still end up in the middle. So it's quite obvious from the Venn diagram that you're going to get the same thing, no matter which brackets you collapse first. So I'll just put that there.
And the shaded area is, I'll sort of put it in a thing so it's sort of obvious, the shaded area is P. intersect Q, intersect R, and it doesn't matter which way around you do the intersections, you get the same thing. And this law of Boolean algebra corresponds to the commutative law that we've just seen. P and Q and R is logically equivalent to P and Q. and R.
Okay, so the rest of these are all very similar and some of the exercises will be just to establish some of these for yourself using truth tables or just by connecting them with the laws of Boolean logic. I suppose one thing to notice is that We have an extra symbol here, which is this conditional, so P implies Q. And we just talked about 9 here. So if you have a look at line 9, we've just gone through that one. But you can get these other laws of propositional logic in the same way.
So P, if and only if Q, is the same thing as having... p implies q and q implies p so this is quite a good thing to remember when you're trying to show something is true if and only if something else is true you have to if you're going to do it properly you need to assume p is true and then and then prove that q is true using that and then you have to do it backwards you have to prove that Q is true implies that P is true as well. And so some of these things are quite helpful for just reminding yourself what is important when you're proving things. Right, I think I shall stop there.
But this can be all picked up in some exercises.