1.3: Predicates and Quantifiers
Okay, the book gives a nice rigorous version of predicates, and I think it’s fairly straightforward, so I won’t linger too long here.
Here’s the basic idea: A “propositional function” is a lot like the functions you learned about in pre-calc. It’s a statement that takes one or more variables, and spits out an answer. The difference is that the propositional functions take in statements and spit out facts about that.
So, for example:
We have a propositional function Z(x), which means “Star Wars x is amazing.”
In reality, only Star Wars 4, 5, and 6 are amazing.
So, what happens to the truth of that function when we enter different numbers? Here’s the readout
Z(1) = FALSE
Z(2) = FALSE
Z(3) = FALSE
Z(4) = TRUE
Z(5) = TRUE
Z(6) = TRUE
This sort of thing can be done with multiple variables, as in the function Z(x, y, z), which we’ll take to mean “Star Wars x, y, and z are all amazing.”
I won’t go through all the permutations, but as long as you use 4, 5, and 6 for those variables, you’ve got a true statement.
This also works for equations. For example:
Let’s say A(x, y, z) means “x + y > z”.
Or, more nerdly: “A is true as long as x + y > z, and otherwise A is false.”
You can readily see where this statement is true or false simply by inserting variables.
Pretty cool, right? It means you can construct any statement and then check to see where it’s true. For example, if you just watched Pulp Fiction, you might say F(x) which means “Marcellus Wallace gets fucked by x.” If the answer is “The Gimp” or “Mrs. Wallace” the statement is true. Otherwise, false.
Now, let’s get our terminology straight. In these statements, you basically have three things: a subject, a predicate, and a variable. The subject is what you’re talking about (e.g. Marcellus Wallace), the predicate is some piece of information about the subject (e.g. gets fucked by), and the variable or variables are something that’s… well… variable (x, y, z, or whatever). Got it?
Also, when you have multiple variables, you talk about particular sets of variables as n-tuples. That is, for 3 variables, x=1, y=5, z=24, you’re talking about a 3-tuple written out as “(1, 5, 24)” A proposition with n variables is an n-place predicate or an n-ary predicate. So, if P has 6 variables, it’s a 6-places predicate or a 6-ary predicate.
Much like a regular old function, we talk about the value of the function with a particular set of variables. So you could say, “What is the value of F(x) at Mrs. Wallace?” The answer would be “True.” Got it?
This stuff may seem a bit obtuse, but remember, a big part of discrete is taking real language and making it very precise.
Lastly, we get a few computer sciencey examples. I don’t have a lot of breadth of knowledge here, so wish me luck!
They give you a statement:
If x>0 then x := x+1
I read that as “If x is greater than zero, x gets x+1.” This is a statement about what happens when x is greater than 0.
If it’s in a computer program, it doesn’t just tell you whether the statement is true – it executes the statement. So, if you input x=5, you’ll get an output of x=6. That is, since 5>0 x gets 5+1.
They talk about two things called “preconditions” and “postconditions.” These terms were confusing to me at first because you expect them to be mirrors of each other or something based on their names. They aren’t like that, but they’re fairly straightforward concepts.
Preconditions are basically the space of legal inputs. So, if your statement is C(x), where C means “Christmas is on x this year,” the precondition is that x must be a day. A more abstract example might be that you have a statement that deals with which of two whole number is largest. The precondition would be that you input two whole numbers.
A postcondition is what things will be like once you execute your program. So, if you have a program that sorts a list of whole numbers and then assigns them to variables from largest to smallest, (w,x,y,z), then the postcondition is that w>x>y>z. Got it?
Next time: Quantifiers!
NEXT STOP: PREDICATES AND QUANTIFIERS!