Skip to content Skip to navigation

Connexions

You are here: Home » Content » First-order Logic

Navigation

Recently Viewed

This feature requires Javascript to be enabled.

First-order Logic

Module by: Ian Barland. E-mail the author

User rating (How does the rating system work?)
Ratings

Ratings allow you to judge the quality of modules. If other users have ranked the module then its average rating is displayed below. Ratings are calculated on a scale from one star (Poor) to five stars (Excellent).

How to rate a module

Hover over the star that corresponds to the rating you wish to assign. Click on the star to add your rating. Your rating should be based on the quality of the content. You must have an account and be logged in to rate content.

:
(0 ratings)

Summary: We replace long lists of particular statements with a few general statements, involving the quantifiers "for all" and "there exists". We see how this changes our proofs, and rules of inference.

Warning:

The information in this module is outdated. Please see my course for a table of contents.

quantifiers

  • - statements we'd like to express: "every neighbor of x is unsafe", or "if num(x) = 3, then every neighbor of x is unsafe". "There is a safe square ... that is a neighbor of x ... if num(x)<3".
  • - Not just games -- can express properties about type-checking, data structures (trees, ...), circuits, ... - exercises
  • - negation of quantifiers.
  • - vacuously true.
  • - multiple quantifiers
  • - alternation of quantifiers -exercises
  • - meaning of; again stress the sentence vs the model
  • - new proofs; new proof rules introduced as needed . pushing negations through quantifiers
  • - re-visit: how this changes how we model waterworld & its deductions
  • - optional: minimal sets of connectives; of deductions rules; when we cavalierly added new proof rules, were we just solving our own straw-man problem?

Why not begin with quantifiers

We saw three stages of logics:

  • Propositional logic, with statements like ...
  • Predicate logic, where the same statement was phrased as .... This introduced the idea of variables, which ranged over atomic propositions.
  • First-order logic, which included quantifiers; the above statements were superceded with the likes of ....
So why, you might ask, didn't we just start out with first-order logic in the first lecture? One reason, clearly, is to introduce concepts one at a time: everything you needed to know about one level was needed in the next, and then some. But there's more: by restricting our formalisms, we can 't express all the concepts of the bigger formalism, but we can have automated ways of checking statements or finding proofs.

In general, this is a common theme in the theory of any subject: determining when and where you can (or, need to) trade off expressibility for predictive value. For example, ...

  • Linguistics: Having a set of precise rules for (say) Tagalog grammar allows you to determine what is and isn't a valid sentence; details of the formal grammar can reveal relations to other languages which aren't otherwise so apparent. On the other hand, a grammar for any natural language is unlikely to exactly capture all things which native speakers say and understand. If working with a formal grammar, one needs to know what is being lost and what is being gained.
    • Dismissing a grammar as irrelevant because it doesn't entirely reflect usage is missing the point of the grammar;
    • conversely, condemning some real-life utterances as ungrammatical (and ignoring them) forgets that the grammar is a model which captures many (if not all) important properties.
    Of course, any reasonable debate on this topic respects these two poles, and is actually about where the best trade-off between them lies.
  • One example from psychology: Say, Piaget might propose four stages of learning in children. It may not trade off total accuracy, for (say) clues of what to look for in brain development.
  • physics: trade off quantum accuracy for newtonian approximations, in large-scale. Or, trade off exact simulations for statistical ("stochastic") approximations.
Understanding the theoretical foundations of a field is often critical for knowing how to apply various techniques in practice.

Content actions

Give Feedback:

E-mail the module author | Rate module ( How does the rating system work?)

Rating system

Ratings

Ratings allow you to judge the quality of modules. If other users have ranked the module then its average rating is displayed below. Ratings are calculated on a scale from one star (Poor) to five stars (Excellent).

How to rate a module

Hover over the star that corresponds to the rating you wish to assign. Click on the star to add your rating. Your rating should be based on the quality of the content. You must have an account and be logged in to rate content.

(0 ratings)

Download:

Module PDF

Add module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections directly in Connexions. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need a Connexions account to use 'My Favorites'.

| A lens (?)

Definition of a lens

Lenses

A lens is a custom view of Connexions content. You can think of it as a fancy kind of list that will let you see Connexions through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to Connexions materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual Connexions member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks