Introduction to Symbolic Logic - Brandeis University



Introduction to Symbolic Logic

June 14, 2005

❖ SD, so far

➢ Rules for ‘&’ and ‘(’

➢ Elimination Rules use main connectives

▪ Elimination rules are the only way to use sentences that are already in the proof

➢ Introduction Rules create main connectives

▪ Introduction rules tend to be strategy rules. We use them to prove different kinds of sentences (&I to prove conjunctions, (I to prove conditionals)

➢ Reiteration

▪ Reiteration is a simple SD rule that lets you repeat any sentence in your proof at any time

• You may want to do this for clarity in your proof

• Some rules require particular sentences appear at particular times, so you may have to use reiteration

➢ More practice using ‘&’ and ‘(’

▪ R(S, R(T |-- R((S&T)

[pic]

▪ (A&D)(S, A, A(D |-- S

[pic]

❖ Introduction and Elimination Rules for ‘~’

➢ The introduction and elimination rules for ‘~’ behave the same way, but introduction is used if your desired conclusion is a negation and elimination is used when it isn’t

▪ You know you want to use ~I when your conclusion is a negation

▪ It’s harder to know when to use ~E; it is a rule of last resort.

▪ The negation rules are proofs by contradiction (Reductio ad absurdum)

➢ Negation Introduction (~I)

▪ From a sub-derivation that has a sentence P as its provisional assumption and sentences Q and ~Q derived within it, ~P can be derived.

• This is another strategy rule:

□ To prove a negation: (1) Assume its negate, (2) Prove a sentence and its opposite, (3) Discharge the PA and derive the negation

• The contradiction of Q and ~Q can be any sentence Q. The contradiction doesn’t have to have anything to do with the PA, but it can.

• The recipe for this rule requires that Q and ~Q appear in the same sub-derivation, so you may have to use reiteration to make that happen

[pic]

▪ Example: (U&M)(S, M&~S |-- ~U

[pic]

• What kind of sentence is ‘~U’?

□ Negation – Use ~I: Assume the negate, prove a contradiction

▪ Example ~(J(H)(~~(J(H) |-- ~~(J(H)

[pic]

• What kind of sentence is ‘~~(J(H)’?

□ Even though you might want to cancel out the double negation, we don’t have a rule that allows us to do that. We can only do things that are allowed by the rules.

□ So, this sentence is a negation, which means we can use ~I.

• Notice that the contradiction used in this proof is made up of molecular sentences and one of them is even the PA

□ It doesn’t have to be this way, but it certainly is allowed.

□ The key thing to remember is that you are trying to find a sentence and its opposite in order to discharge the PA

➢ Negation Elimination (~E)

▪ The method for using ~E is the same as that for ~I, but it is not as clear when to use it

• Unlike other elimination rules, there doesn’t have to be a negation already present in the proof, so it’s unclear what negation you’ll be eliminating

• Unlike other strategy rules, the desired conclusion doesn’t offer any clues that ~E is a good strategy to try

□ Often atomic sentences will require ~E, but not always

□ Occasionally, you might get stuck trying to use another strategy. When this happens, ~E can be used as a rule of last resort

[pic]

▪ Example: ~S(O, O(S |-- S

[pic]

➢ Reductio ad absurdum

▪ If we can derive both a sentence and its negation under a provisional assumption, we can conclude that the PA can be rejected on the grounds that it led to an absurdity. That is, it led to a logically false sentence.

➢ Example: ~(P&Q) |-- P(~Q

▪ What kind of sentence is ‘P(~Q’?

• Conditional – use (I

□ Assume P. Prove ~Q

□ What kind of sentence is ~Q?

➢ Negation – use ~I

▪ Assume Q. Prove a contradiction.

[pic]

▪

❖ Introduction and Elimination Rules for ‘(’

➢ Disjunction Introduction ((I)

▪ Given any sentence P we may derive P(Q or Q(P

• Unlike &I, which requires that both conjuncts be present in the proof before that rule is used, (I only requires one of the disjuncts be in the proof

• This means you can introduce an entirely new sentence to the proof

• The truth-functional properties of ( allow this rule to be truth-preserving. A disjunction is true as long as one of the disjuncts is true. If we already know that P is true, any disjunction with P as a disjunct will also be true

[pic] or [pic]

▪ Use (I whenever you need to prove a disjunction. Sometimes that will be your desired conclusion, but remember that you can also use this rule (and the others) if you want to prove an ingredient for another rule

▪ Example: B&E, [E((F&C)](I |-- M(I

• What kind of sentence is ‘M(I’?

□ Disjunction – Use (I

➢ Prove one of the disjuncts. Since M isn’t in the premises anywhere, we’ll try to prove I

➢ What kind of sentence is I?

▪ Atomic – Can it be derived from the premises alone or do we need to use the rule of last resort(~E)?

▪ If we can get the antecedent of ‘[E((F&C)](I’, we can derive ‘I’.

[pic]

➢ Disjunction Elimination ((E)

▪ (I lets us exploit the fact that a disjunction is true whenever at least one of the disjuncts is true

▪ However, if a disjunction just appears in a proof, we don’t know which disjunct is the true one, or they both could be true

▪ In order to use (eliminate) a disjunction we have to do a proof by cases

• Assume one of the disjuncts and prove the desired conclusion

• Assume the other disjunct and prove the desired conclusion

[pic]

• We know that disjunction is true, so at least one of the disjuncts is true. We can show both that if it is the left disjunct, we can derive the conclusion and that if it is the right disjunct, we can derive the conclusion. So, it doesn’t matter which disjunct is actually the true one (or they both could be true), as long as we have showed that the conclusion can be derived in either case.

▪ (E is a special kind of strategy rule because it is used whenever a disjunction is present in the premises

• When you are devising your plan of attack for a proof, the first thing you should do is check the premises for a disjunction, even before looking at the conclusion

• If a disjunction is present, you must use (E in order to make use of it

• (E is used to prove the desired conclusion

▪ Example: A(G, A(~R, G(~R |-- ~R

• Even though the conclusion is a negation, the presence of a disjunction in the premises supercedes that fact – use (E

□ Assume A. Prove ~R.

➢ Now we want to prove a negation, but since ~R appears as the consequent of the conditionals in the premises, it is likely we won’t have to use ~I

□ Assume G. Prove ~R

□ Derive ~R using (E

[pic]

▪ Example: T(P, ~T(G, T(~T |-- P(G

• ‘T(~T’ is a disjunction in the premises – use (E

□ Assume T. Prove P(G.

□ ‘P(G’ is a disjunction – use (I

➢ Prove either P or G

□ Assume ~T. Prove P(G.

➢ Prove either P or G

[pic]

❖ Introduction and Elimination Rules for ‘(’

➢ Biconditional Elimination ((E)

▪ Remember that a biconditional is true whenever either both sides are true or both sides are false. Since lines in a derivation represent true statements (to us! There’s no truth or semantics at all in the derivation system), we appeal to the case when both sides are true for this rule

▪ If we have a sentence P(Q and either side of it, we can derive the other side

[pic] or [pic]

▪ Example: S&(S(E), C(E, C(G |-- G

• Even though ‘G’ is atomic, it’s worth trying to hack away at the premises to see if G falls out before resorting to ~E

[pic]

➢ Biconditional Introduction ((I)

▪ (I is a strategy rule for proving a biconditional

▪ It appeals to the fact that a biconditional is really just two conditionals in a conjunction

▪ So, to prove a biconditional, we first have to do something like (I in one direction and then repeat it in the other direction

• If we can prove the left side by assuming the right and prove the right side by assuming the left, then we may derive the biconditional and discharge the assumptions

[pic]

▪ Example: P(Q, Q(P |-- P(Q

[pic]

❖ Examples

➢ R(F, ~F |-- ~R

➢ G((M&A), A(~W, ~W(~M |-- ~G

➢ ~(P(Q) |-- ~P&~Q

➢ A Nice Long One (hehe)

▪ ~P&~Q |-- ~(P(Q)

• ~(P(Q) is a negation – use ~I

□ Assume P(Q. (!!! Alarm bells !!!)

➢ P(Q is a disjunction in the premises now (it still counts as a premise even if it is a provisional one)

➢ We have to use (E on it…

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

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

Google Online Preview   Download