Logic: An Introduction (Part I)

Values, Variables and Types

Regardless of your background, you probably have at least some idea about what the terms values and variables mean. However, when talking about them in a technical context it is important to be precise as they are often used interchangeably when they ought not be.

A value is an individual constant which is well-defined. Being a constant means that it is fixed and well-defined means that it is unambiguous. For example, the integer 42 is a value (and the answer to the ultimate question of life, the universe, and everything). You cannot update or change a value because if you did it would no longer be the same value. A value can be represented in many different ways (through encoding) but it always represents the same thing.

A variable is a holder or a container for a value. As such the value of a variable is not fixed. Or put another way, which value the variable is holding can change. Variables have a name, which can be used to reference them without the requirement of knowing what value (or set of values) it contains. Given x = 1 + 3 as an example, x is a variable and it holds the value 4 which is the result of the operation (1+3).

A variable’s type is the entire set or range of values that a variable is allowed to hold.

Propositions and Predicates

In logic, the primary components we will deal with are propositions and predicates.

A proposition (also sometimes referred to as a statement) is a declarative sentence that when evaluated is either TRUE or FALSE, but not both.

Example:

In English, the sentence “The sky is beautiful” is NOT a proposition because while it does make an assertion, it is a subjective one since it is a matter of opinion. Some would evaluate the this assertion as TRUE while others would deem it FALSE. Thus it is ambiguous and thus not a proposition.

The sentence “Is it raining?” is not a proposition because it is a question rather than an assertion or a declaration.

The sentence “Right now, it is 5:00PM Pacific Time in Seattle, Washington” is a proposition because it makes a well-defined assertion which either is or is not.

Some sentences that are mathematical in nature often are not statements because we may not know precisely what a variable represents.

Example:

Consider the equation (2x)+5 = 15. This is NOT a proposition because we do not know what the variable represents. Remember that in order for something to be a proposition it must be either true or false but not both.

Consider the equation 4 + 1 = 5. This is a proposition because without any additional information we can evaluate this as either TRUE or FALSE. In this case it is TRUE.

Note: It is a common mistake to only consider TRUE sentences as valid propositions but propositions can also be FALSE; the important consideration when defining a proposition is that it cannot be both.

A predicate is something which has the form of a declarative sentence but which includes at least one embedded variable whose value is unknown and which you cannot determine to be TRUE or FALSE without knowing the value of said variable(s). We will refer to these embedded variables as the parameters of the predicate.

Example:

Using the same example as from above, the equation (2x)+5 = 15 is a predicate because without additional information, we don’t know what the value of x is and so we cannot determine if it is TRUE or not.

A predicate with n parameters is referred to as an n-place predicate. If you substitute one of the parameters in an n-place predicate with a value, it becomes an (n-1)-place predicate.

Example:

Consider the equation x + y = 5

This is a 2-place predicate; it has two parameters x and y.

Now, consider the same equation with the variable x substituted with the value 4:

4+ y = 5

This is a 1-place predicate; it has one parameter y.

So you may be wondering, if n = 1, wouldn’t an (n-1)-place predicate be a 0-place predicate? The answer is yes. Given the same equation from the previous example, if we replace the last remaining parameter y with a literal value such as 1, the equation becomes:

4 + 1 = 5

You may have noticed that this is the exact same equation as the example given for a proposition. That’s because a 0-place predicate is a proposition. In this way, a proposition can be thought of as a special case of predicates. You can transform a predicate into a proposition by replacing all of its parameters with values. This process is called instantiating the predicate with the given values.

The parameters of a predicate are also referred to as the free variables of a predicate. There is another way to convert predicates into propositions; binding them to a quantifier. Free variables then turn into what are referred to as bound variables. This process is called Quantification (over a set) and it is an important concept in logic and an especially important when it comes to data management.

Bonus:

Consider the following two sentences:

This statement is false.

I’m lying.

These are both self-referential sentences; meaning that they tell us something about themselves. Sentences like these have the potential to cause logical contradictions. The second sentence is called the Liar’s paradox. If you begin an evaluation of the sentence with the assumption that it is TRUE, you will reach the conclusion that it is in fact FALSE. However, if you begin an evaluation of the sentence with the assumption that it is FALSE, you will come to the conclusion that it is in fact TRUE. Because of this you are unable to determine if the sentence is TRUE or FALSE, despite the fact that there are no variables or parameters. The solution is to disregard the statement as a valid proposition.

Similarly, you must discard “ill-formed” expressions as predicates.

Consider the following:

2 is an element of 7

This is an ill-formed predicate because 7 is not a set, it is a value. The expression just doesn’t make any sense and so it should be disregarded. This assumes at least a familiarity with the concept of sets, but I’ll be covering basic set theory in a future post.

Avery Lane

Author: Avery Lane

Hi, I'm Avery and I think computers and math are cool.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.