Prove the formula that: ((∃x)(F(x)∧S(x))→(∀y)(M(y)→W(y)))∧((∃y)(M(y)∧¬W(y))) ⇒(∀x)(F(x)→¬S(x))

Question

Prove the formula that:
((∃x)(F(x)∧S(x))→(∀y)(M(y)→W(y)))∧((∃y)(M(y)∧¬W(y)))
⇒(∀x)(F(x)→¬S(x))

in progress 0
Nguyệt Ánh 3 years 2021-08-24T04:05:01+00:00 1 Answers 3 views 0

Answers ( )

  1. Gerda
    0
    2021-08-24T04:06:18+00:00
    Reply

    Step-by-step explanation:

    Given: [∀x(L(x) → A(x))] →

    [∀x(L(x) ∧ ∃y(L(y) ∧ H(x, y)) → ∃y(A(y) ∧ H(x, y)))]

    To prove, we shall follow a proof by contradiction. We shall include the negation of the conclusion for

    arguments. Since with just premise, deriving the conclusion is not possible, we have chosen this proof

    technique.

    Consider ∀x(L(x) → A(x)) ∧ ¬[∀x(L(x) ∧ ∃y(L(y) ∧ H(x, y)) → ∃y(A(y) ∧ H(x, y)))]

    We need to show that the above expression is unsatisfiable (False).

    ¬[∀x(L(x) ∧ ∃y(L(y) ∧ H(x, y)) → ∃y(A(y) ∧ H(x, y)))]

    ∃x¬((L(x) ∧ ∃y(L(y) ∧ H(x, y))) → ∃y(A(y) ∧ H(x, y)))

    ∃x((L(x) ∧ ∃y(L(y) ∧ H(x, y))) ∧ ¬(∃y(A(y) ∧ H(x, y))))

    E.I with respect to x,

    (L(a) ∧ ∃y(L(y) ∧ H(a, y))) ∧ ¬(∃y(A(y) ∧ H(a, y))), for some a

    (L(a) ∧ ∃y(L(y) ∧ H(a, y))) ∧ (∀y(¬A(y) ∧ ¬H(a, y)))

    E.I with respect to y,

    (L(a) ∧ (L(b) ∧ H(a, b))) ∧ (∀y(¬A(y) ∧ ¬H(a, y))), for some b

    U.I with respect to y,

    (L(a) ∧ (L(b) ∧ H(a, b)) ∧ (¬A(b) ∧ ¬H(a, b))), for any b

    Since P ∧ Q is P, drop L(a) from the above expression.

    (L(b) ∧ H(a, b)) ∧ (¬A(b) ∧ ¬H(a, b))), for any b

    Apply distribution

    (L(b) ∧ H(a, b) ∧ ¬A(b)) ∨ (L(b) ∧ H(a, b) ∧ ¬H(a, b))

    Note: P ∧ ¬P is false. P ∧ f alse is P. Therefore, the above expression is simplified to

    (L(b) ∧ H(a, b) ∧ ¬A(b))

    U.I of ∀x(L(x) → A(x)) gives L(b) → A(b). The contrapositive of this is ¬A(b) → ¬L(b). Replace

    ¬A(b) in the above expression with ¬L(b). Thus, we get,

    (L(b) ∧ H(a, b) ∧ ¬L(b)), this is again false.

    This shows that our assumption that the conclusion is false is wrong. Therefore, the conclusion follows

    from the premise.

    15

Leave an answer

Browse

Giải phương trình 1 ẩn: x + 2 - 2(x + 1) = -x . Hỏi x = ? ( )