Consider iTunes' "smart playlists": you can create a playlist consisting of (say)
All songs I've rated3-stars or better, and whose genre is not Classical
This is "smart" because its a program which is re-run every time your music library changes: For example, if you change a song's genre, it may be immediately added or deleted from the playlist. We realize actually have a simple formula (which we can express in propositional logic with relations). The structure (instance) for a single is the interpretation. This formula is true when interpreted on (my library's representation of) Brian Eno's "Here Come the Warm Jets", but false for Bonnie Tyler's '80's epic "Holding Out for a Hero" and for Bach's " "Little" Fugue in Gm ". We now have one formula, and want to determine its truth-value in many different particular interpretations. In fact, we want to return all interpretations which make the formula (playlist) true.
Look at the GUI box for defining these queries. Compared to propositional logic, what sort of formulas can you define?
Are there queries which can't be directly transliterated into the GUI box? l4
Can you find formulas equivalent to each of the preceding two, which can be expressed?
The upshot is that iTunes came up with a query language which is as expressive as propositionall5 logic. For some queries, it can be awkward to use, but the GUI designers who came up with smart playlists might have figured that few users would want such queries.