INFO I308: 2 Logic, Sets, and Relations

Version 0.2.11

Possible handouts. (Due to an idiosyncracy of the mypage.iu.edu web server, I've renamed Prolog files *.pl to *-pl; please fix the names if you download the files.)

Transition from Primitive Data

Last week we looked at two types of primitive data: characters and numbers.
And did we also notice that boolean (true/false) is a primitive type, conceptually equivalent to a single bit? Everything else, in a sense, can be reduced to these (although it may sometimes be more efficiently to encode it directly as bits?). For example:

Nevertheless, when we combine primitive data, we also need to pay attention to the way it is organized or structured. There are more sophisticated structures than a one-dimensional sequence or a two-dimensional picture.

We'll begin looking at ways of structuring data, first using logic, then set theory, and finally relations, which are sets of a special kind.

Logic

Logic deals with what is true or false: usually called propositions or statements. This has a very nice fit to the primitive data type boolean, which is true or false.

We'll begin with the propositional calculus, which considers each proposition as a unit (atom) and looks at how we may combine propositions; and then proceed to the predicate calculus, which considers propositions as having an internal, subject-predicate structure.

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 (representing entities)
  4. Quantifiers
  5. Additional rules of inference

See Coursepack, section 5.2.2

Prolog

  1. A programming language based on predicate calculus
  2. Facts and rules
  3. Proofs
  4. Closed world assumption
    1. If something is not stated, it's assumed to be false.
    2. Equivalently, if we ask Prolog a question, we're not asking if it's true, but if it's provable from the facts and rules.

See Coursepack, section 5.7.

Prolog Examples

Limitations of Logic

Logic cannot handle some kinds of knowledge (at least, not without some enhancements):

Nevertheless, logic is an excellent foundation for most information representation, which does not have these special needs.

Sets

See Coursepack, section 2.1

Relations

If we've got a bunch of facts of the same type, like this—

father(bill, bob, 1950).
father(andy, joy, 1960).
father(hal, judy, 1970).
father(bob, bill, 1980).

—we can boil them down to a table, like this:

Father-child-year facts in tabular form.
Father Child Year
Bill Bob 1950
Andy Joy 1960
Hal Judy 1970
Bob Bill 1980

If we confine ourselves to tables, we have facts, but more compactly represented; we have nothing to do with rules; we can gain some efficiencies.

Relational Model for Databases

See Coursepack, sections 2.2–2.8

Table Operations

The relational algebra is the study of relations and their operations.

Querying Databases with Relational Algebra

…

  1. Revision notes:
    • Version 0.2.2, 2012 Feb 2: Updated link to coursepack.
    • Version 0.2.1, 2011 Jan 26: Added remark on Pickwick Papers.
    • Version 0.2, 2011 Jan 25: Added Prolog examples.
    • Version 0.1.1, 2011 Jan 25: Added E. F. Codd links.
    • Version 0.1, 2011 Jan 24: Initial outline.
    2. ↩