A predicate name followed by a list of variables such as P(x, y), where P is
predicate name, and x and y are variables, is called an atomic formula.
A well formed formula of predicate calculus is obtained by using the following rules.
1. An atomic formula is a wff.
2. If A is a wff, then ¬A is also a wff.
3. If A and B are wffs, then (A V B), (A ٨ B), (A → B) and (A ¤ B) are wffs.
4. If A is a wff and x is any variable, then (x)A and ($x)A are wffs.
5. Only those formulas obtained by using (1) to (4) are wffs.
Wffs are constructed using the following rules:
1. True and False are wffs.
2. Each propositional constant (i.e. specific proposition), and each propositional
variable (i.e. a variable representing propositions) are wffs.
3. Each atomic formula (i.e. a specific predicate with variables) is a wff.
4. If A, B, and C are wffs, then so are A, (A B), (A B), (A B), and (A B).
5. If x is a variable (representing objects of the universe of discourse), and A is a
wff, then so are x A and x A .
For example, "The capital of Virginia is Richmond." is a specific proposition. Hence it is
a wff by Rule 2.
Let B be a predicate name representing "being blue" and let x be a variable. Then B(x) is
an atomic formula meaning "x is blue". Thus it is a wff by Rule 3. above.
By applying Rule 5. to B(x), xB(x) is a wff and so is xB(x).
Then by applying Rule 4. to them x B(x) x B(x) is seen to be a wff. Similarly if R
is a predicate name representing "being round". Then R(x) is an atomic formula. Hence it
is a wff.
By applying Rule 4 to B(x) and R(x), a wff B(x) R(x) is obtained.
To express the fact that Tom is taller than John, we can use the atomic formula
taller(Tom, John), which is a wff. This wff can also be part of some compound statement
such as taller(Tom, John) taller(John, Tom), which is also a wff. If x is a variable
representing people in the world, then taller(x,Tom), x taller(x,Tom), x
taller(x,Tom), x y taller(x,y) are all wffs among others. However, taller( x,John)
and taller(Tom Mary, Jim), for example, are NOT wffs.
DM 2
, Truth Tables:
Logical identity
Logical identity is an operation on one logical value, typically the value of a
proposition that produces a value of true if its operand is true and a value of false if
its operand is false.
The truth table for the logical identity operator is as follows:
Logical Identity
p p
T T
F F
Logical negation
Logical negation is an operation on one logical value, typically the value of a
proposition that produces a value of true if its operand is false and a value of false
if its operand is true.
The truth table for NOT p (also written as ¬p or ~p) is as follows:
Logical Negation
p ¬p
T F
F T
Logical conjunction:
Logical conjunction is an operation on two logical values, typically the values of two
propositions, that produces a value of true if both of its operands are true.
The truth table for p AND q (also written as p K q, p & q, or p q) is as follows:
If both p and q are true, then the conjunction p K q is true. For all other assignments
of logical values to p and to q the conjunction p K q is false. It can also be said that
if p, then p K q is q, otherwise p K q is p.
DM 3
, Logical Conjunction
P q pKq
T T T
T F F
F T F
F F F
Logical disjunction:
Logical disjunction is an operation on two logical values, typically the values of two
propositions, that produces a value of true if at least one of its operands is true.The truth
table for p OR q (also written as p V q, p || q, or p + q) is as follows:
Logical Disjunction
p q pVq
T T T
T F T
F T T
F F F
Logical implication:
Logical implication and the material conditional are both associated with an operation on
two logical values, typically the values of two propositions, that produces a value of false
just in the singular case the first operand is true and the second operand is false.
Logical Implication
p q p→q
T T T
T F F
F T T
DM 4
, F F T
The truth table associated with the material conditional if p then q (symbolized as p → q)
and the logical implication p implies q (symbolized as p ‹ q) is as shown above.
Logical equality:
Logical equality (also known as biconditional) is an operation on two logical values,
typically the values of two propositions, that produces a value of true if both operands are
false or both operands are true.The truth table for p XNOR q (also written as p ↔ q ,p =
q, or p ≡ q) is as follows:
Logical Equality
p q p≡q
T T T
T F F
F T F
F F T
Exclusive disjunction:
Exclusive disjunction is an operation on two logical values, typically the values of
two propositions, that produces a value of true if one but not both of its operands is
true.The truth table for p XOR q (also written as p Ⓧq, or p ≠ q) is as follows:
Exclusive Disjunction
p q pⓍ q
T T F
T F T
F T T
F F F
Logical NAND:
The logical NAND is an operation on two logical values, typically the values of two
propositions, that produces a value of false if both of its operands are true. In other words,
it produces a value of true if at least one of its operands is false.The truth table for p
NAND q (also written as p ↑ q or p | q) is as follows:
DM 5
predicate name, and x and y are variables, is called an atomic formula.
A well formed formula of predicate calculus is obtained by using the following rules.
1. An atomic formula is a wff.
2. If A is a wff, then ¬A is also a wff.
3. If A and B are wffs, then (A V B), (A ٨ B), (A → B) and (A ¤ B) are wffs.
4. If A is a wff and x is any variable, then (x)A and ($x)A are wffs.
5. Only those formulas obtained by using (1) to (4) are wffs.
Wffs are constructed using the following rules:
1. True and False are wffs.
2. Each propositional constant (i.e. specific proposition), and each propositional
variable (i.e. a variable representing propositions) are wffs.
3. Each atomic formula (i.e. a specific predicate with variables) is a wff.
4. If A, B, and C are wffs, then so are A, (A B), (A B), (A B), and (A B).
5. If x is a variable (representing objects of the universe of discourse), and A is a
wff, then so are x A and x A .
For example, "The capital of Virginia is Richmond." is a specific proposition. Hence it is
a wff by Rule 2.
Let B be a predicate name representing "being blue" and let x be a variable. Then B(x) is
an atomic formula meaning "x is blue". Thus it is a wff by Rule 3. above.
By applying Rule 5. to B(x), xB(x) is a wff and so is xB(x).
Then by applying Rule 4. to them x B(x) x B(x) is seen to be a wff. Similarly if R
is a predicate name representing "being round". Then R(x) is an atomic formula. Hence it
is a wff.
By applying Rule 4 to B(x) and R(x), a wff B(x) R(x) is obtained.
To express the fact that Tom is taller than John, we can use the atomic formula
taller(Tom, John), which is a wff. This wff can also be part of some compound statement
such as taller(Tom, John) taller(John, Tom), which is also a wff. If x is a variable
representing people in the world, then taller(x,Tom), x taller(x,Tom), x
taller(x,Tom), x y taller(x,y) are all wffs among others. However, taller( x,John)
and taller(Tom Mary, Jim), for example, are NOT wffs.
DM 2
, Truth Tables:
Logical identity
Logical identity is an operation on one logical value, typically the value of a
proposition that produces a value of true if its operand is true and a value of false if
its operand is false.
The truth table for the logical identity operator is as follows:
Logical Identity
p p
T T
F F
Logical negation
Logical negation is an operation on one logical value, typically the value of a
proposition that produces a value of true if its operand is false and a value of false
if its operand is true.
The truth table for NOT p (also written as ¬p or ~p) is as follows:
Logical Negation
p ¬p
T F
F T
Logical conjunction:
Logical conjunction is an operation on two logical values, typically the values of two
propositions, that produces a value of true if both of its operands are true.
The truth table for p AND q (also written as p K q, p & q, or p q) is as follows:
If both p and q are true, then the conjunction p K q is true. For all other assignments
of logical values to p and to q the conjunction p K q is false. It can also be said that
if p, then p K q is q, otherwise p K q is p.
DM 3
, Logical Conjunction
P q pKq
T T T
T F F
F T F
F F F
Logical disjunction:
Logical disjunction is an operation on two logical values, typically the values of two
propositions, that produces a value of true if at least one of its operands is true.The truth
table for p OR q (also written as p V q, p || q, or p + q) is as follows:
Logical Disjunction
p q pVq
T T T
T F T
F T T
F F F
Logical implication:
Logical implication and the material conditional are both associated with an operation on
two logical values, typically the values of two propositions, that produces a value of false
just in the singular case the first operand is true and the second operand is false.
Logical Implication
p q p→q
T T T
T F F
F T T
DM 4
, F F T
The truth table associated with the material conditional if p then q (symbolized as p → q)
and the logical implication p implies q (symbolized as p ‹ q) is as shown above.
Logical equality:
Logical equality (also known as biconditional) is an operation on two logical values,
typically the values of two propositions, that produces a value of true if both operands are
false or both operands are true.The truth table for p XNOR q (also written as p ↔ q ,p =
q, or p ≡ q) is as follows:
Logical Equality
p q p≡q
T T T
T F F
F T F
F F T
Exclusive disjunction:
Exclusive disjunction is an operation on two logical values, typically the values of
two propositions, that produces a value of true if one but not both of its operands is
true.The truth table for p XOR q (also written as p Ⓧq, or p ≠ q) is as follows:
Exclusive Disjunction
p q pⓍ q
T T F
T F T
F T T
F F F
Logical NAND:
The logical NAND is an operation on two logical values, typically the values of two
propositions, that produces a value of false if both of its operands are true. In other words,
it produces a value of true if at least one of its operands is false.The truth table for p
NAND q (also written as p ↑ q or p | q) is as follows:
DM 5
