Discrete Structures · Unit 3 · 6 hrs
Logic and Proof Methods
Exam-focused notes for Logic and Proof Methods (Discrete Structures, CSC165): what the TU syllabus asks and how it has actually been tested, with 14 solved past questions from this unit.
What this unit covers
- Logic
- Propositional Logic
- Propositional Equivalences
- Predicates and Quantifiers
- Negation of Quantified Statements
- Proof of quantified statements
- Nested Quantifiers
- Rules of Inferences
- Proof Methods
- Basic Terminologies
- Proof Methods (Direct Proof, Indirect Proof, Proof by Contradiction, Proof By Contraposition, Exhaustive Proofs and Proof by Cases)
- Mistakes in Proof
Rules of Inferences
List any four rules of inference. Using direct and indirect proof show that, for any real number $x$, if $x^3 - 7x^2 + x - 7 = 0$, then $x = 7$ [10]
Rule of Inference Form Name --------- 1 p, p→q ∴ q Modus Ponens 2 ¬q, p→q ∴ ¬p Modus Tollens 3 p→q, q→r ∴ p→r Hypothetical Syllogism 4 p∨q, ¬p ∴ q Disjunctive Syllogism --- Theorem: For any real number x, if x³ - 7x² + x - 7 = 0, then x = 7. Note: The conve...
Full solved answer →Give the premise 'If it rains or strike holds then the exam will be cancelled. If it doesn't rain then it will be sunny day. The exam was not cancelled. Show that it was sunny day'. [5]
Let us define the propositional variables: - p : It rains - q : Strike holds - r : Exam will be cancelled - s : It will be a sunny day --- No. Premise Symbolic Form ----------------------------- P1 If it rains or strike holds, then exam will be cancelled (p...
Full solved answer →Define proposition. Consider the argument 'John, a student in this class knows how to write program in C. Everyone who knows how to write program in C can get a high paying job. Therefore, someone in this class can get high paying job'. Now, explain which rules of inferences are used for each step. [5]
A proposition is a declarative statement that is either true or false, but not both. It has a definite truth value (T or F). Examples: - "The sky is blue." (True proposition) - "2 + 2 = 5." (False proposition) - "What time is it?" (NOT a proposition, it is ...
Full solved answer →Predicates and Quantifiers
Express the following sentences using quantifier. 1) Not all people are loyal. 2)Everybody loves somebody. 3). Someone has passed the exam 4). Aquatic animals can't live without water 5). Some subjects are not interesting. [5]
Definitions used: Let the domain of discourse be the set of all people/subjects/animals unless stated otherwise. --- Let L(x) = "x is loyal" Logical Expression: $$\neg \forall x \; L(x)$$ This is equivalent to: $$\exists x \; \neg L(x)$$ "There exists at le...
Full solved answer →List any one example of tautology. Represent the following sentences into predicate logic. a. Not all employees are loyal. b. All students having good attitude are lovable. [5]
A tautology is a propositional formula that is always true regardless of the truth values of its variables. Example: $$P \lor \neg P \quad \text{(Law of Excluded Middle)}$$ P ¬P P ∨ ¬P ---------------- T F T F T T Since the formula is true in all cases, it ...
Full solved answer →State division and remainder algorithm. Suppose that the domain of the propositional function P(x) consists of the integer 0, 1, 2, 3 and 4. Write out each of the following propositions using disjunctions, conjunctions and negations. a. ∃x P(x)b. ∀x P(x)c. ∃x ¬P(x)d. ∀x ¬P(x)e. ¬∃x P(x)f. ¬∀x P(x)\text{a. } \exists x , P(x) \quad \text{b. } \forall x , P(x) \quad \text{c. } \exists x , \neg P(x) \quad \text{d. } \forall x , \neg P(x) \quad \text{e. } \neg \exists x , P(x) \quad \text{f. } \neg \forall x , P(x)a. ∃xP(x)b. ∀xP(x)c. ∃x¬P(x)d. ∀x¬P(x)e. ¬∃xP(x)f. ¬∀xP(x)[10]
Division Algorithm: Let a be an integer and d a positive integer. Then there exist unique integers q and r with 0 ≤ r < d such that: a = d·q + r Where: - d is called the divisor - a is called the dividend - q is called the quotient → written as q = a div d ...
Full solved answer →Proof Methods
What is proof by contradiction? Give a proof by contradiction to show that if 3n+2 is odd then n is odd. [5]
Proof by contradiction is a method of mathematical proof in which we assume that the statement to be proved is false, and then show that this assumption leads to a logical contradiction (an impossibility). Since the assumption leads to a contradiction, the ...
Full solved answer →Prove that 'If the product of two integers a and b is even then either a is even or b is even' using condition method. [5]
The conditional method (also called proof by contrapositive) proves a statement of the form: P → Q by instead proving its contrapositive: ¬Q → ¬P which is logically equivalent to the original statement. --- Original Statement: If a × b is even, then a is ev...
Full solved answer →Prove that if n is positive integer, then n is odd if and only if 5n + 6 is odd. [5]
We must prove a biconditional statement: n is odd $\iff$ 5n + 6 is odd A biconditional proof requires proving both directions: 1. (Forward) If n is odd, then 5n + 6 is odd. 2. (Backward) If 5n + 6 is odd, then n is odd. We use the standard definitions: - An...
Full solved answer →Prove that the product xy is odd if and only if both x and y are odd integers. [5]
Claim: For integers x and y, the product xy is odd if and only if both x and y are odd. --- From the course notes on Integer and Division: - An integer b is odd if it cannot be written as b = 2k for any integer k; equivalently, b = 2k + 1 for some integer k...
Full solved answer →What is direct proof? Give a direct proof that if m and n are both perfect squares, then mn is also a perfect square. [5]
A direct proof is a method of proving a statement of the form "if P then Q" by assuming that P is true and then, using definitions, axioms, theorems, and logical reasoning step by step, showing that Q must also be true. In other words, we start from the hyp...
Full solved answer →Nested Quantifiers
All over smart people are stupid. Children of stupid people are naughty. John is a children of Jane. Jane is over smart. Represent these statements in FOPL and prove that John is naughty. [5]
English Statement FOPL Representation ------ All over smart people are stupid. ∀x: OverSmart(x) → Stupid(x) Children of stupid people are naughty. ∀x ∀y: Stupid(x) ∧ ChildOf(y, x) → Naughty(y) John is a child of Jane. ChildOf(John, Jane) Jane is over smart....
Full solved answer →Propositional Logic
Let A = 'Aldo is Italian' and B = 'Bob is English'. Formalize the following sentences into proposition.a. Aldo isn't Italian.b. Aldo is Italian while Bob is English.c. If Aldo is Italian then Bob is not English.d. Aldo is Italian or if Aldo isn't Italian then Bob is English.e. Either Aldo is Italian and Bob is English, or neither Aldo is Italian nor is Bob English. [5]
Let: - A = 'Aldo is Italian' - B = 'Bob is English' --- This is the negation of A. $$\neg A$$ --- The word "while" expresses that both statements hold simultaneously, so this is a conjunction. $$A \land B$$ --- This is a conditional (implication) where the ...
Full solved answer →Propositional Equivalences
Give an example of tautology and contradiction. Show that implication and contrapositive are equivalence. [5]
--- A tautology is a compound proposition that is always true, regardless of the truth values of its component propositions. Example: $$p \lor \neg p \quad \text{("p or not p")}$$ $p$ $\neg p$ $p \lor \neg p$ -------------------------------- T F T F T T Sin...
Full solved answer →Make Unit 3 stick
Practice CSC165 with flashcards & quizzes