Skip to main content

Models

Recall the valid argument from the previous section:

All Philosophy majors at UMD are required to take a logic course. Ann is a Philosophy major at UMD. So, Ann is required to take a logic course.

Using formulas of First Order Logic, this argument is represented as follows:

βˆ€x(M(x)β†’L(x)),M(a)⊨L(a).\forall x (M(x)\rightarrow L(x)), M(a)\models L(a).

The validity of this argument means that replacing MM and LL with any predicates and aa with any constant results in a valid argument. For instance, the following instances of the form of the above argument are all valid:

  • All Philosophy majors at UMD are millionaires. Ann is a Philosophy major at UMD. So, Ann is a millionaire.
  • All Democrats voted for Biden. Ann is a Democrat. So, Ann voted for Biden.
  • All ravens are black. Tweety is a raven. So, Tweety is black.
  • All prime number greater than 2 are odd. 7 is a prime number greater than 2. So, 7 is odd.

More generally, for any collection of objects or individuals associated with MM and LL and any object or individual referred to by the name aa, if everything in the MM collection is also in the LL collection and aa is in the MM collection, then aa is in the LL collection.

It is a good exercise to determine which of the following variants of the above argument are valid.

  1. Is βˆ€x(M(x)β†’L(x)),βˆ€xM(x)β‡’L(a)\forall x (M(x)\rightarrow L(x)), \forall x M(x)\Rightarrow L(a) valid?
  1. Is βˆ€x(M(x)β†’L(x)),βˆ€xM(x)β‡’βˆ€xL(x)\forall x (M(x)\rightarrow L(x)), \forall x M(x)\Rightarrow \forall x L(x) valid?
  1. Is βˆ€x(M(x)β†’L(x)),βˆ€xM(x)β‡’βˆƒxL(x)\forall x (M(x)\rightarrow L(x)), \forall x M(x)\Rightarrow \exists x L(x) valid?
  1. Is βˆ€x(M(x)β†’L(x)),βˆƒxM(x)β‡’L(a)\forall x (M(x)\rightarrow L(x)), \exists x M(x)\Rightarrow L(a) valid?
  1. Is βˆ€x(M(x)β†’L(x)),βˆƒxM(x)β‡’βˆƒxL(x)\forall x (M(x)\rightarrow L(x)), \exists x M(x)\Rightarrow \exists x L(x) valid?
  1. Is βˆ€x(M(x)β†’L(x)),βˆƒxM(x)β‡’βˆ€xL(x)\forall x (M(x)\rightarrow L(x)), \exists x M(x)\Rightarrow \forall x L(x) valid?

To verify that all Philosophy majors at UMD are required to take a logic course (βˆ€x(M(x)β†’L(x))\forall x(M(x)\rightarrow L(x))) is true. We need to check for each student at UMD, if that students is a Philosophy major, then that student is required to take a logic course.

In Propositional Logic, the truth-value of a formula depends on a truth-value assignment (i.e., a row of a truth table). The analogue of the truth-value assignment for First Order Logic is a model. There are two components of a model:

  1. A collection of objects or items called the domain.
  2. An interpretation that associates with each constant an element of the domain and with each predicate a collection of elements from the domain.

For example, suppose that the domain consists of the first 5 positive numbers: 11, 22, 33, 44 and 55, that aa is interpretted as 22, that MM is interpretted as the collection 2,32, 3, and 44 and that LL is interpretted as the collection 2,3,42, 3, 4 and 55. Then, every object in the domain that is an MM is also an LL: The only objects that satisfy the predicate MM are 2,32, 3, and 44, and each of those objects are in the interpretation of LL.

We can visualize a model using a table, where each row is labeled by an element of the domain and the columns are labeled with the constants and the predicates. Under the constant, there is a checkmark in the row labeled with the element of the domain that interprets the constant (so there is exactly one checkmark under each constant). Under the predicate, there is a ++ in every row labeled by an element of the domain in the interpretation of the predicate and a βˆ’- in the rows labeled by elements not in the interpretation of the predicate. For instance, the above model can be visualized as follows:

aaMMLL
11βˆ’-βˆ’-
22βœ“\checkmark++++
33++++
44++++
55βˆ’-++

Then, βˆ€x(M(x)β†’L(x))\forall x(M(x)\rightarrow L(x)) is true in the above model since in every row, if there is a ++ underneath MM, then there is a ++ underneath LL. Furthermore, both M(a)M(a) and L(a)L(a) are true since the row labeled with 22 has a ++ underneath both MM and LL.

Example

To see why βˆ€x(M(x)β†’L(x)),βˆƒxM(x)βŠ¨ΜΈβˆ€xL(x)\forall x (M(x)\rightarrow L(x)), \exists x M(x)\not\models \forall x L(x), we can construct the following simple model:

MMLL
11++++
22βˆ’-βˆ’-

Then, we have that:

  1. βˆ€x(M(x)β†’L(x))\forall x (M(x)\rightarrow L(x)) is true since in every row, if there is a ++ underneath MM, then there is a ++ underneath LL;
  2. βˆƒxM(x)\exists x M(x) is true since there is some row with a ++ below MM (namely, the row labeled with 11); and
  3. βˆ€xL(x)\forall x L(x) is false since it is not true that every row beneath LL is labeled with a ++ (in particular, the row labeled with 22 is not labeled with a ++).
Truth in First Order Models

We have not given the full definition of when a formula is true in a model of First Order Logic. The full details of this definition are beyond the scope of this course. However, the examples above (and in the practice questions) should make it clear how to determine the truth value of formulas in simple models that can be visualized as a table.

An important thing to note about models is that the domain may be infinite. For instance, the domain may be the set of all positive numbers, the set of real numbers, etc. In these cases, you cannot use a table to visualize the model.

Putting everything together, we have the following definition of validity for arguments in First Order Logic:

Validity - First Order Logic

Suppose that X1,…,XnX_1, \ldots, X_n and YY are First Order Formulas. The argument with premises X1,…,XnX_1, \ldots, X_n and conclusion YY is valid, denoted X1,…,Xn⊨YX_1, \ldots, X_n\models Y if there is no model in which all the premises X1,…,XnX_1, \ldots, X_n are true and YY is false.

Example

Examples of valid arguments include:

  1. A(a)βŠ¨βˆƒxA(x)A(a)\models \exists x A(x)
    aa is an AA. So, there is some thing is an AA

  2. βˆ€x(A(x)β†’B(x)),βˆ€x(B(x)β†’C(x))βŠ¨βˆ€x(A(x)β†’C(x))\forall x (A(x)\rightarrow B(x)), \forall x(B(x)\rightarrow C(x))\models \forall x(A(x)\rightarrow C(x))
    All AAs are BBs. All BBs are CCs. So, all AAs are CCs.

  3. βˆƒx(A(x)∧B(x)),βˆ€x(B(x)β†’C(x))βŠ¨βˆƒx(A(x)∧C(x))\exists x(A(x)\wedge B(x)), \forall x (B(x)\rightarrow C(x))\models \exists x (A(x)\wedge C(x))
    Some AA is a BB. All BBs are CCs. So, some AA is a CC.

  4. βˆ€x(A(x)β†’B(x)),Β¬βˆƒx(C(x)∧B(x))βŠ¨Β¬βˆƒx(C(x)∧A(x))\forall x (A(x)\rightarrow B(x)), \neg \exists x(C(x)\wedge B(x))\models \neg \exists x(C(x)\wedge A(x))
    All AAs are BBs. No CC is a BB. So, no CC is an AA.

Practice Questions#

A. Consider the following model. Determine whether the following formulas are true or false in this model.

aabbccAABB
11βœ“\checkmark++βˆ’-
22βœ“\checkmark++++
33βœ“\checkmarkβˆ’-++
44++βˆ’-
  1. A(c)∧¬B(a)A(c)\wedge \neg B(a)

  2. A(a)∧¬B(a)A(a)\wedge \neg B(a)

  3. A(c)∧(B(b)∨¬A(a))A(c)\wedge (B(b) \vee \neg A(a))

  4. A(a)β†’A(b)A(a)\rightarrow A(b)

  5. A(a)β†’(B(b)∧B(c))A(a)\rightarrow (B(b)\wedge B(c))

B. Consider the following model. Determine whether the following formulas are true or false in this model.

aabbccAABBCC
11βœ“\checkmark++++++
22βœ“\checkmark++++++
33βœ“\checkmarkβˆ’-++βˆ’-
44++βˆ’-++
  1. βˆ€x(A(x)β†’B(x))\forall x(A(x)\rightarrow B(x))

  2. βˆƒx(B(x)∧¬C(x))\exists x(B(x)\wedge \neg C(x))

  3. βˆ€x(A(x)∨B(x))\forall x(A(x)\vee B(x))

  4. (βˆ€xA(x)βˆ¨βˆ€xB(x))(\forall x A(x)\vee \forall x B(x))

  5. Β¬βˆ€xC(x)\neg \forall x C(x)

C. For each of the following formulas, find a model with at least two elements in the domain that makes the formula true and another model that makes the formula false.

  1. βˆƒx(A(x)∧B(x))\exists x(A(x) \wedge B(x))
  1. (βˆƒxA(x)βˆ§βˆƒxB(x))(\exists x A(x) \wedge \exists x B(x))
  1. βˆ€x(A(x)∨B(x))\forall x (A(x) \vee B(x))
  1. (βˆ€xA(x)βˆ¨βˆ€xB(x))(\forall x A(x) \vee \forall x B(x))
  1. Β¬βˆ€x(A(x)β†’B(x))\neg \forall x(A(x)\rightarrow B(x))

D. Suppose that XX and YY are formulas of First Order Logic. We say XX and YY are equivalent when every model assigns the same truth value to XX and YY. For each pair of formulas, determine whether the formulas are equivalent.

  1. βˆ€xA(x)\forall x A(x) and Β¬βˆƒxΒ¬A(x)\neg \exists x \neg A(x)

  2. βˆ€x(A(x)∧B(x))\forall x (A(x)\wedge B(x)) and (βˆ€xA(x)βˆ§βˆ€xB(x))(\forall x A(x)\wedge \forall x B(x))

  3. βˆ€x(A(x)∨B(x))\forall x (A(x)\vee B(x)) and (βˆ€xA(x)βˆ¨βˆ€xB(x))(\forall x A(x)\vee \forall x B(x))

  4. βˆƒx(A(x)∧B(x))\exists x (A(x)\wedge B(x)) and (βˆƒxA(x)βˆ§βˆƒxB(x))(\exists x A(x)\wedge \exists x B(x))

  5. βˆƒx(A(x)∨B(x))\exists x (A(x)\vee B(x)) and (βˆƒxA(x)βˆ¨βˆƒxB(x))(\exists x A(x)\vee \exists x B(x))

E. Formalize the argument in the cartoon below and give a model that shows it is not a valid argument.

penguins-humor