Predicates and Quantifiers
The predicate is that portion of a statement that gives information about the subject. In logic, the predicate can be represented through the use of predicate symbols and predicate variables. Consider the following:
Mary is studying for a bachelor's degree at GSU.
Let P be the predicate symbol for is studying for a bachelor's degree at GSU, and let x be the predicate variable, which takes its value from the set of all students. Then the above sentence is represented symbolically as x is studying for a bachelor's degree at GSU , or P( x ) .
The above statement can be further refined. Let y also be a predicate variable, taking its value from the set of all colleges, and let R stand for is studying for a bachelor's degree at. The above sentence can now be represented as x is studying for a bachelor's degree at y , or R( x,y ) .
The predicate is a sentence containing a specific number of variables, and becomes a statement when specific values are substituted in place of the predicate variables. The values are taken from the domain of the predicate variables: the domain of x is the set of all students, and the domain of y is the set of all colleges. The values in these sets can be represented either in words or by symbols.
A set can be defined by simply enclosing the set elements in brackets. For instance, is a set of prime numbers less than 10. When using symbols, sets are typically represented by upper case letters, and set elements by lower case. Let T be a set of prime numbers less than 10, and x be an element of T ; this relationship can be represented by the notation x T . Likewise, the notation x T means that x is not an element of (or x is not in) T .
When elements are substituted for variables in a predicate, the result is either true or false. Let P be the set of all prime numbers, let x be an element of P , and let R stand for " x is a prime number less than 10 ". Symbolically, the predicate is represented as R( x ) , where x P . For x = 5, R( x ) is true, but if x = 13, then R( x ) is false. The truth set of the predicate R( x ) is the set of all elements which make R( x ) true. This is denoted symbolically as:
which is read as "the set of all x in P such that R( x ) ", or " x is an element of P such that R( x ) is true". (The vertical bar '|' is translated as "such that".)
Given predicates P( x ) and Q( x ) , where x has a domain of D :
P( x ) Q( x ) means that every element in the truth set of P( x ) is also in Q( x ).
P( x ) Q( x ) means that P( x ) and Q( x ) have identical truth sets .
Quantifiers: and
Quantifiers refer to given quantities, such as "some" or "all", indicating the number of elements for which a predicate is true. The symbol is translated as "for all", "given any", "for each", or "for every", and is known as the universal quantifier . The symbol is the existential quantifier , and means variously "for some", "there exists", "there is a", or "for at least one".
A universal statement is a statement that is true if, and only if, it is true for every predicate variable within a given domain. Consider the following example:
Let B be the set of all species of non-extinct birds, and b be a predicate variable such that b B . Let Q be the statement " b can fly.", and R be the statement " b is either carnivorous or is not." The universal statements for these two predicates can be represented as " b B, Q( b ) " ("for all birds b that are in the set of non-extinct species of birds, b can fly") and " b B, R( b ) " (try to figure out the wording here on your own!). With just a little thought, it is obvious that Q( b ) is false, since there exist flightless birds such as ostriches and penguins. R( b ) , however, is patently true, since it can be said of any bird species that they either eat meat or they don't.
An existential statement is a statement that is true if there is at least one variable within the variable's domain for which the statement is true.
Again, using the above defined set of birds and the predicate R( b ) , the existential statement is written as " b B, R( b ) " ("For some birds b that are in the set of non-extinct species of birds, b can fly"). Now consider a new predicate W( b ) , where W stands for "is bigger than an elephant". The existential statement " b B, W( b ) " can be translated as "There exists a bird which is bigger than an elephant." This statement is false, since no member of set B is bigger than an elephant.
| Practice Exercises |
Negating Quantified Statements
If a universal statement is a statement that is true if, and only if, it is true for every predicate variable within a given domain (as stated above), then logically it is false if there exists even one instance which makes it false. As discussed before, the statement " All birds fly ." is false. But its negation is not " No birds fly ." (also patently false). Instead, the correct negation will be " Some birds do not fly ." Symbolically:
| ~(All birds fly) | Some birds do not fly. |
| or | |
| ~(b B | Q(b)) | b B | ~Q(b) |
The negation of a universal statement ("all are") is logically equivalent to an existential statement ("Some are not").
Similarly, an existential statement is false only if all elements within its domain are false. The negation of "Some birds are bigger than elephants" is "No birds are bigger than elephants."
| ~(Some birds are bigger than elephants) | No birds are bigger than elephants |
| or | |
| ~(b B | Q(b)) | b B | ~Q(b) |
The negation of an existential statement ("some are") is logically equivalent to a universal statement ("all are not").
| D E F I N I T I O N S |
| Practice Exercises |
Universal Conditional Statements
Remember conditional statements? A universal conditional statement is simply a universal statement with a condition, and is symbolically represented as:
x , if P( x ) , then Q( x )
or
x , P( x ) Q( x )
Understanding universal conditional statements will further your understanding of if-then (conditional) statements, in particular, why the truth table of an if-then statement is constructed as it is. Recall that a conditional statement is false only if its hypothesis is true and the result is false, and apply this to an earlier example of a conditional statement:
If someone kicks me, then I will yell "ouch!"
Obviously, if someone kicks you and you yell "ouch!", the above conditional statement is true. But suppose you drop a hammer on your foot and yell ouch? Or nothing happens to you and you therefore say nothing? Neither of these situations makes the above statement false, so it becomes true by default. The only thing that makes this statement false is if someone kicks you and you do not yell "ouch!".
Putting this statement into the form of a universal conditional statement yields the following:
For all things that can happen to me, if someone kicks me, then I will yell "ouch!"
If you consider that the only instance which makes this false is a true hypothesis (someone kicks you) and a false conclusion (you don't yell ouch), it should become apparent that this statement is therefore true for everything else. Particularly, it is always true when the hypothesis is false.
| Practice Exercises |
Negating Universal Conditional Statements
To understand the negation of a universal conditional statement, first review if-then (conditional) negations and negations of universal ("for all") statements:
The negation of a conditional (if-then) statement is logically equivalent to an and statement.
The negation of a universal statement is logically equivalent to an existential statement.
~( x , P( x ) Q( x )) x | ~( P( x ) Q( x ))
Substituting the conditional statement into the universal statement yields the following result:
~( x , P( x ) Q( x )) x | P( x ) ~Q( x )
| Practice Exercises |