Propositional Logic, Clauses, and Entailment

Administrative Announcements and Feedback

• Course feedback forms are published on Ed Discussion and the Discord server.

• Submitting feedback provides critical data directly to the teaching team and the School of Computer Science to improve student experience and course delivery.

Foundations of Propositional Logic and Logical Equivalence

• Propositional logic provides the mathematical foundation necessary for working on assignments, tests, and examinations.

• Propositions can be categorized into:

  • Atomic Propositions: Fundamental, indivisible statements that hold a truth value.

  • Composite (Compound) Propositions: Statements formed by joining atomic propositions using logical connectives.

• Logical Equivalence: Two distinct symbolic propositions are logically equivalent if they yield identical truth values across all possible interpretations in a truth table.

• Example of Logical Equivalence:

  • The material implication $A \rightarrow B$ is logically equivalent to:

  • Disjunctive form: $\neg A \lor B$

  • Negated conjunctive form: $\neg (A \land \neg B)$

• Concrete Real-World Scenario:

  • Let $A$ denote the proposition: "I win a $5,000,000$ lottery."

  • Let $B$ denote the proposition: "I start a company."

  • Implication ($A \rightarrow B$): "If I win the $5,000,000$ lottery, I will start a company."

  • Disjunction ($\neg A \lor B$): "Either I do not win the $5,000,000$ lottery, or I start a company." (Logically guarantees that winning the lottery results in starting a company).

  • Negated Conjunction ($\neg (A \land \neg B)$): "It will not happen that I win the $5,000,000$ lottery and do not start a company."

  • Natural language phrasing varies, but all three expressions represent identical logical constraints verified by matching truth tables.

De Morgan's Laws and Transformation Rules

• Negation Rule: Flips the truth values of a proposition in a truth table.

• De Morgan's Laws: Essential transformation rules used to convert disjunctive relationships (OR) into conjunctive relationships (AND) and vice versa.

  • Statement 1: $\neg (P \lor Q) \equiv \neg P \land \neg Q$

  • Statement 2: $\neg (P \land Q) \equiv \neg P \lor \neg Q$

• De Morgan's laws flip the main connective inside a negated bracket:

  • Conjunction ($\land$) transforms into disjunction ($\lor$).

  • Disjunction ($\lor$) transforms into conjunction ($\land$).

• Double Negation Cancellation: $\neg (\neg P) \equiv P$.

  • Example application: $\neg (\neg P \lor Q) \equiv P \land \neg Q$

Syntax, Semantics, and Distinctions in Logical Notation

• Syntax: The formal symbolic representation and structural rules of propositions.

• Semantics: The interpretation and truth-value assignment of symbolic propositions.

• Key Distinctions Among Logical Connectives and Relations:

  • Material Implication ($A \rightarrow B$): A logical connective that joins two propositions to form a new composite proposition. It evaluates to false only when $A$ is true and $B$ is false.

  • Logical Implication / Entailment ($A \models B$): A meta-logical relationship asserting that in every interpretation where proposition $A$ is true, proposition $B$ must also be true.

  • Logical Equivalence ($A \equiv B$): A meta-logical relationship asserting that $A$ and $B$ evaluate to identical truth values under every possible interpretation.

Identifying Atomic Propositions in Problem Solving

• Correctly identifying atomic propositions is the most critical step in formalizing natural language sentences into logic. Confusing atomic propositions with composite propositions leads to invalid formulations.

• Exam Case Analysis:

  • Given atomic propositions:

  • $P$: "It is sunny today."

  • $Q$: "I will go sailing."

  • Sentence to formalize: "I will go sailing whenever it is sunny. Since it is sunny, I will go sailing."

  • Option Analysis:

  • Expression $P \rightarrow Q$: Translates to "If it is sunny, I will go sailing." This captures only the first half of the statement.

  • Expression $(P \rightarrow Q) \land (Q \rightarrow P)$: Incorrectly adds an converse requirement ("If I go sailing, it is sunny"), which is not asserted.

  • Complete Propositional Expression: $((P \rightarrow Q) \land P) \rightarrow Q$. Captures both the implication rule ("I go sailing whenever it is sunny") and the premise/conclusion structure ("Since it is sunny, I will go sailing").

Interpretations and the Satisfaction Relation

• Interpretation ($\pi$): A function that assigns a specific truth value ($\text{true}$ or $\text{false}$) to every atomic proposition, anchoring abstract logical statements to a concrete world state.

  • For $n$ binary propositional variables, there exist $2^n$ possible interpretations (rows in a truth table).

  • For $3$ variables, there are $2^3 = 8$ distinct interpretations.

• Satisfaction Relation ($\models$):

  • An interpretation $\pi$ satisfies a proposition $P$ (written $\pi \models P$) if and only if $\pi(P) = \text{true}$.

  • An interpretation $\pi$ satisfies a set of propositions $S$ (written $\pi \models S$) if and only if $\pi$ satisfies every proposition contained in $S$

• Detailed Satisfaction Example:

  • Let $\pi$ be an interpretation defined by:

  • $\pi(A) = \text{true}$

  • $\pi(B) = \text{false}$

  • $\pi(C) = \text{true}$

  • Satisfaction evaluations:

  • $\pi \models A$ and $\pi \models C$

  • $\pi \models (A \land C)$ because both $\pi(A)$ and $\pi(C)$ evaluate to true.

  • $\pi \models (A \lor B)$ because $\pi(A) = \text{true}$.

  • $\pi \models (C \lor B)$ because $\pi(C) = \text{true}$.

  • Set Satisfaction Analysis:

  • For set $S_1 = \{A, C\}$: $\pi \models S_1$ because $\pi \models A$ and $\pi \models C$

  • For set $S_2 = \{A, B\}$: $\pi \not\models S_2$ because $\pi \not\models B$. A single unsatisfied element in a set causes the whole set to fail satisfaction under $\pi$

Definition and Structural Format of Clauses

• Clause Definition: A clause is a specialized proposition constrained to a specific syntactic shape.

• Canonical Clause Format:

  • Implication syntax: $\text{Body} \rightarrow \text{Head}$

  • Left-arrow notation: $\text{Head} \leftarrow \text{Body}$

  • Structural rules:

  • Head: Must be a disjunction ($\lor$) of literals.

  • Body: Must be a conjunction ($\land$) of literals.

  • Literal: An atomic proposition or its negation.

  • In directional arrow notation, the expression closest to the arrowhead represents the Head, while the expression on the opposite side represents the Body.

• Valid Clause Variants:

  • Standard clause: Disjunction in Head, Conjunction in Body.

  • Fact / Single literal: A standalone atomic proposition (or its negation) is a valid clause.

  • Clause with Empty Body: Contains only a Head (disjunction of literals) without prerequisites in the body (e.g., $A \lor B \leftarrow \emptyset$

• Invalid Clause Example:

  • Expression: $C \rightarrow \neg (A \lor B)$

  • Reasons for invalidity: Negation is outside the parentheses. Applying De Morgan's laws yields $C \rightarrow (\neg A \land \neg B)$, which places a conjunction ($\land$) into the Head, violating clause format requirements.

Wumpus World Case Study: Transforming Rules to Clauses

• Domain Rule: In a grid world, cell $(1,1)$ contains a breeze ($B_{1,1}$) if and only if an adjacent cell contains a pit ($P_{1,2}$ or $P_{2,1}$).

• Symbolic Representation: $B_{1,1} \leftrightarrow (P_{1,2} \lor P_{2,1})$

• Step-by-Step Transformation into Clauses:

  1. Biconditional Breakdown: Split the equivalence into two directional implications:

  • Direction 1: $B_{1,1} \rightarrow (P_{1,2} \lor P_{2,1})$

  • Direction 2: $(P_{1,2} \lor P_{2,1}) \rightarrow B_{1,1}$

  1. Analyzing Direction 1 ($B_{1,1} \rightarrow P_{1,2} \lor P_{2,1}$):

  • Expressed in left-arrow form: $(P_{1,2} \lor P_{2,1}) \leftarrow B_{1,1}$

  • Head is $(P_{1,2} \lor P_{2,1})$ (disjunction of literals).

  • Body is $B_{1,1}$ (literal).

  • Status: Valid Clause.

  1. Analyzing Direction 2 ($(P_{1,2} \lor P_{2,1}) \rightarrow B_{1,1}$):

  • Expressed in left-arrow form: $B_{1,1} \leftarrow (P_{1,2} \lor P_{2,1})$

  • Body contains a disjunction ($\lor$), which violates clause format.

  1. Applying Logical Transformations to Direction 2:

  • Apply implication transformation rules:        $(P_{1,2} \rightarrow B_{1,1}) \land (P_{2,1} \rightarrow B_{1,1})$

  • Convert to left-arrow clause set:

    • Clause 2a: $B_{1,1} \leftarrow P_{1,2}$

    • Clause 2b: $B_{1,1} \leftarrow P_{2,1}$

  • Status: Both are Valid Clauses (Literal $\leftarrow$ Literal).

• Predictive vs. Explanatory Directions:

  • Predictive Direction ($P \rightarrow B$): Knowing a pit exists directly predicts a breeze in adjacent cells.

  • Explanatory Direction ($B \rightarrow P_{1,2} \lor P_{2,1}$): Observing a breeze indicates at least one adjacent cell contains a pit, functioning as an existential constraint without specifying the exact cell.

Clauses as Constraints and Forbidden Combinations

• A clause acts as a logical constraint over candidate world states.

• Equivalent Representations of a Clause:

  1. Implication Format: $\text{Body} \rightarrow \text{Head}$

  2. Plain Disjunction of Literals: $\neg (\text{Body}) \lor \text{Head}$

  3. Forbidden Combination Format: $\neg (\text{Body} \land \neg \text{Head})$

• Mechanism of Forbidden Combinations:

  • In disjunction form, a clause is satisfied as long as at least one literal is true.

  • Under De Morgan's laws, this transforms into a negated conjunction: $\neg (L_1 \land L_2 \land \dots \land L_k)$.

  • An interpretation fails a clause if and only if it matches the specific variable assignment specified inside the negated conjunction (the forbidden combination).

  • Automated solvers (e.g., SAT algorithms) utilize forbidden combinations to quickly prune invalid interpretations during state-space searches.

Knowledge Bases and Mental Model Elimination

• Knowledge Base ($KB$): A set or stack of logical clauses defining environment rules and observed facts.

• Model of a Knowledge Base: An interpretation $\pi$ (a truth table row) that satisfies every clause in $KB$.

• Model Elimination Example in Wumpus World:

  • Assume an environment represented by $4$ boolean variables: $2^4 = 16$ total theoretical interpretations (possible worlds).

  • Observation: The agent enters cell $(1,1)$ and perceives a breeze ($B_{1,1} = \text{true}$).

  • Knowledge Constraint: $B_{1,1} \leftrightarrow (P_{1,2} \lor P_{2,1})$

  • Truth Table Evaluation:

  • Out of $16$ worlds, $4$ worlds assign $P_{1,2} = \text{false}$ and $P_{2,1} = \text{false}$.

  • Since $B_{1,1} = \text{true}$, these $4$ worlds violate the knowledge base constraint.

  • The agent eliminates these $4$ invalid worlds from its mental representation, leaving $12$ valid candidate models.

  • Purpose of Agent Mental Models: Enables artificial agents to reason safely by eliminating impossible states internally, avoiding high-risk physical trial-and-error.

Logical Consequence and Entailment

• Entailment Definition: A proposition $G$ is a logical consequence of a Knowledge Base $KB$ (written $KB \models G$) if and only if $G$ evaluates to true in every model of $KB$

• Mathematical Form:

  • $KB \models G \iff \forall \pi (\pi \models KB \implies \pi \models G)$

• Model Set Interpretation:

  • Let $M(KB)$ be the set of interpretations satisfying $KB$.

  • Let $M(G)$ be the set of interpretations satisfying $G$.

  • $KB \models G \iff M(KB) \subseteq M(G)$

  • If the set of models satisfying $KB$ is entirely contained within the set of models satisfying $G$, $G$ is entailed by $KB$.

• Comparison Summary:

  • Material Implication ($A \rightarrow B$): A single connective creating a compound proposition.

  • Logical Implication ($A \models B$): Meta-logical assertion between two individual propositions across all interpretations.

  • Entailment ($KB \models G$): Meta-logical assertion that a goal proposition$G$holds in all models satisfying a full set of clauses ($KB).\n\n# Introduction to Automated Inference\n\n* Manually evaluating entailment and satisfaction using truth tables requires constructing 2^n rows.\n* Truth table construction becomes computationally intractable as the number of variables n increases.\n* Inference engines use conversion to clause form and forbidden combinations to automate logical deduction efficiently without constructing full truth tables.\n\n# Questions and Discussion\n\n* **Question:** In the clause definition, why is eg (A \lor B) prohibited from serving as a literal or clause component?\n* **Answer:** Applying De Morgan's laws to eg (A \lor B)$converts the expression into$ eg A \land eg B$. Placing a conjunction ($\land$) into the head of a clause breaks the foundational syntactic requirement that a clause head must consist strictly of a disjunction ($\lor$$) of literals.