Below are some proofs in predicate logic and some examples of how to show a statement is invalid with a model.

 

 

(x)~Kx, (x)(~Kx→~Sx) ├ (x)(Hx v ~Sx)

 

1          (1)        (x) ~Kx                                    A

2          (2)        (x)(~K → ~Sx)             A

1          (3)        ~Ka                              1, UE

2          (4)        ~Ka → ~Sa                  2, UE

1, 2       (5)        ~Sa                              3, 4 MPP

1, 2       (6)        Ha v ~Sa                      5, v-I

1, 2       (7)        (x)(Hx v ~Sx)               6, UI

           

 (x)(Gx → ~Fx), (x)(~Fx → ~Hx) ├ (x)(Gx → ~Hx)

 

            1          (1)        (x)(Gx → ~Fx)              A

            2          (2)        (x)(~Fx → ~Hx)           A

            1          (3)        Ga → ~ Fa                   1, UE

            2          (4)        ~Fa → ~Ha                  2, UE

            5          (5)        Ga                                A

            1, 5       (6)        ~Fa                              3, 5 MPP

            1, 2, 5   (7)        ~Ha                              4, 6 MPP

            1, 2       (8)        Ga → ~Ha                    5, 7 CP

            1, 2       (9)        (x)(Gx → ~Hx)             8, UI

 

($x)~(Cx v ~ Rx) ├ ($x)~Cx

 

      1          (1)        ($x)~(Cx v ~ Rx)          A

      2          (2)        ~(Ca v ~Ra)                 A

      2          (3)        ~Ca & Ra                     2, DeMorgan’s law

      2          (4)        ~Ca                              3, &-E

      2          (5)        $x(~Cx)                        4, $-I

      1          (6)        $x(~Cx)                        1, 2, 5, $-E

 

 

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

 

            1          (1)        $xFx→"xGx                A

            2          (2)        Fa                                A

            2          (3)        $xFx                             2, EI

            1,2        (4)        "xGx                           1, 3 MPP

            1,2        (5)        Ga                                4, UE

            1          (6)        Fa→Ga                                    2, 5 CP

            1          (7)        "x(Fx→Gx)                 6, UI

 

 

 

 

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

 

            1          (1)        P→~"xFx                    A

            2          (2)        "x(P & Fx)                  A

            2          (3)        P & Fa                         2, UE

            2          (4)        P                                  3, &-E

            1,2        (5)        ~"xFx                          1, 4 MPP

            2          (6)        Fa                                3, &-E

            2          (7)        "xFx                            6, UI

            1,2        (8)        "xFx & ~"xFx             5, 7

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

 

$x(P v Fx) ├ ~P→$xFx

 

            1          (1)        $x(P v Fx)                    A

            2          (2)        P v Fa                          A

            3          (3)        P                                  A

            3          (4)        ~~P                              3, DN

            3          (5)        ~P→$xFx                     Negated antecedent (51)

            6          (6)        Fa                                A

            6          (7)        $xFx                             6, E-I

            6          (8)        ~P→$xFx                     Affirmed consequence (50)

            2          (9)        ~P→$xFx                     2, 3, 5, 6, 8 v-elim

            1          (10)      ~P→$xFx                     1,2,9 $-elim

 

~P→$xFx ├ $x(P v Fx)

 

            1          (1)        ~P→$xFx                     A

            2          (2)        ~$x(P v Fx)                  A

            2          (3)        "x~(P v Fx)                 2, QE

            2          (4)        ~(P v Fa)                      3, UE

            2          (5)        ~P & ~Fa                     4, De Morgan

            2          (6)        ~P                                5, &-E

            1, 2       (7)        $xFx                             1, 6 MPP

            2          (8)        ~Fa                              5, &-E

            2          (9)        "x~Fx                          8, UI

            2          (10)      ~$xFx                           9, QE

            1, 2       (11)      $xFx & ~$xFx              7, 10 &-I

            1          (12)      $x(P v Fx)                    2, 11 RAA

 

           

 

 

 

 

 

 

 

 

 

Note: To show a sequent is invalid, one needs to find an interpretation where the interpretation makes the premises true but the conclusion false.

 

$x)Fx ├ Fm

 

Let:      U = N

            Fx = x is odd

            m = 4

Under this interpretation, ($x)Fx is true (for example 3 satisfies it), but Fm is false, since 4 is not odd. Therefore, this interpretation shows that the sequent is invalid. 

 

 

(x)(Fx→Gx), (x)(Hx→Gx) ├ ($x)(Hx & Fx)

 

Let:      U = N

            Fx = x < 5

            Hx = 5 < x < 10

            Gx = x < 10

 

Under this interpretation, clearly, (x)(Fx → Gx) and (x)(Hx → Gx) are true, since, for all x, if x is less than 5, its obviously less than 10 and for all x greater than 5 and less than 10, it is true that x is also less than 10.  But, there is no x, such that x is both 5<x<10 and x<5, hence ($x)(Hx & Fx) is false under this interpretation.  So, we have found an interpretation that makes (x)(Fx → Gx) and (x)(Hx → Gx) true, but ($x)(Hx & Gx) false, in other words we have shown that the sequent is invalid.

 

 

(x)($y)~Lxy ├ (x)~Lxx

 

Let:      U = N

            Lxy = x is equal to y

 

With this interpretation, it is obvious that (x)($y)~Lxy is true, since, for any x, there is a y (say let y =x+1) such that x is not equal to y.  But, (x)~Lxx is false, since (x)~Lxx is equalivent to ~($x)Lxx and we know that there is a natural number (all of them in fact) such that x=x, other words we know that ($x)Lxx is true, so (x)~Lxx must be false. Thus, with this interpretation the sequent is shown to be invalid.