Okay, we will be looking at tautologies, contradictions and logical equivalences in this lecture, which gives us an opportunity to write out a couple more truth tables, because there's always good practice to be had when doing this type of stuff. So, tautologies. So it comes from the Greek word which means that you've said it already. So it's kind of like a redundant piece of an argument.
It's already been established. But it has a slightly different meaning and logic. Let's just consider the truth table. for two propositions.
So we'll take, we'll just say p is a proposition, could any statement you like at all. So p or not p. I think we can see immediately.
that this is going to be something that's always true because if you know either it's true or it's negative is true well then at least one of them has to be so um but let's just do the truth table for that we would get we only have one proposition so we only have two things to check namely namely when it's true and when it's false and then of course not p will give you false and true just swaps them over and p or not p we can now calculate so this is true whenever at least one of them is true so this one or this one is true so this one's true so it's true and this one's true so it's true okay now when you have this last column being all true then we call it a tautology Let's have, okay, let's just put that there, and then let's do another one, one that contains two statements. So we'll do P, and P implies Q, implies Q. Right, so you could say, well, I think, yeah, think of this this way. If p is true, and you know that whenever p is true, q is true, it is the case that from that you can deduce that q is true.
This is actually a well-known part of kind of logical argument that was known to the ancient Greeks called modus ponens so this is it's actually a Latin it means like the art of um it means the the method of um of inference basically um so uh but let's let's just let's not think about that now let's just write out truth table. So I'm going to do P Q, there'll be four possibilities. I'll do P implies Q, I'll do P and P implies Q, and then I'll do the final thing.
So that'll be star and that'll go in the final column. So let's build this up. So we're going to have true true true false false true false false Right, so let's just write out when, you know, build this up bit by bit.
So P implies Q. Now the only time that is false is when you know that P is true, but Q turns out to be false. So it's true here, it's false here, but it's true in all the other places. Okay, just the definition of that.
Right, so now we want... P, we know P is true and we know that P implies Q. So let's see when that's true.
So P is true, P implies Q is true. P is true, P implies Q is false, that's false. P is false, P implies Q, well that's still false.
P is false. P implies Q is true. So that is false.
OK, now we need to look at this column and we want to take the implies of this column with Q. So again, if we've got just this together. Whatever this is and it implies Q, the only time that's wrong is when this is false but this is true.
So we want to look for when that's true, when that's true and work it out from there. So here it's true and Q is true so we're true. Otherwise this first thing is false. So always this has to be true.
Okay. And so this is a tautology. Another tautology we could come up with, and this is relevant because it's called the law of the excluded middle, is that P...
is equivalent to not not P. So if it's not raining, if it's raining as a statement and then I say well it's not not raining, would be the same thing as saying it is raining. Okay so tautologies that's what you do in almost all cases you're just going to be writing out the truth table for these things and then you just see whether the last column is all true or not. There is a similar thing which is the sort of false version of tautologies. So tautologies are always true, contradictions are always false.
So contradiction is, you're saying something which goes against what's already been said. So this is the same thing, but the last column is always false. So a good example, if we're doing like it's raining or it's not raining, well what if we say it's raining and it's not raining? So P and not P.
We could write out the truth table for that. P not P, and then P and not P. So we're going to get true, we're going to get false, we're going to get false and true, and then this is true.
when this and this are true. But this and this, no, one of them is wrong. This and this, no, one of them is wrong. So when you get the final line, the final column of the thing that you're working out, when it's all false, this is a contradiction. Okay.
So those are some opportunities to just write out some more truth tables and you will get the those will be in in the tutorial sheets. Okay one more one more A concept that I would like to discuss, which is when you're comparing two propositions, it can be the case that they are true exactly at the same time. I'll just say that and then we'll do an example. So if some proposition, and let's call it R.
is true exactly when some proposition S is true, then they are logically equivalent. Logically equivalent. So I'll go for logic equiv.
Okay, so best thing to do is let's take an example. So we're going to take the two statements not of P and Q. and not of P or not of Q. And we're going to see that they are the same.
This is, I think, basically... De Morgan's law if you remember that from the table of Boolean algebra you will find essentially this same statement but let's not worry about it let's just draw out the two truth tables. So we've got P, we've got Q, and then we've got not.
Let's do it bit by bit, P and Q, and then let's do not of P and Q. So we've got true, true, true, false, false, true, false, false. And here these are true.
This is this and this. So it's only true whenever both of them are true. But it is there. And then all of the rest of them it is false. And then if I want to take the not of that then I just have to reverse all these.
So And now let's do this second one. Not P or not Q. P, Q. Not P or not Q.
I think we'll just do it all at once. So true, false, true, true, true, false, false, true, false, false. Those are my four options.
and then I just want to work out what this is. So not P would be false, not Q would be false. Is one or other of these true?
No. Otherwise, one of them, because one of these is false, one of these is going to be true, and so the rest of them are true. Okay. And so these two statements are logically equivalent. So they are true at exactly the same time.
Okay, in the next session we will look at the laws of propositional logic, which are all going to be a series of logical equivalences. And they'll correspond exactly to the table that you saw for the Boolean algebra.