Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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}$$
$\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.
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?
