80-211 Arguments and Inquiry                                                                      Spring 2003

 

Exam 1

 

 

1. State what it means for a set of premises G to imply (semantically) a sentence A.

 

G semantically implies A if and only if whenever a truth value assignment makes every formula in G true, then it also makes A true.

 

 

2. State whether the following claims are true or false and briefly explain your answer.

 

            (a)- A sequent with a tautology as conclusion and a contingent sentence as a premise is always valid.

 

True, since in other to show invalidity you need a case where the premises are true and the conclusion false, but since the conclusion is a tautology this cannot happen.

 

 

 

(b)- A sequent with a tautology as a premise and a contingent sentence as a conclusion is always valid.

 

False, since the conclusion is a contingent sentence there is at least one assignment that makes it false call it V. Now since the premise is a tautology it is true for any truth value assignment, in particular its true for V, hence there is an assignment that makes the premises true but the conclusion false.

 

 3. Answer any two of the questions below (i.e. (a), (b) or (c) )

 

(a) Explain briefly the completeness theorem and soundness theorem (i.e. consistency)  for the propositional calculus in terms of the notions of validity and derivability.

 

The soundness theorem for the propositional calculus states that whenever one can prove a formula A from a set of assumptions G (G├ A), then it is the case G semantically implies A (G ╞ A).

 

The completeness theorem for the propositional calculus states that whenever G semantically implies A (G ╞ A), then one can prove the formula A from the set G (G├ A)

 

 

 

 

(b) Suppose we introduced a new connective * in our language that represents the “exclusive or” (that is, either A or B, but not both). First list the truth table for * and then explain why v-introduction is no longer a valid rule of inference when “v” is read as “*”. 

 


P, Q    P * Q

 


T  T        F

T  F        T

F  T        T

F  F        F

 

Ú-intro would not be a valid rule of inference when “Ú” is read as “*” since when using Ú-intro you can introduce any formula you wish.  If one has already established that A, and the one introducees a true formula B, then the result A*B is a false sentence, hence the rule is not valid.

 

(c) For the list of sequents (A) given below, state whether any of the given sequents (i)-(iv) are substitution instances of those sequents (A). If one of the sequents (B) is a substitution instance of one of the sequents (A) state what is being substituted.

 

Sequents (A): 

            1.  ├ P v ~P

            2.   ~(P v Q) ├ ~P & ~Q

            3. ├ P v (P→Q)

            4. ~P v Q ├ P→Q

 

Sequents(B):

            (i)  ~((R v Q) & (P→Q)) ├ ~(R v Q) v ~(P→Q)

            (ii)  ├ (P→Q)↔R) v (((P→Q)↔R)→(P v Q))

            (iii)  ├ ((PvQ)→R) v ~((P v R)→Q))

            (iv)  ~(P v Q) v ((P & Q)→R) ├ (P v Q)→ ((P & Q)→R)

 

 

(ii) is a substitution instance of 3.  Where P/(P→Q) ↔ R and Q/P Ú Q

 

(iv) is a substation instance of 4.   Where P/(P Ú Q) and Q/((P & Q)→R)

 

 

 

 

 

 

 

 

 

 

 

4. Prove the following sequents (a-d) using only the 10  primitive rules of the propositional calculus.

 

           

(a) P→ ~Q ├ Q→ ~P

 

1          (1)        P→~Q                         A

2          (2)        Q                                 A

2          (3)        ~~Q                             2, DN

1, 2      (4)        ~P                                1, 3 MTT

1          (5)        Q→~P                         2, 4 CP

 

 

 

(b)  P→R, Q→R ├ (P v Q)→R

 

1          (1)        P→R                           A

2          (2)        Q→R                           A

3          (3)        P Ú Q                          A

4          (4)        P                                  A

1, 4      (5)        R                                  1,4 MPP

6          (6)        Q                                 A

2, 6      (7)        R                                  2, 6 MPP

1,2,3    (8)        R                                  3,4,5,6,7 Ú-E

1,2       (9)        (P Ú Q) → R               3, 8 CP

 

 

(c)  F↔G ├ (F v G)→F & G

 

1          (1)        F ↔ G                         A

2          (2)        F Ú G                          A

1          (3)        F→G & G→F             1, Def ↔

1          (4)        F→G                           3, &-E

1          (5)        G→F                           3, &-E

6          (6)        F                                  A

1, 6      (7)        G                                 4, 6 MPP

1, 6      (8)        F & G                          6, 7 &-Intro

9          (9)        G                                 A

1, 9      (10)      F                                  5, 9 MPP

1, 9      (11)      F & G                          9, 10 &-intro

1, 2      (12)      F & G                          2, 6, 8, 9, 11 Ú-E

1          (13)      (F Ú G)→(F & G)       2, 12 CP

 

 

 

 

(d)  P & Q ├ ~(P→ ~Q)

 

1          (1)        P & Q                          A

2          (2)        P→~Q                         A

1          (3)        P                                  1, &-E

1, 2      (4)        ~Q                               2, 3 MPP

1          (5)        Q                                 1, &-E

1,2       (6)        Q & ~Q                       4, 5 &-intro

1          (7)        ~(P→~Q)                    2, 6 RAA

 

 

5. Give the truth table for the following formula and state whether it is tautologous, contingent, or inconsistent.

 

            ((P & Q) & ~(P↔Q))

 

 


P  Q     ((P & Q) & ~(P↔Q))

 


T  T            T       F    F  T

T  F            F       F    T  F

F  T           F        F    T  F

F  F           F        F    F  T

 

The truth table shows that the formula is inconsistent.

 

6. Using truth tables determine whether the following sequent is valid or invalid.

 

            ~P → Q ,  Q ├ ~P

 


P  Q     ~P→Q,  Q  ├  ~P

 


T  T          T        T        F

T  F          T         F        F

F  T          T         T        T

F  F          F         F        T

 

 

 

 

 

 

 

 

 

 

7. Prove (a) and (b) using the primitive and any of the derived rules listed below (and of course you can use any substitution instance of them).

 

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

Affirmed consequence                                        Q ├ P→Q

 

(a)  P→Q ├ ~P v Q

 

1          (1)        P→Q                           A

2          (2)        ~(~P Ú Q)                   A

2          (3)        ~~P & ~Q                   2, DeMorgan

2          (4)        ~~P                             3, &-E

2          (5)        P                                  4, DN

1,2       (6)        Q                                 1, 5 MPP

2          (7)        ~Q                               3, &-E

1,2       (8)        Q & ~Q                       6, 7 &-I

1          (9)        ~P Ú Q                                    2, 8 RAA

 

 

(b) ├ (P→Q) v (Q→R)   

 

            (1)        Q Ú ~Q                       Law of the excluded middle

2          (2)        Q                                 A

2          (3)        P→Q                           2, Affirmed Cons.

2          (4)        (P→Q) Ú (Q→R)        3, Ú-I

5          (5)        ~Q                               A

5          (6)        Q→R                           5, Negated ant.

5          (7)        (P→Q) Ú (Q→R)        6, Ú-I

            (8)        (P→Q) Ú (Q→R)        1, 2, 4, 5, 7 Ú-E