Propositional Logic: Core Concepts and Natural Deduction

Logics: Core Concepts

• Artificial Intelligence (AI) Challenge: Formalize intelligence as symbolic reasoning with explicit knowledge representations.

  • Example: Imagine teaching a computer to play chess. Instead of just showing it games, we give it clear rules like "A knight moves in an L-shape." This is symbolic reasoning.

• Knowledge Representation (KR) Challenge: Represent knowledge in computers and use it algorithmically.

  • Example: How do we tell the computer that "the sky is blue"? We need a way to store that information so it can use it later.

• Logic: A theoretical framework for symbolic knowledge expression and reasoning characterization.

  • Example: Like grammar rules for language, logic provides rules for how we can build true statements and draw conclusions.

• Knowledge Base: A set of logical sentences expressing knowledge.

  • Example: All the rules about chess, plus the current board position, would be a knowledge base for a chess AI.

• Common Ingredients of Logics:

  • Syntax: Rules for constructing well-formed statements.

    • Example: "It is raining" is a well-formed statement. "Raining it is" is not.

  • Semantics: Meanings of statements, truth conditions, and what they describe (models).

    • Example: The meaning of "It is raining" is that water is falling from the sky. It's true if water is falling, and false otherwise.

  • Inference: Determining when one statement follows from others.

    • Example: If "It is raining" is true, and "If it is raining, then I need an umbrella" is true, then we can infer "I need an umbrella."

Propositional Logic (PL): Syntax and Semantics

• Propositional Logic (PL): Studies basic inference.

• Syntax Definition:

  • Propositional Variables (p.v.s): Basic atomic statements, e.g., $p, q, r$, assigned truth-values T (True) or F (False).

    • Example: Let $p$ be "It is raining." Let $q$ be "The ground is wet."

  • Connectives: Used to build complex sentences:

    • $\land$ (conjunction, "and")

      • Example: $p \land q$ means "It is raining AND the ground is wet."

    • $\lor$ (disjunction, "or")

      • Example: $p \lor q$ means "It is raining OR the ground is wet (or both)."

    • $\lnot$ (negation, "not")

      • Example: $\lnot p$ means "It is NOT raining."

    • $\to$ (implication, "if… then…")

      • Example: $p \to q$ means "IF it is raining, THEN the ground is wet."

    • $\leftrightarrow$ (equivalence, "if and only if")

      • Example: $p \leftrightarrow q$ means "It is raining IF AND ONLY IF the ground is wet." (This might not always be true in the real world, but it shows the meaning of the connective).

  • Special p.v.s: $\top$ (always true), $\bot$ (always false).

    • Example: $\top$ could represent "$1=1$". $\bot$ could represent "$1=0$".

• Semantics Definition:

  • Truth-Tables: Define the truth-values of complex sentences based on their components (e.g., $A \land B$ is true iff both $A$ and $B$ are true).

    • Example: For $p \land q$:

    • If $p$ is True and $q$ is True, then $p \land q$ is True.

    • If $p$ is True and $q$ is False, then $p \land q$ is False.

    • If $p$ is False and $q$ is True, then $p \land q$ is False.

    • If $p$ is False and $q$ is False, then $p \land q$ is False.

  • Implication ($A \to B$): True if $B$ is true, or if $A$ is false. Only false when $A$ is true and $B$ is false.

    • Example: "IF it rains ($p$), THEN the ground gets wet ($q$)."

    • If it rains (T) AND the ground gets wet (T), the statement is True.

    • If it rains (T) BUT the ground is NOT wet (F), the statement is False (this is the only way for an implication to be false).

    • If it does NOT rain (F) AND the ground gets wet (T), the statement is True (maybe someone watered it).

    • If it does NOT rain (F) AND the ground is NOT wet (F), the statement is True.

  • Equivalence ($A \leftrightarrow B$): True iff $A$ and $B$ have the same truth-value.

    • Example: "The light is on ($A$) IFF the switch is up ($B$)." This statement is true if both $A$ and $B$ are true, or if both $A$ and $B$ are false.

Valuations and Logical Equivalence

• Valuation ($v$): An assignment of truth-values to propositional variables ($v: L \to {T, F})$; extends to all sentences ($v: SL \to {T, F})$).

  • Example: Let $p$ be "It is sunny" and $q$ be "I am happy." A valuation $v<em>1$ could be $v</em>1(p) = T$, $v<em>1(q) = T$. Another valuation $v</em>2$ could be $v<em>2(p) = F$, $v</em>2(q) = T$.

  • $v$ satisfies $A$ (or is a model of $A$) if $v(A) = T$.

    • Example: If our sentence $A$ is $p \to q$, then valuation $v<em>1$ (T,T) satisfies $A$ because $T \to T$ is True. Valuation $v</em>2$ (F,T) also satisfies $A$ because $F \to T$ is True.

• Logical Equivalence ($A \equiv B$): Two sentences $A, B$ have the same meaning if they are true under the same valuations (i.e., $\text{Mod}(A) = \text{Mod}(B)$).

  • Example: The sentence "IF it rains, THEN the ground is wet" ($p \to q$) is logically equivalent to "EITHER it does NOT rain OR the ground is wet" ($\lnot p \lor q$). You can check with a truth table that they are true in exactly the same situations.

• Models of a Sentence/Set ($\text{Mod}(A)$ / $\text{Mod}(S)$): The set of all valuations that satisfy the sentence/all sentences in the set.

• Tautology: A sentence true for every possible valuation (e.g., $p \lor \lnot p$).

  • Example: "It is raining OR it is NOT raining." This statement is always true, no matter the weather.

• Contradiction: A sentence false for every possible valuation (e.g., $p \land \lnot p$).

  • Example: "It is raining AND it is NOT raining." This statement is always false, it can't be both.

• Satisfiable: A sentence true for at least one valuation ($\text{Mod}(A) \ne \emptyset$).

  • Example: "It is raining." This is satisfiable because there are times when it is raining. It's not always true, but it's not always false either.

  • A sentence is satisfiable iff it is not a contradiction.

  • A sentence is not satisfiable iff its negation is a tautology.

Logical Inference and Complexity

• Logical Consequence ($S \models B$): A conclusion $B$ is a logical consequence of a set of premises $S$ if every valuation that makes all sentences in $S$ true also makes $B$ true (i.e., $\text{Mod}(S) \subseteq \text{Mod}(B)$).

  • Example: If our premises $S$ are {"It's Monday", "If it's Monday, then the store is open"}, then "The store is open" ($B$) is a logical consequence. If the premises are true, the conclusion must be true.

• Cn($S$): The set of all logical consequences of $S$.

• Inference and Satisfiability: Checking if an inference $A<em>1, \dots, A</em>n \models B$ is valid is equivalent to checking if the sentence $(A<em>1 \land \dots \land A</em>n) \land \lnot B$ is unsatisfiable.

  • Example: To check if "If it's raining ($p$), then the ground is wet ($q$)" implies "If the ground is not wet ($\lnot q$), then it's not raining ($\lnot p$)", we would check if $(p \to q) \land \lnot (\lnot q \to \lnot p)$ is unsatisfiable.

• Satisfiability Problem (SAT): Given a PL sentence, is it satisfiable?

  • Decidable: Yes, an algorithm exists (e.g., truth-table method).

  • Complexity: In NP (can be verified in polynomial time).

  • NP-Complete: SAT is NP-complete (Cook's Theorem); finding a polynomial-time algorithm would prove P=NP.

  • Practical Outlook: Computationally infeasible in the worst case; requires practical SAT-solvers or restricted language fragments.

Natural Deduction and Completeness

• Proof-Theoretic Inference ($S \vdash B$): $B$ can be derived from $S$ using a system of proof rules (Natural Deduction).

• Natural Deduction Rules: Include introduction and elimination rules for connectives (e.g., $\land i, \land e$, $\to e$ (modus ponens), $\to i$).

  • Example: From "It is raining" and "If it is raining, then the ground is wet," we can use the $\to e$ (Modus Ponens) rule to derive "The ground is wet."

  • Derived rules include Modus Tollens (MT) and the Law of Excluded Middle (LEM).

• Theorem: A sentence $A$ is a theorem if it can be derived without premises ($\vdash A$).

  • Example: $\vdash p \lor \lnot p$ (It is raining or it is not raining) is a theorem because it can be proven universally true without needing any starting assumptions.

• Inconsistent: A sentence $A$ is inconsistent if a contradiction ($\bot$) can be derived from it ($A \vdash \bot$).

  • Example: The sentence "I am alive and I am not alive" is inconsistent because it leads to a contradiction.

• Completeness Theorem for PL ($S \vdash B \iff S \models B$): The proof-theoretic ($\vdash$) and model-theoretic ($\models$) inference relations are equivalent.

  • Soundness Theorem ($\vdash \implies \models$): Proof rules never lead from true premises to false conclusions.

  • Example: If we follow all the rules of logic correctly, we'll never prove something false from true statements.

  • Completeness Theorem ($\models \implies \vdash$): Proof rules are sufficient to capture all valid logical consequences.

  • Example: If something is a logical consequence (true in all models), then there is a way to prove it using our rules.

• Consequences: Consistent = Satisfiable; Theorems = Tautologies.

Horn Logic: A Tractable Fragment

• Horn Clause: A sentence of the form $(a<em>1 \land \dots \land a</em>m) \to b$, where $a_i$ and $b$ are propositional variables ($m \ge 0$).

  • Example: "IF (the alarm rings AND it's a weekday), THEN I wake up." ($(alarm \land weekday) \to wakeup$)

  • Fact: A Horn clause with $m=0$ (e.g., $b$).

    • Example: "The light is on." ($lightOn$). This is a fact because it doesn't depend on any other conditions.

  • Integrity Constraint: A Horn clause with $b=\bot$ (e.g., $(a<em>1 \land \dots \land a</em>n) \to \bot$).

    • Example: "IF (I am sleeping AND the alarm is ringing loudly), THEN there is a problem." ($(sleeping \land alarmLoud) \to \bot$). This means it's an undesirable situation because it leads to a contradiction.

• Horn Sentence: A conjunction of Horn clauses.

• Limited Expressiveness: Cannot express implications whose conclusion is a disjunction of p.v.s.

  • Example: Cannot express "IF it rains, THEN the ground is wet OR I stay inside." (Cannot have $p \to (q \lor r)$). Conclusions in Horn clauses must be a single propositional variable or $\bot$.

• Tractability: Reasoning in Horn Logic is tractable, unlike full PL.

  • Example: Finding solutions or checking consequences in Horn Logic is much faster for computers than in general Propositional Logic.

• Consensus Valuation ($v<em>1 \sqcap v</em>2$): A valuation where a variable is true iff it's true in both $v<em>1$ and $v</em>2$.

  • Example: If $v<em>1$ says "P is True, Q is False" and $v</em>2$ says "P is True, Q is True", then their consensus valuation $v<em>1 \sqcap v</em>2$ would say "P is True, Q is False." (Only what they both agree is true remains true).

• Theorem: A set of valuations $M$ is the set of models for some Horn sentence iff $M$ is closed under consensus.

• Trade-off: Horn Logic offers tractability at the cost of limited expressiveness.