REVIEW TIPS 2

teacher image

MORE COMPLEX SYMBOLIZATION

When we work with quantifiers the most basic thing to remember is that ordinarily a universal quantifier sets up a conditional relationship while an existential quantifier sets up a conjunction.  The English sentences may not sound that much different, but what we need to express can be very different.  The reason: we can make a generalization about everyone without it applying to any individual at all, as when I say that all unicorns are white, meaning only that if there is something that is a unicorn then it will be white.  Saying no unicorns are white does not actually contradict this, since in the absence of actual unicorns neither statement could be shown to be false.  However, once we say some unicorns are white we are committing ourselves (truthfully or not) to saying there are such things as unicorns.
All ambitious students work hard.             No ambitious students work hard.
(x)[(Ax & Sx) -> Wx]                               (x)[(Ax & Sx) -> ~Wx]

Some ambitious students work hard.         Some ambitious students do not work hard.
(Ex)[(Ax & Sx) & Wx]                            (Ex)[(Ax & Sx) & ~Wx]
In working with sentences that involve more than one quantifier the most important thing is to recognize how the ideas are meant to connect so that we know how to use our parentheses and brackets to identify the main connective (and connectives do include the curls and the quantifiers).  Sometimes we can work with equivalent expressions, as in the following, but once the arrow is not the main connective we also need to introduce another variable, regardless of the fact that it will apply to the same individuals.
If every student is working hard then none of them will fail.         Every student working hard means that none of them will fail.
(x)(Sx -> Wx) -> (x)(Sx -> ~Fx)                                              (x)[(Sx -> Wx) -> (y)(Sy -> ~Fy)]
Once we start working with expressions involving relationships (typically something with an active transitive verb) we need to be especially careful. 

Every student likes some classes.     Some students do not like any classes.     There are students who dislike some classes.
(x)[(Sx -> (Ey)(Cy & Lxy)]             (Ex)[(Sx & (y)(Cy -> ~Lxy)]                  (Ex)[(Sx & (Ey)(Cy & ~Lxy)]
(x)(Ey)[Sx ->(Cy & Lxy)]          (Ex)(y)[Sx & (Cy -> ~Lxy)]                    (Ex)(Ey)[Sx & (Cy & ~Lxy)]

TESTING FOR VALIDITY

The reverse method for truth tables is adequate to test any propositional argument form (one without quantifiers) and so are consistency trees.  For expression that do involve quantifiers it is far easier to use consistency trees, but a key error is failing to observe the new name rule in instantiating any expression as you work down a particular branch.  As with derivations, the key thing to remember is to begin with anythng that involves an existential quantifier, then go back to anything with a universal quantifier in order to use the same name (and with UI we can use more than one name).

Where any mechanical method (truth tables or consistency trees) will not always work is when we have more complex expressions involving dyadic predicates.  These will not be assigned during a test.

DERIVATIONS

We have two types of rules to work with.  One is a set of transformation or equivalence rules that may be used inside any part of an expression.
Commutation   (Com)
       P & Q ::  Q & P    
       P v Q  ::  Q v P     
       P<->Q  ::  Q<->P   

Association   (Assoc)
       P & (Q & R)  ::  (P & Q) & R      
       P  v (Q v R)  ::  (P v Q) v R   
        (Do note that this relationship does not apply to biconditionals.)

Distribution  (Dist)
       P & (Q v R)  ::  (P & Q) v (P & R)
       P v (Q & R)  ::  (P v Q) & (P v R)

Double Negation   (DN)
       P :: ~~P
In the application of all other rules, in order to shorten the number of steps in a derivation, we allow DN to be understood rather than expressed

DeMorgan's Law   (DM)
       ~(P & Q)  ::  ~P v ~Q
       ~(P v Q)  ::  ~P & ~Q

Implication  (Impl)
       P -> Q  ::  ~P v Q     be careful to negate what is to the left of the arrow

Equivalence (Equiv)
P <-> Q   ::   (P -> Q)  &  (Q -> P)  

Transposition  (Trans)
       P -> Q   ::  ~Q -> ~P

Quantifier Negation  (QN
       ~(x)Fx  ::  (Ex)~Fx        note that we never have an expression such as ~x

The other is a set of inference rules which allow us to introduce or eliminate our connectives, including quantifiers.  These can be used only with the main connective in an expression (meaning, unlike our equivalence rules they cannot be used inside a parenthesis).
P & Q  |-  P     Simplification  (Simp)
P, Q  |-  P & Q      Conjunction  (Conj)
P v Q, ~P  |- Q      Disjunctive syllogism  (DS)
P  |- P v Q     Addition  (Add)
P -> Q, P |- Q       Modus ponens  (MP)
P -> Q, ~Q  |- ~P      Modus tollens  (MT)
P -> Q, Q -> R |- P -> R     Hypothetical syllogism  (HS)
(x)Fx  |-  Fa     Universal instantiation  (UI)
Fa  |- (x)Fa      Universal generalization  (UG)   normally this requires that the name in question cames from a previous application of the UI rule; the exception is when in a conditional proof we establish a statement such as Fa -> Ga  and then go to (x)(Fx - Gx) 
(Ex)Fx  |- Fa    Existential instantiation  (EI)    the name brought into play must be new--not appearing either in the statement of the argument fom or in a previous step
Fa |- (Ex)Fx     Existential generalization  (EG)

red flagThe major difficulty students have is in not working with the main connective.  For instance, suppose we have an argument form such as the following: 
~(x)(Fx -> Gx) -> (y)(Hy),  (x)Fx & (x)~Gx |-  Ha

In analyzing it the temptation may be to instantiate right away, or to break down the second premise and then instantiate that.  Looking closer and recognizing that the main connective in the antecedent of the first premise is a curl, a different approach becomes necessary.
1.  ~(x)(Fx -> Gx) -> (y)(Hy)
2.  (x)Fx & (x)~Gx                    \ show Ha
3.  (Ex)Fx & ~Gx) -> (y)Hy       1, QN 
4.  (x)Fx                                     2, Simp
6.  Fa                                         5,  UI   
7.  (x)~Gx                                  2, Simp
8.  ~Ga                                      7,  UI
9.  Fa & ~Ga                              6,8,  Conj
10. (Ex)(Fx & ~Gx)                     9,  EG
11.  (y)Hy                                   3,10,  MP
12.  Ha                                       11,  UI

But let's suppose you were stumped and could not see how to attack the problem with a direct derivation.  An indirect derivation is always possible.
1.  ~(x)(Fx -> Gx) -> (y)(Hy)
2.  (x)Fx & (x)~Gx                    \ show Ha
       3.  ~Ha                               HIP
       4.  (Ey)~Hy                         3,  EG
       5.  ~(y)Hy                           4,  QN
       6.  (x)(Fx -> Gx)                  1,5,  MT
       7.  Fa -> Ga                         6, UI
       8.  (x)Fx                               2, Simp
       9.  Fa                                   8, UI
       10.  Ga                                 7,9,  MP
       11.  (x)~Gx                           2,  Simp
       12.  ~Ga                               11,  UI
        13.  Ga & ~Ga                     10,12,  Conj
14.  Ha                                         3-13,  IP

In working with any subordinate derivation, do not forget to indent to show that none of the information on the lines between the hypothesis and the result of the steps is necessarily going to be true apart from the hypothesis itself.  With an indirect proof, as in the example above, we need to show that a contradiction results.  In using a conditional proof we need to show that assuming an antecedent is true will lead to a particular consequent so that the conditional is true regardless of whether the actual statement in the hypothesis is correct.