2.3 Discrete Mathematics
2.3.2 Logic
Sources: My Norwegian
pages on logic, Perkal
Also, see my pages on logic programming in C.
A statement is either true (T) or false (F). "The fish is dead" is a statement, whereas "don't be dull" is not.
In logic, we have 3 basic connectives; and, or, not. We can use these to make compound statements.
"The fish is dead and you are beautiful."
"My uncle owns America or you are beautiful."
"I am not from India and you are not dead."
Let p and q be statements. Then, to decide the truth value of a compound statement, we could use a truth table:
| p | q | p or q (p v q) | p and q (p & q) |
| T | T | T | T |
| F | T | T | F |
| T | F | T | F |
| F | F | F | F |
Does 1=1 AND 2=2? Yes, so (T & T) = T.
But does 1=1 AND 3=4? No, so (T & F) = F.
But does 1=1 OR 3=4? Yes, so (T OR F) = T, and so on.
If you compare this to the truth table of Boolean algebras, you will notice they are equivalent.
You can connect as many statements as you want together to form a compound statement. Two compound statements are equivalent if they have the same truth tables.
2.3.2.1 Implication
Let p = "You are beautiful", and let q = "I will be happy",
then
p >
q (p implies q) means "If you are beautiful, then I will be happy".
Now, what is the truth table for p >
q?
Now, if you ARE beautiful, AND I AM happy, then p Þ q is obviously true. But what if you are not beautiful, and I am happy? Well, the only thing I have stated is that if you are beautiful, then I will be happy. I haven't said I won't be happy if you aren't beautiful, now have I? I might be happy for other reasons. Hence, if you aren't beautiful, but I am still happy, p > q is still true! What if you are not beautiful, and I am not happy? Have I lied? No, I haven't said anything about what happens if you are not beautiful, so p Þ q is still true. Last case: what if you are beautiful, and I am not happy? Well, then I have lied, so p > q is false. To sum it up:
| p | q | p > q |
| T | T | T |
| F | T | T |
| F | F | T |
| T | F | F |
Notice that p > q is true when [(p is false) OR (q is true)], which means that p > q = ~p v q
Also notice that if false = 0 and true = 1, then p implies q (p > q) can be calculated with normal mathetmatical operators as follows:
p <= q (p less than or equal to q)
We also have that ~ (p >
q) =
p v
~q, because
~ (p &
q) = ~(~p v
q) as p >
q =
~p v
q
= ~~p v
~q by de
Morgan's Law (q)
= p v
~q
by Double Complement Law (s)
Sometimes, p is called the hypothesis, and q is called the conclusion. From the truth table (and our little discussion), we se that an implication is false only when the hypothesis is true and the conclusion is false.
2.3.2.2 Converse, contrapositive, inverse
Statement: p Þ
q
Converse: q Þ
p
Contrapositive: (~q) Þ
(~p)
Inverse: (~p) Þ
(~q)
If you know Norwegian, you can learn a bit about sentence logic here (Logikk og argumentasjon).
