Predicate Logic#
Predicate logic deals with predicates, which are propositions containing variables.
A predicate is an expression of one or more variables defined on some specific domain. A predicate with variables can be made a proposition by either assigning a value to the variable or by quantifying the variable.
Example
Let \(E(x, y)\) denote “\(x = y\)”
Let \(X(a, b, c)\) denote “\(a + b + c = 0\)”
Let \(M(x, y)\) denote “\(x is married to y\)”
Well Formed Formula#
Well Formed Formula (WFF) is a predicate holding any of the following:
All propositional constants and propositional variables are WFFs.
If \(x\) is a variable and \(Y\) is a WFF, \(∀xY\) and \(∃xY\) are also WFFs.
Truth value and false values are WFFs.
Each atomic formula is a WFF.
All connectives connecting WFFs are WFFs.
Quantifiers#
The variable of predicates is quantified by quantifiers. There are two types of quantifier in predicate logic: Universal Quantifier and Existential Quantifier.
Universal Quantifier#
Universal quantifier states that the statements within its scope are true for every value of the specific variable. It is denoted by the symbol \(∀\).
\(∀xP(x)\) is read as “for every value of \(x\), \(P(x)\) is true.”
Example
“Man is mortal” can be transform into the propositional form \(∀xP(x)\) where \(P(x)\) is the predicate which denotes \(x\) is mortal and the universe of discourse is all men.
Existential Quantifier#
Existential quantifier states that the statements within its scope are true for some values of the specific variable. It is denoted by the symbol \(∃\).
\(∃xP(x)\) is read as “for some values of \(x\), \(P(x)\) is true.”
Example
“Some people are dishonest” can be transformed into the propositional form \(∃xP(x)\) where \(P(x)\) is the predicate which denotes \(x\) is dishonest and the universe of discourse is some people.
Nested Quantifiers#
If we use a quantifier that appears within the scope of another quantifier, it is called nested quantifier.
Example
\(∀x∃yP(x, y)\) where \(P(x, y)\) denotes \(x + y = 0\)
\(∀a∀b∀cP(a, b, c)\) where \(P(a, b)\) denotes \(a + (b + c) = (a + b) + c\)
Note
\(-∀a∃bP(x, y) ≠ ∃a∀bP(x, y)\)