CSC 224/226 Notes Packet #1: Logic and Proofs
Packet #1: Logic & Proofs
Applied Discrete Mathematics
Table of Contents
Course ObjectivesPage 2
Propositional Calculus InformationPages 3-13
Course Objectives
At the conclusion of this course, you should be able to
1. Represent logical statements in propositional and predicate calculus, and use truth tables and formal proofs to determine their truth values.
2. Create a truth table for a logical expression. Derive a logical expression from a given truth table. Design a circuit to perform a simple task.
3. Construct a circuit from a logical expression using AND, OR, and NOT gates. Simplify logical expressions. Derive a logical expression from a given circuit.
4. Describe set notations using predicate calculus. Determine the power of a set. Use predicate calculus to prove set theoretic propositions.
5. Describe and use the first, second, and general principles of proof by induction. Derive closed form representations for recursively defined sequences; prove their correctness by induction. Derive recursive sequences from closed form functions and prove their equivalence by induction.
6. Describe asymptotic growth of functions, compare functions using big-oh notation. Compare asymptotic growth and prove inequalities by induction. Determine and solve recurrences arising from algorithms. Determine big-oh running times for algorithms.
7. Define binary relations and their properties using predicate calculus. Represent binary relations as ordered pairs, matrices, predicates, or graphs. Combine binary relations by union, intersection, and composition using matrix operations. Find the reflexive, symmetric, and transitive closures of a binary relation.
8. Describe and calculate permutations and combinations with and without replacement and with and without distinguishable objects. Describe and apply the pigeonhole principle.
9. Describe and determine the existence of Euler circuits and paths and Hamilton circuits and paths in graphs. Determine the minimum spanning tree of a graph. Construct and analyze Hasse diagrams for partially ordered sets.
Propositional Calculus Outline
I.Proposition (Sections 1.1 and 1.2)
A.Definition
B.Compound
1.Connectives: ,,¬,,,,,
2.Variables
II.Truth Tables (Sections 1.1 and 1.2)
A.Table of compound results using all combinations of input variables
B.Definitions
1.
2.
3.¬
4.
5.
6.
7.
8.
C.Tautology and Contradiction - using truth tables for short proofs
D.Logical Implications
E.Logical Equivalences
III.Formal Proofs using statements and reasons (Section 3.1)
A.Axioms of Logical Implications
B.Axioms of Logical Equivalences
C.Two substitution rules
IV.Types of formal proofs (Section 3.1)
A.Direct
B.Indirect
1.Contradiction
2.Other
V.Hints for Attacking a propositional calculus proof
VI.Logic Functions (Section 9.1)
A.Number of cases
B.Disjunctive Normal Form
C.Generation of logic statements from truth table
VII.Logic Circuits (Section 9.3)
A.Finding logic circuit for given logic function
B.Finding logic function for given logic circuit
C.Manipulating the logic function for specific characteristics and designing new logic circuit
D.Creating logic function from input-output specifications
Propositional Calculus
A.Proposition - a sentence or statement which is either true or false but NOT BOTH. It cannot be unspecified (ambiguous) or vacuous.
1.n> n for all integers n>1
2.n= n (ambiguous)
3.How are you? (vacuous)
B.Compound propositions
1.lower case letters stand for propositions -- q, p, r, etc.
2.connectives between propositions
¬not or negative
and
or (inclusive)
implies
if and only if
or (exclusive)
Examples:
p q
(p q) (s t )
At this time we will consider only a finite number of connectives.
Converse:
p qq p is converse
Contrapositive:
p q¬q ¬p is contrapositive
Truth Tables:
1.Simple propositions are input (independent) variables that are either true or false.
2.Compound proposition (output) is either true or false.
3.1 = true; 0 = false
4.Must consider all combinations of input variables.
Example 1.1: p q; that is p q q p(Equivalence rule)
p q p q q p
0 0 1 11
0 1 1 00
1 0 0 01
1 1 1 11
If p q is true (=1) then p = q
Tautology – A proposition that is always true independent of input values
(e.g. p ¬p).
Contradiction – A proposition that is always false independent of input values
(e.g. p ¬p) .
TautologyContradiction
p ¬p p ¬p p ¬p
0 1 1 0
1 0 1 0
Truth Tables for Connectives
p q:p q:
p q p qp q p q
0 0 00 0 0
0 1 10 1 0
1 0 11 0 0
1 1 11 1 1
¬p:p q:
p ¬pp q p q
0 10 0 1
1 00 1 1
1 0 0
1 1 1
p q:p q:
p q p qp q p q
0 0 10 0 0
0 1 00 1 1
1 0 01 0 1
1 1 11 1 0
Example 1.2: (p r) (¬p r)(implication rule)
p r (p r) (¬p r) ¬p
0 0 1 1 1 1 1
0 1 1 1 1 1 1
1 0 0 1 1 0 0
1 1 1 1 1 1 0
Logical equivalences
Example 1.3: (p q) (q r) (p r)(Hypothetical Syllogism)
p q r (p q) (q r) (p r)
0 0 0 1 1 1 1 11
0 0 1 1 1 1 1 11
0 1 0 1 0 0 1 01
0 1 1 1 1 1 1 11
1 0 0 0 1 0 1 10
1 0 1 0 1 0 1 01
1 1 0 1 0 0 1 10
1 1 1 1 1 1 1 11
oknot true
Note that this rule works only from LEFT to RIGHT and not vice-versa. It is called a “Logical implication”, whose symbol is ”P logically implies Q” is writtenPQ.
Example 1.4: (p q) s p s(Implication)
p q s (p q) s p s
0 0 0 0 1 11
0 0 1 0 1 11
0 1 0 1 0 11
0 1 1 1 1 11
1 0 0 1 0 10
1 0 1 1 1 11
1 1 0 1 0 10
1 1 1 1 1 11
Formal Proof for (p q) s p s:
Statement Reason
1.(p q) s Hypothesis
2.p p q Addition
3.p s 1,2; Hypothetical Syllogism
Class Lemma: if (p q) s then p s and q s
Example 1.5: [(s g) p] (p a) ¬a ¬g
s gp a (s g) p (p a) ¬a ¬g ¬g ¬a
0 0 0 00 1 1 1 1111
0 0 0 10 1 1 1 1110
0 0 1 00 1 0 0 1111
0 0 1 10 1 1 1 1110
0 1 0 01 0 1 0 1001
0 1 0 11 0 1 0 1100
0 1 1 01 1 0 0 1001
0 1 1 11 1 1 1 1100
1 0 0 01 0 1 0 1111
1 0 0 11 0 1 0 1110
1 0 1 01 1 0 0 1111
1 0 1 11 1 1 1 1110
1 1 0 01 0 1 0 1001
1 1 0 11 0 1 0 1100
1 1 1 01 1 0 0 1001
1 1 1 11 1 1 1 1100
Formal Proof:
Statements Reasons
1.(s g) p Hypothesis
2.p a Hypothesis
3.g p 1; Class Lemma
4.g a 2, 3; Hypothetical Syllogism
5.¬a ¬g 4; Contrapositive
Example 1.6: Formal Proof
Given:p qProve:s r
q s
p r
Direct Proof:
Statements Reasons
1.p q Assumption
2.q s Assumption
3.p r Assumption
4.(p q) (r s) 2, 3; 26a Constructive Dilemma
5.r s 1, 4; Modus Ponens
6.s r 5; Commutative
In a direct proof one needs to show that given p then q, i.e. p q.
For an indirect proof one can use any logically equivalent method. A common type of indirect proof is proof by contradiction. One assumes the negation of the conclusion along with the assumptions and shows a contradiction.
i.e. (p ¬q) 0 p q
p¬q c (p¬q)0 pq pq
0 0 1 10 0
0 0 1 10 1
1 0 0 01 0
0 0 1 11 1
logically equivalent
Example 1.7: Proof by Contradiction:
Statements Reasons
1.p q Assumption
2.q s Assumption
3.p r Assumption
4.¬(s r) Negation of Conclusion
5.¬s ¬r 4; DeMorgan
6.¬s 5; Simplification
7.¬q 2, 6; Modus Tollens
8.¬r ¬s 5; Commutative
9.¬r 8; Simplification
10.¬p 3, 9; Modus Tollens
11.¬p ¬q 7, 10; Conjunction
12.¬(p q) 11; DeMorgan
13.¬(p q) (p q) 1, 12; Conjunction
14.Contradiction 13; Rule 7b
Two Substitution Rules
1.If a compound proposition P is a tautology and if all occurrences of some variable of P, say a, are replaced by the same proposition E, then the resulting compound proposition Pis also a tautology. [Does not necessarily give same proposition.]
a q ¬a q is a tautology. If for all occurrences of p we substitute (s r). (s r) q ¬(s r) q is also a tautology.
2.If compound proposition P contains a proposition Q and if Q is replaced by a logically equivalent proposition Q, then the resulting compound proposition Pis logically equivalent to P.
p q ¬q ¬p is a proposition.
p q ¬p q i.e., ¬p q is logically equivalent to p q.
Therefore, ¬p q ¬q ¬p is logically equivalent to p q ¬q ¬p.
Logic Circuits
Useful reduction rules:
De Morgan's:
(X + Y)' = X'Y'
(XY)' = X' + Y'
[P + (QR)] = (P + Q)(P + R)
P(Q + R) = PQ + PR
1