Logic is a way of deducing new facts based on previously known facts. In the field of Mathematics, the study of logic is essential as a means of arriving at proofs and theorems.
In Mathematical logic, we will explore propositions, assertions, and truth values as a language for expressing mathematical facts. Then, we will consider conjunctions, disjunctions, implications, and the biconditionals as a means of combining known facts to derive new facts.
A proposition is a sentence or a mathematical expression that is either definitely true or definitely false.
Some texts also refer to propositions as statements. A subtle difference is that a proposition is an abstract logical concept, but the statement is the way of expressing that concept. For example, the same proposition may be referred by a different statement in two different languages.
Propositions cannot be questions, procedures, or just numbers. Any theorem or result that has been proved true is a proposition.
It is customary to denote a proposition with capital letter, usually starting with \( P, Q, R, \ldots \).
For example, consider the following propositions
A proposition with variables is known as an open sentence, predicate, open statement, or a propositional function.
Open sentences are denoted by parametrizing the corresponding proposition with the variable.
$$ P(x) : \text{An open sentence involving the variable } x $$
In the case of an open sentence with the variable \( x \), if the domain of the variable \( x \) is known to be the set \( S \), then the proposition is known as an open sentence over the domain \( S \).
Every proposition has a truth value, namely true or false, usually denoted by \( T \) and \( F \), respectively.
Consider the proposition "Every even number is divisible by 2". The truth value of this proposition is \( T \).
As another example, consider the proposition "49 is divisible by 9". The truth value of this proposition is \( F \).
The possible truth values of a proposition are listed in a table known as a truth table.
For example, the following table lists the negation logical operation, which negates the truth value of the statement -- true changes to false and vice versa.
| \(P\) | \(\neg P\) |
|---|---|
| T | F |
| F | T |
The negation of a proposition modifies the truth value of that proposition -- true changes to false and vice versa. The negation of a proposition \( P \) is denoted as \( \neg P \) and vocalized as "not \( P \)".
The following truth table lists the negation operation.
| \(P\) | \(\neg P\) |
|---|---|
| T | F |
| F | T |
$$ P : \text{The integer 2 is even} $$
$$ \neg P : \text{The integer 2 is not even} $$
The logical or of propositions is known as their disjunction. The disjunction of two propositions \( P \) and \( Q \) is true when either of them is true. It is denoted as \( P \vee Q \) and it is vocalized as "\( P \) or \( Q \)".
The following truth table lists possible outcomes of a disjunction of two propositions.
| \(P\) | \(Q\) | \( P \vee Q \) |
|---|---|---|
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
The logical and of propositions is known as their conjunction. The conjunction of two propositions \( P \) and \( Q \) is true when both of them are simultaneously true. It is denoted as \( P \wedge Q \) and it is vocalized as "\( P \) and \( Q \)".
The following truth table lists possible outcomes of a conjunction of two propositions.
| \( P \) | \( Q \) | \( P \wedge Q \) |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
The exclusive-or of two propositions is true when either of them is true, but not when both of them are true. It is usually denoted as \( P \oplus Q \) and it is vocalized as "\( P \) or \( Q \), but not both", or "\( P \) xor \( Q \)".
The following truth table lists possible outcomes of an exclusive-or of two propositions.
| \( P \) | \( Q \) | \( P \oplus Q \) |
|---|---|---|
| T | T | F |
| T | F | T |
| F | T | T |
| F | F | F |
In logic, a materical conditional is a proposition of the form If the proposition \( P \) is true, then the proposition \( Q \) is also true. A material conditional is also known as an implication or simply as a conditional proposition.
An implication is denoted as \( P \Rightarrow Q \) and vocalized as "\( P \) implies \( Q \)" or "If \( P \), then \( Q \)".
By definition, the implication \( P \Rightarrow Q \) is false only when \( P \) is true and \( Q \) is false. Because \( P \) being true is enough to make \( Q \) true, it is also said that "\(P\) is a sufficient condition for \( Q \)".
Here's the truth table of the implication.
| \( P \) | \( Q \) | \( P \Rightarrow Q \) |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
In an implication \( P \Rightarrow Q \), the proposition \( P \) is known as the hypothesis, antecedent or premise. The proposition \( Q \) is known as the conclusion, the consequent or the consequence.
Consider the propositions
$$ P: \text{The integer } x \text{ is a multiple of 8} $$ $$ Q: \text{The integer } x \text{ is divisible by 2} $$
It can be shown that for the integer \( x \) when \( P \) is true, then the proposition \( Q \) is also true. In this case the implication \( P \Rightarrow Q \) denotes the proposition
$$ R: \text{If the integer } x \text{ is a multiple of 8, then } x \text{ is divisible by 2} $$
Implications are frequently encountered in mathematical reasoning and proofs. The implication \( P \Rightarrow Q \) is commonly expressed in these ways
It is generally a good idea to remember these various ways of verbalizing implications to detect them in mathematical literature.
For propositions or open sentences, the implication \( Q \Rightarrow P \) is known as the converse of the implication \( P \Rightarrow Q \).
Here's the truth table for the converse.
| \( P \) | \( Q \) | \( P \Rightarrow Q \) | \( Q \Rightarrow P \) |
|---|---|---|---|
| T | T | T | T |
| T | F | F | T |
| F | T | T | F |
| F | F | T | T |
For propositions or open sentences, the implication \( \neg Q \Rightarrow \neg P \) is known as the contrapositive of the implication \( P \Rightarrow Q \).
Here's the truth table for the contrapositive.
| \( P \) | \( Q \) | \( P \Rightarrow Q \) | \( \neg P \) | \( \neg Q \) | \( \neg Q \Rightarrow \neg P \) |
|---|---|---|---|---|---|
| T | T | T | F | F | T |
| T | F | F | F | T | F |
| F | T | T | T | F | T |
| F | F | T | T | T | T |
Note that the truth values of the implication are the same as those of the contrapositive. Thus, they are logically equivalent. This equivalence enables mathematical proofs where directly proving the implication is hard, but the contrapositive is easier to prove.
The conjunction of an implication and its converse is known as a biconditional and is denoted as \( P \Leftrightarrow Q \). Thus,
$$ P \Leftrightarrow Q = (P \Rightarrow Q) \wedge (Q \Rightarrow P) $$
The biconditional \( P \Leftrightarrow Q \) is vocalized as "\( P \) is equivalent to \( Q \)". Thus, the biconditional is true only when both \( P \) and \( Q \) are either both true or both false.
The biconditional truth table is shown below.
| \( P \) | \( Q \) | \( P \Rightarrow Q \) | \( Q \Rightarrow P \) | \( P \Leftrightarrow Q \) |
|---|---|---|---|---|
| T | T | T | T | T |
| T | F | F | T | F |
| F | T | T | F | F |
| F | F | T | T | T |
Biconditional can also be vocalized as "\( P \) if and only if \( Q \)" or "\( P \) is a necessary and sufficient condition for \( Q \)". It is also common to refer to a biconditional as "\( P \) iff \( Q \)".
The negation \( \neg \), disjunction \( \vee \), conjunction \( \wedge \), implication \( \Rightarrow \), and biconditional \( \Leftrightarrow \) are referred to as logical connectives.
Individual propositions, known as the component propositions are combined using logical connectives to form a compound proposition.
In an implication \( P \Rightarrow Q \), the propositions \( P \) and \( Q \) are component propositions, and the implication is a compound proposition.
In a disjunction \( P \vee Q \), the propositions \( P \) and \( Q \) are component propositions and the disjunction is a compound proposition.
If a compound proposition is true for all truth values of the component propositions, then the compound proposition is known as a tautology.
It is easy to see that \( P \vee (\neg P) \) is a tautology.
| \( P \) | \( \neg P \) | \( P \vee \neg P \) |
|---|---|---|
| T | F | T |
| T | F | T |
| F | T | T |
| F | T | T |
If a compound proposition is false for all truth values of the component propositions, then the compound proposition is known as a contradiction.
Note that the negation of a tautology is always a contradiction and vice versa.
It is easy to see that \( P \wedge (\neg P) \) is a contradiction.
| \( P \) | \( \neg P \) | \( P \wedge \neg P \) |
|---|---|---|
| T | F | F |
| T | F | F |
| F | T | F |
| F | T | F |
Two compound propositions are said to be logically equivalent if they have the same truth values for all combinations of truth values of the component propositions. Thus, if two propositions \( P \) and \( Q \) are logically equivalent, then \( P \) and \( Q \) are both simultaneously true or simultaneously false. Thus, the biconditional \( P \Leftrightarrow Q \) is a tautology in the case of logically equivalent propositions.
Logical equivalence of two propositions \( P \) and \( Q \) is denoted as \( P \equiv Q \). It is vocalized as "\( P \) is logically equivalent to \( Q \)".
Observe that the propositions \( P \wedge Q \) and \( Q \wedge P \) are logically equivalent.
| \( P \) | \( P \) | \( P \wedge Q \) | \( Q \wedge P \) |
|---|---|---|---|
| T | T | T | T |
| T | F | F | F |
| F | T | F | F |
| F | F | F | F |
The disjunction and conjunction operations are commutative. This means
$$ P \vee Q \equiv Q \vee P $$ $$ P \wedge Q \equiv Q \wedge P $$
The disjunction and conjunction operations are associative. This means
$$ P \vee (Q \vee R) \equiv (P \vee Q) \vee R $$ $$ P \wedge (Q \wedge R) \equiv (P \wedge Q) \wedge R $$
The disjunction and conjunction operations are distributive. This means
$$ P \vee (Q \wedge R) \equiv (P \vee Q) \wedge (P \vee R) $$ $$ P \wedge (Q \vee R) \equiv (P \wedge Q) \vee (P \wedge R) $$
The negation of a disjunction operation is logically equivalent to the conjunction of negations of the component propositions. This means
$$ \neg (P \vee Q) \equiv (\neg P) \wedge (\neg Q) $$
Similarly, the negation of a conjunction operation is logically equivalent to the disjunction of negations of the component propositions. This means
$$ \neg (P \wedge Q) \equiv (\neg P) \vee (\neg Q) $$
Open sentences such as \( P(x) \) over a domain \( S \) can be converted to a proposition by expressing, for example, "For every \( x \in S, P(x) \)". Here, "for every \( x \in S \)" is known as a quantifier and the resulting proposition is known as a quantified proposition.
The variable is said to be bound if it has been quantified or a value has been assigned to it. Otherwise, it is known as a free variable.
Consider the quantified proposition "For every \( x \in S, P(x) \)". The quantifier "for every", also vocalized as "for each" or "for all" is known as the universal quantifier and is denoted by the symbol \( \forall \).
A proposition quantified with the universal quantifier is known as a universally quantified proposition.
Thus, the quantified proposition "For every \( x \in S , P(x) \)" is expressed in symbolic form as \( \forall x \in S, P(x) \).
Consider the quantified proposition "For some \( x \in S, P(x) \)". The quantifier "for some" is known as an existential quantifier. It is denoted by the symbol \( \exists \). It is vocalized using numerous phrases such as "there exists", "there is", "for some", "for at least one" and they all mean the same thing.
A proposition quantified with the existential quantifier is known as a existentially quantified proposition.
Thus, the proposition "For some \( x \in S, P(x) \)" is expressed symbolically as \( \exists x \in S, P(x) \).
With a sound understanding of logic, you are ready for a comprehensive overview of strategies for developing mathematical proofs.
Help us create more engaging and effective content and keep it free of paywalls and advertisements!
Please share your comments, questions, encouragement, and feedback.