Suppose we have the rule of hypothesis introduction, conditional introduction, and conditional elimination. From just these rules of inference, in classical propositional calculus, we never need a rule of repetition, nor need CqCpq as an axiom. In other words, if those rules hold, then "q, p|-q" comes as a valid schema and CqCpq is a theorem.
1 | q hypothesis introduction
2 || p hypothesis introduction
3 ||| q hypothesis introduction
4 || Cqq 3-3 conditional introduction
5 || q 1, 4 conditional elimination
6 | Cpq 2-5 conditional introduction
7 CqCpq 1-6 conditional introduction.
Monday, September 26, 2011
Monday, September 19, 2011
Define a propositional form as follows:
1) Lower case letters, along with lower case letters subscripted with numbers a1, b2, c13 are propositional forms.
2) If x and y are both propositional forms, then Cxy is a propositional form.
Let Cab denote the material conditional with 'a' and 'b' taking truth values in {T, F}. Let "C1 ...Cn" denote a concatenation of n conditionals, and "a1...a(n+1)" a concatenation of (n+1) logical variables. E. G. C1...C3a1...a4 denotes CCCa1a2a3a4. Let a/b denote a substitution of variable "a" with "b", let a/Cab denote that we substitute variable "a" with Cab.
Axiom 1: CCpqCCqrCpr
Axiom 2: CqCpq
Theorem 1: CCCpqC1...C(10^100)a1...a((10^100)+1)CqC1...C(10^100)a1...a((10^100)+1)
Demonstration:
1 CCqCpqCCCpqC1...C(10^100)a1...a((10^100)+1)CqC1...C(10^100)
a1...a((10^100)+1) Axiom 1, p/q, q/Cpq, r/C1...C(10^100)a1...a((10^100)+1)
2 CCCpqC1...C(10^100)a1...a((10^100)+1)CqC1...C(10^100)a1...a((10^100)+1) Axiom 2, 1 detachment.
1) Lower case letters, along with lower case letters subscripted with numbers a1, b2, c13 are propositional forms.
2) If x and y are both propositional forms, then Cxy is a propositional form.
Let Cab denote the material conditional with 'a' and 'b' taking truth values in {T, F}. Let "C1 ...Cn" denote a concatenation of n conditionals, and "a1...a(n+1)" a concatenation of (n+1) logical variables. E. G. C1...C3a1...a4 denotes CCCa1a2a3a4. Let a/b denote a substitution of variable "a" with "b", let a/Cab denote that we substitute variable "a" with Cab.
Axiom 1: CCpqCCqrCpr
Axiom 2: CqCpq
Theorem 1: CCCpqC1...C(10^100)a1...a((10^100)+1)CqC1...C(10^100)a1...a((10^100)+1)
Demonstration:
1 CCqCpqCCCpqC1...C(10^100)a1...a((10^100)+1)CqC1...C(10^100)
a1...a((10^100)+1) Axiom 1, p/q, q/Cpq, r/C1...C(10^100)a1...a((10^100)+1)
2 CCCpqC1...C(10^100)a1...a((10^100)+1)CqC1...C(10^100)a1...a((10^100)+1) Axiom 2, 1 detachment.
Sunday, September 18, 2011
Is ApNp a Conjunctive Normal Form?
The notion of a conjunctive normal form first appears in Paul Bernays's second Habilitationsschrift [1] (doctoral thesis). In that text, Bernays established the completeness of propositional calculus [2]. On p. 38-39 of Formal Logic [3] Arthur Prior writes in the context of a completeness proof for propositional calculus:
"What they show [Hilbert and Ackermann] is that any formula of the propositional calculus is equivalent either (i) to a single propositional variable or the negation of one, or (ii) to an alternation of which all the members are either propositional variables or their negations, or alternations (or alternations of alternations, etc.) of such or (iii) to a conjunction of which all members are of the form listed under (i) and (ii), or conjunctions (or conjunctions of conjunctions, etc.) of such. We may describe all these forms as 'conjunctions of alternations of propositional-variables-or-their-negations', if (a) we call a form like 'KKpqr' a 'conjunction of p, q, and r' instead of calling it a 'conjunction of the-conjunction-of-p-and-q and r', and similarly with alternations, and (b) we regard a single propositional variable (or negation of one) as an alternation with a single alternant (it is as it were a limiting case of alternation; in any case such a variable is equivalent to the alternation of itself with itself-EpApp), and (c) we also regard a single propositional variable (or negation of one) as a conjunction with a single conjunct, and a single alternation as a conjunction-of-alternations with a single conjunct. The forms which would be 'conjunctions of alternations of propositional variables or their negations' would include such examples as
(i) p and Np (conjunctions-with-one-member of alternations-with-one-member).
(ii) ApNq (a conjunction-with-one-member of an alternation with two membes).
(iii) AApNqNp (a conjunction-with-one-member of an alternation with three members).
(iv) KpApq (a conjunction of an alternation-with-one-member and an alternation with two members).
(v) KApqApNq (a conjunction of two alternations-with-two-members).
(vi) KApAqrKApqApAst (a conjunction-with-three-members of an alternation-with-three-members, and an alternation-with-two-members, and another alternation-with-three-members.)
That every truth-functional formula can be 'put into normal form', i.e. shown to be equivalent to (i. e. to imply and be implied by) a formula of the above sort..."
So, for Prior, conditions (i), (ii), and (iii) in the first paragraph almost surely would define a "conjunctive normal form". This suggests that in the context of a (correct) proof of the completeness of propositional logic, that is, where the notion of a conjunctive normal form first got defined, ApNp is indeed a conjunctive normal form.
1 This information I retrieved http://books.google.com/books?id=1xEVkzuX5e0C&pg=PA501&lpg=PA501&dq=conjunctive+normal+form+bernays+Habilitationsschrift&source=bl&ots=DfCwTAO-wL&sig=rMok5p3XCMoGxQY8j-YEWLKCkes&hl=en&ei=GlZ2TpjNMoS6tgfu_6DSDA&sa=X&oi=book_result&ct=result&resnum=1&ved=0CBsQ6AEwAA#v=onepage&q=conjunctive%20normal%20form%20bernays%20Habilitationsschrift&f=false on September 18, 2011.
2 This information I retrieved from http://www.encyclopedia.com/doc/1G2-2830905020.html on September 18, 2011.
3 Prior, Arthur. Formal Logic Oxford University Press 1962.
"What they show [Hilbert and Ackermann] is that any formula of the propositional calculus is equivalent either (i) to a single propositional variable or the negation of one, or (ii) to an alternation of which all the members are either propositional variables or their negations, or alternations (or alternations of alternations, etc.) of such or (iii) to a conjunction of which all members are of the form listed under (i) and (ii), or conjunctions (or conjunctions of conjunctions, etc.) of such. We may describe all these forms as 'conjunctions of alternations of propositional-variables-or-their-negations', if (a) we call a form like 'KKpqr' a 'conjunction of p, q, and r' instead of calling it a 'conjunction of the-conjunction-of-p-and-q and r', and similarly with alternations, and (b) we regard a single propositional variable (or negation of one) as an alternation with a single alternant (it is as it were a limiting case of alternation; in any case such a variable is equivalent to the alternation of itself with itself-EpApp), and (c) we also regard a single propositional variable (or negation of one) as a conjunction with a single conjunct, and a single alternation as a conjunction-of-alternations with a single conjunct. The forms which would be 'conjunctions of alternations of propositional variables or their negations' would include such examples as
(i) p and Np (conjunctions-with-one-member of alternations-with-one-member).
(ii) ApNq (a conjunction-with-one-member of an alternation with two membes).
(iii) AApNqNp (a conjunction-with-one-member of an alternation with three members).
(iv) KpApq (a conjunction of an alternation-with-one-member and an alternation with two members).
(v) KApqApNq (a conjunction of two alternations-with-two-members).
(vi) KApAqrKApqApAst (a conjunction-with-three-members of an alternation-with-three-members, and an alternation-with-two-members, and another alternation-with-three-members.)
That every truth-functional formula can be 'put into normal form', i.e. shown to be equivalent to (i. e. to imply and be implied by) a formula of the above sort..."
So, for Prior, conditions (i), (ii), and (iii) in the first paragraph almost surely would define a "conjunctive normal form". This suggests that in the context of a (correct) proof of the completeness of propositional logic, that is, where the notion of a conjunctive normal form first got defined, ApNp is indeed a conjunctive normal form.
1 This information I retrieved http://books.google.com/books?id=1xEVkzuX5e0C&pg=PA501&lpg=PA501&dq=conjunctive+normal+form+bernays+Habilitationsschrift&source=bl&ots=DfCwTAO-wL&sig=rMok5p3XCMoGxQY8j-YEWLKCkes&hl=en&ei=GlZ2TpjNMoS6tgfu_6DSDA&sa=X&oi=book_result&ct=result&resnum=1&ved=0CBsQ6AEwAA#v=onepage&q=conjunctive%20normal%20form%20bernays%20Habilitationsschrift&f=false on September 18, 2011.
2 This information I retrieved from http://www.encyclopedia.com/doc/1G2-2830905020.html on September 18, 2011.
3 Prior, Arthur. Formal Logic Oxford University Press 1962.
Monday, August 30, 2010
Order AND Parentheses Free Notation?
In mathematics and logic expressions often get written with the operation in infix notation... we write a+b, a^b, a v b. As logicians and mathematicians know this means that we either have to establish an order of operations when we have more than operation involved, such as Exponents, Multiplication, Division, Addition, Subtraction for arithmetic, or use parentheses, or have ambiguous expressions. Since at least the time of Lukasiewicz, mathematical and logical scholars have known that we can stop excusing our dear Aunt Sally. In Lukasiewicz notation instead of writing (5+2)*4, we can simply write *+5 2 4. In reverse Lukasiewicz notation we can write 5 2+4*. I highly recommend that you read the link there, and translate some common logical or mathematical expressions into reverse Lukasiewicz notation. Since these notational systems establish that we can write mathematical and logical expressions in prefix notation (Lukasiewicz notation), infix notation, and postfix notation (reverse Lukasiewicz notation), can we write mathematical and logical expressions in a way such that the operations involved can come *anywhere* in the expression *without* having a fixed order as declined languages do?
For variables or constants, suppose we write a unique subscript below each of them. For an n-ary operation suppose we write n sequenced subscripts which correspond to the subscripts in the order of variables or constants it operates on. E. G. if we write xa yb+ab, then we indicate that the operation "+" operates on x and y. We can then immediately write xa+abyb as well as +abxayb. So, suppose we have a function F such that a b cF=b c*a+. Then we could write 4c8dFcba6a7e+de2b. So, do you believe that this gives us an order free notation for the operations in a logical or mathematical expression? Please answer this question and write a response down on paper before reading my further comment.
For variables or constants, suppose we write a unique subscript below each of them. For an n-ary operation suppose we write n sequenced subscripts which correspond to the subscripts in the order of variables or constants it operates on. E. G. if we write xa yb+ab, then we indicate that the operation "+" operates on x and y. We can then immediately write xa+abyb as well as +abxayb. So, suppose we have a function F such that a b cF=b c*a+. Then we could write 4c8dFcba6a7e+de2b. So, do you believe that this gives us an order free notation for the operations in a logical or mathematical expression? Please answer this question and write a response down on paper before reading my further comment.
Saturday, August 7, 2010
Lately I've read Susan Bassein's An Infinite Series Approach to Calculus . She presents an interesting proof, in my opinion, that the positive square root of 2 cannot get expressed exactly in terms of rational numbers. At least once I could understand her language.
Here, we'll define a 2nd power root of n as any number x such that x2=n. The positive square root, denoted sqr(n) hereafter, consequently comes as a positive number which satisfies this equation. Due to the way exponentiation works there only exists one positive number here. With that definition in mind, we'll proceed to show that if b, and c are integers, then sqr(2) ≠ b/c.
First since sqr(2) ≠ b/c, we have that 2 &ne (b/c)2. So, 2c2 &ne b2. We can also derive sqr(2) ≠ b/c from 2c2 &ne b2, so if we show 2c2 &ne b2, then the conjecture follows. We'll now develop some seemingly trivial lemmas.
Lemma 1: the product of two odd numbers d, e is another odd number.
Since d=2y+1, and e=2z+1, we have de=(2y+1)(2z+1)=4yz+2y+2z+1=2(yz+y+z)+1. Since yz+y+z equals another integer, 2(yz+y+z)+1 is odd.
Lemma 2: the product of two even numbers, f, g, is another even number.
Since f=2w, g=2v, fg=(2w)(2v)=2(2wv). Since 2wv equals another integer, fg is even.
If one does something even more seemingly "trivial" here, something else can become apparent.
Lemma 3: the square of an even number h is also even.
Since h=2z, h2=(2z)2=22z2
Now suppose that b in 2c2 &ne b2 is odd. So, b2 is odd also. Since 2c2 is even this implies this inequality as correct.
Suppose that b is even, and c is odd. Then, the inequality holds since 2c2 is even also and can only get divided by 2 once, and b2=(2n)2=22n which implies it can get divided by 2 twice.
Now suppose that b in 2c2 &ne b2 is even and c is even also. So, both b2 and c2 are even also. All even numbers can get written as a product 2xo, where o denotes an odd number. Consequently, b and c can get divided by 2 x times, or we could say that b and c have x even factors. So, now treating y as any integer, y2=[(2x)o]2=(2x)2*o2. So, we have 22x*o2=2x*2x*o2. Thus, b and c have x+x=2x even factors. Since this holds, 2c2 has an odd number of even factors. So, the inequality holds.
Therefore, for all integers b, c, sqr(2) ≠ b/c.
As far as I can tell, there's no hidden reductio ad absurbum lurking here, but it might come as trickier to spot than I believe.
Here, we'll define a 2nd power root of n as any number x such that x2=n. The positive square root, denoted sqr(n) hereafter, consequently comes as a positive number which satisfies this equation. Due to the way exponentiation works there only exists one positive number here. With that definition in mind, we'll proceed to show that if b, and c are integers, then sqr(2) ≠ b/c.
First since sqr(2) ≠ b/c, we have that 2 &ne (b/c)2. So, 2c2 &ne b2. We can also derive sqr(2) ≠ b/c from 2c2 &ne b2, so if we show 2c2 &ne b2, then the conjecture follows. We'll now develop some seemingly trivial lemmas.
Lemma 1: the product of two odd numbers d, e is another odd number.
Since d=2y+1, and e=2z+1, we have de=(2y+1)(2z+1)=4yz+2y+2z+1=2(yz+y+z)+1. Since yz+y+z equals another integer, 2(yz+y+z)+1 is odd.
Lemma 2: the product of two even numbers, f, g, is another even number.
Since f=2w, g=2v, fg=(2w)(2v)=2(2wv). Since 2wv equals another integer, fg is even.
If one does something even more seemingly "trivial" here, something else can become apparent.
Lemma 3: the square of an even number h is also even.
Since h=2z, h2=(2z)2=22z2
Now suppose that b in 2c2 &ne b2 is odd. So, b2 is odd also. Since 2c2 is even this implies this inequality as correct.
Suppose that b is even, and c is odd. Then, the inequality holds since 2c2 is even also and can only get divided by 2 once, and b2=(2n)2=22n which implies it can get divided by 2 twice.
Now suppose that b in 2c2 &ne b2 is even and c is even also. So, both b2 and c2 are even also. All even numbers can get written as a product 2xo, where o denotes an odd number. Consequently, b and c can get divided by 2 x times, or we could say that b and c have x even factors. So, now treating y as any integer, y2=[(2x)o]2=(2x)2*o2. So, we have 22x*o2=2x*2x*o2. Thus, b and c have x+x=2x even factors. Since this holds, 2c2 has an odd number of even factors. So, the inequality holds.
Therefore, for all integers b, c, sqr(2) ≠ b/c.
As far as I can tell, there's no hidden reductio ad absurbum lurking here, but it might come as trickier to spot than I believe.
Friday, March 19, 2010
Monday, October 26, 2009
Quarterback "Controversy" in Cleveland
First let us note that there has existed quarterback controversies in Cleveland for years and years. Kelly Holcomb vs. Tim Couch, Charlie Frye vs. Derek Anderson in 2007, Derek Anderson vs. Brady Quinn in 2008 and 2009. National announcers have noted that the Cleveland Browns have changed quarterbacks very, very many times since 1999. Thus, Cleveland fans have almost come to expect it as business-as-usual if the Browns staff can't decide on a quarterback.
In 2007 Derek Anderson became the Browns starter and had good enough of a year to make the NFL Pro Bowl. So, there existed little question that he would start for the Browns in 2008. But, when he didn't fare all too well, he eventually got benched for Brady Quinn. Both players ended their seasons injured, and thus one could get lead to believe that there existed a real question in the mind of new Cleveland coach Eric Mangini in 2009. But, for Mangini there never existed a question. Brady Quinn would play as his quarterback. So why the apparent "controversy"?
Brady Quinn's contract has clauses in it that he would have made about $11 million if he took over 70 percent of the snaps in 2009. So, if somehow it could look like there existed a "controversy" for the position between Quinn and Anderson, there wouldn't exist a huge backlash from the fans for benching Quinn if the Browns' season quickly went sour. So, Mangini helped lead fans into the notion of a quarterback "controversy." He didn't play either Quinn or Anderson in the Browns' final preseason game so no one could tell who would start for the Browns. And he wouldn't announce who would start until almost opening kickoff or someone leaked who would start to the press (which did happen).
If it got made to look that Brady Quinn didn't have all that much talent, the fans woulnd't retailiate for benching him if the Browns' season quickly went sour and Cleveland didn't have a need to win football games this year. And of course, it did go sour. On top of that Quinn played weakly enough that it looked and looks legitimate to bench him. And Quinn might even realize he benched for monetary reasons. After all, even though he has played for 10 quarters and 36 quarters remain, he's already put his house on the market. Quinn knows he won't get enough snaps for his almost $11 million bonus. So, he (rationally) wants to find a less expensive place to live.
Again, Mangini wanted Quinn as his quarterback. But, after losing the first two games of the season, and losing badly to the Baltimore Ravens at halftime in the 3rd game, Mangini got instructed by his bosses to bench Quinn immediately. After all, why would you spend almost $11 million on a quarterback if he's not going to lead your team to a (home) playoff game? With an 0-3 record clearly in sight, even with a strong turnaround in the next few games the Browns almost surely wouldn't do that. Therefore, bench Quinn, play Anderson. We set things up to make this easy, remember?
Mangini may even have liked benching Quinn in a way. For by benching Quinn, Quinn takes on the role of playing the scout's team offense for the defense. Conceivably, or so someone might argue, that could help develop the Browns' defense more by having the better quarterback scout the opposing team's offense for the defense to practice against. So, when Derek Anderson struggled after playing for a bit, Mangini showed no hesitation in saying that he didn't anticipate benching Anderson. "Build" the defense for next year.
Fact or fiction? You decide.
In 2007 Derek Anderson became the Browns starter and had good enough of a year to make the NFL Pro Bowl. So, there existed little question that he would start for the Browns in 2008. But, when he didn't fare all too well, he eventually got benched for Brady Quinn. Both players ended their seasons injured, and thus one could get lead to believe that there existed a real question in the mind of new Cleveland coach Eric Mangini in 2009. But, for Mangini there never existed a question. Brady Quinn would play as his quarterback. So why the apparent "controversy"?
Brady Quinn's contract has clauses in it that he would have made about $11 million if he took over 70 percent of the snaps in 2009. So, if somehow it could look like there existed a "controversy" for the position between Quinn and Anderson, there wouldn't exist a huge backlash from the fans for benching Quinn if the Browns' season quickly went sour. So, Mangini helped lead fans into the notion of a quarterback "controversy." He didn't play either Quinn or Anderson in the Browns' final preseason game so no one could tell who would start for the Browns. And he wouldn't announce who would start until almost opening kickoff or someone leaked who would start to the press (which did happen).
If it got made to look that Brady Quinn didn't have all that much talent, the fans woulnd't retailiate for benching him if the Browns' season quickly went sour and Cleveland didn't have a need to win football games this year. And of course, it did go sour. On top of that Quinn played weakly enough that it looked and looks legitimate to bench him. And Quinn might even realize he benched for monetary reasons. After all, even though he has played for 10 quarters and 36 quarters remain, he's already put his house on the market. Quinn knows he won't get enough snaps for his almost $11 million bonus. So, he (rationally) wants to find a less expensive place to live.
Again, Mangini wanted Quinn as his quarterback. But, after losing the first two games of the season, and losing badly to the Baltimore Ravens at halftime in the 3rd game, Mangini got instructed by his bosses to bench Quinn immediately. After all, why would you spend almost $11 million on a quarterback if he's not going to lead your team to a (home) playoff game? With an 0-3 record clearly in sight, even with a strong turnaround in the next few games the Browns almost surely wouldn't do that. Therefore, bench Quinn, play Anderson. We set things up to make this easy, remember?
Mangini may even have liked benching Quinn in a way. For by benching Quinn, Quinn takes on the role of playing the scout's team offense for the defense. Conceivably, or so someone might argue, that could help develop the Browns' defense more by having the better quarterback scout the opposing team's offense for the defense to practice against. So, when Derek Anderson struggled after playing for a bit, Mangini showed no hesitation in saying that he didn't anticipate benching Anderson. "Build" the defense for next year.
Fact or fiction? You decide.
Subscribe to:
Comments (Atom)