Logic: An Introduction (Part II)

Logical Connectives

In my last blog post we discussed propositions and predicates. To summarize, a proposition is a declarative sentence that can be proven TRUE or FALSE. Similarly, a predicate takes the form of a declarative sentence but contains at least one embedded variable (parameter) and cannot be evaluated as TRUE or FALSE unless input for said parameters is provided.

A logical connective is an operator that is used to form more complex predicates by combining predicates together. The most well-known of these logical connectives are conjunction (logical AND), disjunction (logical OR), and negation (logical NOT). Probably less commonly known are implication and equivalence.

SymbolMeaningTerminology
¬NOTNegation
ANDConjunction
ORDisjunction
IMPLIESImplication (if…then…)
IS EQUIVALENT TOEquivalence (if and only if)
Note: If you take a course in mathematical logic, you will have a formal discussion of proofs. You start with a formal language, which describes the symbols you're allowed to use and how to combine them, and the rules of inference, which describe the valid ways of making steps in a proof. This is important because natural languages like English are informal and imprecise, as a consequence, the meaning of words sometimes depends on context; this kind of ambiguity is why formal language and symbols exist. However, throughout my writings I will use a mix of formal and informal language and syntax for the sake of learning.

Simple and Compound Predicates

If a logical connective is regarded as a logical operator, we can say that it takes one or more predicates as its operand and returns another predicate.

Example:

Consider the logical operator ∧

Consider the predicates x = 11 and y = 15 as the operands

The compound predicate would be (x = 11) ∧ (y = 15)

In informal language this reads as: I propose that x equals 11 and y equals 15.

With an AND operator, the compound predicate only evaluates to TRUE if both the simple predicates also individually evaluate to TRUE.

Note: The simple predicates that make up the operands of the logical operator are also sometimes referred to as components of the compound predicate. Isn’t natural language fun?

Propositional Variables

Let’s consider another kind of compound predicate. Consider the following:

P ∧ Q ⇒ P ⇒ Q

This looks a bit different than the predicates we’ve looked at so far. That’s because this example uses the propositional variables P and Q. If you consider that a variable is a “holder” for a value, then you can think of a propositional variable as a “holder” for a proposition.

An assertion that contains at least one propositional variable is referred to as a propositional form. If you substitute all propositional variables (of the given propositional form) with a proposition the propositional form is transformed into a proposition in and of itself.

Phew, even reading that back to myself that is a tricky sentence. You may think at this point that a propositional form seems very similar to a predicate. So what’s the difference? Well, let’s recall that a predicate takes the form of a declarative sentence (just like a proposition) but has embedded variables. A predicate cannot be evaluated to TRUE or FALSE until values are substituted for these variables. Meanwhile a propositional form uses propositional variables which themselves represent a truth value (TRUE or FALSE).

This means that we can treat propositional variables as arbitrary predicates with truth values without having to fully express the details of the underlying proposition

Example:

Let P represent 3 + 5 = 8

Let Q represent 1 + 1 = 2

Consider the propositional form P ∧ Q

If we replace the proposition variables (P,Q) the propositional form is transformed to the following proposition:

3 + 5 = 8 ∧ 1 +1 = 2

Which evaluates to TRUE.

Similarly, we can use letters like P,Q,R, ect. In expressions like this:

P(x), Q(y), R(s,t)

These represent arbitrary predicates with parameters.

Example:

Let P represent 3 + 2x = 9

What is the value of P(x) given that x = 3

You would evaluate this by substituting P(3) which means to pass 3 as the value for parameter x to the predicate 3 + 2x = 9 which forms the proposition 3 + (2*3) = 9 which evaluates to TRUE and thus P(x) evaluates to TRUE

If we pass any other value for x, the resulting proposition evaluates to FALSE.

Logical Operator Precedence and Parentheses

I’m sure everyone remembers PEMDAS (Parentheses, Exponents, Multiplication, Division, Addition, Subtraction), the order of operations from your middle school math class. Just like algebraic expressions follow the order of operations, logical expressions follow an order of precedence. And just like the algebraic expressions, you can override this order using parentheses.

Note: Even though formal rules of the syntax do not always strictly require parentheses, it is a good idea to add them even if redundant to avoid any confusion or misinterpretation. It increases readability and is just as valid.

Here are the Logical Connective Precedence Rules:

RankConnective
1¬
2∧, ∨
3⇒, ↔

Note that some operators have the same rank.

Example:

Given P ∧ Q ⇒ R the precedence rules state that this is equivalent to (P ∧ Q) ⇒ R rather than P ∧ (Q ⇒ R)

For operations with equal rank, formal rules state that you should read operations from right to left. This is called the associative rule.

Example:

Given P ⇒ Q ⇒ R, the associative rule states that this should be equivalent to P ⇒ (Q ⇒ R) rather than (P ⇒ Q) ⇒ R

This is an important rule to keep in mind, but for the sake of clarity I will most often use parentheses in my posts.