User:Logicgroup2
|}Unit 2 (P.Hurley): Propositional Logic
Text: A Concise Introduction Logic 10th Ed. By Patrick Hurley
Group Members: L. Rosenbloom, T. Zha, A. Peri, L. Bonomini, L. Lee , S. Eisen, A. Binder, M. Leinoff, Z. Duan, J. Serow, H.Wang,
Contents of unit 2: The Logical forms of statements (negation, conjunction, etc.). Symbolic representation of logical statement forms. Translation from English into symbolic language. Truth Tables. Natural deduction.
Chapter 6
6.1 Symbols and Translation The fundamental elements in propositional logic are whole statements (propositions). Statements are represented by letters, which are combined with operators to form complex symbolic representations. A simple statement does not contain any other statement as a component, and it can be represented with an uppercase letter. A compound statement contains at least one simple statement. There are five logical operators.
Operator Name Logical Function Used to Translate ～ tilde negation not, it is not the case that . dot conjunction and, also, moreover v wedge disjunction or, unless ⊃ horseshoe implication if...then...only if ≡ triple bar equivalence if and only if
Main Operator: the operator in a compound statement that governs the largest component(s) in the statement.
Negations- the main operator is a tilde, and it is always placed in front of the proposition it negates. It cannot be used to connect two propositions. The tilde is the only operator that can immediately follow another. Example: Rolex does not make computers= ~R Conjunctions- the main operator is a dot. It is used to translate conjunctions such as: and, also, but, however, yet, still, moreover, although, and nevertheless. Example: Tiffany sells jewlery, and Gucci sells cologne= T.G Disjunctions- the main operator is a wedge. It is used to translate "or" and "unless." The word "either" is often used to introduce disjunctive statements. Example: Aspen Allows snowboards or Telluride does= A v T Conditionals- The main operator is a horseshoe. It is used to translate "if...then" and "only if." The expressions "in case," "provided that, " "given that," and "on condition that" are usually translated in the same way as if. The statement that follows "if" is always the antecedent, and the statement that follows "only if" is always the consequent. Example: If Purdue raises tuition, then so does Notre Dame= P ⊃ N. Sufficient Condition- Event A is said to be a sufficient condition for event B whenever the occurrence of A is all that is requires for the occurrence of B. The statement that names the sufficient condition is the antecedent of the conditional. Necessary Condition- Event A is said to be a necessary condition for Event B whenever B cannot occur without the occurrence of A. The statement that names necessary condition should be placed in the consequent. Biconditionals- The main operator is the triple bar. It is used to translate "if and only if" and "is a necessary and sufficient condition for." Example: JFK tightens security if and only if O'Hare does= J ≡ O
Whenever more than two letters appear in a translated statement, brackets, parentheses, or braces must be used to indicate the proper range of the operators. Clues such as commas, semicolons, "either," and "both" are usually given to indicate the correct placement of the parentheses. Example: Prozac relieves depression and Allegra combats allergies, or Zocor lowers cholesterol= (P . A) v Z
Function of "either" and "both" Not either A or B ~ (A v B) Either not A or not B ~ A v ~B Not both A and B ~ (A . B) Both not A and not B ~ A . ~B
6.2 Truth Functions A truth function is any compound proposition whose truth value is completely determined by the truth values of its components. Definitions of the Logical Operators: The definition of the logical operators are presented in terms of statement variables, which are lowercase letters that can stand for any statement. Statement variables are used to construct statement forms. A statement form is an arrangement of statement variables and operators such that the uniform substitution of statements in place of the variables results in a statement. Truth table-- An arrangement of truth values that shows in every possible case how the truth value of a compound proposition is determined by the truth values of its simple components.
Negation p ~p
T F
F T
Conjunction p q p.q
T T T
T F F
F T F
F F F
Disjunction p q pvq
T T T
T F T
F T T
F F F
Conditional p q p⊃q
T T T
T F F
F T T
F F T
Biconditional p q p≡q
T T T
T F F
F T F
F F T
Computing the Truth Value of Longer Propositions
First Step: Write the truth values of the simple propositions immediately below the respective letters and bring the operators and parentheses down:
( A v D ) ⊃ E
( T v F ) ⊃ F
Next we compute the truth value of the proposition in parentheses and write it beneath the operator to which it pertains
( A v D ) ⊃ E
( T v F ) ⊃ F
T ⊃ F
Finally we use the last completed line to obtain the truth value of the conditional, which is the "main operator" in the proposition:
( A v D ) ⊃ E
( T v F ) ⊃ F
T ⊃ F
F --> final answer
The order to be followed in entering truth values in this:
1. Individual letters representing simple propositions 2. Tildes immediately preceding individual letters 3. Operators joining letters or negated letters 4. Tildes immediately preceding parentheses. 5. And so on.
6.3 6.4
6.3 Truth Tables for Propositions A truth table gives the truth value of a compound proposition for every possible truth value of its simple components. Each line in the truth table represents one such possible arrangement of truth values. In constructing a truth table the first step is to determine the number of lines or rows. Each line represents one possible arrangement of truth values. The total number of lines is equal to the number of possible combinations of truth values for the simple propositions. Where "L" designates the number of lines and "n" the number of different simple propositions, the number of lines may be computed by the following formula: L = 2n
By means of this formula we obtain the following table:
Number of different simple propositions Number of lines in truth table 1 2 2 4 3 8 4 16 5 32 6 64
Examples...
(A v ~B) ⊃ B The number of different simple propositions is two. Thus the number of lines in the truth table is four. Then, divide the number of lines in half. The result is two. Go to the first letter on the left (A) and enter T (for true) on the first two lines and F (false) on the remaining two lines.
(A v ~B) ⊃ B T T F F
Next, divide the number (two) in half and, since the result is one, write one T, one F, one T and one F beneath the next letter (B):
(A v ~B) ⊃ B T T T F F T F F
Now, every possible combination of truth and falsity have been assigned to A and B. This covers the entire realm of possibilities. Then, duplicate the B column under the second B.
(A v ~B) ⊃ B T T T T F F F T T F F F
Finally, compute the remaining columns. Firs the column under the tilde is computed from the column under B. The column under the wedge is computed from the column under A and the column under the Tilde. The column under the horseshoe is computed from the column under the wedge and the column under B:
(A v ~ B) ⊃ B T T F T T T T T T F F F F F F T T T F T T F F F
Classifying Statements A compound statement is said to be a logically true or tautologous statement if it is true regardless of the truth values of its components. It is said to be a logically false or self-contradictory statement if it is false regardless of the truth values of its components. It is said to be a contingent statement if its truth value varies depending on the truth values of its components. By inspecting the column of truth values under the main operator, one can determine how the compound proposition should be classified:
Column under main operator Statement classification all true tautologous (logically true) all false self-contradictory (logically false) at least one true, at least one false contingent
The truth value of a compound proposition is "contingent" on the truth values of its components.
Comparing Statements Truth tables may also be used to determine how two propositions are related to each other. Two propositions are said to be logically equivalent statements if they have the same truth value on each line under their main operators, and they are contradictory statements if they have opposite truth values on each line under their main operators. If neither of these relations hold, the propositions are either consistent or inconsistent. Two (or more) propositions are consistent statements if there is at least one line on which both (or all) of them turn out to be true. By comparing the main operator columns, one can determine which is the case.
Columns under main operators Relation Same truth value on each line logically equivalent opposite truth value on each line contradictory there is at least one line on which
the truth values are both true consistent
there is no line on which the truth
values are both true. inconsistent
6.4 Truth Tables for Arguments
Truth tables provide the standard technique for testing the validity of arguments in propositional logic. To construct a truth table for an argument, follow these steps:
1. Symbolize the arguments using letters to represent the simple propositions 2. Write out the symbolized argument, placing a single slash between the premises and a double slash between the last premise and the conclusion. 3. Draw a truth table for the symbolized argument as if it were a proposition broken into parts, outlining the columns representing the premises an conclusion. 4. Look for a line in which all of the premises
6.5 Indirect Truth Table
Indirect truth table provides a shorter and faster method for testing the validity of arguments than do ordinary truth tables. This table is especially applicable to arguments that contain a large number of different simple propositions.
Indirect truth table can also be used to test a series of statements for consistency.
Testing arguments for validity
Consider the following symbolized argument: ～A﹞(B v C) ～B
C﹞A
Step one: We begin as before by writing the symbolized argument on a single line, placing a single slash between the premises and a double slash between the last premises and the conclusion. ～A ﹞(B v C)/ ～B// C﹞A
T T F
Step two: Use negations ～A ﹞(B v C)/ ～B// C﹞A
T T F T F F
Step three: ～A ﹞(B v C)/ ～B// C﹞A T F T F T T T F T F F
This example has a perfectly consistent assignment of truth values, which makes the premises true and the conclusion false. The argument is therefore valid.
Here is another example: Step one: We begin by assigning T to the premises and F to the conclusion A﹞(B v C) / B﹞D/ A //～C﹞D
T T T F
Step two: from the conclusion we can now derive the truth values of C and D, which are then transferred to the first two premises: A﹞(B v C) / B﹞D/ A //～C﹞D
T F T F T T F F F
Step three: the truth value of B is now derived from the second premise and transferred, together with the truth value of A, to the first premise：
A﹞(B v C) / B﹞D/ A //～C﹞D T T F F F F T F T T F F F A contradiction now appears in the truth values assigned to the first premise. The inconsistent truth values are circled. We have shown that it is impossible for the premises to be true and the conclusion false. The argument is therefore valid.
Conclusion:
→ Contradiction → argument is valid
Assume argument invalid (True premises, false conclusion)
→ No contradiction → argument is invalid as assumed
Testing Statements for consistency
The method for testing a series of statements for consistency is similar to the method for testing arguments. We begin by writing the statements on a line, separating each with a single slash mark. Then we assume that the statements are consistent.
Here is an example:
A v B
B﹞(C v A)
C﹞～B
～A
Step one:
A v B/ B﹞(C v A)/ C﹞～B/～A
T T T T
Step two: A v B/ B﹞(C v A)/ C﹞～B/～A F T T T T T T F T T F T T F
Since this computation leads necessarily to a contradiction, the group of statements is inconsistent.
Conclusion
→ Contradiction → statements are inconsistent
Assume statements consistent (assume all of them true)
→No contradiction → statements are as assumed (consistent)
7.1 Natural Reduction in Propositional Logic
7.1 Rules of Implication I
Natural reduction is a method for establishing the validity of propositional type arguments that is both simpler and more enlightening than the method of truth table. (350)
The first eight rules of inference are called rules of implication because they consist of basic argument forms whose premises imply their conclusion. The following four rules are examples of rules of implication.
Modus ponens (MP) Modus tollens (MP) Pure hypothetical syllogism (HS) Disjunctive syllogism (DS)
- Due to the amount of information that relates to this particular unit and the fact that this is one collaborative wiki page- please see the main textbook for examples pertaining to the Natural Deduction in Propositional Logic. (7.1 Rules of Implication I: page 350 to page 361)
7.2 Section 7.2, which is titled: Rules of Implication II, introduces four new rules of implication. They are Constructive dilemma (CD), Simplification (Simp), Conjunction (Conj), and Addition (Add).
Here is a detailed look at each rule of implication.
Constructive dilemma can be broken down into two modus ponens steps. The first premise states that if we have p then we have q, and if we have r then we have s. But when looking at the second premise, we have either p or q. Then, by following modus ponens, we have either q or s. Constructive dilemma is also the only form of dilemma that will be included as a rule of inference.
Simplification states that if two propositions are true on a single line, then each of them is true separately. According to the implication rule, only the left-hand conjunct may be stated in the conclusion.
Conjunction states that two propositions, A and B, asserted separately on different lines may be conjoined on a single line. The two propositions may be conjoined in whatever order we choose (either A and B or B and A) without appeal to the commutatively rule for conjunction.
Addition states that whenever a proposition is asserted on a line by itself it may be joined disjunctively with any proposition we choose. If A is asserted to be true by itself, its follows that A or B is true. The new proposition must always be joined disjunctively to the given proposition. If A is stated on a line by itself, we are not justified in writing A and B as a consequence of addition. Addition is the only rule of inference that can introduce new letters.
7.3 Rules of Replacement: As opposed to rules of implication, rules of replacement are pairs of logically equivalent statements. These two statements can replace one another interchangeably. The symbol (::) double semicolon, is used to signify logical equivalence. This symbol is a metalogical symbol as it does not make a statement about things but the statements they are in; and therefore both interchangeable have completely identical truth values.
De Moragan's rule The rule can be summarized as when moving a negative from inside or outside a parenthesis of an AND or an OR phrase, as the negative is distributed the AND becomes an OR and visa versa. NOT (P OR Q) :: (NOT P) AND (NOT Q) NOT (P AND Q) :: (NOT P) OR (NOT Q)
Commutativity states that the truth value of a conjunction and disjuntion is not affected by the order of the components. Therefore the component statements may be switched with one another without affecting the truth value. (P OR Q) :: (Q OR P) (P AND Q) :: Q AND P)
Associativity: States that the truth value of a conjunctive or disjunctive statement is unaffected by the placement of parentheses when the same operator is used throughout the statement.
[P OR ( Q OR R)] :: [(P OR Q) OR R]
[P AND ( Q AND R)] :: [(P AND Q) AND R]
Distribution: States that when a proposition is conjoined to a disjunctive statement in parenthesis or disjointed to a conjunctive statement in parenthesis the proposition may be distributed in its conjunction or disjunction to the conjoined or disjoined statements. [P AND (Q OR R)] :: [(P AND Q) OR (P AND R)] [P OR (Q AND R)] :: [(P OR Q) AND (P OR R)]
Double Negation States that the a double negative is logically equivalent to a positive and may be used interchangeably.
P:: ~~P
7.4 Transposition asserts that the antecedent and consequent of a conditional statement may switch places if and only if tildes are inserted before both or tildes are removed from both.
Material implication is less obvious than transposition, but it can be illustrated by substituting actual statement in place of the letters.
Material equivalence has two formulations. The first is the same as the definition of material equivalence. The second formulation is easy to remember through recalling the two ways in which P is equivalent to q may be true.
Exportation asserts that the statement “ if we have p, then if we have Q we have r” is logically equivalent to “ if we have both p and q, we have r”.
Tautology, the last rule introduced in this section, is obvious its effect is to eliminate redundancy in disjunctions and conjunctions.
7.5 On occasion, you may find yourself trying to solve a proof in which the direct method can’t help you, most likely because you aren’t given enough information derive the conclusion. When this occurs, you can use a method known as the conditional proof in order to help solve your problem. The conditional proof gives you the ability to obtain a line in the form of a conditional statement. To illustrate how the conditional works, an example is given below:
1. A Your browser may not support display of this image. (B · C)
2. (B Your browser may not support display of this image. D) Your browser may not support display of this image. E / AYour browser may not support display of this image. E
We note that in this proof we are not given any single statements to start with. However, we also notice that in both the first and second lines and the conclusion, we have conditional statements, so this would be a good candidate for a conditional proof. We will use the conditional method with the concluding statement in this case, though you are allowed to use the method to obtain any line in the sequence.
The Proof
Step 1: The first step in obtaining a conditional proof is identifying where in the proof it is needed, which gives you your starting point of the conditional. We have already said that we will use the conclusion. To begin obtaining the conditional, assume the sufficient condition.
1. A Your browser may not support display of this image. (B · C)
2. (B Your browser may not support display of this image. D) Your browser may not support display of this image. E / AYour browser may not support display of this image. E
Your browser may not support display of this image. 3. A ACP
Step 2: Now you can derive whatever statements you need from the assumed statement A using the 18 rules of implication and replacement.
1. A Your browser may not support display of this image. (B · C)
2. (B Your browser may not support display of this image. D) Your browser may not support display of this image. E / AYour browser may not support display of this image. E
Your browser may not support display of this image. 3. A ACP
4. B · C 3, 1 MP
5. B 4 Simp
6. B Your browser may not support display of this image. D 5 Add
7. E 6, 2 MP
8. AYour browser may not support display of this image. E
There are several important rules to remember in any conditional proof. The first line of the sequence
(marked ACP above for “Assume Conditional Proof”) and the last line, E in this case, form the sufficient condition and the necessary condition, respectively, of the final conditional proof, line 8 in this case. Below is a second example, this time for a proof in which all you are given is the conclusion. It also demonstrates the ability of the conditional proof to assume as large a statement as you want, provided it is in parentheses or brackets. ( Other things to keep in mind: once you exit the conditional proof sequence, you MAY NOT use any of the lines derived within later on in the proof, including if you have the need to use a second conditional in the same proof. Think of the dark line as a separate proof entirely. As mentioned above, you may use as many conditional proofs as you need in order to arrive at your necessary conclusion.)
Your browser may not support display of this image. / [(A Your browser may not support display of this image. (B Your browser may not support display of this image. C) · D] Your browser may not support display of this image. E
1. [(A Your browser may not support display of this image. (B Your browser may not support display of this image. C) · D] ACP
2. E 1, MP
3. [(A Your browser may not support display of this image. (B Your browser may not support display of this image. C) · D] Your browser may not support display of this image. E 1-2, CP
Proving a Logical Truth (Hurley 7.7)
If you have a logical truth (a tautology), you can use both conditional and indirect proof methods to establish the truth of the statement. This works because any argument with a tautology for a conclusion is valid regardless of its premises.
Step 1: Write the statement to be proven as if it was the conclusion of a conditional or indirect proof.
Step 2: Indent the first line of the proof and treat is as the beginning for a conditional or indirect statement.
Here is an example of proving the same truth using both Conditional and Indirect Methods.
The Truth: / P Your browser may not support display of this image. (Q Your browser may not support display of this image. P)
The Proofs:
Conditional
/ P Your browser may not support display of this image. (Q Your browser may not support display of this image. P)
Your browser may not support display of this image. Your browser may not support display of this image. 1. P ACP
2. Q ACP
3. PYour browser may not support display of this image. P 1, Add
4. P 3, Taut
5. Q Your browser may not support display of this image. P 2-4, CP
6. P Your browser may not support display of this image. (Q Your browser may not support display of this image. P) 1-5, CP
Indirect
/ P Your browser may not support display of this image. (Q Your browser may not support display of this image. P)
Your browser may not support display of this image. 1. ~ [P Your browser may not support display of this image. (Q Your browser may not support display of this image. P)] AIP
2. ~ [~P Your browser may not support display of this image. (Q Your browser may not support display of this image. P)] 1, Impl
3. ~ [~P Your browser may not support display of this image. (~Q Your browser may not support display of this image. P)] 2, Impl
4. ~ ~P · ~ (~Q Your browser may not support display of this image. P) 3, DM
5. P · ~(~Q Your browser may not support display of this image. P) 4, DN
6. P · ~(~~Q · ~P) 5, DM
7. P · ~(~P ·~~Q) 6, Com
8. (P · ~P) 7, Assoc
9. P · ~P 8, Simp
10. ~~ [P Your browser may not support display of this image. (Q Your browser may not support display of this image. P)] 1-9, IP
11. P Your browser may not support display of this image. (Q Your browser may not support display of this image. P) 10, DN
As you can see, in this instance it required fewer steps to derive the conclusion using the conditional method than it did the indirect method. However, in some instances, the indirect method works more quickly. Both methods allow you to derive the appropriate conclusion.
7.6 Indirect Proofs Indirect proof is a method similar to conditional proofs and can be used on any argument to either obtain the conclusion or some line leading to the conclusion. In order to use the indirect proof method, you must assume the negation of the statement that is to be obtained. Use this assumption to derive a contradiction, and then conclude that the original assumption is false. The first statement that is assumed false is tagged "AIP" (Assumed indirect proof) and is written inside an indent of a line and all work that stems from this step must be written within the indent of the line as well. When a contradiction is found, you may step out of the indented line, write down the negation of the first assumed line and label it "IP" (Indirect proof).
7.7
Proving a Logical Truth (Hurley 7.7)
If you have a logical truth (a tautology), you can use both conditional and indirect proof methods to establish the truth of the statement. This works because any argument with a tautology for a conclusion is valid regardless of its premises.
Step 1: Write the statement to be proven as if it was the conclusion of a conditional or indirect proof.
Step 2: Indent the first line of the proof and treat is as the beginning for a conditional or indirect statement.
Here is an example of proving the same truth using both Conditional and Indirect Methods.
The Truth: / P http://www.earlham.edu/~peters/writing/matimp.gif http://www.earlham.edu/~peters/writing/matimp.gif (Q http://www.earlham.edu/~peters/writing/matimp.gif http://www.earlham.edu/~peters/writing/matimp.gif P)
The Proofs:
Conditional
/ P http://www.earlham.edu/~peters/writing/matimp.gif http://www.earlham.edu/~peters/writing/matimp.gif (Q http://www.earlham.edu/~peters/writing/matimp.gif http://www.earlham.edu/~peters/writing/matimp.gif P)
image image 1. P ACP
2. Q ACP
3. Phttp://www.earlham.edu/~peters/writing/disjunct.gif http://www.earlham.edu/~peters/writing/disjunct.gif P 1, Add
4. P 3, Taut
5. Q http://www.earlham.edu/~peters/writing/matimp.gif http://www.earlham.edu/~peters/writing/matimp.gif P 2-4, CP
6. P http://www.earlham.edu/~peters/writing/matimp.gif http://www.earlham.edu/~peters/writing/matimp.gif (Q http://www.earlham.edu/~peters/writing/matimp.gif http://www.earlham.edu/~peters/writing/matimp.gif P) 1-5, CP
Indirect
/ P http://www.earlham.edu/~peters/writing/matimp.gif http://www.earlham.edu/~peters/writing/matimp.gif (Q http://www.earlham.edu/~peters/writing/matimp.gif http://www.earlham.edu/~peters/writing/matimp.gif P)
image 1. ~ [P http://www.earlham.edu/~peters/writing/matimp.gif http://www.earlham.edu/~peters/writing/matimp.gif (Q http://www.earlham.edu/~peters/writing/matimp.gif http://www.earlham.edu/~peters/writing/matimp.gif P)] AIP
2. ~ [~P http://www.earlham.edu/~peters/writing/disjunct.gif http://www.earlham.edu/~peters/writing/disjunct.gif (Q http://www.earlham.edu/~peters/writing/matimp.gif http://www.earlham.edu/~peters/writing/matimp.gif P)] 1, Impl
3. ~ [~P http://www.earlham.edu/~peters/writing/disjunct.gif http://www.earlham.edu/~peters/writing/disjunct.gif (~Q http://www.earlham.edu/~peters/writing/disjunct.gif http://www.earlham.edu/~peters/writing/disjunct.gif P)] 2, Impl
4. ~ ~P · ~ (~Q http://www.earlham.edu/~peters/writing/disjunct.gif http://www.earlham.edu/~peters/writing/disjunct.gif P) 3, DM
5. P · ~(~Q http://www.earlham.edu/~peters/writing/disjunct.gif http://www.earlham.edu/~peters/writing/disjunct.gif P) 4, DN
6. P · ~(~~Q · ~P) 5, DM
7. P · ~(~P ·~~Q) 6, Com
8. (P · ~P) 7, Assoc
9. P · ~P 8, Simp
10. ~~ [P http://www.earlham.edu/~peters/writing/matimp.gif http://www.earlham.edu/~peters/writing/matimp.gif (Q http://www.earlham.edu/~peters/writing/matimp.gif http://www.earlham.edu/~peters/writing/matimp.gif P)] 1-9, IP
11. P http://www.earlham.edu/~peters/writing/matimp.gif http://www.earlham.edu/~peters/writing/matimp.gif (Q http://www.earlham.edu/~peters/writing/matimp.gif http://www.earlham.edu/~peters/writing/matimp.gif P) 10, DN
As you can see, in this instance it required fewer steps to derive the conclusion using the conditional method than it did the indirect method. However, in some instances, the indirect method works more quickly. Both methods allow you to derive the appropriate conclusion.