Question

1. If I can assume "not P" and derive "not Q", I have completed an indirect proof of the statement "P → Q".

T/F? Why?

2. If I want to prove "P → (x XOR NOT y)", it suffices to prove "P → (x AND y)".

T/F? Why?

3. Suppose I assume "A" and derive "B". Then I start over, assume "not B", and derive a contradiction. Then I may conclude that A is a tautology.

T/F? Why?

4. Suppose I first assume "A xor B" and prove "C".

Then I start over, assume "P", and prove "A and not B".

Finally I start again, assume "Q", and prove "not A and B".

Then I may conclude "(P or Q) → C".

T/F? Why?

5. Suppose I first assume A and derive B.

Then I start over, assume "not C", and derive "not B".

Then I start over, assume "C and not A", and derive "0".

I can now conclude that A, B, and C are all equivalent to one another.

T/F? Why?

Answer 1

Solution is provided below. If any doubt please comment it below.

1. False

Explanation:

• not Pà not Q is not equivalent to P à Q.
• When P is false and Q is true not P à not Q is false but P à Q is true.

2. False

Explanation:

• P → (x XOR NOT y)
• x XOR NOT y = ( x AND y ) OR (NOT x AND y)
• So x XOR NOT y ≠ x AND y
• Therefore P → (x XOR NOT y) is not equivalent to P → ( x AND y )

3. True

Explanation:

• not B assumed to be true.
• So B is false.
• A → B assumed to be true and B is false.
• So A is false.
• But it is given that derived a contradiction.
• Therefore A is tautology.

4. True

Explanation:

• A xor B
• C
• P
• A and not B
• Q
• not A and B
• So B is false.
• Since P is true , P or Q is true and C is true
• So, (P or Q) → C is tautology

5. True

Explanation:

• A à B
• not C ànot B
• C and not A derives 0, which means not (C and not A) = not C or A
• If A is true, then B has to be true, which implies not B is false.
• If not B is false then not C has to be false, which implies C is true.
• If not C is true, then C is flase.
• If not C is true then not B has to be true.
• If not B is true then B is false.
• If B is false, then A has to be false.
• So A, B and C are equivalent.