2.3 Discrete Mathematics2.3.2 Logic

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.
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.
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).