0
$\begingroup$

I'm totally new to predicate logic and I need to determine if following formulas are tautology or not.

I can clearly see that first formula tautology is, but how could I check it for the others?

$$\begin{align} \alpha ~&=~ \forall x~\big(P(x) \vee \neg P(x)\big) \\[2ex]\beta ~&=~ \big(\forall x~P(x)\big) \vee \big(\forall x~\neg P(x)\big) \\[2ex]\gamma ~&=~ \big(\forall x~P(x)\big) \vee \big(\exists x~\neg P(x)\big) \end{align}$$

$\endgroup$
1
$\begingroup$

$\beta$ is not a tautology. If some things have prpooerty $P$, but other things do not, then neither $\forall x P(x)$ nor $\forall x \neg P(x)$ is the case. As a concrete example: Take the natural numbers and let $P(x)$ be '$x$ is even'

$\gamma$ is a tautology, since either everything has property $P$ (whatever that property is), or there is something that does not have property $P$. You can also think about it as follows: you know that $P \lor \neg P$ is a tautology, and therefore $\forall x P(x) \lor \neg \forall x P(x)$ is a tautology as well. But $\neg \forall x P(x)$ is eqwuivalent to $\exists x \neg P(x)$, and so $\forall x P(x) \lor \exists x \neg P(x)$ is a tautology.

$\endgroup$
  • $\begingroup$ Thank you very much! Now it's clear. $\endgroup$ – Jakub Ramza Apr 21 '17 at 1:40
0
$\begingroup$

The statements read:

$\alpha := \forall x~(P(x)\vee\neg P(x))$ : "Any $x$ will either satisfy $P$ or it will not."

$\beta := (\forall x~P(x))~\vee~(\forall x ~\neg P(x))$ : "Either every $x$ will satisfy $P$, or every $x$ will not satisfy $P$."

$\gamma := (\forall x~P(x))~\vee~(\exists x ~\neg P(x))$ : "Either every $x$ will satisfy $P$, or some $x$ will not satisfy $P$."

As you stated, $\alpha$ is clearly a tautology; due to the disjunction exhausting the possibilities (by way of the Law of Excluded Middle).

Consider, which of the remaining two statements also exhausts the possibilities, and which does not?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.