1.
(a)
| P | Q | -P | ∨ | Q |
| T | T | F | F | F |
| T | F | F | T | T |
| F | T | T | T | F |
| F | F | T | T | T |
(b)
| S | G | (S | ∨ | G) | ∧ | (-S | ∨ | -G) |
| T | T | T | T | T | T | F | F | F |
| T | F | T | T | F | T | F | T | T |
| F | T | F | T | T | T | T | T | F |
| F | F | F | F | F | T | T | T | T |
2.
(a)
| P | Q | -[ | P | ∧ | (Q | ∨ | -P)] |
| T | T | F | T | T | T | T | F |
| T | F | T | T | F | F | F | F |
| F | T | T | F | F | T | T | T |
| F | F | T | F | F | F | T | T |
3.
(a)
| P | Q | P+Q |
| T | T | F |
| T | F | T |
| F | T | T |
| F | F | F |
(b)
P + Q = (P ∧ ¬Q) ∨ (¬P ∧ Q)
Truth table -
| P | Q | P+Q | (P | ∧ | ¬Q) | ∨ | (¬P | ∧ | Q) |
| T | T | F | T | F | F | F | F | F | T |
| T | F | T | T | T | T | T | F | F | F |
| F | T | T | F | F | F | T | T | T | T |
| F | F | F | F | F | T | F | T | F | F |
4.
P ∨ Q
= ¬¬P ∨ ¬¬Q
= ¬ (¬ P ∧ ¬ Q) (De Morgan's Law)
Truth table -
| P | Q | P | ∨ | Q | ¬ ( | ¬ | P | ∧ | ¬ | Q) |
| T | T | T | T | T | T | F | T | F | F | T |
| T | F | T | T | F | T | F | T | F | T | F |
| F | T | F | T | T | T | T | F | F | F | T |
| F | F | F | F | F | F | T | F | T | T | F |
5.
(a)
| P | Q | P ↓ Q |
| T | T | F |
| T | F | F |
| F | T | F |
| F | F | T |
(b)
P ↓ Q = ¬ P ∧¬ Q
= ¬ (P ∨ Q)
Truth table verification -
| P | Q | P ↓ Q | ¬ | (P | ∨ | Q) |
| T | T | F | F | T | T | T |
| T | F | F | F | T | T | F |
| F | T | F | F | F | T | T |
| F | F | T | T | F | F | F |
(c)
(i) ¬P = ¬P ∧ ¬P
= P ↓ P
(ii) P ↓ Q
= (from the previous ones) ¬ (P ∨ Q)
So, (P ∨ Q) = ¬ (P ↓ Q)
= (P ↓ Q) ↓ (P ↓ Q) (from c(i))
(iii) ¬ (P ∧ Q)
= ¬ P ∨ ¬ Q
Hence, (P ∧ Q) = ¬(¬ P ∨ ¬ Q)
= ¬ ((¬P ↓ ¬Q) ↓ (¬P ↓ ¬Q)) (from the previous one)
= ¬ (¬ (¬P ↓ ¬Q)) (from c(i))
= ¬P ↓ ¬Q
= (P ↓ P) ↓ (Q ↓ Q)
6.
(a)
| P | Q | P | Q |
| T | T | F |
| T | F | T |
| F | T | T |
| F | F | T |
(b)
P | Q = ¬ P ∨ ¬ Q
Truth table -
| P | Q | P | Q | ¬ | P | ∨ | ¬ | Q |
| T | T | F | F | T | F | F | T |
| T | F | T | F | T | T | T | F |
| F | T | T | T | F | T | F | T |
| F | F | T | T | F | T | T | F |
(c)
(i)
¬P = ¬ (P ∧ P)
= ¬ P ∨ ¬P
= P | P
(ii)
P ∨ Q
= ¬P | ¬ Q (from (b))
= (P | P) | (Q | Q) (from c(i)
(iii)
P ∧ Q
= ¬ (¬P ∨ ¬Q)
= ¬ ((P|P) ∨ (Q|Q))
= ¬ (((P|P) | (P|P)) | ((Q|Q) | (Q|Q)) ) (from ii)
= (((P|P) | (P|P)) | ((Q|Q) | (Q|Q)) ) | (((P|P) | (P|P)) | ((Q|Q) | (Q|Q)) ) (from i)
7. Boring stuff. Skipping.
8. Ditto!
9.
(a)
| (P | ∨ | Q) | ∧ | (¬ | P | ∨ | ¬ | Q) |
| T | T | T | F | F | T | F | F | T |
| T | T | F | T | F | T | T | T | F |
| F | T | T | T | T | F | T | F | T |
| F | F | F | F | T | F | T | T | F |
Neither.
(b)
| (P | ∨ | Q) | ∧ | (¬ | P | ∧ | ¬ | Q) |
| T | T | T | F | F | T | F | F | T |
| T | T | F | F | F | T | F | T | F |
| F | T | T | F | T | F | F | F | T |
| F | F | F | F | T | F | T | T | F |
A contradiction.
(c)
| (P | ∨ | Q) | ∨ | (¬ | P | ∨ | ¬ | Q) |
| T | T | T | T | F | T | F | F | T |
| T | T | F | T | F | T | T | T | F |
| F | T | T | T | T | F | T | F | T |
| F | F | F | T | T | F | T | T | F |
A tautology.
12.
(a) ¬(¬P ∨ Q) ∨ (P ∧ ¬R)
= (¬¬P ∧ ¬Q) ∨ (P ∧ ¬R)
= (P ∧ ¬Q) ∨ (P ∧ ¬R)
= P ∧ (¬Q ∨ ¬R)
(b) ¬(¬P ∧ Q) ∨ (P ∧ ¬R)
= ( ¬¬P ∨ ¬Q)) ∨ (P ∧ ¬R)
= (P ∨ ¬Q) ∨ (P ∧ ¬R)
(c) (P ∧ R) ∨ [¬R ∧ (P ∨ Q)]
= (P ∧ R) ∨ [(¬R ∧ P) ∨ (¬R ∧ Q)]
= (P ∧ R) ∨ (¬R ∧ P) ∨ (¬R ∧ Q)
13.
First DM law -> ¬(P ∧ Q) is equivalent to ¬P ∨ ¬Q
Double negation -> ¬¬P = P
¬(P ∨ Q)
= ¬ (¬ (¬ P ∧ ¬Q)) (First)
= (¬ P ∧ ¬Q)) (double neg)
which is the second law.
14.
[P ∧ (Q ∧ R)] ∧ S
= [P ∧ (Q ∧ R)] ∧ S
= P ∧ [(Q ∧ R) ∧ S]
= P ∧ [Q ∧ (R ∧ S)]
= (P ∧ Q) ∧ [(R ∧ S)
15.
2^n
16.
It's true if either both are false or both are true, or P is true.
Can be expressed as
[(P ∧ Q) ∨ (¬P ∧ ¬Q)] ∨ P
Truth table -
| P | Q | Desired | [(P ∧ Q) | ∨ | (¬P ∧ ¬Q)] | ∨ | P |
| F | F | T | F | T | T | T | F |
| F | T | F | F | F | F | F | F |
| T | F | T | F | F | F | T | T |
| T | T | T | T | T | F | T | T |
17.
True when they have different values.
Can be expressed as (P ∧ ¬Q) ∨ (¬P ∧ Q)
Truth table -
| (P | ∧ | ¬ | Q) | ∨ | (¬ | P | ∧ | Q) |
| F | F | T | F | F | T | F | F | F |
| F | F | F | T | T | T | F | T | T |
| T | T | T | F | T | F | T | F | F |
| T | F | F | T | F | F | T | F | T |
No comments:
Post a Comment