Propositional Logic PDF

Module 1 Reading Material ========================= Propositional Logic Proposition:\ \ A proposition is a declarative sentence that is either true or false, but not both.\ \ T if True.\ F if False. [Examples]: All the following declarative sentences are propositions:\ \ 1. New Delhi is the Capi...

Module 1 Reading Material ========================= Propositional Logic Proposition:\ \ A proposition is a declarative sentence that is either true or false, but not both.\ \ T if True.\ F if False. [Examples]: All the following declarative sentences are propositions:\ \ 1. New Delhi is the Capital of India. (True)\ 2. 2 + 2 = 3. (False)\ \ The following declarative sentences are not propositions:\ \ 1. What time is it?\ 2. Read this carefully.\ 3. x + 1 = 2.\ 4. x + y = z Reason: Since, these sentences given here cannot only True or only False. Representation of Propositions: -------------------------------- We use letters to denote propositional variables (or sentential variables), that is, variables that represent propositions, just as letters are used to denote numerical variables. The conventional letters used for propositional variables are p, q, r, s,... Atomic Proposition: ------------------- Propositions that cannot be expressed in terms of simpler propositions are called atomic propositions. Example: P: "The Sky is blue" (or)\ q: "It is raining" Compound Propositions: ---------------------- A proposition which is developed using two or more atomic propositions and logical connectives/ operators is called as a compound proposition. Example: "The sky is blue and it is raining." Here, the two propositions are connected using "and" Logical Operators: ------------------ While considering n propositions, we need to consider 2^n^ truth values for building the truth tables. As it would cover all the possible combinations. ### Negation (\~): [Notations:] ∼p, −p, p′, Np, and !p. [Terminology:] "Not p" [Truth Table: ] **p** **\~p** ------- --------- F **T** T **F** [Example]: Consider the statement: p: "Vani's s mart phone has at least 32 GB of memory" The negation of the statement would be: ### Conjunction/ AND (\^): [Notations:] p \^ q\ \ [Terminology:] "p and q" [Truth table:] **p** **q** **(p \^ q)** ------- ------- -------------- F F **F** F T **F** T F **F** T T **T** [Example]: p: "It is cold outside." q: "I am wearing a sweater" p \^ q: "It is cold outside and I am wearing a sweater." [Key Fact:] Conjunction of p, q is true only if both p and q are T 3. ### Disjunction/ Inclusive OR (v): [Notation:] p v q\ \ [Terminology:] "p or q" [Truth Table: ] **p** **q** **(p V q)** ------- ------- ------------- F F **F** F T **T** T F **T** T T **T** [Example]: p: "I drink coffee" q: "I drink tea" p v q: "I drink coffee or tea"\ \ [Key Fact:] Disjunction of p, q is false only if both p and q are false. 4. ### XOR/ Exclusive OR (⊕): [Notation:] p ⊕ q [Terminology:] "p exclusive or q"/ "p xor q" [Truth Table]: +-----------------------------------+-----------------------------------+ | **p q** | **p ⨁ q** | +===================================+===================================+ | T T | F | | | | | T F | T | | | | | F T | T | | | | | F F | F | +-----------------------------------+-----------------------------------+ [Example]: p: "I will go to London" q; "I will go to Toronto" p ⊕ q: "I will go to London or I will go to Toronto, but not both" [Key Fact:] The XOR of p, q is false if both have same truth values, i.e, p ⊕ q is False if p is false and q is false or if p is true and q is true. 5. ### Implication/ conditional (-\>): [Notation:] p -\> q\ [\ Terminology:] - "p implies q". - "If p then q" - "If p, q" - "p only if q" - "p is sufficient for q" - "a sufficient condition for q is p" - "q if p" - "q whenever p" - "q when p" - "q is necessary for p" - "q follows from p" - "q unless \~p" - " q provided that p" [Truth Table: ] **P** **q** **(p → q)** ------- ------- ------------- F F **T** F T **T** T F **F** T T **T** [Example]: p: "It is sunny outside." q: "We will go to the Beach." p -\> q: "If it is sunny outside, we will go to the beach." [Key Facts: ] - If p is False, then p -\> q is automatically True. - If q is True, then p -\> q is automatically True. - The only way p -\> q is False is when p is True and q is False. - p -\> q can be equivalently expressed as \~p v q. ### Converse of an implication: The converse of an implication p -\> q is q -\> p. [Example]:\ \ consider p -\> q: "If it is summer, the weather is hot" Then the converse of the above statement is:\ \ q -\> p: "If the weather is hot, then it is summer."\ \ Inverse of an implication:\ \ The inverse of an implication p -\> q is \~p -\> \~q\ \ [Example]:\ \ Consider p -\> q: "If it is raining, then the cricket match is not being played." Then the inverse of the above statement is\ \~p -\> \~q: "If it is not raining, then the cricket match is being played." ### Contrapositive of an implication: The contrapositive of an implication p -\> q is \~q -\> \~p. [Example]:\ Consider p -\> q: "If it is raining, then the cricket match is not being played." Then the contrapositive of the above statement is \~q -\> \~p: "If the cricket match is being played, then it is not raining." 6. ### Biconditional/ Logical equality (↔): [Notation:] p ↔ q [\ Terminology:] "p if and only if q" (or) "p if q" [Truth Table: ] **p** **q** **(p ⬌ q)** ------- ------- ------------- F F **T** F T **F** T F **F** T T **T** [Example:] [\ ]Consider the following propositions: p: "The garbage truck comes down my street" q: "It is Thursday morning." p ↔ q: "The garbage truck comes down my street if and only if it is Thursday morning." [Key Fact:] A biconditional is true if the truth values of both p and q are same, i.e if both are true or if both are false. Logical Equivalences: --------------------- Two or more compound propositions are equivalent if they have the same truth values, regardless of the truth values of the propositional variables. [Example]: +-----------+-----------+-----------+-----------+-----------+-----------+ |   |   | **Conditi | **Convers | **Inverse | **Contrap | | | | onal** | e** | ** | ositive** | |   | | | | | | +===========+===========+===========+===========+===========+===========+ | p | q | p   →  q | q  →   p | \~p → \~q | \~q →\~p | +-----------+-----------+-----------+-----------+-----------+-----------+ | T | T | T | T | T | T | +-----------+-----------+-----------+-----------+-----------+-----------+ | T | F | F | T | T | F | +-----------+-----------+-----------+-----------+-----------+-----------+ | F | T | T | F | F | T | +-----------+-----------+-----------+-----------+-----------+-----------+ | F | F | T | T | T | T | +-----------+-----------+-----------+-----------+-----------+-----------+ Equivalent [Key facts:\ \ ]1. An implication and its contrapositive are logically equivalent: p -\> q ≡ \~q -\> \~p 2\. The converse and inverse of an implication are logically equivalent: q -\> p ≡ \~p -\> \~q Important Logical Equivalences: ------------------------------- +-----------------------------------+-----------------------------------+ | ***Equivalence*** | ***Name*** | +===================================+===================================+ | *p* \^ **T** ≡ *p* | Identity laws | | | | | *p* v **F** ≡ *p* | | +-----------------------------------+-----------------------------------+ | *p* v **T** ≡ **T** | Domination laws | | | | | *p* \^ **F** ≡ **F** | | +-----------------------------------+-----------------------------------+ | *p* v *p* ≡ *p* | Idempotent laws | | | | | *p* \^ *p* ≡ *p* | | +-----------------------------------+-----------------------------------+ | ⇁(⇁ *p*) ≡ *p* | Double negation laws | +-----------------------------------+-----------------------------------+ | *p* v *q* ≡ *q* v *p* | Commutative laws | | | | | *p* \^ *q* ≡ *q* \^ *p* | | +-----------------------------------+-----------------------------------+ | (*p* v *q*) v *r* ≡ *p* v (*q* v | Associative laws | | *r*) | | | | | | (*p* \^ *q*) \^ *r* ≡ *p* \^ (*q* | | | \^ *r*) | | +-----------------------------------+-----------------------------------+ | *p* v (*q* \^ *r*) ≡ (*p* v *q*) | Distributive laws | | \^ (*p* v *r*) | | | | | | *p* \^ (*q* v *r*) ≡ (*p* \^ *q*) | | | v (*p* \^ *r*) | | +-----------------------------------+-----------------------------------+ | ⇁(*p* \^ *q*) ≡ ⇁*p* v ⇁*q* | De Morgan's laws | | | | | ⇁(*p* v *q*) ≡ ⇁*p* \^ ⇁*q* | | +-----------------------------------+-----------------------------------+ | *p* v (*p* \^ *q*) ≡ *p* | Absorption laws | | | | | *p* \^ (*p* v *q*) ≡ *p* | | +-----------------------------------+-----------------------------------+ | *p* v ⇁*p* ≡ **T** | Negation laws | | | | | *p* \^ ⇁*p* ≡ **F** | | +-----------------------------------+-----------------------------------+ Logical Equivalences involving Conditionals: +-----------------------------------------------------------------------+ |   | | | | p → q  ≡ \~p v q | | | | p → q  ≡ \~q v \~q | | | | p v q ≡ \~p v q | | | | p ∧ q ≡ \~(p v \~q) | | | | \~(p → q) ≡ p ∧ \~q | | | | (p → q) ∧ (p → r) ≡ p → (q ∧ r) | | | | (p → r) ∧ (1 → r) ≡ (p v q) → r | | | | (p → q) v (p → r) ≡ p → (q v r) | | | | (p → r) v (q → r) ≡ (p ∧ q) → r | +-----------------------------------------------------------------------+ Logical Equivalences involving Biconditionals: **p ↔ q ≡ (p → q) ⋀ (q → p)** Demorgan's Laws: ----------------- 1. \~ (p \^ q) ≡ \~p v \~q 2. \~ (p v q) ≡ \~p \^ \~q 3. p -\> q ≡ \~p v q Counter Example: ---------------- An example or instance which proves that two or more compound propositions are not logically equivalent is called as a counter example. (or) An instance/ example for which the given mathematical statement is false is called as a counter example. [Example:] Consider the following statement: "All prime numbers are odd" This statement is not true for all prime numbers as for the prime number 2, 2 is even. - 2 is a counter example for the statement "All prime numbers are odd." Tautology: ---------- P \~ p p v \~ p --- ------ ---------- T F T F T T A compound proposition that is always true for every combination of truth values of its propositional variables.\ \ [Example]: p v \~p Contradiction: --------------- A compound proposition that is always false for every combination of truth values of its propositional variables. [Example]: p \^ \~p p \~ p p \^ \~p --- ------ ---------- T F F F T F Solving Compound Propositions: ------------------------------ Consider solving the following compound expression and evaluate its truth values. (p v \~q) -\> (p ∧ q) Step 1: Set up your table: We need to have our truth table such that each component of the compound statement is represented, as well as the entire statement itself. --- --- ------ ---------- ------- ----------------------- p q \~ q p v \~ q p ∧ q (p v \~q) -\> (p ∧ q) --- --- ------ ---------- ------- ----------------------- Here, these components are sufficient for evaluating the truth value of the given compound expression. [Trick:] It is always helpful to put the components you will work with in order to evaluate the final truth values together. For instance, we have column 4 and 5 placed together which are helpful for evaluating the final column. Step 2: List out all the possible combinations of truth values for each column. =============================================================================== We would require 2^n^ truth values to list out all the possible combinations for any given compound expression. In our case, there are namely two propositional variable p and q. hence, we require 2^2^ = 4 truth values. +-----------+-----------+-----------+-----------+-----------+-----------+ | p | q | \~ q | p v \~ q | p ∧ q | (p v \~q) | | | | | | | -\> (p ∧ | | | | | | | q) | +===========+===========+===========+===========+===========+===========+ | T | T | | | | | | | | | | | | | T | F | | | | | | | | | | | | | F | T | | | | | | | | | | | | | F | F | | | | | +-----------+-----------+-----------+-----------+-----------+-----------+ Step 3: Complete the rest of the table using the basic operations: ------------------------------------------------------------------ Evaluating the truth values of \~ q column by using the negation operation: +-----------+-----------+-----------+-----------+-----------+-----------+ | p | q | \~ q | p v \~ q | p ∧ q | (p v \~q) | | | | | | | -\> (p ∧ | | | | | | | q) | +===========+===========+===========+===========+===========+===========+ | T | T | F | | | | | | | | | | | | T | F | T | | | | | | | | | | | | F | T | F | | | | | | | | | | | | F | F | T | | | | +-----------+-----------+-----------+-----------+-----------+-----------+ Evaluating the truth values of p v \~ q by using column 1 and column 3 and "or" operation: +-----------+-----------+-----------+-----------+-----------+-----------+ | p | q | \~ q | p v \~ q | p ∧ q | (p v \~q) | | | | | | | -\> (p ∧ | | | | | | | q) | +===========+===========+===========+===========+===========+===========+ | T | T | F | T | | | | | | | | | | | T | F | T | T | | | | | | | | | | | F | T | F | F | | | | | | | | | | | F | F | T | T | | | +-----------+-----------+-----------+-----------+-----------+-----------+ Evaluating the truth values of p ∧ q using column 1 and column 2 and "and" operation: +-----------+-----------+-----------+-----------+-----------+-----------+ | p | q | \~ q | p v \~ q | p ∧ q | (p v \~q) | | | | | | | -\> (p ∧ | | | | | | | q) | +===========+===========+===========+===========+===========+===========+ | T | T | F | T | T | | | | | | | | | | T | F | T | T | F | | | | | | | | | | F | T | F | F | F | | | | | | | | | | F | F | T | T | F | | +-----------+-----------+-----------+-----------+-----------+-----------+ Evaluating the truth values of the compound expression by using column 4 and column 4 and using the implication operation: +-----------+-----------+-----------+-----------+-----------+-----------+ | p | q | \~ q | p v \~ q | p ∧ q | (p v \~q) | | | | | | | -\> (p ∧ | | | | | | | q) | +===========+===========+===========+===========+===========+===========+ | T | T | F | T | T | T | | | | | | | | | T | F | T | T | F | F | | | | | | | | | F | T | F | F | F | T | | | | | | | | | F | F | T | T | F | F | +-----------+-----------+-----------+-----------+-----------+-----------+ Predicates & Quantifiers ======================== Predicates: ------------ Any statement of the form P(x~1~, x~2~,..., x~n~) is a propositional function P at the n -- tuple (x~1~, x~2~,..., x~n~) and P Is also called the n -- ary predicate or the n -- place predicate. [Analogy:] Think of predicates as functions which take the values of the variables as input and returns an output "True" or "False" based on the truth value obtained after substitution of the variable. **True** **x~1~,x~2~,\.....,x~n~ P(x~1~,x~2~,\.....,x~n~)** **False** [Example]: Consider the following statement: P (x, y) = \[x + y = 0\] - Is this predicate true for all the values of x and y? - Is this predicate true for some values of x and y? Here, we can clearly see that this predicate/ statement is only true when y = - x (or) x = - y and in all the other cases, this statement would be false. Since, the truth value of this predicate is dependent on the values that x and y can take we call the statement P (x, y) as a predicate. Domain/ Universe of Discourse: ------------------------------ It is the set from which the n -- tuples/ variables in the predicate take their values from. [Example]: The domain could be\ - Set of Natural Numbers\ - Set of whole numbers, etc.. Quantifiers: ------------ Quantifiers are expressions/ phrases/ symbols that explains about how many elements/ objects a statement applies to (or) for which values of the variables, the predicate can be true. Types of quantifiers: --------------------- 1. Universal quantifier: --------------------- If P(x) is a predicate, then the statement "P(x) is true for all values of x in the domain" is called as universal quantification. It is denoted by the symbol ∀ and expressed as ∀ P(x).\ \ [Example]: P(x): ∀x (x is a square ⇒ x is a rectangle) "For all x, if x is a square then x is a rectangle." 2. Existential quantifier: ----------------------- If P(x) is a predicate, then the statement "P(x) is true for at least one value of x" (or) "There exists some element x in the domain such that P(x) is true" is called as an existential quantification. It is denoted by the symbol ∃ and expressed as ∃x P(x).\ \ [Example]: P(x): ∃x (x ≥ x^2^) "For some value of x, x is greater than equal to x square." This predicate is True if x = 0 and in all other cases, it would be False. [Note]:\ \ The existential quantification can be thought of in two ways: 1. There exists at least one value of x for which P(x) is true. 2. There exist some values of x for which P(x) is true. Logical Equivalences of quantified predicates: ----------------------------------------------- - Statements involving predicates and quantifiers are logically equivalent if and only if they have the same truth value for every predicate substituted into the statements and for every domain of discourse used for the variables. - Use the notation S ≡ T to show logically equivalent statements involving predicates and quantifiers. - We can use the known laws of logic as well as truth tables to prove/ check for logical equivalences. Negating of quantified predicates: ---------------------------------- 1. The negation of a universally quantified predicate is equivalent to the existential of that predicate. 2. The negation of an existentially quantified predicate is equivalent to the universal of that predicate. Example: \~ (∀x P(x)) ≡ ∃x \~P(x) and \~ (∃x P(x)) ≡ ∀x \~P(x) [Rule Of Thumb for Negation: ] When a negation sign "jumps over" a quantifier, the quantifier "flips." Nested Quantifiers: ------------------- Nested quantifiers occur when one quantifier is used within the scope of another quantifier in a logical expression. These quantifiers can be either universal (denoted by ∀) or existential (denoted by ∃). [Note:] The order of quantifiers is important in case of nested quantifiers. If two or more quantifiers are the same then the order doesn't matter whereas in case of different quantifiers, the order is important. [Examples:] 1. **Universal-Universal (∀*x* ∀*y*):** a. Example: ∀*x* ∀*y* (*x* + *y*=*y* + *x*) b. Meaning: \"For all *xx* and for all *yy*, the sum of *xx* and *yy* equals the sum of *yy* and *xx*.\" This expresses that addition is commutative for all values of *xx* and *yy*. 1. Universal-**Existential (∀*x* ∃*y*):** c. Example: ∀*x* ∃*y*(*x* + *y* =0) d. Meaning: \"For every *xx*, there exists a *yy* such that *x* + *y*=0.\" This implies that for any number *x*, there is another number *y* (its additive inverse) that, when added to *xx*, results in *0*0. 2. **Existential-Universal (∃*x* ∀*y*):** e. Example: ∃*x* ∀*y* (*x* × *y* = *y*) f. Meaning: \"There exists an *x* such that for all *y*, *x* × *y* = *y*.\" This is true if *x*=1, since multiplying any number *y* by 1 gives *y*. 3. **Existential-Existential (∃*x* ∃*y*):** b\. Meaning: \"There exist *x* and *y* such that *. x*^2^+*y*^2^=1.\" This statement asserts that there are specific values of *x* and *y* that satisfy this equation (which is the equation of a circle with radius1) Rules Of Inference: -------------------- We represent the rules of inference in the following way: Premises \_\_\_\_\_\_\_\_\_\_\_\_\_ ∴ Conclusion +-----------------------+-----------------------+-----------------------+ | **Rule of inference** | **Tautology** | **Name** | +=======================+=======================+=======================+ | *p* | ( *p* **⋀** ( *p | **Module pones (MP)** | | | **→** q* ) ) ***→** | | | *p **→** q* | q* | | | | | | | *一一* | | | | | | | | *q* | | | +-----------------------+-----------------------+-----------------------+ | **⇁** *q* | ( **⇁***q* **⋀** ( *p | **Module tones (MT)** | | | **→** q* ) ) ***→* | | | *p **→** q* | ⇁** *p* | | | | | | | **⇁** *p* | | | +-----------------------+-----------------------+-----------------------+ | *p **→** q* | (( *p **→** q* ) | **Hypothetical | | | **⋀** ( *q **→** r* ) | syllogism (HS)** | | *q **→** r* | ) ***→*** ( *p **→** | | | | r* ) | | | *p **→** r* | | | +-----------------------+-----------------------+-----------------------+ | *p* ⋁ *q* | (( *p* **⋁** *q* ) | **Disjunctive | | | **⋀ ⇁** *p* ) ***→** | syllogism (DS)** | | **⇁** *p* | q* | | | | | | | *q* | | | +-----------------------+-----------------------+-----------------------+ | *p* | *p **→*** **(** *p* ⋁ | **Addition** | | | *q* ) | | | *p* ⋁ *q* | | | +-----------------------+-----------------------+-----------------------+ | *p* ⋁ *q* | **(** *p* **⋀** *q* ) | **Simplification** | | | ***→** p* | | | *p* | | | +-----------------------+-----------------------+-----------------------+ | *p* | ( **(** *p* ) **⋀** ( | **Conjunction** | | | *q* ) ) ***→* (** *p* | | | *q* | **⋀** *q* ) | | | | | | | *p* **⋀** *q* | | | +-----------------------+-----------------------+-----------------------+ | *p* ⋁ *q* | ( ( *p* ⋁ *q )* **⋀** | **Resolution** | | | ( **⇁***p* ⋁ r ) ) | | | **⇁***p* ⋁ *r* | ***→* (** *q* **⋀** | | | | *r* ) | | | *q* ⋁ *r* | | | +-----------------------+-----------------------+-----------------------+ How to verify rules of inference? ---------------------------------- If we consider any rule of inference, the best way to think of understanding the rule of inference is through the fundamental notion of truth tables. Example: Consider the rule of inference: Modus Ponens p -\> q p Therefore, q How can we think of the validity of this rule of inference? ------------------------------------------------------------ Let us try considering the given premises. Here, the premises are p -\> q and p and by the notion of premises/ arguments we mean that they are True. - The truth value of p -\> q must be True as well as the truth value of p must be True. Let us look at the case wherein this is being obeyed. p q **(p → q)** --- --- ------------- F F **T** F T **T** T F **F** T T **T** The highlighted instances are the cases wherein p -\> q is true and q is True. But we need to check the case wherein both p as well as p -\> q are true simultaneously. And this refers to the last row of the truth table. +-----------------------+-----------------------+-----------------------+ |   | q | **(p → q)** | | | | | | p | | | +=======================+=======================+=======================+ | F | F | **T** | +-----------------------+-----------------------+-----------------------+ | F | T | **T** | +-----------------------+-----------------------+-----------------------+ | T | F | **F** | +-----------------------+-----------------------+-----------------------+ | T | T | **T** | +-----------------------+-----------------------+-----------------------+ And if we look at the truth value of q in this row, we can clearly conclude that q is True. This forms the basis for developing the rule of inference: "Modus Ponens" [Example]: **1.** +-----------------------------------------------------------------------+ | \"If it is raining, then I will make tea.\" p →q Modus Ponens (Law of | | Detachment) | | | | \"It is raining.\" p ((p→q) ∧ p)→q | | | | \"Therefore, I will make tea.\" ∴q | | | | 2. | +-----------------------------------------------------------------------+ "If it is raining, then I will make tea."        p → q         **Modus Tollens** "I do not make tea."                                   \~q            ((p → q) ∧ \~q) ⇒ \~q "Therefore, it is not raining."           ∴ \~p \ \ ** 3.** "If it is raining, then I will make tea."            p → q         **Hypothetical Syllogism** "If i make tea, then i will read a book."       q → r          ((p → q) ∧ \~q) ⇒ q → r "Therefore, if it rains, then i will read a book."  ∴ p → r  ** 4.**  "I will make tea, or i will read a book"               q v r              **Disjunctive Syllogism** "I will not make tea.."                                          \~q                  ((q v r) ∧ \~q) ⇒ r "Therefore, I will read a book."                          ∴ r    ** 5.**  "I will not make tea.."                                                 q                 **Addition** "Therefore, I will make tea, or i will read a book."     ∴ q v r         q ⇒ q v r +-----------------------------------------------------------------------+ | "I will make tea and I will read a book."           q  ∧ r           | |             **Simplification** | | | | "Therefore, if it rains, then i will read a | | | | book, or i will read a book."           ∴q                          | | (p ∧ q)  ⇒   p | +-----------------------------------------------------------------------+ ** 6.**  ** ** **7.**  "It is raining, or i will make tea."                             p v q              **Resolution** "It is not raining, or i will read a book."                 \~p v r    ((p v q) ∧ (\~pvr)) ⇒ (q v r) "Therefore, i will make tea, or i will read a book   ∴ q v r Proof Methods: -------------- 1. Direct Proof: ------------- A direct proof for p -\> q starts by assuming p and finishing by establishing q. [Example]: Prove that if n is an odd integer, then n^2^ is also odd. p: n is an odd integer q: n^2^ is odd. p -\> q: If n is an odd integer, then n^2^ is odd. So, we will start by assuming p is true - n is an odd integer, - whenever n is an odd integer, it can be expressed in the form\ n = 2k + 1 \-\--(1) - Let us evaluate the value of n^2^ with the help of eq (1) - n^2^ = (2k + 1)^2^ = 4k^2^ + 4k + 1 = 2 (2k^2^ + 2k) + 1 - Let us assume that 2k^2^ + 2k = p - n^2^ = 2p + 1 which is in the form of an odd integer. Proof by contraposition/ Indirect proof: ---------------------------------------- - It starts by assuming \~ q, and finishes by establishing \~ p. - In the proof, we can also use axioms, previously proven theorems, and inference rules. [Example]: Prove that if n is an integer and 3n + 2 is odd, then n is odd. [Proof]: This statement is of the form p -\> q where, p: 3n + 2 is odd q: n is odd p -\> q: If 3n + 2 is odd, then n is odd. Consider the contrapositive of the above implication which is \~ q -\> \~p - \~ q -\> \~ p: "If n is even, then 3n + 2 is even" Let us consider n is even, Whenever n is even, we can express n as n = 2k - If we evaluate the value of 3n + 2 using n = 2k, - 3n + 2 = 3 (2k) + 2 = 6k + 2 = 2 (3k + 1) - Let us assume 3k + 1 = p - 3n + 2 = 2p This is of the form of an even number - The statement \~ q -\> \~ p is true. Since, implication and the contrapositive of it are equivalent we can establish that p -\> q itself is true. Therefore, the statement "if n is an integer and 3n + 2 is odd, then n is odd." Is true. Vacuous Proof: -------------- **P** **q** **(p → q)** ------- ------- ------------- F F T F T T T F F T T T If we consider Q(3): if 3 \< 0, then 3^3^ \> 3 Here, if we try to break this statement down into propositions, p: 3 \< 0 q: 3^3^ \> 3 p -\> q: if 3 \< 0, then 3^3^ \> 3 Here, we can clearly prove this mathematical statement p -\> q by simply proving that p is false If we consider p, then p is the statement 3 \< 0 and definitely we know that 3 is not less than 0 - Mathematically, p is false. Whenever p is false, we can establish that p -\> q is true. Therefore, the statement "if 3 \< 0, then 3^3^ \> 3" is true. 4. Trivial Proof: -------------- A trivial proof in mathematics is a type of proof that establishes the truth of an implication p -\> q by showing that the conclusion q is always is true, regardless of the truth value of the premise p. In other words, if the statement q is true without any dependence of p, then the implication p -\> q is also true. [Explanation]: Consider the truth table of an implication p -\> q **P** **q** **(p → q)** ------- ------- ------------- F F T F T T T F F T T T If we consider the cases wherein the truth value of q is true, then in those cases\ p -\> q is always true. But we are unsure about what is the truth value of p -\> q when q is false. This forms the basis for development of Trivial proof. [Example]: Let P(n) be the statement:\ "If a and b are positive integers with a ≥ b, then a^n^ ≥ b^n^ " where the domain consists of all nonnegative integers. Prove that P(0) is true. If we consider the mathematical statement, then we can break it down into propositions as follows: p: "a ≥ b" q: "a^n^ ≥ b^n^" p -\> q: "If a ≥ b, then a^n^ ≥ b^n^" Here, if we consider P(0), then the statement would be if a ≥ b, then a^0^ ≥ b^0^ - If a ≥ b, then 1 ≥ 1 Here, if we consider q, then we definitely know that 1 = 1 and the statement q is always mathematically true. Therefore, on the basis of q being true, we can establish that p -\> q is true and this would complete the proof. Hence, the mathematical statement: "If a and b are positive integers with a ≥ b, then a^n^ ≥ b^n^" is true.