Introduction to Symbolic Logic - Brandeis University



Introduction to Symbolic Logic

June 16, 2005

❖ More Proof Practice

➢ Problems in June 15 Notes

❖ Basic Concepts of SD

➢ Def. A sentence P of SL is derivable in SD from a set ( of sentences of SL iff there is a derivation in SD in which all the primary assumptions are members of ( and P occurs in the scope of only those assumptions.

▪ ( |-- P: P is derivable from (

▪ A derivation in SD is a series of sentences of SL in which each sentence either is taken as an assumption with an indication of its scope or is justified by one of the rules of SD.

▪ A sentence or subderivation is in the scope of an assumption if the scope line immediately to the left of the assumption is also to the left of the sentence or subderivation

➢ Def. An argument of SL is valid in SD iff the conclusion of the argument is derivable in SD from the set consisting of the premises. An argument of SL is invalid in SD iff it is not valid in SD

➢ Theorems

▪ Some times it is possible to derive a sentence P from an empty set of premises. This is called a theorem.

▪ Def. A sentence P of SL is a theorem in SD iff P is derivable in SD from the empty set.

▪ Example: |-- B((C((B&C))

• We attempt to do this proof the same way we’ve always done them. The difference now is that we don’t have any premises to work with, so we have to look to the conclusion to see how to proceed.

• The conclusion shows us that we should use (I (twice) to do this proof. Again, it is important to take the PAs in the correct order.

[pic]

➢ Equivalence

▪ Def. Sentences P and Q are equivalent in SD if and only if Q is derivable in SD from {P} and P is derivable in SD from {Q}.

▪ To show equivalence in SD, do two proofs. One that takes the first sentence as a premise and derives the second sentence, and vice versa.

➢ Inconsistency

▪ Def. A set ( of sentences of SL is inconsistent in SD iff both a sentence of P of SL and its negation ~P are derivable in SD from (. A set ( of sentences of SL is consistent in SD iff it is not inconsistent in SD.

▪ To show inconsistency in SD, take the sentences in ( as premises and derive a contradiction.

▪ Example: Show {(M(B)(B, A(M, A&~B} is inconsistent in SD

[pic]

▪ If a set of sentences is inconsistent in SD, then any sentence of SL is derivable from that set.

• We could always use ~E to prove the conclusion since an inconsistent set leads to a contradiction.

❖ 3 More Rules

➢ If you are feeling comfortable with SD, you may want to try adding 3 additional derivation rules to your repertoire

➢ Each of these rules are completely unnecessary – you can still do a proof using just the rules of SD, but they can save you time and they’re not really that confusing anyway

➢ Modus Tollens (MT)

▪ This rule works like (E, except that the ingredients it requires are slightly different. It still requires two lines be cited when it is used:

• A conditional

• The negation of the consequent

▪ If you have these two things, then you can derive the negation of the antecedent

[pic]

▪ Again, this rule isn’t required to do a proof. If you don’t have it and you have these two ingredients, you can easily get ~P using ~I, but this rule saves you some steps

➢ Hypothetical Syllogism (HS)

▪ This rule can save you from a short (I proof. It requires two ingredients:

• A conditional of the form P(Q

• A conditional of the form Q(R

▪ In order to use HS, you must have two conditionals one of whose consequent matches the other’s antecedent

▪ If you have these two things, then you can derive the conditional P(R

[pic]

➢ Disjunctive Syllogism (DS)

▪ Now this rule can save you a lot of work!

▪ This rule is like a shorthand version of (E. It requires two ingredients:

• A disjunction

• The negation of one of its disjuncts

▪ If you have these two things, then you can derive the other disjunct. This certainly makes sense truth-functionally, but it also works syntactically. The same result could be found using (E, but it would take at least 7 lines.

[pic]

➢ Remember that these rules only work on full sentences the same way that the original 11 rules of SD do

❖ Replacement Rules

➢ We are already familiar with several equivalences in SL

▪ De Morgan’s Laws, Double Negation, (P(Q)((~P(Q)

➢ We can show using truth tables that these sentences are truth-functionally equivalent, but that is a proof based on semantics

▪ Remember that everything in SD is purely syntactic. Although SD was developed with an eye to semantics, showing something on the semantic side is not enough to show it on the syntactic side

➢ That means that even though we suspect that these equivalences still hold in SD, we need to show that they are equivalent in SD in order to use them in our system

▪ A system that includes any rules in addition to the 11 we have already been using is an extension to that system. We’ll call it SD+.

• Be careful! If a question on a midterm or HW asks you to show something using SD, then these extra rules are off limits!

➢ Proving the equivalences in SD is often somewhat trivial (Commutation, Association), but it can be quite difficult (De Morgan)

▪ Remember that the proof of equivalence in SD actually requires two SD proofs to show both directions

➢ The rules of replacement are special because they can actually work on sentential components, not just complete sentences

▪ Remember that the rules of SD only work on the main connective!

▪ This means that you don’t have to extract a component of a sentence in order to use a replacement rule on it

• Example: G((H&K) can become G((~~H&K) using Double Negation(DN)

▪ Each application of a rule still requires its own line! Go one step at a time

➢ What are the rules?

▪ Commutation (Com)

• P&Q ( Q&P

• P(Q ( Q(P

▪ Association (Assoc)

• P&(Q&R) ( (P&Q)&R

• P((Q(R) ( (P(Q)(R

▪ Implication (Impl)

• P(Q ( ~P(Q

▪ Double Negation (DN)

• P ( ~~P

▪ De Morgan (DeM)

• ~(P&Q) ( ~P(~Q

• ~(P(Q) ( ~P&~Q

▪ Idempotence (Idem)

• P ( P&P

• P ( P(P

▪ Transposition (Trans)

• P(Q ( ~Q(~P

▪ Exportation (Exp)

• P((Q(R) ( (P&Q)(R

▪ Distribution (Dist)

• P&(Q(R) ( (P&Q)((P&R)

• P((Q&R) ( (P(Q)&(P(R)

▪ Equivalence (Equiv)

• P(Q ( (P(Q)&(Q(P)

• P(Q ( (P&Q) ( (~P&~Q)

➢ When would you use these rules?

▪ You can use them at any time of your proof

▪ Use them to avoid using annoying rules

• Example: Sometimes changing a disjunction into a conditional can save you from doing (E

▪ Use them to skip steps

• Example: If you need to get A&B but all you have is B&A, you can use Com on it to save you from breaking it apart and putting it back together

▪ Use them to prove your conclusion

• Example: Sometimes changing your conclusion into a disjunction from a conditional will make it easier to prove. Just make sure on the last step of your proof that you change it back to the real conclusion

➢ Do you have to use these rules?

▪ The rules of replacement are mostly just a convenience. Any proof you are given should be provable (if it’s supposed to be) using just the 11 rules of SD

▪ However, the replacement rules can save you a lot of time and aggravation, if you decide to use them

➢ Practice

▪ (D(B)((E(~C), ~B&[~D&(~E(C)] |-- ~C(E

• If we use SD+, we may be able to avoid some of the more annoying aspects of this proof.

□ Using SD, we would have to use (E (twice!) AND the conclusion is a (, so we would have to use (I in each subderivation of (E

□ However, knowing when to use a RR and why is hard. Until you get the hang of it, the examples in the book can look like they’re pulling lines out of nowhere

➢ To get started with using these rules, stick with Impl and DeM

1) (D(B)((E(~C) P |-- ~C(E ( (~C(E)&(E(~C)

2) ~B&[~D&(~E(C)] P

3) (~B&~D)&(~E(C) 2 Assoc

4) ~(B(D)&(~E(C) 3 DeM

5) ~(B(D) 4 &E

6) ~(D(B) 5 Com

7) E(~C 1,6 DS

8) ~E(C 4 &E

9) ~C(~~E 8 Trans

10) ~C(E 9 DN

11) (~C(E)&(E(~C) 7, 10 &I

12) ~C(E 11 Equiv

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download