Logical connectives and truth functions.

Question

Lets take a look on the following sets of logical connectives: $$K_{1}=\{\rightarrow,\equiv\},\ K_{2} = \{\vee, \wedge\} $$

For each logical connective $*\ $ in $\ K_{1}\cup K_{2}$, answer the following question: is there a statement, built only with logical connectives of the other group (the group of which $*$ isn't in) that represents the truth-function of $\ *\ $?

My partial solution:

I have prooved the following: Let A be a logical statement build only from logical connectives in $\{\vee, \wedge\}$, and $\mathcal{AP}=\{p_1,p_2\}$. Let $M$ be the assigning where for every atomic proposition p, $\ M(p)=F$ then $$M\not\models{A}$$

and therefore there is no such logical statement that represents the truth-functions of $\equiv, \rightarrow$.

I was able to find a logical statement A that built only from logical conectives in ${K_1}$ and represents $\wedge$: $$A=({p_1}\rightarrow{p_2})\equiv{p_1}$$

For the last option of representing $\wedge$ i think i should prove the following: Let A be a logical statement build only from logical connectives in $K_{1}$, and $\mathcal{AP}=\{p_1,p_2\}$. Let $M_1, M_2$ be the assignings: $$M_1(p1)=T, M_2(p1)=F$$ $$M_1(p2)=F, M_2(p2)=T$$

Then $$M_1\not\models{A}\ or\ M_2\not\models{A}$$

An answer, or even better, a general way of dealing with this kind of questions will be very helpful.

Thanks.

Answer 1

I outlined a method here. If you have questions about it, please ask!

Also, as you point out "(p1→p2)≡p1" can get used to represent $\land$. Thus in Polish notation {C, E} can represent K. Now, can {C, E} represent A? A has the following truth table, which you can find in my answer to your other question also:

p  q   Apq
0  0   0
0  1   1
1  0   1
1  1   1

Now, can the connectives in {A, K} represent the truth functions in {C, E}?

p  q  Kpq  Apq 
0  0  0    0
0  1  0    1
1  0  0    1
1  1  1    1

Well, we could apply the method I suggested in the other answer. However, notice that K00=0 and A00=0. Consequently, suppose we have an arbitrary formula with just "A", "K" and variables in it. Assign "0" to all variables. It follows that such a formula will equal 0 also. Since E00=1, and C00=1, it follows that neither E, nor C can get represented by {K, A}.

I'll try and clarify that a K-A only formula will equal 0 when all of its variables equal 0 below:

K00=0 and

A00=0

Thus, where X belongs to {K, A}, X00=0. So then

X0X00=X00, since X00=0. Now since we have X00=0 and X0X00=X00, by transitivity of "=", X0X00=0. Or with spaces X 0 X00=X 0 0=0

XX000=X00, since X00=0. Now since we have XX000=X00 and X00=0, by transitivity of "=" it follows that XX000=0. Or with spaces X X00 0=X 0 0=0.

Thus, any formula of length 5 having K, A, and only 0s, equals 0.

A longer formula contains either X0X00 or XX000 within it, and thus wherever X0X00 or XX000 appears, either one (or both) can get replaced by 0. Also, anywhere where X00 appears, it can get replaced by 0. And if you do this long enough, you'll find that any formula will equal 0.