Logic

Foundations of mathematics

Introduction

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.

Prerequisites

To understand logic, we recommend familiarity with the concepts in

Follow the above links to first get acquainted with the corresponding concepts.

Logic: Propositions

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.

Examples of true propositions

  1. The integer 2 is even
  2. 32 is divisible by 16
  3. No odd number is divisible by 2

Examples of false propositions

  1. \( 5 = 2 \)
  2. \( \real \subseteq \natural \)

Examples of non-propositions

  1. Add \( 2 \) to both sides
  2. 42
  3. What is the solution of \( 4x = 32 \)?

Logic: Proposition notation

It is customary to denote a proposition with capital letter, usually starting with \( P, Q, R, \ldots \).

For example, consider the following propositions

  1. \( P \): The integer \( 2 \) is even.
  2. \( Q \): \( 32 \) is divisible by \( 16 \)

Logic: Open sentence

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 $$

Examples of open sentences

  1. \( P(x): \) The integer \( x \) is divisible by 3
  2. \( Q(x,y): 5x = 2y \)

Logic: Open sentence over a domain

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 \).

Logic: Truth value

Every proposition has a truth value, namely true or false, usually denoted by \( T \) and \( F \), respectively.

Examples

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 \).

Logic: Truth table

The possible truth values of a proposition are listed in a table known as a truth table.

Example

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

Logic: Negation of a proposition

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

Example

$$ P : \text{The integer 2 is even} $$

$$ \neg P : \text{The integer 2 is not even} $$

Disjunction of propositions

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

Conjunction of propositions

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

Logic: Exclusive or

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

Logic: Implication

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.

Examples

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} $$

Logic: Expressing implications

Implications are frequently encountered in mathematical reasoning and proofs. The implication \( P \Rightarrow Q \) is commonly expressed in these ways

  1. If \( P \), then \( Q \)
  2. \( P \) implies \( Q \)
  3. \( P \) only if \( Q \)
  4. \( P \) is sufficient for \( Q \)
  5. \( Q \) if \( P \)
  6. \( Q \) whenever \( P \)
  7. \( Q \) is necessary for \( P \)

It is generally a good idea to remember these various ways of verbalizing implications to detect them in mathematical literature.

Logic: Converse of an implication

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

Logic: Contrapositive of an implication

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.

Logic: Biconditional

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 \)".

Logic: Connectives

The negation \( \neg \), disjunction \( \vee \), conjunction \( \wedge \), implication \( \Rightarrow \), and biconditional \( \Leftrightarrow \) are referred to as logical connectives.

Logic: Compound propositions

Individual propositions, known as the component propositions are combined using logical connectives to form a compound proposition.

Examples

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.

Logic: Tautology

If a compound proposition is true for all truth values of the component propositions, then the compound proposition is known as a tautology.

Example

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

Logic: Contradiction

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.

Example

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

Logic: Equivalent propositions

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 \)".

Example

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

Logic: Commutative law

The disjunction and conjunction operations are commutative. This means

$$ P \vee Q \equiv Q \vee P $$ $$ P \wedge Q \equiv Q \wedge P $$

Logic: Associative law

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 $$

Logic: Distributive law

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) $$

Logic: De Morgan's law

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) $$

Logic: Quantified propositions

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.

Logic: Universal quantifier

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) \).

Logic: Existential quantifier

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) \).

Next-article

With a sound understanding of logic, you are ready for a comprehensive overview of strategies for developing mathematical proofs.

Please share

Let your friends, followers, and colleagues know about this resource you discovered.

Let's connect

Please share your comments, questions, encouragement, and feedback.