#discrete mathematics #1st order logic

Question

Prove or disprove (a) ∃x(P(x) ↔ Q(x)) → ¬∀xQ(x) ∨ ∃xP(x).

Answer 1

LHS: 

$\exists_x(P(x) ↔ Q(x)) \equiv \exists_x((P(x) → Q(x)) \land (Q(x) → P(x)))$

RHS: 

$\forall_x\neg{Q(x)} \lor \exists_xP(x) \equiv \exists_x(\neg{Q(x)}) \lor P(x)) \equiv \exists_x(Q(x) \to P(x))$

1. using De Morgan’s laws for quantifiers.
2. and as existential quantifier can distribute over OR operator

We can simply observe that $\exists_x((P(x) → Q(x)) \land (Q(x) → P(x))) \to \exists_x(Q(x) \to P(x))$

$\therefore ∃x(P(x) ↔ Q(x)) → ¬∀xQ(x) ∨ ∃xP(x) \equiv True$