📗 -> 04/30/25: ECS170-L14

🎤 Vocab

❗ Unit and Larger Context

Small summary

✒️ -> Scratch Notes

Propositional Logic: a simple logic language used to describe a world, using sentences that follow a particular syntax

Sentence - A expression assessable for Truth Value
Atomic Sentence - True | False | P | Q | R | …
Complex Sentence - A combination of sentences bound together with logic operators
- “There is no pit in (1,1)” :

Knowledge Base: a set of sentences (declarations) in a formal language, e.g., propositional logic

Used to create deductions
- we know that there is not pit
- we know that the square is breezy if and only if there is a pit in a neighboring square
- …

Model: a truth assignment function that maps each propositional symbol to either True or False

A sentence could be true or false in a model, depending on the truth assignments. It can be true in some models, true in all models, or false in all models
A model is a model of the KB if it satisfies every sentence in the KB, or all the sentences in the KB are true

Both Logic and Natural Language aim to express information
Logical Formalism - A language to express truth-conditional meaning

More rigorous than natural language
Can characterize reasoning (inference) of various forms

Pros of Propositional Logic (PL)

In contrast to DB languages or programming languages

PL is declarative rather than procedural
PL has sufficient expressive power to deal with partial information, using disjunction and negation
PL is compositional, can compose complex statements from their sentences and operators

Cons of PL

Meaning is context-independent
- Cannot capture context dependent information, like natural languages “look”
Limitations on the expressivity, can only state specific truths, not generic ones
- Specific truth: B1,1 is a pit
- Generic truth: Squares adjacent to pits are breezy

with that context, we move onto…

First Order Logic (FOL)

Propositional Logic (PL) assumes the world contains

Atomic terms for statements
Operators to combine with atomic statements
First-order logic (FOL) assumes the world contains
Objects - people, houses, numbers, …
Relations - red, round, prime, …
Functions - father of, best friend, …
Quantification - all wumpuses smell bad; some squares are breezy
Statements - about objects, relations, functions, and their quantification

There is higher order logic: Second-order logic also quantifies over relations

FOL and Natural Language (NL)

FOL expressivity is closer than PL to NL
FOL statements are context independent and unambiguous, while NL is still context dependent and ambiguous

FOL symbols

Constants - John, 2, …
Variables - x, y, a, b…
Logical operators from PL
Predicates - True, False, Person, give, more than, …
- Person(John)
- KingOf(John, a)
Functions - Sqrt, LeftLegOf
Quantifier -
Equality -

Quantifiers

Be careful with translating NL into FOL using quantifiers

For All:

Everyone in ECS170 is smart:

Good -
BAD -
- This means everyone is in ECS170 and everyone is smart

Exists

Someone in ECS170 is smart:

Good -
BAD -
- This could be true vacuously, even if x is not in ECS170

Equality

is true under a given interpretation if and only if and refer to the same object

Father(John) = Henry, says that the object referred to by Father(John) and the object referred to by Henry are the same

FOL Syntax in Backus Naur Form

Models in FOL

Models in FOL consist of:

A set of object
Their relations
An interpretation that mas
- Constant symbols -> objects
- Predicate symbols -> relations
- Function symbols -> functional relations

🧪 -> Refresh the Info

Did you generally find the overall content understandable or compelling or relevant or not, and why, or which aspects of the reading were most novel or challenging for you and which aspects were most familiar or straightforward?)

Did a specific aspect of the reading raise questions for you or relate to other ideas and findings you’ve encountered, or are there other related issues you wish had been covered?)

Vault

Explorer

ECS170-L14