Name: Answer Key

 

Exam II

 

Part 1 (20 pts)

 

(a) Explain what it means to say that a sentence in the predicate calculus is semantically true. Also state what it means for a sequent to be semantically valid in predicate logic.

 

A sentence in the predicate calculus is semantically true iff the sentence is true in very interpretation of the predicates and very domain.

 

A sequent G ├ j in the predicate calculus is semantically true iff whenever a model thinks that every sentence in G is true, then it thinks that j is true.

 

(b) Why can’t we use interpretations to show that a sentence is semantically true? 

 

One cannot use this method to show that a sentence is semantically true, since there are  infinitely many interpretations one can assign to the predicates in the sentence and also, there are infinitely many ways to define the domain.

 

 

(c) Recall the conceptual connections between quantifiers and sentential connectives. Given the following interpretation, eliminate the quantifier in the sentence, $x(Fx & Gx), by rewriting it using the appropriate sentential connectives:

 

                  UD       : { Julie, Tom, Mike }

                  j           : Julie

                  t           : Tom

                  m         : Mike

 

 

(Fj & Gj) Ú (Ft & Gt) Ú (Fm & Gm)

 

 

 

 

                 

 

 

 

 

 

 

 

 

(d) For formula (i) and (ii) below, state the scope of each quantifier.

 

            (i)         $xFx & "xGx

 

            The scope of $ is Fx and the scope of " is Gx

 

            (ii)        "x(Px→$yRxy)

 

            The scope of " is Px→$yRxy and the scope of $ is Rxy

 

 

Part II ( 10 pts ): Given the description of the predicates and relations translate the two sentences below into the appropriate symbolism. 

 

(a)        Bxy: x bores y

            Sxy: x is a student of y

            Px: x is a professor

            Lxy: x listens to y

 

(i)   Some professors do not listen to any of their students.

 

$x(Px & "y(Syx → ~Lxy)

 

      (ii) Every professor bores some of his or her students.

 

"x(Px → $y(Syx & Bxy))

 

 

 

Part III ( 20 pts): For the sentences below give interpretations that show that the sequents are not semantically valid.

 

            (a)        "xFx → "xGx ├ "x(Fx→Gx)

 

Take the following:

 

UD = The natural numbers

Fx = x is prime

Gx = x < 0

 

Explanation:  Clearly "xFx is false in this case, since there are numbers that are not prime, for example 6.  So, then "xFx→"xGx is true.  Now, note that "x(Fx→Gx) is false since there is a number n such that ~(Fn→Gn), for example 5.  So, the above interpretation shows that the sequent is invalid.

 

 

 

(b)        ~"xFx ├ "x~Fx

 

Take the following:

 

UD = The natural numbers

Fx = x is prime

 

Explanation:  Clearly ~"xFx is true in this case, since for example ~F8 holds.  But, "x~Fx is not true since there are natural numbers such that Fn, for example F5.  So, then the sequent is shown to be invalid.

 

 

Part IV (30 pts): Prove the following sequents using the four quantifier rules and primitive or derived rules of the propositional calculus.

 

Commonly used propositional rules:

 

DeMorgan’s Law:                                                ~(P v Q)  ┤├  ~P & ~Q

Commutativity:                                                     P v Q  ┤├  Q v P

Distribution:                                                          P & (Q v R)  ┤├ (P & Q) v (P & R)

Transposition:                                                      P → Q ┤├ ~Q → ~P

Law of excluded middle                                       ├ P v ~P

Negated antecedent                                            ~P ├ P→R

Negated arrow                                                      ~(P→Q) ┤├ P & ~Q

 

(a)        $x(Fx v Gx) ├ $xFx v $xGx   

 

1          (1)        $x(Fx Ú Gx)                            A

2          (2)        Fa Ú Ga                                   A

3          (3)        Fa                                            A

3          (4)        $xFx                                        3, $-intro

3          (5)        $xFx Ú $xGx                           4, Ú-intro

6          (6)        Ga                                            A

6          (7)        $xGx                                        6, $-intro

6          (8)        $xFx Ú $xGx                           7, Ú-intro

2          (9)        $xFx Ú $xGx                           2, 3, 5, 6, 8 Ú-elim

1          (10)      $xFx Ú $xGx                           1, 2, 9 $-elim

 

 

 

 

 

 

 

 

 

 

 

(b)  "x($yFyx→"zFxz) ├ "y"x(Fyx→Fxy)

 

      1                (1)        "x($yFyx → "zFxz)                             A

      1                (2)        $yFyb → "zFbz                                    1, UE

      3                (3)        Fab                                                       A

      3                (4)        $yFyb                                                   3, $-intro

      1, 3             (5)        "zFbz                                                   2, 4 MPP

      1, 3             (6)        Fba                                                       5, UE

      1                (7)        Fab→Fba                                             3, 6 CP

      1                (8)        "x(Fax→Fxa)                                      7, UE

      1                (9)        "y"x(Fyx→Fxy)                                  8, UE

     

 

            (c)        "xFx ├ ~$xGx ↔ ~($x(Fx & Gx) & "y(Gy→Fy))

           

                        Hint: In one of the directions use transposition.

 

See homework 11 problem #3

 

Part V (20 Pts): Prove the following sequents using the any primitive or derived rules for propositional logic and any primitive rule or application of QE (Quantifier Exchange) of predicte logic.

 

QE rules:           ~"xFx ┤├ $x~Fx

                                "xFx┤├ ~$x~Fx

                                "x~Fx┤├ ~$xFx

                                ~"x~Fx┤├ $xFx

                       

            (a)        "xFx → "xGx ├ $x(Fx → Gx)

 

1          (1)        "xFx → "xGx                                     A

2          (2)        ~$x(Fx→Gx)                                        A

2          (3)        "x~(Fx→Gx)                                       2, QE

2          (4)        ~(Fa→Ga)                                            3, UE

2          (5)        Fa & ~Ga                                             4, negated arrow (above)

2          (6)        Fa                                                        5, &-elim

2          (7)        "xFx                                                    6, UI

1,2        (8)        "xGx                                                   1,7 MPP

2          (9)        ~Ga                                                      5, &-elim

2          (10)      $x~Gx                                                  2, $-intro

2          (11)      ~"xGx                                                 10, QE

1,2        (12)      "xGx & ~"xGx                                    8, 11 &-intro

1          (13)      $x(Fx→Gx)                                          2, 12 RAA

 

 

 

 

 

            (b)        ~"x(P & Fx)├ (P→ ~"xFx)

 

1          (1)        ~"x(P & Fx)                                        A

2          (2)        ~(P→ ~"xFx)                                     A

2          (3)        P & "xFx                                            2, Negated arrow

2          (4)        P                                                          3, &-elim

2          (5)        "xFx                                                    3, &-elim

2          (6)        Fa                                                        5, UE

2          (7)        P & Fa                                                 4, 6 &-intro

2          (8)        "x(P & Fx)                                          7, UI

1, 2      (9)        ~"x(P & Fx) & "x(P & Fx)                1, 8 &-intro

1          (10)      P→ ~"xFx                                          2, 9 RAA