1.2 Statements, predicates and connectives
What is a statement?
A logical statement or proposition is an expression that can meaningfully be assigned the values of true or false. A statement might be written in words or mathematical symbols, or often as a combination of both.
A statement must be true or false but not both. It cannot be half-true or sort-of-true.
- “\(1>0\)” is a true statement
- “2047 is a prime number” is a false statement
- “What is the meaning of life?” is not a logical statement
- “if \(n^2=4\) then what is \(n\)?” is a precise mathematical question (though with more than one answer) but is not a statement
- “\(n^2=4\) has two integer solutions” is a true statement
A predicate is a ‘statement’ whose truth is dependent on one or more variables.
- “\(n^2=4\)” is an example of a predicate
Let us pause to consider what we mean by a variable. When you begin studying algebra you might think of variables as unknown numbers. But of course you often want to solve for the value of the variable at which point it is no longer unknown.
A variable also does not have to be a number. It might be a vector or a matrix: let \(\mathbf v\) denote the positive of the particle. It could be a set: let \(S\) be the set of integer solutions of the equation \(n^2=4\). It could even by a function: let \(s\) denote the function whose value at a positive real number \(y\) is the solution of the equation \(x^2=y\).
Ultimately a variable is simply a placeholder which gives a name for some entity that you want to consider.
To consider the “algebra” of statements we will denote our statements by \(P,Q,\dots\)
Note that we now have variables which are statements. Since statements must, by definition, have a well-defined (though not necessarily known) truth value, we might alternatively think of the variables \(P,Q,\dots\) as having values of true or false.
We can denote predicates by \(P(n),P(x)\) etc. to indicate the variable on which they depend, e.g. \[P(n): \quad n^2=4\]
Logical Connectives
Many of the statements we meet in practice, are rather long and complicated statements. It is often useful to break them down into smaller parts and consider how these smaller parts contribute to the truth value of the original statement. We begin with the following three fundamental logical connectives:
Conjunction. The conjunction of two logical statements is true exactly when both statements are true. If \(P\) and \(Q\) are logical statements then the conjunction is denoted by \(P\land Q\) (pronounced “\(P\) and \(Q\)”) and the truth value can be described using a logic table (or truth table). \[ \begin{array}{c|c|c} P&Q&P\land Q\\\hline T&T&T\\ T&F&F\\ F&T&F\\ F&F&F \end{array} \]
Disjunction. The disjunction of two logical statements is true exactly when at least one of the statements are true. If \(P\) and \(Q\) are logical statements then the disjunction is denoted by \(P\lor Q\) (pronounced “\(P\) or \(Q\)”) and the truth table is \[ \begin{array}{c|c|c} P&Q&P\lor Q\\\hline T&T&T\\ T&F&T\\ F&T&T\\ F&F&F \end{array} \] When we say “or” we will always mean the inclusive or, that is one or both of the statements are true unless we explicitly say that one or other but not both statements holds. For example when we say
if \(a\) is even or \(b\) is even then \(ab\) is even
then the predicate “\(a\) is even or \(b\) is even” allows the cases
- \(a\) even and \(b\) odd;
- \(a\) odd and \(b\) even; and also allows the case
- \(a\) even and \(b\) even.
- Negation. The negation of a logical statement is true exactly when the statement is false. If \(P\) is a logical statement then the negation is denoted by \(\lnot P\) (pronounced “not \(P\)”) and the truth table is \[ \begin{array}{c|c} P&\lnot P\\\hline T&F\\ F&T \end{array} \] For example if \(P\) is the statement “\(2047\) is a prime number” then \(\lnot P\) means “it is false that \(2047\) is a prime number”; a statement which would normally be written / read as “\(2047\) is not a prime number”.
Note that bracketing of expressions is important: \((P\land Q) \lor R\) is different to \(P\land (Q\lor R)\). Likewise \((\lnot P) \land Q\) is different to \(\lnot (P \land Q)\).
By convention if we write \(\lnot P \land Q\) then we mean the former: \((\lnot P) \land Q\). We will not write expressions such as \(P\land Q \lor R\) as these are ambiguous.
When statements are written in words the “bracketing” may be ambiguous, so one must be careful to avoid confusion. How should the following statement be read?
if \(a\) is even or \(b\) is even and \(c\) is odd then \(ab+c\) is odd
From the context we might reasonably guess the intended meaning as being:
if ((\(a\) is even \(\lor\) \(b\) is even) \(\land\) \(c\) is odd) then \(ab+c\) is odd
To avoid ambiguity with writing this in words we might say something along the following lines:
Suppose that \(a\) is even and \(b\) is even. Then if \(c\) is odd then \(ab+c\) is odd
Conjunction, disjunction and negation are sufficient to build any other true/false-valued combinations of statements.
Exclusive OR \[ \begin{array}{c|c|c} P&Q&P \text{ xor } Q\\\hline T&T&F\\ T&F&T\\ F&T&T\\ F&F&F \end{array} \] We can write \(P\) xor \(Q\) as \[(P\lor Q) \land (\lnot P \lor \lnot Q).\] Here \((P\lor Q)\) tells us that at least one of \(P,Q\) is true while \((\lnot P \lor \lnot Q)\) says that at least one of \(P,Q\) is false. Hence the conjunction of these two expressions will be true when exactly one of \(P,Q\) is true and exactly one is false.
Another way to write \(P\) xor \(Q\) is as \[(P\lor Q) \land \lnot( P \land Q).\] Again \((P\lor Q)\) tells us that at least one of \(P,Q\) is true while \(\lnot( P \land Q)\) means “it is not true that both \(P,Q\) are true” so again the conjunction tells us that exactly one of \(P,Q\) is true.
Yet another way to write it is to say that we have two allowed cases: \(P\) is true and \(Q\) is false; \(P\) is false and \(Q\) is true. In symbols we can write this as the disjunction \[(P\land \lnot Q) \lor (\lnot P \land Q).\] Since each of these expressions are true in exactly the same cases we say that they are logically equivalent.