Discrete Mathematics Note Chapter 1
Logic and Proofs
Propositional Logic
Proposition
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\)."
Precedence
\(\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:
- \(p \downarrow p \equiv \lnot p\).
- \((p\downarrow q) \downarrow (p \downarrow q) \equiv p \lor q\).
- \((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
Predicate
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:
- Assume all premises are true
- 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.
Terms
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.
Contradiction
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)\).
Constructive
- Establish \(P(c)\) is \(\mathrm{T}\) for some \(c\).
- Use Existential Generalization, \(\exists x P(x)\) is true.
Nonconstructive
- Assume no \(c\) exists that \(P(c)\) is \(\mathrm{T}\).
- Find a contradiction.
Uniqueness Proof
To prove \(\exists x (P(x) \wedge \forall y (y \neq x \rightarrow \lnot P(y)))\).
- Prove existence of qualified \(x\).
- 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