Propositional Logic, Truth tables, and Logical Equivalences
This made from latex equations, so please go to website to see it phrase easier. Or try to download the extension called TeX for Gmail:
Use truth tables to show which one is valid
P ∧ (Q ∨ R) ⇔ (P ∧ Q) ∨ (P ∧ R) (Distribution of ∧)
| P | Q | R | (Q ∨ R) | (P ∧ Q) | (P ∧ R) | P ∧ (Q ∨ R) | (P ∧ Q) ∨ (P ∧ R) |
|---|---|---|---|---|---|---|---|
| T | T | T | T | T | T | T | T |
| T | F | F | F | F | F | F | F |
| F | T | F | T | F | F | F | F |
| F | F | T | T | F | F | F | F |
| T | F | F | F | F | F | F | F |
| F | F | T | T | F | F | F | F |
| F | T | F | T | F | F | F | F |
| F | F | F | F | F | F | F | F |
¬(P ∧ Q) ⇔ ¬P ∨ ¬Q (de Morgan's Law)
| P | Q | ¬P | ¬Q | (P ∧ Q) | ¬(P ∧ Q) | ¬P ∨ ¬Q |
|---|---|---|---|---|---|---|
| T | T | F | F | T | F | F |
| T | F | F | T | F | T | T |
| F | T | T | F | F | T | T |
| F | F | T | T | F | T | T |
¬(P ∨ Q) ⇔ ¬P ∧ ¬Q (de Morgan's Law)
| P | Q | ¬P | ¬Q | (P ∨ Q) | ¬(P ∨ Q) | ¬P ∧ ¬Q |
|---|---|---|---|---|---|---|
| T | T | F | F | T | F | F |
| T | F | F | T | T | F | F |
| F | T | T | F | T | F | F |
| F | F | T | T | F | T | T |
(P ⇒ Q) ⇔ (¬Q ⇒ ¬P) (Contraposition)
| P | Q | ¬P | ¬Q | (P ⇒ Q) | (¬Q ⇒ ¬P) |
|---|---|---|---|---|---|
| T | T | F | F | T | T |
| T | F | F | T | F | F |
| F | T | T | F | T | T |
| F | F | T | T | T | T |
Decide whether each of the following sentences is valid, unsatisfiable, or neither.
Verify your decisions using truth tables or the equivalence rules from the lecture.
a. Smoke ⇒ Smoke
| Smoke | Smoke |
|---|---|
| T | T |
| F | T |
b. Smoke ⇒ Fire
| Smoke | Fire | Smoke ⇒ Fire |
|---|---|---|
| T | T | T |
| F | T | T |
| T | F | F |
| F | F | T |
c. (Smoke ⇒ Fire) ⇒ (¬Smoke ⇒ ¬Fire)
| Smoke | Fire | ¬Smoke | ¬Fire | (Smoke ⇒ Fire) | (¬Smoke ⇒ ¬Fire) | (Smoke ⇒ Fire) ⇒ (¬Smoke ⇒ ¬Fire) |
|---|---|---|---|---|---|---|
| T | T | F | F | T | T | T |
| F | T | T | F | T | F | F |
| T | F | F | T | F | T | T |
| F | F | T | T | T | T | T |
d. Smoke ∨ Fire ∨ ¬Fire
| Smoke | Fire | ¬Fire | Smoke ∨ Fire ∨ ¬Fire |
|---|---|---|---|
| T | T | F | T |
| F | T | F | T |
| T | F | T | T |
| F | F | T | T |
e. ((Smoke ∧ Heat) ⇒ Fire) ⇔ ((Smoke ⇒ Fire) ∨ (Heat ⇒ Fire))
| Smoke | Heat | Fire | (Smoke ∧ Heat) | (Smoke ⇒ Fire) | (Heat ⇒ Fire) | ((Smoke ∧ Heat) ⇒ Fire) | ((Smoke ⇒ Fire) ∨ (Heat ⇒ Fire)) |
|---|---|---|---|---|---|---|---|
| T | T | T | T | T | T | T | T |
| T | F | F | F | F | T | T | T |
| F | T | F | F | T | F | T | T |
| F | F | T | F | T | T | T | T |
| T | F | F | F | F | T | T | T |
| F | F | T | F | T | T | T | T |
| F | T | F | F | T | F | T | T |
| F | F | F | F | T | T | T | T |
f. (Smoke ⇒ Fire) ⇒ ((Smoke ∧ Heat) ⇒ Fire)
| Smoke | Heat | Fire | (Smoke ⇒ Fire) | (Smoke ∧ Heat) | ((Smoke ∧ Heat) ⇒ Fire) | (Smoke ⇒ Fire) ⇒ ((Smoke ∧ Heat) ⇒ Fire) |
|---|---|---|---|---|---|---|
| T | T | T | T | T | T | T |
| T | F | F | F | F | T | T |
| F | T | F | T | F | T | T |
| F | F | T | T | F | T | T |
| T | F | F | F | F | T | T |
| F | F | T | T | F | T | T |
| F | T | F | T | F | T | T |
| F | F | F | T | F | T | T |
g. Big ∨ Dumb ∨ (Big ⇒ Dumb)
| Big | Dumb | (Big ⇒ Dumb) | Big ∨ Dumb ∨ (Big ⇒ Dumb) |
|---|---|---|---|
| T | T | T | T |
| F | T | T | T |
| T | F | F | T |
| F | F | T | T |
h. (Big ∧ Dumb) ∨ ¬Dumb
| Big | Dumb | ¬Dumb | (Big ∧ Dumb) | (Big ∧ Dumb) ∨ ¬Dumb |
|---|---|---|---|---|
| T | T | F | T | T |
| F | T | F | F | F |
| T | F | T | F | T |
| F | F | T | F | T |
Represent the following sentences in propositional logic.
Can you use truth table to determine whether or not the unicorn is mythical? What about magical? Horned?
If the unicorn is mythical, then it is immortal, but if it is not mythical, then it is a mortal mammal. If the unicorn is either immortal or a mammal, then it is horned. The unicorn is magical if it is horned.
x: the unicorn is mythical
¬y: the unicorn is immortal
¬x: the unicorn is not mythical
y: the unicorn is a mortal
r: the unicorn is a mammal
z: he unicorn is horned
o: The unicorn is magical
If the unicorn is mythical, then it is immortal x ⇒ ¬y
but if it is not mythical, then it is a mortal mammal ¬x ⇒ y ∧ r
If the unicorn is either immortal or a mammal, then it is horned ¬y ∨ r ⇒ z
The unicorn is magical if it is horned z ⇒ o
This 5 variables, means 2^5 = 32 means there will be a complication of T and F, so I need to do binary instead of, in order to make the work easier
T means 1, F means 0, the truth table in binary shows below:
00000
00001
00010
00011
=4
00100
00101
00110
00111
=4
01000
01001
01010
01011
01100
01101
01110
01111
= 8
10000
10001
10010
10011
10100
10101
10110
10111
11000
11001
11010
11011
11100
11101
11110
11111
=16
= 4 + 4 + 8 + 16 = 16 + 16 = 32
| x | y | z | r | o | ¬x | ¬y | x ⇒ y | ¬x ⇒ z | y ∨ z | y ∨ z ⇒ r | r ⇒ o |
|---|---|---|---|---|---|---|---|---|---|---|---|
| F | F | F | F | F | T | T | T | F | F | T | T |
| F | F | F | F | T | T | T | T | F | F | T | T |
| F | F | F | T | F | T | T | T | F | F | T | F |
| F | F | F | T | T | T | T | T | F | F | T | T |
| F | F | T | F | F | T | T | T | T | T | F | T |
| F | F | T | F | T | T | T | T | T | T | F | T |
| F | F | T | T | F | T | T | T | T | T | T | F |
| F | F | T | T | T | T | T | T | T | T | T | T |
| F | T | F | F | F | T | F | T | F | T | F | T |
| F | T | F | F | T | T | F | T | F | T | F | T |
| F | T | F | T | F | T | F | T | F | T | T | F |
| F | T | F | T | T | T | F | T | F | T | T | T |
| F | T | T | F | F | T | F | T | T | T | F | T |
| F | T | T | F | T | T | F | T | T | T | F | T |
| F | T | T | T | F | T | F | T | T | T | T | F |
| F | T | T | T | T | T | F | T | T | T | T | T |
| T | F | F | F | F | F | T | F | T | F | T | T |
| T | F | F | F | T | F | T | F | T | F | T | T |
| T | F | F | T | F | F | T | F | T | F | T | F |
| T | F | F | T | T | F | T | F | T | F | T | T |
| T | F | T | F | F | F | T | F | T | T | F | T |
| T | F | T | F | T | F | T | F | T | T | F | T |
| T | F | T | T | F | F | T | F | T | T | T | F |
| T | F | T | T | T | F | T | F | T | T | T | T |
| T | T | F | F | F | F | F | T | T | F | T | T |
| T | T | F | F | T | F | F | T | T | F | T | T |
| T | T | F | T | F | F | F | T | T | F | T | F |
| T | T | F | T | T | F | F | T | T | F | T | T |
| T | T | T | F | F | F | F | T | T | T | F | T |
| T | T | T | F | T | F | F | T | T | T | F | T |
| T | T | T | T | F | F | F | T | T | T | T | F |
| T | T | T | T | T | F | F | T | T | T | T | T |
Logical Equivalence
a. For each of the following, find a satisfying truth assignment, (values of the propositions which make the formula true), if any exists.
- ((a⇒ ¬b)∧a)
- (((a⇒c) ⇒ ¬b)∧(a∨b))
- (a⇒ ¬b)∧a)
(¬a v ¬b) ∧ a)
((a ∧ ¬a) v (a ∧ ¬b))
False v (a ∧ ¬b)
Means that:
a = T
b = F
- (((a⇒c) ⇒ ¬b)∧(a∨b))
(a⇒c) = (¬a ∨ c)
((a⇒c) ⇒ ¬b) = ((¬a ∨ c) ⇒ ¬b) = (¬(¬a ∨ c) ∨ ¬b) = (a ∧ ¬c) ∨ ¬b
(((a⇒c) ⇒ ¬b)∧(a∨b)) = ((a ∧ ¬c) ∨ ¬b) ∧ (a∨b)
Referring from the 1.
a = T
b = F
((a ∧ ¬c) ∨ ¬b) ∧ (a∨b)
(( T ∧ ¬c) ∨ T) ∧ (T∨F)
We need to replace c = F, so:
(( T ∧ ¬F) ∨ T) ∧ (T∨F)
((T ∧ T) ∨ T) ∧ (T∨F)
(T ∧ T) ∨ T) = T
(T∨F) = T
=> T ∧ T = T
So c = F
b. For each of the following, find a falsifying truth assignment, (values of the propositions which make the formula false), if any exists.
- ((a⇒ ¬b)∨a)
(a⇒ ¬b)∨a)
(¬a ∨ ¬b) ∨ a)
¬a ∨ ¬b v a
(¬a v a) v ¬b
True v ¬b ( tautology mean always True)
Means there is no falsifying assignment
- ((¬b⇒ (a⇒c))∨(a∧b))
(a⇒c) = (¬a ∨ c)
(¬b⇒ (¬a ∨ c)) = b ∨ (¬a ∨ c) = b ∨ ¬a ∨ c
(b ∨ ¬a ∨ c) ∨ (a∧b)
when F v F, means
(b ∨ ¬a ∨ c) = F => b;c = False, a=True
(a∧b) = F => a = True, b = False