Discrete Mathematics Note Chapter 1

Logic and Proofs

Propositional Logic


Definition: A proposition is a declarative sentence that is either true or false, but not both.

Truth value

Big \(\mathrm{T}\) for true and big \(\mathrm{F}\) for false.

Logical operators (Connectives)

Negation (Not)

The negation of \(p\), \(\lnot p\), is the proposition "It is not the case that \(p\)."

Conjunction (And)

The conjunction of \(p\) and \(q\), is the proposition "\(p\) and \(q\)."

Disjunction (Inclusive Or)

The disjunction of \(p\) and \(q\), is the proposition "\(p\) or \(q\)."

Exclusive Or (Xor)

The exclusive or of \(p\) and \(q\), is the proposition "\(p\) or \(q\), but not both."

Conditional Operator (If-then)

The conditional statement of \(p\) and \(q\), is the proposition "if \(p\), then \(q\)."

\(p \rightarrow q\) is false only when \(p\) is true and \(q\) is false.

Converse: \(q \rightarrow p\) Inverse: \(\lnot p \rightarrow \lnot q\) Contrapositive: \(\lnot q \rightarrow \lnot p\).

Biconditional Operator

The biconditional statement of \(p\) and \(q\), is the proposition "\(p\) if and only if \(q\)."


\(\lnot > \land > \lor > \rightarrow > \leftrightarrow\).

Truth Table

Columns display variables and propositions; Rows display different cases.

For \(n\) variables, there will be \(2^n\) rows.

Applications of Propositional Logic

System specification: Express English sentences in logical statements.

Consistent system specification: A list of propositions is consistent if it is possible to assign truth values to the proposition variables so that each proposition is true.

Propositional Equivalences

Compound Propositions

Tautology: statement that is always true.

Contradiction: statement that is always false.

Contingency: its value depends.

Logical Equivalence

Propositions \(p\) and \(q\) are called logically equivalent if \(p \leftrightarrow q\) is a tautology. This case can be denoted as \(p \Leftrightarrow q\), or \(p \equiv q\).

Already proved equivalence

Laws Law Names
\(p \land \mathrm{\mathrm{T}} \equiv p\), \(p \lor \mathrm{F} \equiv p\) Identity laws
\(p \land \mathrm{F} \equiv \mathrm{F}\), \(p \lor \mathrm{T} \equiv \mathrm{T}\) Domination laws
\(p \lor p \equiv p, p \land p \equiv p\) Idempotent laws
\(\lnot (\lnot p) \equiv p\) Double negation law
\(p \land q \equiv q \land p, \\ p \lor q \equiv q \lor p\) Commutative laws
\(p \lor (q \lor r) \equiv (p \lor q) \lor r,\\ p \land (q \land r) \equiv (p \land q) \land r\) Associative laws
\(p \lor (q \land r) \equiv (p \lor q) \land (p \lor r),\\ p \land (q \lor r) \equiv (p \land q) \lor (p \land r)\) Distributive laws
\(\lnot (p \land q) \equiv \lnot p \lor \lnot q,\\ \lnot (p \lor q) \equiv \lnot p \land \lnot q\) De Morgan's laws
\(p \lor (p \land q) \equiv p,\\ p \land (p \lor q) \equiv p\) Absorption laws
\(p \lor \lnot p \equiv \mathrm{T}, p \land \lnot p \equiv \mathrm{F}\) Negation laws

The operator \(\downarrow\) is called Peirce arrow, and stands for \(Nor\) operation. It's functional complete, and we have:

  1. \(p \downarrow p \equiv \lnot p\).
  2. \((p\downarrow q) \downarrow (p \downarrow q) \equiv p \lor q\).
  3. \((p \downarrow p) \downarrow (q \downarrow q) \equiv p \land q\).

Propositional Satisfiability

A compound proposition is satisfiable if there is an assignment to all variables that make it true.

If it is a contradiction, it is called unsatisfiable.

Predicates and Quantifiers


A predicate is a statement that contains variables. Once the variables' values are set, its truth value is set too.

Universal Quantification

A universal quantification of \(P(x)\), denoted by \(\forall x\ P(x)\), is the statement that "\(P(x)\) is true for all x in the domain."

It's equivalent of \(\bigcap\limits_{x \in D} P(x)\).

Existential Quantification

An existential quantification of \(P(x)\), denoted by \(\exists x\ P(x)\), is the statement that "\(P(x)\) is true for at least one x in the domain".

It's equivalent of \(\bigcup\limits_{x \in D} P(x)\).

Binding Variables

A variable constrained by quantifiers is called bound variable. Otherwise, it's called Free variable.

Constants are not in any of the two types.

Logical Equivalences Involving Quantifiers

Two statements are logically equivalent \(\mathrm{iff}\) they have the same truth value when predicates specified in the same set of values.

Some useful equivalence

\(\forall x (A(x) \land B(x)) \equiv \forall x A(x) \land \forall x B(x)\).

\(\exists x (A(x) \lor B(x)) \equiv \exists x A(x) \lor \exists x B(x)\).

\(\lnot \forall x P(x) \equiv \exists x \lnot P(x)\).

\(\lnot \exists x P(x) \equiv \forall x \lnot P(x)\).

\(\forall x(P(x) \rightarrow A) \equiv \exists x P(x) \rightarrow A\).

\(\forall x(A \rightarrow P(x)) \equiv A \rightarrow \forall x P(x)\).

Nested Quantifiers

Two quantifiers are nested if one is within the scope of the other.

The order of nested quantifiers matters when they are of different types.

Rules of Inference

Valid Arguments

An argument in propositional logic is a sequence of statements that end with a conclusion.

Valid arguments are called proofs. Valid means the preceding statements determines the truth of the conclusion.

An argument form in propositional logic is a sequence of compound propositions involving propositional variables.

Valid argument forms are those whose value is true once their premises are all true in propositional variables forms.

An argument's validity is identical with its form's validity.

To prove validity:

  1. Assume all premises are true
  2. Use the rules of inference and logical equivalence to determine that the conclusion is true

Rules of Inference

Rules of inference are simple argument forms whose correctness can be established with truth tables.

Rules Rule Names
\((p\ \land\ (p\rightarrow q)) \rightarrow q\) Modus ponens
(mode that affirms in Latin)
\((\lnot q\ \land\ (p \rightarrow q)) \rightarrow \lnot p\) Modus tollens
(mode the denies in Latin)
\(((p \rightarrow q)\ \land\ (q \rightarrow r)) \rightarrow (p \rightarrow r)\) Hypothetical Syllogism
\(((p \lor q) \land \lnot p) \rightarrow q\) Disjunctive Syllogism
\(p \rightarrow (p \lor q)\) Addition
\((p \land q ) \rightarrow p\) Simplification
\(((p \lor q)\ \land\ (\lnot p \lor r)) \rightarrow (q \lor r)\) Resolution

Adding quantifiers, we have another table.

Rules Rule Names
\(\dfrac{\forall x P(x)}{\therefore P(c)}\) Universal instantiation
\(\dfrac{P(c)\ \mathrm{for\ any\ } c}{\therefore \forall x P(x)}\) Universal generalization
\(\dfrac{\exists x P(x)}{\therefore P(c)\ \mathrm{for\ some\ } c}\) Existential instantiation
\(\dfrac{P(c)\ \mathrm{for\ some\ } c}{\therefore \exists x P(x)}\) Existential generalization

If you deny the premises to prove the negation of conclusion, or affirm the conclusion to prove the premises, then you may walk in the trap of fallacy.

Introduction of Proofs

The construction of a valid proof is an art, honed after much practice.


A proof is valid argument establishes the truth of a mathematical statement.

A theorem is a statement shown true.

A axiom is a statement we assume to be true.

A lemma is a less important theorem helpful in proving.

A corollary is a derived lemma from theorems.

A conjecture is a guess statement that is being proposed to be true. It becomes a theorem once it has been proved true.

Direct Proof

\(\forall x (P(x) \rightarrow Q(x)) \Leftrightarrow P(c) \rightarrow Q(c)\) for arbitrary \(c\).

\(\rightarrow:\) Universal instantiation

\(\leftarrow:\) Universal generalization

Assume \(P(x)\) is true, and use rules and other theorems to reach \(Q(x)\).

Contraposition Proof

\[ P \rightarrow Q \equiv \lnot Q \rightarrow \lnot P \]

So we can assume \(\lnot Q(x)\) is true, and then try to reach \(\lnot P(x)\).

Vacuous Proof

If we know \(P\) is false then \(P \rightarrow Q\) is vacuously true.

Trivial Proof

If we know \(Q\) is true then \(P \rightarrow Q\) is trivial true.


Try to prove \(p\), we can assume \(p\) is false, and then deduce \(p \rightarrow (q \vee \lnot q )\).

Another form: For \(p \rightarrow q\), we can assume \(\lnot q \wedge p\), and then deduce \((\lnot q \wedge p) \rightarrow (t \wedge \lnot t)\).

Proofs of Equivalence

To show \(p_1, p_2, \ldots, p_n\) are equivalent, we can prove that \(p_1 \rightarrow p_2 \rightarrow \cdots \rightarrow p_n\), and then prove \(p_n \rightarrow p_1\).

Proof Methods and Strategy

Proof by Cases

Break the premise \(p\) into \(p_1, p_2, \ldots p_n\). And prove that \(p_i \rightarrow q\) for all \(i\).

Finally we have \((\bigwedge (p_i \rightarrow q)) \leftrightarrow ((\bigvee p_i) \rightarrow q)\).

Existence Proof

To prove \(\exists x P(x)\).


  1. Establish \(P(c)\) is \(\mathrm{T}\) for some \(c\).
  2. Use Existential Generalization, \(\exists x P(x)\) is true.


  1. Assume no \(c\) exists that \(P(c)\) is \(\mathrm{T}\).
  2. Find a contradiction.

Uniqueness Proof

To prove \(\exists x (P(x) \wedge \forall y (y \neq x \rightarrow \lnot P(y)))\).

  1. Prove existence of qualified \(x\).
  2. Prove that \(y \neq x \rightarrow \lnot P(y)\), or prove \((P(x) \wedge P(y)) \rightarrow x = y\).

Backward Reasoning

To prove a statement \(q\), we try to find a provable statement \(p\) that \(p \rightarrow q\) holds.

By using this method recursively, we may finally reach those given premises.

Additional Methods of Proofs

  • Mathematical induction

  • Structural induction

  • The Cantor diagonalization argument

  • Combinatorial proofs