Introduction to Propositions

Discrete Mathematics Overview

• Course Title: Discrete Mathematics

• Week 22: Propositional Logic

• Instructor: Aarbaz Alam

Introduction to Propositions

• Definition of Proposition: A proposition is a declarative statement that asserts a fact.

• Fact and Truthfulness: A fact does not always yield truth. A fact may sometimes be confusing or certain.

• Examples of Propositions and their Truth Values:

  • 1 + 1 = 2 → True

  • Sun rises at south → False

  • There are 12 months in a year → True

  • There are 30 days in a month → Not always true, as it can be 28, 29, 30, or 31.

Non-Propositional Statements

• Statements that do not declare facts or conditions:

  • Interrogative: e.g., "Is it raining?"

  • Probabilistic Statement: e.g., "The chance of rainfall tomorrow"

  • Statement with Variables: e.g., "x + 2 = 5"

Propositional Logic

• Definition of Propositional Logic: The study of the mathematical analysis of propositions for formal deduction of propositions.

• Example Statements in Propositional Logic:

  • Statement 1: "Lilly only absents her class if she is sick or it rains."

  • Statement 2: "Today Lilly is absent."

  • Statement 3: "Today it’s not rainy."

• Inference: From these statements, we can infer that Lilly is sick today.

Propositional Variables

• Definition: Propositional variables are symbols that represent propositions.

  • Example assignments:

  • 𝑥 = "iPhones are manufactured by Apple"

  • 𝑦 = "LSBU is a University"

• Truth Values: A propositional variable can take values of either True or False.

  • If 𝑥 is a propositional variable, then:

  • 𝑥 ∈ {True, False}, where True = T and False = F.

• Binary Variable: These propositions are termed binary variables due to their two possible truth values.

• Symbolisation: Assigning symbols to statements reduces computational complexity. Common applications include electronic announcement systems and electronic translators.

Propositional Operators

• Operators Defined: For given propositional variables: 𝑥, 𝑦, 𝑧.

  • 𝑥 = "I want a cup of coffee"

  • 𝑦 = "I want a cup of tea"

  • 𝑧 = "It’s morning time"

• Basic Operators:

  • Conjunction (AND): 𝑥 ∧ 𝑦 ≡ 𝑥𝑦 ≡ "I want a cup of coffee and a cup of tea"

  • Disjunction (OR): 𝑥 ∨ 𝑦 ≡ 𝑥 + 𝑦 ≡ "I want a cup of coffee or tea or both"

  • Negation (NOT): ~𝑥 ≡ "I don’t want coffee"

• Composite Operators:

  • Implication (If-Then): 𝑧 ⇒ 𝑥 ≡ "If it’s morning time, then I want a cup of coffee"

  • Bi-implication (If and only if): 𝑦 ⟺ 𝑧 ≡ "I want a cup of tea if and only if it’s morning time"

Truth Tables

• Definition: A truth table is a tool for exploring all possible combinations of truth values for compound propositions.

• Theorem: If a compound proposition contains 𝑛 propositional variables, then the truth table contains 𝑛 columns and 2^𝑛 rows.

  • Proof: Each variable can be either True or False, leading to 2 possible values per variable.

  • Set of propositional variables: 𝑄 = {𝑝1, 𝑝2, …, 𝑝𝑛} ⇒ |𝑄| = n. All combinations in n variables equals |𝑃1 × 𝑃2 × … × 𝑃𝑛| = 𝑃𝑖n = 2^𝑛.

Truth Tables of Fundamental Operators

• Conjunction (AND): Results

  • 𝑥 𝑦 𝑥 ∧ 𝑦

  • T T T

  • T F F

  • F T F

  • F F F

• Disjunction (OR): Results

  • 𝑥 𝑦 𝑥 ∨ 𝑦

  • T T T

  • T F T

  • F T T

  • F F F

• Negation (NOT): Results

  • 𝑥 ~𝑥

  • T F

  • F T

Truth Tables of Composite Operators

• Implication (If-Then): Results

  • 𝑥 𝑦 𝑥 ⇒ 𝑦

  • T T T

  • T F F

  • F T T

  • F F T

• Bi-implication: Results

  • 𝑥 𝑦 𝑥 ⟺ 𝑦

  • T T T

  • T F F

  • F T F

  • F F T

Identities of Propositional Operators

• Operator Precedence Levels:

  • Level 1: ~

  • Level 2: ∧

  • Level 3: ∨

  • Level 4: ⇒

  • Level 5: ⟺

• Equivalence Statements:

  • 𝑥 ⇒ 𝑦 ≡ ~𝑥 ∨ 𝑦

  • 𝑥 ⨁ 𝑦 ≡ [ ~𝑥 ∧ 𝑦 ∨ (𝑥 ∧ ~𝑦)]

  • 𝑥 ⨁ T ≡ ~𝑥

  • 𝑥 ⨁ F ≡ 𝑥

  • 𝑥 ⟺ 𝑦 ≡ ~𝑥 ⨁ 𝑦 ≡ 𝑥 ⇒ 𝑦 ∧ 𝑦 ⇒ 𝑥 ≡ 𝑦 ⟺ 𝑥

Important Terms in Propositional Logic

• Converse: The converse of 𝑝 ⇒ 𝑞 is 𝑞 ⇒ 𝑝.

• Inverse: The inverse of 𝑝 ⇒ 𝑞 is ~𝑝 ⇒ ~𝑞.

• Contrapositive: The contrapositive of 𝑝 ⇒ 𝑞 is ~𝑞 ⇒ ~𝑝.

• Equivalence: 𝑝 ⟺ 𝑞 means 𝑝 and 𝑞 imply each other.

Constructing Truth Tables for Composite Propositions

• Example Statement: Construct truth table for 𝑝 ∧ (𝑞 ∨ ~𝑟).

  • Step 1: Identify the propositional variables.

  • Step 2: Construct possible combinations of truth values for all variables.

Proving Logical Equivalence Using Truth Tables

• Definition: Two compound propositions are logically equivalent if they have identical truth values for all variable combinations.

Satisfiability

• Definition: A compound proposition is satisfiable if there is at least one truth value combination that makes it true; otherwise, it is unsatisfiable.

• Example Checks for Satisfiability:

  • For 𝑥 ∨ ~𝑦 → Satisfiable with solutions {T, T}, {T, F}, {F, F}.

  • For 𝑥 ∧ ~𝑥 → Not satisfiable.

Applications of Satisfiability

• Use Case: Determines the solvability of problems with multiple constraints.

• Computational Aspect: Requires exhaustive exploration of all possibilities.

• Example: Monte-Carlo Simulation in rocket launches ensures no settings lead to mission failure.

Logical Inference

• Definition: An argument is a sequence of propositions.

  • Premises: All propositions except the last one in an argument.

  • Conclusion: The final proposition in an argument.

• Tautology and Contradiction: A conclusion is a tautology if true for all variable combinations, otherwise, it is a contradiction.

  • Example: 𝑃(𝑥, 𝑦) = 𝑥 ∧ ~𝑥 ∧ 𝑦 is a tautology.

Rules of Inference

• Modus Ponens: If 𝑃 and 𝑃 ⇒ 𝑄, then 𝑄.

• Modus Tollens: If 𝑃 ⇒ 𝑄 and ~𝑄, then ~𝑃.

• Hypothetical Syllogism: If 𝑃 ⇒ 𝑄 and 𝑄 ⇒ 𝑅, then 𝑃 ⇒ 𝑅.

• Disjunctive Syllogism: If 𝑃 ∨ 𝑄 and ~𝑃, then 𝑄.

• Addition: From 𝑃, infer 𝑃 ∨ 𝑄.

• Simplification: From 𝑃 ∧ 𝑄, infer 𝑃.

Conclusion

• Final Thoughts: Understanding propositional logic is crucial as it forms the foundation for more complex logical structures and reasoning within mathematics and computer science.