In-Depth Notes on Propositional Logic Reasoning

Propositional Logic Reasoning

Definitions

  • Propositional Logic: A branch of logic dealing with propositions that can be true or false.

  • Inference: The process of deriving logical conclusions from premises known or assumed to be true.

  • Inference Rule: A template that specifies how one can infer a conclusion from premises.

Examples of Propositional Logic

  • Example 1:

    • If it is snowing, then it is cold.

    • If it is cold, then John is wearing a coat.

    • It is snowing.

    • Conclusion: Therefore, John is wearing a coat.

  • Example 2:

    • If it is raining, it is not cold.

    • If it is not raining, John is not wearing a coat.

    • It is cold.

    • Conclusion: Therefore, John is not wearing a coat.

  • Example 3:

    • If it is snowing, it is cold or it is wet.

    • If it is cold, John is wearing a coat.

    • It is snowing.

    • Conclusion: Therefore, John is wearing a coat.

  • Example 4:

    • If it is snowing, it is cold. (Premise 1)

    • If it is cold, John is wearing a coat. (Premise 2)

    • It is snowing. (Premise 3)

    • Conclusion: Therefore, John is wearing a coat.

Glasses Logic Problem

  • Premises:

    • If I was reading the newspaper in the kitchen, then my glasses are on the kitchen table.

    • If my glasses are on the kitchen table, then I saw them at breakfast.

    • I did not see my glasses at breakfast.

    • I was reading the newspaper in the living room or in the kitchen.

    • If I was reading in the living room, then my glasses are on the coffee table.

  • Symbols:

    • Let P = reading in kitchen, Q = glasses on kitchen table, R = saw glasses at breakfast, S = reading in living room, T = glasses on coffee table.

    • Representation:

    • $P
      ightarrow Q$

    • $Q
      ightarrow R$

    • $¬R$

    • $S \/ P$

    • $S
      ightarrow T$

    • Conclusion: $ herefore T$ (John's glasses are on the coffee table)

Inference Rules

  • Modus Ponens (MP):

    • Structure:

    • If $P$, then $Q$; $P$ is true; therefore, $Q$ is true.

    • Example:

    • If it is sunny ($P$), then I will study AI ($Q$). It is sunny ($P$) ⇒ Therefore, I will study AI ($Q$).

  • Modus Tollens (MT):

    • Structure:

    • If $P$, then $Q$; $¬Q$ is true; therefore, $¬P$ is true.

    • Example:

    • If it is sunny ($P$), then I will study AI ($Q$). I will not study AI ($¬Q$) ⇒ Therefore, it is not sunny ($¬P$).

  • Disjunction:

    • Structure:

    • $P \/ Q$; $¬P$ is true; therefore, $Q$ is true.

    • Example:

    • I will study AI ($P$) or I will study OS ($Q$). I will not study AI ($¬P$) ⇒ Therefore, I will study OS ($Q$).

  • Conjunction:

    • Structure:

    • $P$ and $Q$ is true; therefore, $P$ is true and $Q$ is true.

    • Example:

    • I will study AI ($P$) and I will study OS ($Q$) ⇒ Therefore, I will study AI ($P$).

Simplification and Addition

  • Simplification:

    • If $P \land Q$ is true, then $P$ is true and $Q$ is true.

  • Addition:

    • If $P$ is true, then $P \/ Q$ is true for any $Q$.

Hypothetical Chaining and Resolution

  • Hypothetical Chaining:

    • Characterizes combining implications: If $P
      ightarrow Q$ and $Q
      ightarrow R$, then $P
      ightarrow R$.

  • Resolution:

    • Deals with disjunctions: If $(P \/ Q) \land (¬P \/ R)$ is true, then $Q \/ R$ is true.

Proof by Resolution Example

  • Given premises:

    • $Q$

    • $¬Q \/ P$

    • $¬P \/ ¬Q \/ R$

    • Goal $R$.

Proving as Search

  • Start Node: The set of given premises.

  • Operator: Inference rule.

  • Goal: A state containing the proof.

  • Solution: A path from start node to goal.

Inference Examples

  • Example 1:

    • Premises:

    • $W
      ightarrow F$

    • $W \/ S$

    • $¬S$

    • Goal: $F$

    • Steps:

      1. $W
        ightarrow F$ (Pre)

      2. $W \/ S$ (Pre)

      3. $¬S$ (Pre)

      4. $W$ (Disjunction [2,3])

      5. $ herefore F$ (Modus Ponens [1,4]).

  • Example 2 and beyond: Similar structure with given premises leading to the specified goal through inference rules.

Conclusion

  • Propositional logic serves as a foundation for logical reasoning, allowing one to derive conclusions based on given premises and applying various inference rules effectively. Each example demonstrates practical applications of these rules, reinforcing the conceptualunderstanding of logical reasoning in real-world contexts.