1

I'm having serious trouble understanding how to prove whether the below statements are true or false. Normally (when I'm working with simple stuff like p(x) → q(x)) I would create a truth table and see if there is a way to make the left side true and the right side false. In this case I have no clue how to begin. Questions: How do I solve this? Is it possible to do it simply using truth tables and if so, how does it work when I have something like p(x,y)? Can one p(x,y) = 1 and another p(x,y) = 0 in the same statement? Thanks in advance for any help.

∀x∀y(¬p(x,y) ∨ ¬q(x,y)), ∀x∀y(¬p(x,y) ↔ ¬s(x,y)), ∀x∀y(¬q(x,y) ↔ ¬t(x,y)) ⊨ ∀x∀y(¬s(x,y) ∨ ¬t(x,y))

∃x∃y(¬p(x,y) ∧ ¬q(x,y)), ∀x∀y(¬p(x,y) ∨ s(x,y)), ∀x∀y(¬q(x,y) ∨ t(x,y)) ⊨ ∃x∃y(s(x,y) ∧ t(x,y))

Ani
  • 13

1 Answers1

0

In general, truth table method does not work in predicate logic, due to the fact that we have to consider also interpretations with infinite domain.

In order to show that :

$\Gamma \vDash \varphi$

holds, where $\Gamma$ is a set of formulae, we need a proof (in a suitable proof system).

In the case of :

$∀x∀y(¬p(x,y) ∨ ¬q(x,y)), ∀x∀y(¬p(x,y) ↔ ¬s(x,y)), ∀x∀y(¬q(x,y) ↔ ¬t(x,y)) \vDash ∀x∀y(¬s(x,y) ∨ ¬t(x,y))$

due to the very simple formulae involved, we can try with an "informal" argument.

Forget about the quantifiers (all universal) and consider two "generic" objcets $a$ and $b$ in a domain $D$ whatever (i.e.$a,b \in D$).

Thus, from the premises of the formula above we have :

$(¬p(a,b) ∨ ¬q(a,b)), (¬p(a,b) ↔ ¬s(a,b)), (¬q(a,b) ↔ ¬t(a,b))$;

now we can use propositional logic.

If $¬p ↔ ¬s$ and $¬q ↔ ¬t$, from $¬p ∨ ¬q$ we can conclude with : $¬s ∨ ¬t$.

"Going back" to f-o logic, we have : $(¬s(a,b) ∨ ¬t(a,b))$.

But $a,b$ where objects whatever in the domain $D$; thus we can "generalize" the last formula, concluding with :

$\forall x \forall y (¬s(x,y) \lor ¬t(x,y))$.

Mauro ALLEGRANZA
  • 94,169