Question

1. Construct a truth table for: (¬p ∨ (p → ¬q)) → (¬p ∨ ¬q)

2. Give a proof using logical equivalences that (p → q) ∨ (q → r) and (p → r) are not logically equivalent.

3.Show using a truth table that (p → q) and (¬q → ¬p) are logically equivalent.

4. Use the rules of inference to prove that the premise p ∧ (p → ¬q) implies the conclusion ¬q. Number each step and give the rule used and which statement numbers the rule uses.

Answer 1

Sol. 1)

p	q	~p	~q	p-->~q	~pV(p-->~q)	~pV~q	(~pV(p-->~q))-->(~pV~q)
0	0	1	1	1	1	1	1
0	1	1	0	1	1	0	0
1	0	0	1	1	1	0	0
1	1	0	0	0	0	0	1

Table used in this question

Logical Disjunction (OR) (V):

A	B	AVB
0	0	0
0	1	1
1	0	1
1	1	1

Negation(~)

A	B
0	1
1	0

Logical Implication/if-then (Conditional) (-->)

A	B	A-->B
0	0	1
0	1	1
1	0	0
1	1	1

Logical conjunction (AND) (/\)

A	B	A /\ B
0	0	0
0	1	0
1	0	0
1	1	1

Sol. 2)

(p-->q) V (q-->r) and  (p-->r) are not logically equivalent.

p	q	r	p-->q	q-->r	(p-->q) V (q-->r)	(p-->r)
0	0	0	1	1	1	1
0	0	1	1	1	1	1
0	1	0	1	0	1	1
0	1	1	1	1	1	1
1	0	0	0	1	1	0
1	0	1	0	1	1	1
1	1	0	1	0	1	0
1	1	1	1	1	1	1

From the above clearly appears that (p-->q) V (q-->r) and (p-->r) are not the same. So they are not logically equivalent.

Sol. 3)

(p-->q) and (~q-->~p) are logically equivalent.

p	q	~p	~q	(p-->q)	(~q-->~p)
0	0	1	1	1	1
0	1	1	0	1	1
1	0	0	1	0	0
1	1	0	0	1	1

The above table clearly shows that (p-->q) and (~q-->~p) are logically equivalent.

Sol. 4)

p /\ (p-->~q) --> ~q

using rule of modus ponens which states that if p and  p-->q is true then we can infer q is true. In tautology it is

rule: p /\ (p-->q) -->q

Therefore

p /\ (p-->~q) --> ~q

We can also prove the above with truth table.

p	q	~q	p-->~q
0	0	1	1
0	1	0	1
1	0	1	1
1	1	0	0

So you can see when p is true , and (p-->q) is true ~q is also true.

Note: 0 is also represented as true(T) and 1 is also represented a false(F).