Harriet Hall here writes "
Caldwell Esselstyn
Esselstyn did an uncontrolled interventional study
of patients with angiographically documented severe coronary artery
disease who were not hypertensive, diabetics, or smokers. He wanted to
test how effective one physician could be in helping patients achieve a
total cholesterol level of 150 mg/dL or less, and what effect
maintaining that level would have on coronary disease. Patients agreed
to follow a plant-based diet with <10% of calories derived from fat.
They were asked to eliminate oil, dairy products (except skim milk and
no-fat yogurt), fish, fowl, and meat. They were encouraged to eat
grains, legumes, lentils, vegetables, and fruit. Cholesterol-lowering
medication was individualized.
There were originally 24 patients: 6 dropped out early on, 18
maintained the diet, one of these 18 died of an arrhythmia and 11
completed a mean of 5.5 years followup. Repeat angiography showed that
of 25 coronary artery lesions, 11 regressed and 14 remained stable. At
10 years, 11 patients remained: 6 continued the diet and had no further
coronary events; 5 resumed their pre-study diet and reported 10 coronary
events.
In a 12 year followup report,
the 6 who had maintained the diet at 10 years and the 5 who had gone
off it and had coronary events had apparently somehow morphed into 17
patients who had remained adherent to the diet and who had had no
coronary events. I couldn’t understand the discrepancy in numbers;
perhaps readers can explain it to me if I missed something."
First off, it may seem that another number doesn't match in that the follow-up study says that the original study had 24 patients, while the first study above mentions 22. But, the first study says "The study included 22 patients with angiographically documented, severe
coronary artery disease that was not immediately life threatening." So, there isn't any necessarily contradiction in numbers there.
Second, the first study says "Of the 22 participants, 5 dropped out within 2 years, and 17 maintained
the diet, 11 of whom completed a mean of 5.5 years of follow-up." This does NOT say that 11 of them, implying that 6 quit the diet, but that 11 of them engaged in follow-up. As the follow-up study says: "At 5 years, 11 of
these patients underwent angiographic analysis by the percent stenosis
method, which demonstrated disease arrest in all 11 (100%) and
regression in 8 (73%)." So, the 11 who completed the follow-up appears to refer to the patients who completed angiograms. 6 of the 17 didn't complete follow-up by not engaging in angiograms.
Another discrepancy in the numbers may appear to exist in that the follow study says "The remaining 18 patients adhered to the study diet and medication for 5 years.", while the first indicates 17 maintaining the diet. But, that 17 number appears in the passage about 5.5 years of follow-up and the second study says "One patient admitted
to the study with <20% left ventricular output died from a
ventricular arrhythmia just weeks after the 5-year follow-up angiogram
had confirmed disease regression. Autopsy revealed no myocardial infarction. " So, there doesn't exist any contradiction there.
A further discrepancy may seem to exist in that the first study says "Among the 11 remaining patients after 10 years, six continued the diet
and had no further coronary events, whereas the five dropouts who
resumed their prestudy diet reported 10 coronary events." This might seem like 5 more patients (5 out of the 22 who had angiographically documented coronary artery disease) dropped out of the study, which would contradict 17 patients in the follow study. However, the five dropouts here probably refers to the original 5 of the original 22 angiographically documented patients who dropped out of the dietary program withing 2 years. Esselstyn may have only mentioned 6 continuing the diet here, because he was only able to verify 6 still on the dietary plan when he published this. The other 11 (not all angiographically documented patients) he may not have verified as still on the dietary plan until later... and that's perhaps part of the reason why he provided the update to the study in the first place.
Monday, May 28, 2012
Tuesday, April 10, 2012
Mimic Operations
The author writes informal proofs in the following. The author uses Reverse Polish Notation also.
Suppose we have an infinite set S, and a operation "*". A mimic operation *' of * consists of an operation on S such that for all but a finite number of points a1, ..., an *=a1, ..., an *'. So, for a unary operation F on the natural numbers N, a mimic operation F' satisfies xF=xF' except for a finite set of natural numbers {a1,...,an}. For a binary operation G on N, a mimic of B, B' satisfies xyB=xyB' except for a finite number of pairs of natural numbers {(a, b)1,...,(a, b)n} and so on.
Theorem 1: For any n-ary operation O on an infinite set, there exists an infinity of mimic operations, O'.
Proof: An n-ary operation O can get defined by a set of n 1 + tuples. E. G. the binary operation of addition can get defined by the triples (2, 4, 6), (1, 1, 2) such that for (x, y, z), xy+=z. Now consider the set of such tuples T for O. Vary the n 1 + part of the tuples in T for some finite number of tuples. This forms a set of tuples T' which describes an n-ary operation distinct from O in but a finite number of points, and thus forms a mimic operation O'. Note that since there exist an infinity of tuples belonging to T, there exists an infinity of ways to form T' given T. Thus, given an n-ary operation O, there exists an infinity of mimic operations O'.
Define a k-mimic operation Mk of an operation M as an operation which differs from M by but k points, where both operations operate over an infinite set. In other words, for an operation Mn of arity n with mimic Mkn, a1...anMn=a1...anMkn, except for k tuples {(b1, ..., bn), ..., (l1, ..., ln)} where this equality fails.
Theorem 2: For any n-ary operation O on an infinite set, there exists an infinity of k mimic operations.
Proof: Since given the set of tuples T for an operation O there exist an infinity of ways to form T' (see the proof of Theorem 1). From T' we have an infinity of k-mimic operations O' of O.
Theorem 3: If a binary operation O satisfies commutativity, then if xxO=xxO1, O1 does not satisfy commutativity.
Proof: If O1 is a 1-mimic of O, then xyO=xyO1 for all but one pair (a, b). Suppose that for all x and y, if xyO=yxO, and xyO1=yxO1. Suppose that (a, b) consists of the point where O and O1 differ, by say letting abO=c, and letting abO1=d, where d does not equal c. It follows then that abO1=d=baO1 by supposition of commutation for O1. But, this implies that the pair (b, a) consists of a second point where O and O1 differ, which contradicts the supposition of O1 as a 1-mimic of O. Consequently, the theorem follows and if O1 satisfies commutation it at least consists of a 2-mimic.
Conjecture: If On and Ok are mimics of operation O, then On and Ok are mimics of each other.
The author thinks theorem 3 generalizes to o-mimics, where "o" indicates any positive odd number. The author also thinks that converse of the theorem holds in that if a 1-mimic does satisfy commutation, the operation which it mimics will not satisfy commutation also. Do there exist any relationships (or lack thereof) between an associative operation and its mimics? Between an idempotent operation and its mimics?
The author writes informal proofs in the following. The author uses Reverse Polish Notation also.
Suppose we have an infinite set S, and a operation "*". A mimic operation *' of * consists of an operation on S such that for all but a finite number of points a1, ..., an *=a1, ..., an *'. So, for a unary operation F on the natural numbers N, a mimic operation F' satisfies xF=xF' except for a finite set of natural numbers {a1,...,an}. For a binary operation G on N, a mimic of B, B' satisfies xyB=xyB' except for a finite number of pairs of natural numbers {(a, b)1,...,(a, b)n} and so on.
Theorem 1: For any n-ary operation O on an infinite set, there exists an infinity of mimic operations, O'.
Proof: An n-ary operation O can get defined by a set of n 1 + tuples. E. G. the binary operation of addition can get defined by the triples (2, 4, 6), (1, 1, 2) such that for (x, y, z), xy+=z. Now consider the set of such tuples T for O. Vary the n 1 + part of the tuples in T for some finite number of tuples. This forms a set of tuples T' which describes an n-ary operation distinct from O in but a finite number of points, and thus forms a mimic operation O'. Note that since there exist an infinity of tuples belonging to T, there exists an infinity of ways to form T' given T. Thus, given an n-ary operation O, there exists an infinity of mimic operations O'.
Define a k-mimic operation Mk of an operation M as an operation which differs from M by but k points, where both operations operate over an infinite set. In other words, for an operation Mn of arity n with mimic Mkn, a1...anMn=a1...anMkn, except for k tuples {(b1, ..., bn), ..., (l1, ..., ln)} where this equality fails.
Theorem 2: For any n-ary operation O on an infinite set, there exists an infinity of k mimic operations.
Proof: Since given the set of tuples T for an operation O there exist an infinity of ways to form T' (see the proof of Theorem 1). From T' we have an infinity of k-mimic operations O' of O.
Theorem 3: If a binary operation O satisfies commutativity, then if xxO=xxO1, O1 does not satisfy commutativity.
Proof: If O1 is a 1-mimic of O, then xyO=xyO1 for all but one pair (a, b). Suppose that for all x and y, if xyO=yxO, and xyO1=yxO1. Suppose that (a, b) consists of the point where O and O1 differ, by say letting abO=c, and letting abO1=d, where d does not equal c. It follows then that abO1=d=baO1 by supposition of commutation for O1. But, this implies that the pair (b, a) consists of a second point where O and O1 differ, which contradicts the supposition of O1 as a 1-mimic of O. Consequently, the theorem follows and if O1 satisfies commutation it at least consists of a 2-mimic.
Conjecture: If On and Ok are mimics of operation O, then On and Ok are mimics of each other.
The author thinks theorem 3 generalizes to o-mimics, where "o" indicates any positive odd number. The author also thinks that converse of the theorem holds in that if a 1-mimic does satisfy commutation, the operation which it mimics will not satisfy commutation also. Do there exist any relationships (or lack thereof) between an associative operation and its mimics? Between an idempotent operation and its mimics?
Sunday, October 16, 2011
Alternative Ways to Approach Propositional Calculus
There exist several ways to approach propositional calculus: axiomatically, through natural deduction, sequent calculi, semantic tableaux. An axiomatic presentation sometimes will start with a list of axioms, the rule of substitution, and the rule of conditional elimination (Co for "conditional out"). For example, one could start with the axiom set {CCpqCCqrCpr, CCNppp, CpCNpq} A1 or {CqCpq, CCpCqrCCpqCpr, CCNpNqCqp} A2. But, let's say we start another way.
Suppose we have the rules of conditional proof alon with substitution and conditional elimination. In other words, we have a rule which allows to introduce any propositional form as a hypothesis, so long as we keep track of its scope, and we have a rule of conditional introduction (Ci for "conditional in"). Suppose also, we don't want to use any axioms for propositional calculus. What sorts of rules of inference do we need?
Well, since the above axiom sets work as sufficient for propositional calculus, we could use the deduction metatheorem from CCNppp to obtain the rule of inference CNpp|-p. So, instead of using A1 we could use R3 {(Cpq, Cqr, p |-r), (CNpp|-p), (p, Np|-q)} along with just conditional elimination and substitution for propositional calculus. But, really, given the rules of conditional proof, we don't need all those rules as primitive rules. (Cpq, Cqr, p |-r) can get derived using just conditional proof as follows:
1 Cpq hypothesis
2 Cqr hypothesis
3 p hypothesis
4 q 3, 1 Co
5 r 4, 2 Co
We can also derive CqCpq, and CCpCqrCCpqCpr and using just conditional proof as follows:
1 | q hypothesis
2 || p hypothesis
3 ||| q hypothesis
4 || Cqq 3-3 Ci
5 || q 1, 4 Co
6 | Cpq 2-5 Ci
7 CqCpq 1-6 Ci
1 | CpCqr hypothesis
2 || Cpq hypothesis
3 ||| p hypothesis
4 ||| q 3, 2 Co
5 ||| Cqr 3, 1 Co
6 ||| r 4, 5 Co
7 || Cpr 3-6 Ci
8 | CCpqCpr 2-7 Ci
9 CCpCqrCCpqCpr 1-8 Ci
So, by the first proof instead of considering A1 with substitution and conditional elimination, we can consider {CCNppp, CpCNpq} N1 along with the rules of conditional proof, conditional elimination and substitution. By the second and third proofs instead of considering A2 we can consider N2 {CCNpNqCqp} along with the same rules which go along with N1. Now using the deduction metatheorem instead of considering N1 we can consider R1 {(CNpp|-p) R1a, (p, Np|-q) R1b} and R2 {(CNpNq, q |-p) MT}. A few weeks ago I took an old logic book and tried to prove certain theorems in both R1 and R2.
So, let's compare some proofs of Peirce's law CCCpqpp in R2 and R1 (of course more proofs exist, the following just give examples). In R1 a proof might go:
1 | CCpqp hypothesis
2 || Np hypothesis
3 ||| p hypothesis
4 ||| q 2, 3 R1b
5 || Cpq 3-4 Ci
6 || p 5, 1 Co
7 | CNpp 2-6 Ci
8 | p R1a
9 CCCpqpp 1-8 Ci
In R2 a proof might go:
1 | CCpqp hypothesis
2 || Np hypothesis
3 ||| p hypothesis
4 |||| Nq hypothesis
5 ||||| Np hypothesis
6 |||| CNpNp 5-5 Ci
7 |||| Np 2, 6 Co
8 ||| CNqNp 4-7 Ci
9 ||| q 3, 8 MT
10 || Cpq 2-9 Ci
11 || p 10, 1, Co
12 | CNpp 2-11 Ci
13 || Np hypothsis
14 ||| NNCNpp hypothesis
15 |||| NNNp hypothesis
16 ||||| Np hypothesis
17 |||| CNpNp 16-16 Ci
18 |||| Np 13, 17 Co
19 ||| CNNNpNp 15-18 Ci
20 ||| p 13, 12 Co
21 ||| NNp 20, 19 MT
22 || CNNCNppNNp 14-21 Ci
23 || NCNpp 13, 22 MT
24 | CNpNCNpp 13-23 Ci
25 | p 12, 24 MT
26 CCCpqpp 1-25 Ci
Let's also compare proofs of CNNpp and CpNNp. In R1 a proof for CNNpp might go:
1 | NNp hypothesis
2 || Np hypothesis
3 || p 1, 2 R1b
4 | CNpp 2-3 Ci
5 | p 4, R1a
6 CNNpp 1-5 Ci
In R2 a proof for CNNpp might go:
1 | NNp hypothesis
2 || Np hypothesis
3 ||| NNNNp hypothesis
4 |||| NNp hypothesis
5 ||| CNNpNNp 4-4 Ci
6 ||| NNp 1, 5 Co
7 || CNNNNpNNp 3-6 Ci
8 || NNNp 2, 7 MT
9 | CNpNNNp 2-8 Ci
10 | p 1, 9 MT
11 CNNpp 1-10 Ci.
For CpNNp in R1 we can have:
1 | p hypothesis
2 || Np hyopthesis
3 || NNNp 1, 2 R1b
4 | CNpNNNp 2-3 Ci
5 | NNp 4, R2b
6 CpNNp 1-5 Ci
For CpNNp in R2 we can have:
1 | p hypothesis
2 || NNNp hypothesis
3 ||| NNp hypothesis
4 |||| NNNNNp hypothesis
5 ||||| NNNp hypothesis
6 |||| CNNNpNNNp 5-5 Ci
7 |||| NNNp 2, 6 Co
8 ||| CNNNNNpNNNp 4-7 Ci
9 ||| NNNNp 3, 8 MT
10 || CNNpNNNNp 3-9 Ci
11 || Np 2, 10 MT
12 | CNNNpNp 2-11 Ci
13 | NNp 1, 12 MT
14 CpNNp 1-13 Ci.
Suppose we have the rules of conditional proof alon with substitution and conditional elimination. In other words, we have a rule which allows to introduce any propositional form as a hypothesis, so long as we keep track of its scope, and we have a rule of conditional introduction (Ci for "conditional in"). Suppose also, we don't want to use any axioms for propositional calculus. What sorts of rules of inference do we need?
Well, since the above axiom sets work as sufficient for propositional calculus, we could use the deduction metatheorem from CCNppp to obtain the rule of inference CNpp|-p. So, instead of using A1 we could use R3 {(Cpq, Cqr, p |-r), (CNpp|-p), (p, Np|-q)} along with just conditional elimination and substitution for propositional calculus. But, really, given the rules of conditional proof, we don't need all those rules as primitive rules. (Cpq, Cqr, p |-r) can get derived using just conditional proof as follows:
1 Cpq hypothesis
2 Cqr hypothesis
3 p hypothesis
4 q 3, 1 Co
5 r 4, 2 Co
We can also derive CqCpq, and CCpCqrCCpqCpr and using just conditional proof as follows:
1 | q hypothesis
2 || p hypothesis
3 ||| q hypothesis
4 || Cqq 3-3 Ci
5 || q 1, 4 Co
6 | Cpq 2-5 Ci
7 CqCpq 1-6 Ci
1 | CpCqr hypothesis
2 || Cpq hypothesis
3 ||| p hypothesis
4 ||| q 3, 2 Co
5 ||| Cqr 3, 1 Co
6 ||| r 4, 5 Co
7 || Cpr 3-6 Ci
8 | CCpqCpr 2-7 Ci
9 CCpCqrCCpqCpr 1-8 Ci
So, by the first proof instead of considering A1 with substitution and conditional elimination, we can consider {CCNppp, CpCNpq} N1 along with the rules of conditional proof, conditional elimination and substitution. By the second and third proofs instead of considering A2 we can consider N2 {CCNpNqCqp} along with the same rules which go along with N1. Now using the deduction metatheorem instead of considering N1 we can consider R1 {(CNpp|-p) R1a, (p, Np|-q) R1b} and R2 {(CNpNq, q |-p) MT}. A few weeks ago I took an old logic book and tried to prove certain theorems in both R1 and R2.
So, let's compare some proofs of Peirce's law CCCpqpp in R2 and R1 (of course more proofs exist, the following just give examples). In R1 a proof might go:
1 | CCpqp hypothesis
2 || Np hypothesis
3 ||| p hypothesis
4 ||| q 2, 3 R1b
5 || Cpq 3-4 Ci
6 || p 5, 1 Co
7 | CNpp 2-6 Ci
8 | p R1a
9 CCCpqpp 1-8 Ci
In R2 a proof might go:
1 | CCpqp hypothesis
2 || Np hypothesis
3 ||| p hypothesis
4 |||| Nq hypothesis
5 ||||| Np hypothesis
6 |||| CNpNp 5-5 Ci
7 |||| Np 2, 6 Co
8 ||| CNqNp 4-7 Ci
9 ||| q 3, 8 MT
10 || Cpq 2-9 Ci
11 || p 10, 1, Co
12 | CNpp 2-11 Ci
13 || Np hypothsis
14 ||| NNCNpp hypothesis
15 |||| NNNp hypothesis
16 ||||| Np hypothesis
17 |||| CNpNp 16-16 Ci
18 |||| Np 13, 17 Co
19 ||| CNNNpNp 15-18 Ci
20 ||| p 13, 12 Co
21 ||| NNp 20, 19 MT
22 || CNNCNppNNp 14-21 Ci
23 || NCNpp 13, 22 MT
24 | CNpNCNpp 13-23 Ci
25 | p 12, 24 MT
26 CCCpqpp 1-25 Ci
Let's also compare proofs of CNNpp and CpNNp. In R1 a proof for CNNpp might go:
1 | NNp hypothesis
2 || Np hypothesis
3 || p 1, 2 R1b
4 | CNpp 2-3 Ci
5 | p 4, R1a
6 CNNpp 1-5 Ci
In R2 a proof for CNNpp might go:
1 | NNp hypothesis
2 || Np hypothesis
3 ||| NNNNp hypothesis
4 |||| NNp hypothesis
5 ||| CNNpNNp 4-4 Ci
6 ||| NNp 1, 5 Co
7 || CNNNNpNNp 3-6 Ci
8 || NNNp 2, 7 MT
9 | CNpNNNp 2-8 Ci
10 | p 1, 9 MT
11 CNNpp 1-10 Ci.
For CpNNp in R1 we can have:
1 | p hypothesis
2 || Np hyopthesis
3 || NNNp 1, 2 R1b
4 | CNpNNNp 2-3 Ci
5 | NNp 4, R2b
6 CpNNp 1-5 Ci
For CpNNp in R2 we can have:
1 | p hypothesis
2 || NNNp hypothesis
3 ||| NNp hypothesis
4 |||| NNNNNp hypothesis
5 ||||| NNNp hypothesis
6 |||| CNNNpNNNp 5-5 Ci
7 |||| NNNp 2, 6 Co
8 ||| CNNNNNpNNNp 4-7 Ci
9 ||| NNNNp 3, 8 MT
10 || CNNpNNNNp 3-9 Ci
11 || Np 2, 10 MT
12 | CNNNpNp 2-11 Ci
13 | NNp 1, 12 MT
14 CpNNp 1-13 Ci.
Wednesday, October 12, 2011
Expressing All Statement Forms of Two Logical Variables as Conditionals
Every statement form which has only two logical variables can get expressed (i. e. comes as logically equivalent to) with {C, N} as the only set allowed for logical operations. For example, the statement form for conjunction Kxy, can get expressed as NCxNqy. Allowing only C and N as the only logical operations in a formula, can we express all statement forms with only two logical variables as conditionals? In other words, can we express all statement forms with only two logical variables such that C is the primary connective, or equivalently such that in Polish notation C is the first symbol of the statement form?
I answer yes. To see that this holds, you can consider the Sheffer stroke D:D00=1, D01=1, D10=1, D11=0. Since Nx==Dxx, and Dxy==CxNy (in other words we can define N and D in this way, and Nx comes as logically equivalent to Dxx, and Dxy comes as logically equivalent to CxNy), for any statement form which comes as a negation, we can transform it into a conditional, by first transforming it into a statement form with the Sheffer stroke D as its primary connective, and then transform the obtained statement form directly into a conditional.
More concretely one can see that you can do such as follows: let abcd indicate that the statement form has value "a" for the pair (0, 0) where 0 indicates falsity, and 1 truth, "b" for the pair (0, 1), c for the pair (1, 0), and d for the pair (1, 1). So, for example 0101 indicates that the statement form has truth value of false (0) when both arguments are false, has truth value of truth (1) when the first argument is false and the second true, has truth value of false (0) when the first argument is true and the second false, and has truth value of true (1) when both arguments are true. Thus, to show that all statement forms of two variables can get expressed as a conditional we only need to come with one example for 0000 through 1111.
For 0000, CCppNCpp works.
For 0001, from Kpq one can infer NCpNq, from which one can infer DCpNqCpNq, from which it follows that CCpNqNCpNq.
For 0010, from KpNq one can infer NCpq, to DCpqCpq to CCpqNCpq.
For 0011, from p we can infer CCqqp (in general C1y==y).
For 0100, from KqNp to NCqp, DCqpCqp, CCqpNCqp.
For 0101, from q to CCppq.
For 0110, from NEpq to NKCpqCqp to NNCCpqNCqp to CCpqNCqp
For 0111, Apq to CNpq
For 1000, KNpNq to NCNpNNq to NCNpq to DCNpqCNpq to CCNpqNCNpq
For 1001, from Epq to KCpqCqp to NCCpqNCqp to DCCpqNCqpCCpqNCqp to CCCpqNCqpNCCpqNCqp
For 1010, from Nq to CCppNq
For 1011, from NKNpq to NNCNpNq to CNpNq or Cqp
For 1100, from Np to CCqqNp
For 1101, Cpq
For 1110, NKpq to NNCpNq to CpNq
For 1111, Cpp.
I answer yes. To see that this holds, you can consider the Sheffer stroke D:D00=1, D01=1, D10=1, D11=0. Since Nx==Dxx, and Dxy==CxNy (in other words we can define N and D in this way, and Nx comes as logically equivalent to Dxx, and Dxy comes as logically equivalent to CxNy), for any statement form which comes as a negation, we can transform it into a conditional, by first transforming it into a statement form with the Sheffer stroke D as its primary connective, and then transform the obtained statement form directly into a conditional.
More concretely one can see that you can do such as follows: let abcd indicate that the statement form has value "a" for the pair (0, 0) where 0 indicates falsity, and 1 truth, "b" for the pair (0, 1), c for the pair (1, 0), and d for the pair (1, 1). So, for example 0101 indicates that the statement form has truth value of false (0) when both arguments are false, has truth value of truth (1) when the first argument is false and the second true, has truth value of false (0) when the first argument is true and the second false, and has truth value of true (1) when both arguments are true. Thus, to show that all statement forms of two variables can get expressed as a conditional we only need to come with one example for 0000 through 1111.
For 0000, CCppNCpp works.
For 0001, from Kpq one can infer NCpNq, from which one can infer DCpNqCpNq, from which it follows that CCpNqNCpNq.
For 0010, from KpNq one can infer NCpq, to DCpqCpq to CCpqNCpq.
For 0011, from p we can infer CCqqp (in general C1y==y).
For 0100, from KqNp to NCqp, DCqpCqp, CCqpNCqp.
For 0101, from q to CCppq.
For 0110, from NEpq to NKCpqCqp to NNCCpqNCqp to CCpqNCqp
For 0111, Apq to CNpq
For 1000, KNpNq to NCNpNNq to NCNpq to DCNpqCNpq to CCNpqNCNpq
For 1001, from Epq to KCpqCqp to NCCpqNCqp to DCCpqNCqpCCpqNCqp to CCCpqNCqpNCCpqNCqp
For 1010, from Nq to CCppNq
For 1011, from NKNpq to NNCNpNq to CNpNq or Cqp
For 1100, from Np to CCqqNp
For 1101, Cpq
For 1110, NKpq to NNCpNq to CpNq
For 1111, Cpp.
Monday, September 26, 2011
With Conditional Proof You Never Need a Rule of Repetition
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.
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 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.
Subscribe to:
Comments (Atom)