Predicate logic formulas without quantifiers can be verified using derivation. But when it comes to first order logic (predicate logic with quantifiers), the simplest way is to apply logical reasoning. Most of these questions asked will be for very small formulas and we can easily apply logical reasoning to check if they are valid. The method is to convert the logical formula into its corresponding English meaning. This is shown in the following examples:
(1) $\forall (x) P(x) \vee \forall(x)Q(x) \implies \forall (x) (P(x) \vee Q(x))$
(2) $\exists (x) P(x) \wedge \exists (x)Q(x) \implies \exists (x) (P(x) \wedge Q(x))$
(3) $\exists (x) (P(x) \vee Q(x)) \implies \forall (x) P(x) \vee \forall (x) Q(x)$
(4) $\exists (x) (P(x) \vee Q(x)) \implies \sim \forall (x) P(x) \vee \exists (x) Q(x)$
(1) The corresponding English meaning: If $P(x)$ is true for all $x$, or if $Q(x)$ is true for all $x$, then for all $x$, either $P(x)$ is true or $Q(x)$ is true. This is always true and hence valid. To understand deeply, consider $X = \{3,6,9,12\}$. For LHS of implication to be true, either $P(x)$ must be true for all elements in $X$ or $Q(x)$ must be true for all elements in $X$. In either case, if we take each element $x$ in $X$, either one of $P(x)$ or $Q(x)$ will be true. Hence, this implication is always valid.
(If still in doubt, let $P(x)$ mean $x$ is a multiple of $3$ and $Q(x)$ means $x$ is a multiple of $2$)
(2) The corresponding English meaning: If $P(x)$ is true for at least one $x$, and if $Q(x)$ is true for at least one $x$, then there is at least one $x$ for which both $P(x)$ and $Q(x)$ are true. This is not always true as $P(x)$ can be true for one $x$ and $Q(x)$ can be true for some other $x$ . To understand deeply, consider $X = \{3,6,9,12\}$. Let $P(x)$ be $x$ is a multiple of $9$ and $Q(x)$ be $x$ is a multiple of $6$. Now, LHS of implication is true, since $P(x)$ is true for $x = 9$, and $Q(x)$ is true for $x = 6$. But RHS of implication is not true as there is no $x$ for which both $P(x)$ and $Q(x)$ holds. Hence, this implication is not valid.
(3) If there is at least one $x$ for which either $P(x)$ is true or $Q(x)$ is true then $P(x)$ is true for all $x$ or $Q(x)$ is true for all $x$. Just one read is enough to see this is an invalid implication.
(4)If there is at least one $x$ for which either $P(x)$ or $Q(x)$ is true then either it is not the case that $P(x)$ is true for all $x$ or $Q(x)$ is true for at least one $x$. This is clearly invalid as LHS of implication becomes true if $P(x)$ is true for some $x$ and $Q(x)$ is not true for any $x$, but RHS will be false.
A little modification to the statement is enough to make it valid: $$\exists (x) (P(x) \vee Q(x)) \implies \sim (\forall (x) \sim P(x)) \vee \exists (x) Q(x)$$ which means if there is at least one $x$ for which either $P(x)$ or $Q(x)$ is true then either it is not the case that $\sim P(x)$ is true for all $x$ (which means P(x) is true for some $x$) or $Q(x)$ is true for some $x$.
De Morgan's law is applicable in first order logic and is quite useful:
$$\forall(x)(P(x)) \equiv \neg \exists (x)(\neg P(x))$$
This is a logical reasoning statement which means if $P(x)$ is true for all $x$, then there can never exist an $x$ for which $P(x)$ is not true. This formula is quite useful in proving validity of many statements as is its converse given below:
$$\exists(x)(P(x)) \equiv \neg \forall (x)(\neg P(x))$$
Predicate logic formulas without quantifiers can be verified using derivation. But when it comes to first order logic (predicate logic with quantifiers), the simplest way is to apply logical reasoning. Most of these questions asked will be for very small formulas and we can easily apply logical reasoning to check if they are valid. The method is to convert the logical formula into its corresponding English meaning. This is shown in the following examples:
(1) $\forall (x) P(x) \vee \forall(x)Q(x) \implies \forall (x) (P(x) \vee Q(x))$
(2) $\exists (x) P(x) \wedge \exists (x)Q(x) \implies \exists (x) (P(x) \wedge Q(x))$
(3) $\exists (x) (P(x) \vee Q(x)) \implies \forall (x) P(x) \vee \forall (x) Q(x)$
(4) $\exists (x) (P(x) \vee Q(x)) \implies \sim \forall (x) P(x) \vee \exists (x) Q(x)$
(1) The corresponding English meaning: If $P(x)$ is true for all $x$, or if $Q(x)$ is true for all $x$, then for all $x$, either $P(x)$ is true or $Q(x)$ is true. This is always true and hence valid. To understand deeply, consider $X = \{3,6,9,12\}$. For LHS of implication to be true, either $P(x)$ must be true for all elements in $X$ or $Q(x)$ must be true for all elements in $X$. In either case, if we take each element $x$ in $X$, either one of $P(x)$ or $Q(x)$ will be true. Hence, this implication is always valid.
(If still in doubt, let $P(x)$ mean $x$ is a multiple of $3$ and $Q(x)$ means $x$ is a multiple of $2$)
(2) The corresponding English meaning: If $P(x)$ is true for at least one $x$, and if $Q(x)$ is true for at least one $x$, then there is at least one $x$ for which both $P(x)$ and $Q(x)$ are true. This is not always true as $P(x)$ can be true for one $x$ and $Q(x)$ can be true for some other $x$ . To understand deeply, consider $X = \{3,6,9,12\}$. Let $P(x)$ be $x$ is a multiple of $9$ and $Q(x)$ be $x$ is a multiple of $6$. Now, LHS of implication is true, since $P(x)$ is true for $x = 9$, and $Q(x)$ is true for $x = 6$. But RHS of implication is not true as there is no $x$ for which both $P(x)$ and $Q(x)$ holds. Hence, this implication is not valid.
(3) If there is at least one $x$ for which either $P(x)$ is true or $Q(x)$ is true then $P(x)$ is true for all $x$ or $Q(x)$ is true for all $x$. Just one read is enough to see this is an invalid implication.
(4)If there is at least one $x$ for which either $P(x)$ or $Q(x)$ is true then either it is not the case that $P(x)$ is true for all $x$ or $Q(x)$ is true for at least one $x$. This is clearly invalid as LHS of implication becomes true if $P(x)$ is true for some $x$ and $Q(x)$ is not true for any $x$, but RHS will be false.
A little modification to the statement is enough to make it valid: $$\exists (x) (P(x) \vee Q(x)) \implies \sim (\forall (x) \sim P(x)) \vee \exists (x) Q(x)$$ which means if there is at least one $x$ for which either $P(x)$ or $Q(x)$ is true then either it is not the case that $\sim P(x)$ is true for all $x$ (which means P(x) is true for some $x$) or $Q(x)$ is true for some $x$.
De Morgan's law is applicable in first order logic and is quite useful:
$$\forall(x)(P(x)) \equiv \neg \exists (x)(\neg P(x))$$
This is a logical reasoning statement which means if $P(x)$ is true for all $x$, then there can never exist an $x$ for which $P(x)$ is not true. This formula is quite useful in proving validity of many statements as is its converse given below:
$$\exists(x)(P(x)) \equiv \neg \forall (x)(\neg P(x))$$
GATECSE