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.

No comments:

Post a Comment