Question

Recall, we have five connectives in propositional logic ¬, ∧, ∨, →, ↔ (negation, conjunction, disjunction, conditional and biconditional). In fact, to express every possible outcome we only need the negation and the conditional connectives Show how this is done by writing alternative expressions (i.e. logically equivalent ones) for the expressions below, using only the connectives ¬ and →. Type or paste your answers in the Write Submission box. As usual, you may substitute ~ for ¬ and --> for → , if you're typing answers.(a) p ∧ q(b) p ∨ q(c) p ↔ q

Answer 1

(a) ¬(p→¬q)

(b) ¬p→q

(c) ¬((p→q)→¬(q→p))

Explanation

taking into account the truth table for the conditional connective:

p | q | p→q

T | T | T

T | F | F

F | T | T

F | F | T

(a) and (b) can be seen from truth tables:

for (a) p∧q:

p | q | ¬q | p→¬q | ¬(p→¬q) | p∧q

T | T | F | F | T | T

T | F | T | T | F | F

F | T | F | T | F | F

F | F | T | T | F | F

As they have the same truth table, they are equivalent.

In a similar manner, for (b) p∨q:

p | q | ¬p | ¬p→q | p∨q

T | T | F | T | T

T | F | F | T | T

F | T | T | T | T

F | F | T | F | F

again, the truth tables are the same.

For (c)p↔q, we have to remember that p ↔ q can be written as (p→q)∧(q→p). By replacing p with (p→q) and q with (q→p) in the answer for part (a) we can change the ∧ connector to an equivalent using ¬ and →. Doing this we get ¬((p→q)→¬(q→p))