Introduction to Mathematical Logic and Propositional Statements

Overview of the Mathematical Logic Course

• Course Structure and Relationship to Set Theory

  • Mathematical logic is the foundational subject for the current series of lectures, which will span approximately eight to ten classes.
  • Graph theory has been completed, including its revision phase.
  • Logic is taught prior to set theory because the principles of mathematical logic are utilized to explain and teach the concepts of set theory more effectively.
  • The initial focus is on propositional logic, covering basics and foundational questions.

• Classification of Logical Concepts and Questions

  • The curriculum is divided into six distinct types of questions in mathematical logic:
    • Basic Level: Type 1, Type 2, and Type 3 questions.
    • Advanced Level: Type 4, Type 5, and Type 6 questions. Students should expect one or two questions from the advanced level in the GATE exam.
  • The subject is categorized into two main branches:
    • Propositional Logic: The fundamental/basic level of logic.
    • Predicate Logic: The advanced level of logic.

Misconceptions and the Real Utility of Logic

• Relationship with Digital Logic

  • A common misconception among students is that mathematical logic can be entirely solved using digital logic concept.
  • The concept of digital logic is only recommended for Type 2 questions.
  • Applying digital logic to advanced types (Type 4, 5, and 6) often leads to significant confusion and is not the intended methodology.

• Beyond Truth Tables

  • Logic is not merely the construction of truth tables. While truth tables are a part of the subject, they are only a combination of specific cases.
  • Advanced logic involves mathematical techniques that avoid drawing large, time-consuming truth tables.

• The Power of Statement Validity

  • The primary purpose of mathematical logic in computer science and competitive exams like GATE is to provide the power to check the validity of statements.
  • It helps determine if a statement makes sense, is valid, or is logically sound in real-time applications.

• Mathematical Logic in the Context of Software Engineering

  • Developing software is more than just knowing a programming language. It follows a structural sequence:
    1. Theorems: Scientific foundations and research.
    2. Algorithms: Derived from theorems to provide structural methods.
    3. Programming Languages (PL): The tool used to implement the algorithm.
    4. Software: The final presentation or product used by companies to solve real-time problems.
  • Theorems are not just single-line statements like $\sin^2(x) + \cos^2(x) = 1$. To prove such theorems, one starts with diagrams, calculates specific values (like $\sin 30$ or $\cos 30$), and uses multiple statements leading to a final conclusion.
  • The Role of Logic: Logic provides the power to check if each individual statement in a theorem is valid. If every underlying statement is valid, logic confirms if the final conclusion is valid.

Propositional Statements

• Categorizing English Statements

  • English grammar includes various types of sentences: questioning, ordering, exclamatory, imperative, and imprecating.
  • Mathematical logic does not use all these types. It extracts a special category known as Factual Statements.

• Definition of a Propositional Statement

  • A propositional statement is a factual statement that describes a fact and results in a binary outcome (two possible outcomes).
  • Outcomes can be represented as: True or False, Yes or No, $1$ or $0$, In or Out, Head or Tail.

• Types of Propositional Statements

  • Simple Propositional Statement: These are basic statements that cannot be broken down further. If you attempt to break them, they lose their meaning.
    • Example: "My name is Satish Yadav."
    • Mathematical Example: $5 > 3$ (This is a factual statement with a truth value of True).
  • Compound Propositional Statement: These are statements that can be broken down into two or more simple propositional statements. They are broken at specific "breakable points."
    • Example: "Today is raining and my name is Satish Yadav."
    • Mathematical Example: $5 \ge 3$. This can be broken into "$5 > 3$ OR $5 = 3$".

Logical Connectives

• Definitions and Properties

  • Connectives are the "breakable points" in compound statements.
  • Direct Truth Value: You can only directly define the truth value of a simple statement. Compound statements do not have direct truth values; their values depend on the truth values of the simple statements they are composed of.
  • Truth Tables as Case Studies: A truth table represents all possible combinations of the truth values of simple statements to determine the compound statement's result. If a compound statement has two variables ($p$ and $q$), there are $2^2 = 4$ cases.

• Conjunction (AND)

  • Signified by words like "and" or "but."
  • Symbolic representation: $p \land q$.
  • Property - "AND hates False": Conjunction is only true if ALL constituent simple statements are true. If even one simple statement among thousands is false, the entire compound statement becomes false.

• Disjunction (OR)

  • Two types exist: Inclusive OR and Exclusive OR (XOR).
  • Exclusive OR (XOR): Defined as "either this or that, but not both." Example: A person being "dead or alive."
  • Inclusive OR: Used most commonly in mathematics. Defined as "this, that, or both."
  • Symbolic representation: $p \lor q$.
  • Example from Graph Theory: Dominating Sets. A vertex belongs to a dominating set if the "vertex directly belongs OR its adjacent belongs." This is inclusive because if both the vertex and its adjacent belong, the condition is still satisfied.
  • Property - "OR loves True": If even one simple statement among thousands is true, the entire compound statement results in true.

• Conditional Statements (Implication)

  • Symbolic representation: $p \rightarrow q$.
  • Phrasing variants:
    • If $p$, then $q$
    • If $p$, $q$
    • $q$ is $p$
    • $p$ only if $q$
    • $q$ when $p$
    • $p$ implies $q$
    • $q$ whenever $p$
    • $q$ unless $\neg p$
  • Validity Logic - "False implies anything is True": A conditional statement $p \rightarrow q$ is only false when the premise ($p$) is true but the conclusion ($q$) is false ($T \rightarrow F = F$). In all other cases, it is true.
  • Metaphor 1: The Pizza Party Promise: A teacher promises, "If you win the match ($p$), then I will give a pizza party ($q$)."
    1. $T \rightarrow T = T$: You won, I gave pizza. Promise fulfilled.
    2. $T \rightarrow F = F$: You won, I didn't give pizza. Promise broken/false.
    3. $F \rightarrow T = T$: You lost, but I gave pizza anyway. You cannot call me a liar; the promise is technically not violated.
    4. $F \rightarrow F = T$: You lost, I didn't give pizza. You cannot claim I made a false promise because the condition for testing the promise (winning) was never met.
  • Metaphor 2: The Graph Theory Theorem (Sharma and Shukla Uncles): Consider the theorem "If a perfect matching exists ($p$), then the number of vertices is even ($q$)."
    • Sharma Uncle brings a graph where a perfect matching exists and vertices are even. The theorem holds ($T \rightarrow T$).
    • Shukla Uncle brings a graph where a perfect matching exists but vertices are NOT even. This is the ONLY way to disprove/break the theorem ($T \rightarrow F$).
    • The third uncle brings a graph where a perfect matching DOES NOT EXIST ($F$). He cannot use this example to disprove the theorem because the theorem only makes a claim about graphs that DO have matching. Thus, the theorem remains True ($F \rightarrow P = T$).
  • Mathematical Example: "If $x$ is even, then $x^2$ is even." While this is true for all even integers, for odd integers like $x = 1$, the premise is false ($1$ is even = False). Therefore, the implication is still logically true for integers like $1$ because $F \rightarrow T = T$.

• Biconditional Statement

  • Symbolic representation: $p \leftrightarrow q$.
  • Signified by "if and only if."
  • Property - "Same Behavior": The statement is true only if both $p$ and $q$ have the same truth value (both true or both false).
  • Example: "A graph is an Euler graph if and only if the degrees of all vertices are even."

Categorizing Logical Expressions

• Tautology (Valid Expression): An expression where every case in the last column of the truth table is True.
• Contradiction: An expression where every case in the last column of the truth table is False.
• Contingency: An expression that is neither a tautology nor a contradiction. It contains a mixture of True and False outcomes.
• Satisfiable Expression: An expression that results in True for at least one case (at least one True in the result column).
• Logical Implications of Satisfiability:
  • All Tautologies (Valid expressions) are Satisfiable.
  • All Contingencies are Satisfiable.
  • False Statement: "All Satisfiable expressions are Contingency." This is false because a tautology is satisfiable but not a contingency.

Type 1 Questions: Methodology

• The Pressure Method (Proof by Forced Falsity):
  • Instead of truth tables, test if an expression is a tautology by intentionally trying to make it False.
  • Principle: If a person is truly honest, no amount of pressure will make them change. Similarly, if an expression is a Tautology, it should be impossible to make it False.
  • The Process for $X \rightarrow Y$:
    1. Assume the whole expression is False. This necessitates that the left side must be True and the right side must be False.
    2. Assign values to variables based on this assumption.
    3. Check for contradictions. If, during the assignment of values, the expression results in a True outcome despite the intention to make it False, the expression is a Tautology.
  • Example Problem Analysis: $[p \land (p \rightarrow q) \land (\neg q \lor m)] \rightarrow m$
    1. Assume the result $m$ is False ($F$).
    2. For the implication to be False, the entire left bracket must be True ($T$).
    3. Since the left side is joined by AND, every part ($p$, $p \rightarrow q$, and $\neg q \lor m$) must be True.
    4. Substitute $m = F$ into $\neg q \lor m$. For this to be True, $\neg q$ must be True, meaning $q = F$.
    5. Substitute $p = T$ and $q = F$ into $p \rightarrow q$. This yields $T \rightarrow F = F$.
    6. The "AND" connective sees this False and makes the entire left side False.
    7. The final implication becomes $F \rightarrow F$, which is True. The attempt to force the expression to be False failed; thus, it is a Tautology.

Questions & Discussion

• Student Question (Anmol/Sawman): "Are you live? Is the chat working?"
  • Response: Yes, the instructor confirms they are live and asks students to interact to ensure clarity.
• Student Observation (Rishabh): Regarding the third condition of conditional statements ($F \rightarrow T$) being confusing.
  • Response: The instructor provides the "Mathematician Theorem" and "Mother/Sister Dishwashing" metaphors to clarify that you cannot disprove a conditional statement if the prerequisite (the "if" part) never happened.
• Dialogue on Methodology: One student mentions using truth tables to solve an example provided.
  • Response: The instructor advises against truth tables for time-sensitive exams like GATE, as checking multiple options (A, B, C, D) would be impossible within the time limit. The instructor also notes a student likely made a mistake in their table if they didn't find the expression to be a tautology.
• Homework/Practice: Students expressed excitement for more questions. The instructor noted that practice is essential to solve these without even lifting a pencil and that more Type 1 and Type 2 questions would follow on Monday.