2
$\begingroup$

Hi guys I'm new to sentential logic and here is the problem:

Suppose that there is a truth-functional connective "#", and we only know that (P # (P # P)) is a tautology. Now we are asked to say something, if any, about the truth-table of "#".

The answer given is : The truth-value of (P # P) must be T. I cannot understand this thoroughly. What I have learned about the truth-functional connective is only its definition, which states that the truth-value of the new sentence constructed by it depends only on the truth-value of its components sentence. Then I know if we can write down the truth table for a connectives like "$\neg$", it would be a truth-functional connective since the value of "$\neg$P" depends only on P.

This structure (P # (P # P)) looks a bit complicated for me, and can anyone help me to explain its meaning?

$\endgroup$
2
  • 3
    $\begingroup$ I'm not sure I believe that answer. What if $\#$ is the NAND operator, $P\#Q=\neg(P\land Q)$? Seems to me that $P\#(P\#P)$ is a tautology, because $T\#(T\#T)=T\#F=T$ and $F\#(F\#F)=F\#T=T$ but $P\#P$ is not a tautology because $T\#T=F.$ Or did I completely misunderstand the problem? $\endgroup$ – bof Jan 10 '17 at 4:08
  • $\begingroup$ Maybe provide a name and page number of the textbook the problem is from? Your question appears to be lacking some context; or at least the redundant context a human often needs to understand a question. $\endgroup$ – user400188 Jan 10 '17 at 9:28
4
$\begingroup$

Once you know the definition of $\#$, you evaluate something like $(P \# (P \# P))$ just like other mathematical statements: first evaluate the inside $(P \# P)$, and once you know what that is (say, $(P\#P)$ evaluates to $Q$), then evaluate $(P \# Q)$.

For example, suppose # is defined by the following truth table:

\begin{array}{c|c|c} P & Q & (P \# Q) \\ \hline T & T & F \\ T & F & T \\ F & T & T \\ F & F & T \\ \end{array}

Then we can work out $(P \# (P \# P))$ as follows:

\begin{array}{c|c|c} P & (P \# P) & (P \# (P \# P))\\ \hline T & F & T \\ F & T & T \\ \end{array}

And so now we see that $(P \# (P \# P))$ is a tautology ... meaning that $(P \# (P \# P))$ can be a tautology without $(P \# P)$ being true. Indeed, I just defined the $\#$ as the NAND which was already pointed out to be a counterexample to the claim the book apparently makes.

OK, so is there maybe something else that we can say about the definition of $\#$? Let's consider all of the 16 possible definitions of $\#$:

\begin{array}{c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c} P & Q & \#_1 & \#_2 & \#_3 & \#_4 & \#_5 & \#_6 & \#_7 & \#_8 & \#_9 & \#_{10} & \#_{11} & \#_{12} & \#_{13} & \#_{14} & \#_{15} & \#_{16}\\ \hline T & T & T & T & T & T & T & T & T & T & F & F & F & F & F & F & F & F\\ T & F & T & T & T & T & F & F & F & F & T & T & T & T & F & F & F & F\\ F & T & T & T & F & F & T & T & F & F & T & T & F & F & T & T & F & F\\ F & F & T & F & T & F & T & F & T & F & T & F & T & F & T & F & T & F\\ \end{array}

And now let's evaluate $\varphi_i=(P \#_i (P \#_i P))$ for each of these 16 possible definitions (I'll flip the table so I have some more room):

\begin{array}{c|c|c} \# & P = T & P = F\\ \#_1 & (T \#_1 (T \#_1 T)) = (T \#_1 T) = T & (F \#_1 (F \#_1 F)) = (F \#_1 T) = T\\ \#_2 & (T \#_2 (T \#_2 T)) = (T \#_2 T) = T & (F \#_2 (F \#_2 F)) = (F \#_2 F) = F\\ \#_3 & (T \#_3 (T \#_3 T)) = (T \#_3 T) = T & (F \#_3 (F \#_3 F)) = (F \#_3 T) = F\\ \#_4 & (T \#_4 (T \#_4 T)) = (T \#_4 T) = T & (F \#_4 (F \#_4 F)) = (F \#_4 F) = F\\ \#_5 & (T \#_5 (T \#_5 T)) = (T \#_5 T) = T & (F \#_5 (F \#_5 F)) = (F \#_5 T) = T\\ \#_6 & (T \#_6 (T \#_6 T)) = (T \#_6 T) = T & (F \#_6 (F \#_6 F)) = (F \#_6 F) = F\\ \#_7 & (T \#_7 (T \#_7 T)) = (T \#_7 T) = T & (F \#_7 (F \#_7 F)) = (F \#_7 T) = F\\ \#_8 & (T \#_8 (T \#_8 T)) = (T \#_8 T) = T & (F \#_8 (F \#_8 F)) = (F \#_8 F) = F\\ \#_9 & (T \#_9 (T \#_9 T)) = (T \#_9 F) = T & (F \#_9 (F \#_9 F)) = (F \#_9 T) = T\\ \#_{10} & (T \#_{10} (T \#_{10} T)) = (T \#_{10} F) = T & (F \#_{10} (F \#_{10} F)) = (F \#_{10} F) = F\\ \#_{11} & (T \#_{11} (T \#_{11} T)) = (T \#_{11} F) = T & (F \#_{11} (F \#_{11} F)) = (F \#_{11} T) = F\\ \#_{12} & (T \#_{12} (T \#_{12} T)) = (T \#_{12} F) = T & (F \#_{12} (F \#_{12} F)) = (F \#_{12} F) = F\\ \#_{13} & (T \#_{13} (T \#_{13} T)) = (T \#_{13} F) = F & (F \#_{13} (F \#_{13} F)) = (F \#_{13} T) = T\\ \#_{14} & (T \#_{14} (T \#_{14} T)) = (T \#_{14} F) = F & (F \#_{14} (F \#_{14} F)) = (F \#_{14} F) = F\\ \#_{15} & (T \#_{15} (T \#_{15} T)) = (T \#_{15} F) = F & (F \#_{15} (F \#_{15} F)) = (F \#_{15} T) = F\\ \#_{16} & (T \#_{16} (T \#_{16} T)) = (T \#_{16} F) = F & (F \#_{16} (F \#_{16} F)) = (F \#_{16} F) = F\\ \end{array}

So, we see that $(P \# (P \# P))$ is a tautology for $\#_1$, $\#_5$, and $\#_9$. What do these definitions have in common? Well, one thing to note is that for all of them it holds that $(P \# Q)$ is true whenever $P$ is false. And that, I think, is pretty much the most interesting thing you can really point out for this problem.

$\endgroup$
1
$\begingroup$

To say that $P\#(P\#P)$ is a tautology means that $F\#(F\#F)=T$ and $T\#(T\#T)=T.$

Note that $F\#F=F$ implies $F\#(F\#F)=F\#F=F.$ Thus, in order for $F\#(F\#F)=T$ to hold, we must have $F\#F=T$ and $F\#T=T.$

$T\#(T\#T)=T$ holds if either $T\#T=T$ (and we don't care about $T\#F$) or else $T\#T=F$ and $T\#F=T.$

So there are three possibilities for the connective $\#$: $$P\#Q=T$$ or $$P\#Q=P\rightarrow Q$$ or $$P\#Q=\neg(P\land Q).$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.