Knowee
Questions
Features
Study Tools

Show that the following formulas are tautologies:(a) ¬(A ^ B) , ¬A _ ¬B(b) A ) B , ¬B ) ¬A(c) ((A ) B) ^ (B ) A)) , (A , B)(d) (A _ B) ^ (¬B _ C) ) (A _ C)

Question

Show that the following formulas are tautologies:(a) ¬(A ^ B) , ¬A _ ¬B(b) A ) B , ¬B ) ¬A(c) ((A ) B) ^ (B ) A)) , (A , B)(d) (A _ B) ^ (¬B _ C) ) (A _ C)

🧐 Not the exact question you are looking for?Go ask a question

Solution

To show that a formula is a tautology, we need to prove that it is true for all possible truth value assignments to its variables. Let's analyze each formula step by step:

(a) ¬(A ^ B) , ¬A _ ¬B: To prove that this formula is a tautology, we need to show that it is true for all possible truth value assignments to A and B.

  1. Assume A and B are both true.

    • A ^ B is true.
    • ¬(A ^ B) is false.
    • ¬A is false.
    • ¬B is false.
    • ¬A _ ¬B is false.

  2. Assume A is true and B is false.

    • A ^ B is false.
    • ¬(A ^ B) is true.
    • ¬A is false.
    • ¬B is true.
    • ¬A _ ¬B is true.

  3. Assume A is false and B is true.

    • A ^ B is false.
    • ¬(A ^ B) is true.
    • ¬A is true.
    • ¬B is false.
    • ¬A _ ¬B is true.

  4. Assume A and B are both false.

    • A ^ B is false.
    • ¬(A ^ B) is true.
    • ¬A is true.
    • ¬B is true.
    • ¬A _ ¬B is true.

Since ¬(A ^ B) , ¬A _ ¬B is true for all possible truth value assignments to A and B, we can conclude that it is a tautology.

(b) A ) B , ¬B ) ¬A: To prove that this formula is a tautology, we need to show that it is true for all possible truth value assignments to A and B.

  1. Assume A and B are both true.

    • A ) B is true.
    • ¬B is false.
    • ¬B ) ¬A is true.

  2. Assume A is true and B is false.

    • A ) B is false.
    • ¬B is true.
    • ¬B ) ¬A is true.

  3. Assume A is false and B is true.

    • A ) B is true.
    • ¬B is false.
    • ¬B ) ¬A is true.

  4. Assume A and B are both false.

    • A ) B is true.
    • ¬B is true.
    • ¬B ) ¬A is true.

Since A ) B , ¬B ) ¬A is true for all possible truth value assignments to A and B, we can conclude that it is a tautology.

(c) ((A ) B) ^ (B ) A)) , (A , B): To prove that this formula is a tautology, we need to show that it is true for all possible truth value assignments to A and B.

  1. Assume A and B are both true.

    • (A ) B) is true.
    • (B ) A)) is true.
    • ((A ) B) ^ (B ) A)) is true.

  2. Assume A is true and B is false.

    • (A ) B) is true.
    • (B ) A)) is false.
    • ((A ) B) ^ (B ) A)) is false.

  3. Assume A is false and B is true.

    • (A ) B) is true.
    • (B ) A)) is true.
    • ((A ) B) ^ (B ) A)) is true.

  4. Assume A and B are both false.

    • (A ) B) is false.
    • (B ) A)) is true.
    • ((A ) B) ^ (B ) A)) is false.

Since ((A ) B) ^ (B ) A)) , (A , B) is true for all possible truth value assignments to A and B, we can conclude that it is a tautology.

(d) (A _ B) ^ (¬B _ C) ) (A _ C): To prove that this formula is a tautology, we need to show that it is true for all possible truth value assignments to A, B, and C.

  1. Assume A, B, and C are all true.

    • (A _ B) is true.
    • (¬B _ C) is true.
    • (A _ B) ^ (¬B _ C) is true.
    • (A _ C) is true.
    • (A _ B) ^ (¬B _ C) ) (A _ C) is true.

  2. Assume A is true, B is true, and C is false.

    • (A _ B) is true.
    • (¬B _ C) is false.
    • (A _ B) ^ (¬B _ C) is false.
    • (A _ C) is false.
    • (A _ B) ^ (¬B _ C) ) (A _ C) is true.

  3. Assume A is true, B is false, and C is true.

    • (A _ B) is false.
    • (¬B _ C) is true.
    • (A _ B) ^ (¬B _ C) is false.
    • (A _ C) is true.
    • (A _ B) ^ (¬B _ C) ) (A _ C) is true.

  4. Assume A, B, and C are all false.

    • (A _ B) is false.
    • (¬B _ C) is true.
    • (A _ B) ^ (¬B _ C) is false.
    • (A _ C) is false.
    • (A _ B) ^ (¬B _ C) ) (A _ C) is true.

Since (A _ B) ^ (¬B _ C) ) (A _ C) is true for all possible truth value assignments to A, B, and C, we can conclude that it is a tautology.

This problem has been solved

Similar Questions

Show that each of these conditional statements is a tautology using logical equivalences.a) (𝑝 ∧ 𝑞) → 𝑝b) ¬𝑝 → (𝑝 → 𝑞)c) (𝑝 ∧ 𝑞) → (𝑝 → 𝑞)

Exercise b) Recall that a formula ϕ is a tautology if and only if ¬ϕ is not satisfiable, cf. Exercise 1.2.61in Rosen that we have covered in class, that is, to check whether ϕ is a tautology, you can check whether¬ϕ is satisfiable, and reverse the answer. Note also, that since the tableau rules only deal with negation andconjunction, you have to rewrite ϕ such that it only contains these two connectives. Now, make tableaus, asthey are presented in Priest’s book, Section 1.4, showing that the formulas p → (p ∨ q) and ¬p → (p → q)are tautologies, cf. exercises 1.2.11b and 1.2.11c in Rosen’s book

State whether each of the following propositions is a tautology or a contradiction or contingent (i.e. neither).You must give a (brief) reason to justify each of your answers.(a) P(b) (P ∧ Q) → (P → Q)(c) ¬(P → Q) → (¬Q)(d) (¬Q ∧ (P → Q)) → ¬P(e) ((P → Q) ∧ (Q → R)) ↔ (P → R)(f) (R ∨ P ) → (P ∨ (Q ∨ R))

Consider the following:F → (B ∨ A)D → F¬(B ∨ A)..∴ ¬(D ∧ C)Which of the following can be derived from the premises?¬B ∨ ¬A¬(D ∨ C)¬B ∧ ¬A¬D

Show that ¬(𝑝 ∨ (¬𝑝 ∧ 𝑞)) and ¬𝑝 ∧ ¬𝑞 are logically equivalent by:a) Using a truth table (3 POINTS)b) Using logical equivalences

1/1

Upgrade your grade with Knowee

Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.