10.1: Introduction

This chapter will talk about a semantics for MQL so that we can determine the truth value of formulas for which the syntax was presented in the previous chapter. Once we have both the syntax and the semantics we will have the logical system MQT.  

Atomic formulas are either propositional letters (p, q, ... P, Q, ...) or formulas consisting of a predicate letter and an individual constant (Fa, Gb, ... )

The latter are subject predicate formulas or SP-formulas.

Propositional letters are true or false just as they were for the propositional calculus.

An SP-formula, Fa, is true if the object referred to by a has the property indicated by F.

We introduce possible worlds of items.(PWI)

The set of items in a PWI is the domain of that PWI.

For MQT we will consider only non-empty finite domains which have at least one item but not an infinite number of items in them.

We can describe our PW by means of tables. Suppose we have a PW with 3 items a, b, c such that property F holds for a and b but not for c. Then this is described by the table

                F

          a    1

          b    1

          c     0

This PW could also be definined by the formulas Fa, Fb, ~Fc.

We can use more complex sets of formulas to define other PWI. For example:

Fa & ~Ga, Fb, Fc, ~Fd & Gd, ~Gc, Gb É Ga:

                F    G

          a    1     0

          b    1     0

          c     1     0

          d     0     1

In a world with a finite number of items - say a, b, c - the statement that all x are F is true iff the statement that Fa & Fb & Fc is true. Thus:

      ("x)Fx is equivalent to Fa & Fb & Fc

So in finite worlds, universal quantifications are equivalent to conjunctions. Similarly, in finite worlds existential quantifications are equivalent to disjunctions:

      ($x)Fx is equivalent to Fa v Fb v Fc

There is a simple 3-step method for eliminating quantifiers.

We'll demonstrate using the formula ($x)(Sx & Gx) in a world with items a, b, c.

1.   Identify the scope of the quantification

      ($x)(Sx & Gx)

2.   Write the scope three times, with the quantified variable replaced first by a, then b, then c.

      (Sa & Ga)   (Sb & Gb)   (Sc & Gc)

3.   If an existential quantifier is being eliminated connect the formulas with a v, otherwise use &.

      (Sa & Ga) v (Sb & Gb) v (Sc & Gc)

We introduce a replacement notation.

      F(X/Y) means formula F with X replacing all free occurrences of Y. (Read it as 'F with X for Y'.)

So             (Fz ≡ Gz)(a/z) v (Fz ≡ Gz)(b/z) v (Fz ≡ Gz)(c/z)

Means      (Fa ≡ Ga) v (Fa ≡ Gb) v (Fc ≡ Gc)

The thing to remember is

                                                UNIVERSAL      -   CONJUNCTION

                                                EXISTENTIAL  -   DISJUNCTION

The same procedure will work for formulas in quantifications occurs in the scope of other quantifiers, for example in formulas like ($z)(Fz & ("x)Gx).

In these cases eleminate the quantifiers one at a time using the process described above, beginning with the innermost quantifiers.

Once a formula has been expanded and its quantifiers eliminated, the truth value can be found by the methods of propositional logic using the truth values in the table that describes the PWI. For example:

Given the world

                F    G    H

          d    1     0     0

          g    1     0     0

the formula

                              ("x)(Gx É Fx)

expands to

                               (Gd É Fd) & (Gg É Fg)

which gets evaluated as

                               (0 É 1) & (1 É 1)

                           =       1      &     1

                           =                1

A formula of MQT is an MQT-tautology iff it is true in every non-empty possible world.

We'll generally just talk about tautologies rather than MQT-tautologies, even though many people restrict that term to propositional logic and call what we have defined logical truths or necessary truths.

A formula is an MQT-contradiction iff it is false in every non-empty possible world.

Luckily we don't have to test the truth of MQT formulas in possible worlds of every cardinality (number of items) because of the following fact.

If there are n predicate letters in a formula, and if the expansion of the formula for 2ⁿ items is a tautology, then the formula will be true in every world, and hence an MQT-tautology.

So there's an upper bound to the work required, but it's a fairly high upper bound. For example, if we have two predicates, F and G, and four items in the domain, then we have 2⁴ possible truth value combinations for F, and for each of them 2⁴ possible truth combinations for G.

So there are 2⁴ x 2⁴ = 2⁸ = 256 possible worlds to test. We need shortcuts, and we'll find some in the next chapter..

MQT has logical equivalences called quantifier equivalences (QEq) which allow us to switch between types of quantifier. We define replacement rules:

     ~("x)~F :: ($x)F

     ("x)F :: ~($x)~F

where :: can be read as 'can replace or be replaced by'

Think of it this way: you can move a negation across a quantifier, but that changes the type of quantifier. This rule also gives us quantifier negation (QN)

     ~("x)F :: ($x)~F

     ("x)~F :: ~($x)F

Other handy equivalences and their labels are:

a. For propositional logic

    ~~p            ::       p                  double negation          (DN)

    p & ~q      ::       ~(p É q)      negated É                      (~É)

    (p É ~q)    ::       ~(p & q)      negated &                     (~&)

    (p É q)      ::       (~p v q)       material implication   (IMP)

    (p v q)       ::       (q v p)          commutation for v      (Com)

    (p & q)      ::       (q & p)         commutation for &     (Com)

                                                     DeMorgan's Laws       (Dem)

    ~(p v q)     ::       (~q & ~p)  

    ~(p & q)    ::       (~q v ~p)   

b. For MQT

                                                       change of scope for v   (CSv)

     ("x)(Fx v p) :: (("x)Fx v p)

     (($x)Fx v p) :: ($x)(Fx v p)

                                                       change of scope for &  (CS&)

     ("x)(Fx & p) :: (("x)Fx & p)

     (($x)Fx & p) :: ($x)(Fx & p)

                                                       change of bound variable  (CBV)

     ("x)F (x):: ("y)F (y/x) provided y does not occur in F(x) (a formula concluding x)

     ($x)F (x):: ($y)F (y/x) provided y does not occur in F(x)

To test validity of arguments in MQT we extend the method of testing formulas. For an argument using n predicate letters, we expand the formulas in the argument to eliminate quantifiers and then test the resulting argument for validity in a world of 2ⁿ items.

Note these definitions

An MQT argument is valid iff in every non-empty possible world if the premisses are true then the conclusion is true.

An MQT argument is invalid iff there is at least one non-empty possible world in which the premisses are true and the conclusion is false.

Note that to show invalidity we may be able to use a counterexample from a possible world with many fewer than 2ⁿ items.

Similarly, given the definition of MQT-tautology, we also know that :

a formula of MQT is not an MQT-tautology iff it is false in at least one non-empty possible world,

which means that to show non-MQT-tautology we may be able to use a counterexample from a possible world with many fewer than 2ⁿ items (for a formula with n predicate letters.)