# CS代考 CSI 2101: Discrete Structures – cscodehelp代写

Inference Rules and Proofs

CSI 2101: Discrete Structures

School of Electrical Engineering and Computer Science, University of Ottawa

January 26, 2022

Copyright By cscodehelp代写 加微信 cscodehelp

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代考 加微信: cscodehelp QQ: 2235208643 Email: kyit630461@163.com