INFO I308: 2 Logic, Sets, and Relations
Transition from Primitive Data
- Primitive data:
- Everything else can be reduced to these.
- Sound (sequence)
- Pictures (array)
- But how else can we structure combinations of primitive data?
- Set theory
- Relations (special case of sets)
- Logic deals with what is true or false
- Boolean type
- Propositional calculus considers each simple proposition as a unit
- How may we combine propositions?
- Predicate calculus which considers propositions with internal structure
- WFF's (well-formed formulas) are a language.
- Propositions are true or false.
- Propositional variables and constants.
- The operators and, or, not
- Truth tables
- Proofs, rules of inference
See Coursepack, section 5.2.1
- Builds on propositional calculus
- Individual variables and constants represent entities
- Additional rules of inference
See Coursepack, section 5.2.2
- Programming language based on predicate calculus
- Facts and rules
- Closed world assumption
- If something is not stated or implied, it's assumed to be false.
- Equivalently, Prolog queries tell us what is provable from the knowledge base, not what's independently true or false
See Coursepack, section 5.7.
Limitations of Logic
Logic alone cannot represent:
- Fuzzy concepts
- Sophisticated prose or poetry
Still, it's a good foundation for much of information representation.
- Identifying sets
- Set operations
- Correspondence with propositional calculus
See Coursepack, section 2.1
Facts of same predicate—
father(bill, bob, 1950).
father(andy, joy, 1960).
father(hal, judy, 1970).
father(bob, bill, 1980).
—can be shown as a table:
Father Child Year
------- --------- -------
Bill Bob 1950
Andy Joy 1960
Hal Judy 1970
Bob Bill 1980
Facts, No Rules
- Tables represent predicates, more compactly.
- Tables represent no rules.
Relational Model for Databases
- Tables are called relations.
- Relations are sets of ordered tuples
- A relational database is a collections of relations
- Relational model developed by E. F. Codd (1970s)
See Coursepack, sections 2.2–2.8
- Set operations:
- Union ∪
- Intersection ∩
- Difference −
- Cartesian product ×
- select σ
- project π
- natural join ⋈
- The horrid division operation, ÷, details omitted
Relational algebra studies relations and their operations.
Querying Databases with Relational Algebra