I am reading over my notes and I can not understand how to show set of connectives are adequate. I understand that in order for a set to be adequate, we must be able to express them in terms of the standard connectives.
for example, we want to show { –> , #} is adequate defined by the truth table :
I want to express not p in terms of p#q but dont know where to start
here is the table given as the answer :
which shows not p = p –> (p#p). I am not sure how they got the p#p result on the table, if P is 0 from table 1 then p#q can be either 1 or 0 right? how is it that it is 0 on table 2 ?
Best Answer
You have it the wrong way around. A set of connectives is adequate if you can express all truth tables using them. The standard connectives are adequate, so it suffices to show that all standard connectives can be written in terms of the connectives in the question.
As EuYu pointed out, I cannot use $0$, so instead we note that $p\#p$ is equivalent to false for all value assignments. Hence in the following, replace $0$ by $p\#p$.
We see that $\lnot p$ is equivalent to $p \to 0$.
We see that $p \lor q$ is equivalent to $(p \to 0) \to q$.
We see that $p \land q $ is equivalent to $ (p \to (q \to 0)) \to 0$.