GATE CSE
First time here? Checkout the FAQ!
x
+3 votes
86 views
Establish these logical equivalences, where x does not occur as a free variable in A. Assume that the domain is nonempty.

a) ∀x(A → P(x)) ≡ A → ∀xP(x)
b) ∃x(A → P(x)) ≡ A → ∃xP(x)
asked in Mathematical Logic by Veteran (11.5k points)   | 86 views

1 Answer

+2 votes
Best answer

a) Suppose A is false. Then A -> P(x) is trivially true because if hypothesis is false then conditional statement is trivially true. hence, both left-hand side and right-hand side are true.

Second case if A is true. Then there are two sub-cases.

(i) P(x) is true for every x, then left hand side is true, because if hypothesis and conclusion both are true then conditional proposition is true. Same reasoning can be given for right hand side also, right-hand side is also true as P(x) is true for every x.

(ii) P(x) is true for some x, left-hand side is false, because for those objects that do not have property P, the conditional A→P(x) is false, and hence it is not true that for all objects in the domain A→P(x) is true.

For right hand side it will always be false because A is true and ∀xP(x) is false

Hence, both propositions are equivalent.

b) If A is false, then both left-hand and right-hand sides are trivially true as hypothesis is false.

If A is true, then there are two sub-cases.

i.P(x) is true for every x, then left-hand side is true, and same reasoning can be given for right hand-side, and right-hand side is also true.>

ii.If P(x) is true for some x, left hand side is true and right hand side is also true.

Hence, both propositions are equivalent.

answered by Veteran (11.5k points)  
selected by


Top Users Sep 2017
  1. Habibkhan

    8586 Points

  2. rishu_darkshadow

    3046 Points

  3. Warrior

    2862 Points

  4. Arjun

    2796 Points

  5. A_i_$_h

    2546 Points

  6. manu00x

    2116 Points

  7. nikunj

    1990 Points

  8. Bikram

    1874 Points

  9. makhdoom ghaya

    1820 Points

  10. SiddharthMahapatra

    1718 Points


26,301 questions
33,864 answers
80,437 comments
31,203 users