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) <math>\forall (x) P(x) \vee \forall(x)Q(x) \implies \forall (x) (P(x) \vee Q(x))</math>
(2) <math>\exists (x) P(x) \wedge \forall(x)Q(x) \implies \exists (x) (P(x) \wedge Q(x))</math>
(3) <math>\exists (x) (P(x) \vee Q(x)) \implies \forall (x) P(x) \vee \forall (x) Q(x)</math>
(4) <math>\exists (x) (P(x) \vee Q(x)) \implies \sim \forall (x) </math>
(1) The corresponding English meaning: If <math>P(x)</math> is true for all <math>x</math>, or if <math>Q(x)</math> is true for all <math>x</math>, then for all <math>x</math>, either <math>P(x)</math> is true or <math>Q(x)</math> is true. This is always true and hence valid. To understand deeply, consider <math>X = {3,6,9,12}</math>. For LHS of implication to be true, either <math>P(x)</math> must be true for all elements or <math>Q(x)</math> must be true for all elements. In either case, if we take each element <math>x</math> in <math>X</math>, either one of <math>P(x)</math> or <math>Q(x)</math> will be true.
(If still in doubt, consider P(x) means x is a multiple of 3 and Q(x) means x is a multiple of 2)
(2) The corresponding English meaning: If <math>P(x)</math> is true for at least one <math>x</math>, and if <math>Q(x)</math> is true for all <math>x</math>, then there is at least one x for which both <math>P(x)</math> and <math>Q(x)</math> are true. This is always true and hence valid. To understand deeply, consider <math>X = {3,6,9,12}</math>. Let P(x) be x is a multiple of 9 and Q(x) be x is a multiple of 3. Now, LHS of implication is true. since P(x) is true for x = 9, and Q(x) is true for all x. Now, the RHS is also true since for 9, both P(x) and Q(x) are true.
(3)
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) <math>\forall (x) P(x) \vee \forall(x)Q(x) \implies \forall (x) (P(x) \vee Q(x))</math>
(2) <math>\exists (x) P(x) \wedge \forall(x)Q(x) \implies \exists (x) (P(x) \wedge Q(x))</math>
(3) <math>\exists (x) (P(x) \vee Q(x)) \implies \forall (x) P(x) \vee \forall (x) Q(x)</math>
(4) <math>\exists (x) (P(x) \vee Q(x)) \implies \sim \forall (x) </math>
(1) The corresponding English meaning: If <math>P(x)</math> is true for all <math>x</math>, or if <math>Q(x)</math> is true for all <math>x</math>, then for all <math>x</math>, either <math>P(x)</math> is true or <math>Q(x)</math> is true. This is always true and hence valid. To understand deeply, consider <math>X = {3,6,9,12}</math>. For LHS of implication to be true, either <math>P(x)</math> must be true for all elements or <math>Q(x)</math> must be true for all elements. In either case, if we take each element <math>x</math> in <math>X</math>, either one of <math>P(x)</math> or <math>Q(x)</math> will be true.
(If still in doubt, consider P(x) means x is a multiple of 3 and Q(x) means x is a multiple of 2)
(2) The corresponding English meaning: If <math>P(x)</math> is true for at least one <math>x</math>, and if <math>Q(x)</math> is true for all <math>x</math>, then there is at least one x for which both <math>P(x)</math> and <math>Q(x)</math> are true. This is always true and hence valid. To understand deeply, consider <math>X = {3,6,9,12}</math>. Let P(x) be x is a multiple of 9 and Q(x) be x is a multiple of 3. Now, LHS of implication is true. since P(x) is true for x = 9, and Q(x) is true for all x. Now, the RHS is also true since for 9, both P(x) and Q(x) are true.
(3)
GATECSE