Inference Rules and Proofs
CSI 2101: Discrete Structures
School of Electrical Engineering and Computer Science, University of Ottawa
January 26, 2022
Copyright By PowCoder代写 加微信 powcoder
Md. Hasan (uOttawa) Discrete Structures 1d MdH W22 January 26, 2022 1 / 14
1 Rules of Inference
Md. Hasan (uOttawa) Discrete Structures 1d MdH W22 January 26, 2022 2 / 14
Valid Arguments
Argument
A sequence of statements that end with a conclusion.
Valid Argument
An argument is valid when its conclusion follow from the truth of the preceeding statements, or premises. In other words, an argument is valid if and only if it is impossible for all the premises to be true and the conclusion to be false.
Fallacies
Fallacies are incorrect reasonings, which lead to invalid arguments.
Md. Hasan (uOttawa) Discrete Structures 1d MdH W22 January 26, 2022 3 / 14
Valid Arguments (cont.)
Valid Arguments in Propositional Logic p→q
– “If it is raining (p), then the class is cancelled (q)” – “It is raining (p)”
– Therefore, “The class is cancelled (q)”
An argument in propositional logic is a sequence of propositions. All but the final proposition is called premises and the final proposition is called the conclusion.
(p1 ∧ p2 ∧ … ∧ pn) → q (Tautology)
Md. Hasan (uOttawa) Discrete Structures 1d MdH W22 January 26, 2022 4 / 14
Rules of Inference for Propositional Logic
Rules of inference are used to check the validity of arguments. Thus, the construction of lengthy truth tables are avoided.
Rule of Inference
∴ ¬p p → q q → r
Table: Rules of Inference Tautology
(p ∧ (p → q)) → q
(¬q ∧ (p → q)) → ¬p
((p → q) ∧ (q → r)) → (p → r)
Modus ponens
Modus tollens
Hypothetical syllogism
Md. Hasan (uOttawa)
Discrete Structures 1d MdH W22
January 26, 2022
Rules of Inference for Propositional Logic (cont.)
Rule of Inference
∴p∨q p ∧ q
∴p∧q p ∨ q ¬p ∨ r
((p ∨ q) ∧ ¬p) → q
p → (p ∨ q)
(p ∧ q) → p
((p) ∧ (q)) → (p ∧ q)
((p ∨ q) ∧ (¬p ∨ r)) → (q ∨ r)
Disjunctive syllogism
Simplification
Conjunction
Resolution
Table: Rules of Inference (cont.)
Md. Hasan (uOttawa)
Discrete Structures 1d MdH W22
January 26, 2022
(Textbook Section 1.6)
Show that the premises “It is not sunny this afternoon and it is colder than yesterday,” “We will go swimming only if it is sunny,” If we do not go swimming, then we will take a canoe trip,” and “If we take a canoe trip, then we will be home by sunset” lead to the conclusion “We will be home by sunset.”
“It is sunny this afternoon” (p) “It is colder than yesterday” (q) “We will go swimming” (r)
“We will take a canoe trip” (s) “We will be home by sunset” (t)
Md. Hasan (uOttawa) Discrete Structures 1d MdH W22 January 26, 2022 7 / 14
Rules of Inference for Quantified Statements
Table: Rules of Inference
Rule of Inference
P(c) for an arbitrary c ∴ ∀xP(x)
∴ P(c) for some element c P(c) for some element c ∴ ∃xP(x)
Universal instantiation
Universal generalization
Existential instantiation
Existential generalization
Md. Hasan (uOttawa)
Discrete Structures 1d MdH W22
January 26, 2022
(Textbook Section 1.6)
Show that the premises “A student in this class has not read the book,” and “Everyone in this class passed the first exam” imply the conclusion “Someone who passed the first exam has not read the book.”
“x is in this class” C(x)
“x has read the book” B(x)
“x passed the first exam” P(x)
Md. Hasan (uOttawa) Discrete Structures 1d MdH W22 January 26, 2022 9 / 14
A proof is a valid argument that establishes the truth of a mathematical statement.
A formal proof includes all steps and the rules for each step in an argument. Formal proofs of useful theorems can be extremely long and hard to follow. In practice, the proofs of theorems designed for human consumption are almost always informal proofs. In an informal proof, steps may be skipped, the axioms being assumed.
A theorem is a statement that can be shown to be true. The term theorem is usually reserved for a statement that is considered at least somewhat important. Less important theorems are called propositions.
Md. Hasan (uOttawa) Discrete Structures 1d MdH W22 January 26, 2022 10 / 14
Proofs (cont.)
Axioms or postulates are statements that are assumed to be true.
A less important theorem that is helpful in the proof of other results is called a lemma. Complicated proofs are usually easier to understand when they are proved using a series of lemmas, where each lemma is proved individually.
A corollary is a theorem that can be established directly from a theorem that has been proved.
A conjecture is a statement that is being proposed to be a true statement, usually on the basis of some partial evidence, a heuristic argument, or the intuition of an expert. It becomes a theorem when a proof is found.
Md. Hasan (uOttawa) Discrete Structures 1d MdH W22 January 26, 2022 11 / 14
Proving Theorems
To prove a theorem of the form ∀x(P(x) → Q(x)), the goal is to show that P(c) → Q(c) is true, where c is an arbitrary element of the domain, and then apply universal generalization. Ultimately, it is necessary to show a conditional statement is true. The statement p → q is a general form of such a statement.
A direct proof of a conditional statement p → q is constructed when the first step is the assumption that p is true; subsequent steps are constructed using rules of inference, with the final step showing that q must also be true.
Proofs that do not start with the premises and end with the conclusion, called indirect proofs.
– Proof by contraposition – Proof by contradiction
Md. Hasan (uOttawa) Discrete Structures 1d MdH W22 January 26, 2022 12 / 14
Proving Theorems (cont.)
Proof by Contraposition
The conditional statement p → q can be proved by showing that its
contrapositive, ¬q → ¬p, is true. Proof by Contradiction
To prove a statement p is true, a contradiction q is chosen such that
¬p → q is true. As q is false and ¬p → q is true, ¬p has to be false. This means p is true. A proof by contradiction can succeed when a direct proof is not easily found.
Mistakes in Proofs
It is an important task to find mistakes in proofs. Each step of a mathematical proof needs to be correct and the conclusion needs to follow logically from the steps that precede it.
Md. Hasan (uOttawa) Discrete Structures 1d MdH W22 January 26, 2022 13 / 14
Thank You!
Questions and Comments?
Md. Hasan (uOttawa) Discrete Structures 1d MdH W22 January 26, 2022 14 / 14
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com