INFO I308: 2 Logic, Sets, and Relations

Transition from Primitive Data

• Primitive data:
  • Characters
  • Numbers
  • Boolean
• Everything else can be reduced to these.
  • Sound (sequence)
  • Pictures (array)
• But how else can we structure combinations of primitive data?
  • Logic
  • Set theory
  • Relations (special case of sets)

Logic

• Logic deals with what is true or false
  • Propositions
  • Statements
  • Boolean type
• Propositional calculus considers each simple proposition as a unit
  • How may we combine propositions?
• Predicate calculus which considers propositions with internal structure
  • Subject
  • Predicate

Propositional Calculus

1. WFF's (well-formed formulas) are a language.
2. Propositions are true or false.
3. Propositional variables and constants.
4. The operators and, or, not
5. Truth tables
6. Proofs, rules of inference

See Coursepack, section 5.2.1

Predicate Calculus

1. Builds on propositional calculus
2. Predicates/relations
3. Individual variables and constants represent entities
4. Quantifiers
5. Additional rules of inference

See Coursepack, section 5.2.2

Prolog

1. Programming language based on predicate calculus
2. Facts and rules
3. Proofs
4. Closed world assumption
   1. If something is not stated or implied, it's assumed to be false.
   2. Equivalently, Prolog queries tell us what is provable from the knowledge base, not what's independently true or false

See Coursepack, section 5.7.

Prolog Examples

• fish.pl
• marketing.pl
• Interactive session with fish and marketing

Limitations of Logic

Logic alone cannot represent:

• Fuzzy concepts
• Uncertainty
• Sophisticated prose or poetry

Still, it's a good foundation for much of information representation.

Sets

• Identifying sets
• Subsets
• Set operations
• Correspondence with propositional calculus

See Coursepack, section 2.1

Relations

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.
  • We gain some efficiency.

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)
  • Dr Codd
  • E. F. Codd's obituary

See Coursepack, sections 2.2–2.8

Table Operations

• 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

See Coursepack