Question

Prove the following entailment in three different ways. a) Prove that (A → ¬B) = b) Prove that (A → ¬B) = c) Prove that (A → ¬B) = (BA A) with truth tables. [2 points] (BA A) with logical equivalences. [2 points] (BA A) with the resolution algorithm. [3 points]

Answer 1

To prove (A → ¬B) = (BA A), we can use the following three methods:

Method 1: Truth tables

Constructing the truth tables for both propositions, we get:

A | B | ¬B | A → ¬B | BA A | (A → ¬B) = (BA A)

-----------------------------------------------

T | T | F | F | T | F

T | F | T | T | T | T

F | T | F | T | F | F

F | F | T | T | F | F

Since both truth tables have identical truth values for each row, we can conclude that (A → ¬B) = (BA A) is a logically valid proposition.

Method 2: Logical equivalences

Using logical equivalences, we can transform (BA A) into (A → (¬B)), as follows:

BA A = ¬B ∨ A (definition of material implication)

= A → ¬B (definition of material implication)

Therefore, (A → ¬B) = (BA A) is a logically valid proposition.

Method 3: Resolution algorithm

Using the resolution algorithm, we can derive the empty clause from the negation of (A → ¬B) = (BA A), as follows:

1. ¬(A → ¬B) ∨ BA A (negation of (A → ¬B) = (BA A))

2. ¬(¬A ∨ ¬B) ∨ BA A (definition of material implication)

3. (A ∧ B) ∨ BA A (De Morgan's law)

4. (B ∨ BA) ∧ (A ∨ BA) (distribution)

5. (A ∨ BA) ∧ (B ∨ BA) (commutativity)

6. (¬A ∨ BA) ∧ (¬B ∨ BA) (De Morgan's law)

7. (¬B ∨ ¬A ∨ BA) ∧ (B ∨ ¬A ∨ BA) (distribution)

8. (¬B ∨ BA) ∧ (B ∨ ¬A ∨ BA) (resolution on clauses 6 and 7)

9. BA (resolution on clauses 5 and 8)

10. ¬BA ∨ BA (

Step-by-step explanation: