Logic

CSCI 4511/6511

Joe Goldfrank

Announcements

  • Homework 2 is due on 29 September at 11:55 PM
    • Bug!
  • Midterm Exam - 16 Oct
    • In class
    • Open note

Review

CSPs

  • State variables: \(X_1, X_2, ... , X_n\)
  • State variable domains: \(D_1, D_2, ..., D_n\)
    • The domain specifies which values are permitted for the state variable
    • Domain: set of allowable variables (or permissible range for continuous variables)1
    • Some constraints \(C_1, C_2, ..., C_m\) restrict allowable values

CSP Constraints

  • \(X_1\) and \(X_2\) both have real domains, i.e. \(X_1, X_2 \in \mathbb{R}\)
    • A constraint could be \(X_1 < X_2\)
  • \(X_1\) could have domain \(\{\text{red}, \text{green}, \text{blue}\}\) and \(X_2\) could have domain \(\{\text{green}, \text{blue}, \text{orange}\}\)
    • A constraint could be \(X_1 \neq X_2\)
  • \(X_1, X_2, ..., X_{100} \in \mathbb{R}\)
    • Constraint: exactly four of \(X_i\) equal 12
    • Rewrite as binary constraint?

Assignments

  • Assignments must be to values in each variable’s domain
  • Assignment violates constraints?
    • Consistency
  • All variables assigned?
    • Complete

Four-Colorings

Two possibilities:

Solving CSPs

  • We can search!
    • …the space of consistent assignments
  • Complexity \(O(d^n)\)
    • Domain size \(d\), number of nodes \(n\)
  • Tree search for node assignment
    • Inference to reduce domain size
  • Recursive search

What Even Is Inference

  • Constraints on one variable restrict others:
    • \(X_1 \in \{A, B, C, D\}\) and \(X_2 \in \{A\}\)
    • \(X_1 \neq X_2\)
    • Inference: \(X_1 \in \{B, C, D\}\)
  • If an unassigned variable has no domain…
    • Failure

Ordering

  • Select-Unassgined-Variable(\(CSP, assignment\))
    • Choose most-constrained variable1
  • Order-Domain-Variables(\(CSP, var, assignment\))
    • Least-constraining value
  • Why?

Restructuring

Tree-structured CSPs:

  • Linear time solution

  • Directional arc consistency: \(X_i \rightarrow X_{i+1}\)

  • Cutsets

  • Sub-problems

Continuous Domains

  • Linear:

\[\begin{aligned} \max_{x} \quad & \boldsymbol{c}^T\boldsymbol{x}\\ \textrm{s.t.} \quad & A\boldsymbol{x} \leq \boldsymbol{b}\\ &\boldsymbol{x} \geq 0 \\ \end{aligned}\]

  • Convex

\[\begin{aligned} \min_{x} \quad & f(\boldsymbol{x})\\ \textrm{s.t.} \quad & g_i(\boldsymbol{x}) \leq 0\\ & h_i(\boldsymbol{x}) = 0 \\ \end{aligned}\]

Logic

Yugoslav Logic

\(R_{HK} \Rightarrow \neg R_{SI}\)
\(G_{HK} \Rightarrow \neg G_{SI}\)
\(B_{HK} \Rightarrow \neg B_{SI}\)
\(R_{HK} \lor G_{HK} \lor B_{HK}\)

…

Goal: find assignment of variables that satisfies conditions

Is It Possible To Know Things?



Yes.


😌

How Even Do We Know Things?

  • What color is an apple?
    • Red?
    • Green?
    • Blue?
  • Are you sure?

Symbols

  • Propositional symbols
    • Similar to boolean variables
    • Either True or False

The Unambiguous Truth

  • It is a nice day.
    • It is difficult to discern an unambiguous truth value.
  • It is warm outside.
    • This has some truth value, but it is ambiguous.
  • The temperature is at least 78°F outside.
    • This has an unambiguous truth value.1

What Matters, Matters

  • Non-ambiguity required
  • Abitrary detail is not
  • The temperature is exactly 78°F outside.
    • We don’t necessarily need any other “related” symbols
  • What is the problem?
  • What do we care about?

Sentences

Sentences

  • What is a linguistic sentence?
    • Subject(s)
    • Verb(s)
    • Object(s)
    • Relationships
  • What is a logical sentence?
    • Symbols
    • Relationships

Familiar Logical Operators

  • \(\neg\)
    • “Not” operator, same as CS (!, not, etc.)
  • \(\land\)
    • “And” operator, same as CS (&&, and, etc.)
    • This is sometimes called a conjunction.
  • \(\lor\)
    • “Inclusive Or” operator, same as CS.
    • This is sometimes called a disjunction.

Unfamiliar Logical Operators

  • \(\Rightarrow\)
    • Logical implication.
    • If \(X_0 \Rightarrow X_1\), \(X_1\) is always True when \(X_0\) is True.
    • If \(X_0\) is False, the value of \(X_1\) is not constrained.
  • \(\iff\)
    • “If and only If.”
    • If \(X_0 \iff X_1\), \(X_0\) and \(X_1\) are either both True or both False.
    • Also called a biconditional.

Equivalent Statements

  • \(X_0 \Rightarrow X_1\) alternatively:
    • \((X_0 \land X_1) \lor \neg X_0\)
  • \(X_0 \iff X_1\) alternatively:
    • \((X_0 \land X_1) \lor (\neg X_0 \land \neg X_1)\)

 

  • Can we make an XOR?

Knowledge Base & Queries

  • We encode everything that we ‘know’
    • Statements that are true
  • We query the knowledge base
    • Statement that we’d like to know about
  • Logic:
    • Is statement consistent with KB?

Models

  • Mathematical abstraction of problem
    • Allows us to solve it
  • Logic:
    • Set of truth values for all sentences
    • …sentences comprised of symbols…
    • Set of truth values for all symbols
    • New sentences, symbols over time

Entailment

  • \(KB \models A\)
    • “Knowledge Base entails A”
    • For every model in which \(KB\) is True, \(A\) is also True
    • One-way relationship: \(A\) can be True for models where \(KB\) is not True.
  • Vocabulary: \(A\) is the query

Knowing Things

Falsehood:

  • \(KB \models \neg A\)
    • No model exists where \(KB\) is True and \(A\) is True

It is possible to not know things:1

  • \(KB \nvdash A\)
  • \(KB \nvdash \neg A\)

It Is Possible To Not Know Things 😔

Lexicon

  • Valid
    • \(A \lor \neg A\)
  • Satisfiable
    • True for some models
  • Unsatisfiable
    • \(A \land \neg A\)

Inference

  • \(KB\) models real world
    • Truth values unambiguous
    • \(KB\) coded correctly
  • \(KB \models A\)
    • \(A\) is true in the real world

Inference - How?

  • Model checking
    • Enumerate possible models
    • We can do better
    • NP-complete 😣
  • Theorem proving
    • Prove \(KB \models A\)

Satisfiability

  • Commonly abbreviated “SAT”
    • Not the Scholastic Assessment Test
    • Much more difficult
    • First NP-complete problem
  • The

Deliberate typographical error!

Satisfiability

  • Commonly abbreviated “SAT”

  • \((X_0 \land X_1) \lor X_2\)

    • Satisfied by \(X_0 = \text{True}, X_1 = \text{False}, X_2 = \text{True}\)
    • Satisfied for any \(X_0\) and \(X_1\) if \(X_2 = \text{True}\)

  • \(X_0 \land \neg X_0 \land X_1\)

    • Cannot be satisfied by any values of \(X_0\) and \(X_1\)

Satisfaction

  • SAT reminiscent of Constraint Satisfaction Problems
  • CSPs reduce to SAT
    • Solving SAT \(\rightarrow\) solving CSPs
    • Restricted to specific operators
    • CSP global constraints \(\rightarrow\) refactor as binary
  • Still NP-Complete

Why Do I Keep On Doing This To You



This is the entire point of the course.


Theory and practice are the same, in theory, but in practice they differ.

CSP Solution Methods

  • They all work
  • Backtracking search
  • Hill-climbing
  • Ordering (?)

SAT Solvers

  • Heuristics
  • PicoSAT
    • Python bindings: pycosat
    • (Solver written in C) (it’s fast)
  • You don’t have to know anything about the problem
    • This is not actually true
  • Conjunctive Normal Form

Conjunctive Normal Form

  • Literals — symbols or negated symbols
    • \(X_0\) is a literal
    • \(\neg X_0\) is a literal
  • Clauses — combine literals and disjunction using disjunctions (\(\lor\))
    • \(X_0 \lor \neg X_1\) is a valid disjunction
    • \((X_0 \lor \neg X_1) \lor X_2\) is a valid disjunction

Conjunctive Normal Form

  • Conjunctions (\(\land\)) combine clauses (and literals)
    • \(X_1 \land (X_0 \lor \neg X_2)\)
  • Disjunctions cannot contain conjunctions:
  • \(X_0 \lor (X_1 \land X_2)\) not in CNF
    • Can be rewritten in CNF: \((X_0 \lor X_1) \land (X_0 \lor X_2)\)

Converting to CNF

  • \(X_0 \iff X_1\)
    • \((X_0 \Rightarrow X_1) \land (X_1 \Rightarrow X_0)\)
  • \(X_0 \Rightarrow X_1\)
    • \(\neg X_0 \lor X_1\)
  • \(\neg (X_0 \land X_1)\)
    • \(\neg X_0 \lor \neg X_1\)
  • \(\neg (X_0 \lor X_1)\)
    • \(\neg X_0 \land \neg X_1\)

Limitations

  • Consider: No cat is a vegetarian
  • Express in propositional symbols?
  • \(\neg\) First cat is a vegetarian
  • \(\neg\) Second cat is a vegetarian
  • \(\neg\) Third cat is a vegetarian …

Solutions

First-Order Logic:

  • \(\forall\) (“for all”)
  • \(\exists\) (“there exists at least one”)

Loops 🙂 :

for cat in cats:
  t = Expr(f"{cat} is not a vegetarian")
  Exprs.push(t)

Probability

Coin Flip

Three outcomes: Heads, Tails, and Edge.

  • If the coin lands heads, it does not land tails or edge:
    • Heads \(\land \neg\) Tails \(\land \neg\) Edge
  • Similarly:
    • Tails \(\land \neg\) Heads \(\land \neg\) Edge
  • &c. 
    • Edge \(\land \neg\) Heads \(\land \neg\) Tails

Coin Flip

Propositional logic tells us:

(Heads \(\land \neg\) Tails \(\land \neg\) Edge ) \(\lor\) (Tails \(\land \neg\) Heads \(\land \neg\) Edge) \(\lor\) (Edge \(\land \neg\) Heads \(\land \neg\) Tails)



This is remarkably unsatisfying.

Belief

  • Heads percentage?
  • Tails percentage?
  • Edge percentage?


How do you know?


What does it mean to know ?

References

  • Stuart J. Russell and Peter Norvig. Artificial Intelligence: A Modern Approach. 4th Edition, 2020.

  • Stanford CS231

  • UC Berkeley CS188