# About some patterns I've noticed in truth functions

https://en.wikipedia.org/wiki/Truth_function

I was looking at the 16 truth functions to see if I notice any patterns. I've found:

1. There are 1 set with 4 ordered pairs, 4 sets with 3 ordered pairs, 6 sets with 2 ordered pairs, 4 sets with 1 ordered pair, and 1 set with 0 ordered pair.

2. If looked at as relations between P and Q, half of them are symmetric and the other half are asymmetric.

3. Only the Proposition Q, the Biconditional, the Exclusive Disjunction, and the Negation of Q are total functions from P to Q.

4. Proposition Q entails the Material Implication from P to Q. Proposition Q has less ordered pairs, 2, than the Material Implication from P to Q, 3. This seems analogous to being a member of a subset entailing being a member of that set's superset.

Is there anything wrong with the statements above? Any insight from these that are interesting?

Also, is there something non-obviously special about the Material Implication function that makes it analogous to Logical Entailment?

• by "assymetric' do you mean that $r_{i,j}=$ opposite of $r(j,i)$ ; what about $r_{i,i}$ ? Jun 4 at 18:01

All of your observations are totally correct, but some of them are phrased in confusing ways. Let's look at them one by one.

1. There are 1 set with 4 ordered pairs, 4 sets with 3 ordered pairs, 6 sets with 2 ordered pairs, 4 sets with 1 ordered pair, and 1 set with 0 ordered pair.

It took me a minute to realize what you were trying to say here. I think a better way to phrase your observation is as follows: "One of these functions yields 'true' on all 4 possible inputs. Four of them yield 'true' on 3 of the inputs. Six of them yield 'true' on 2 of the inputs. Four of them yield 'true' on 1 of the inputs. One of them yields 'true' on none of the inputs."

We can summarize your observation with this formula: the number of truth functions that yield "true" on precisely $$k$$ inputs is $${4 \choose k} = \frac{4!}{k!(4-k)!}$$. The reason that the binomial coefficient comes into play is that specifying a truth function consists of choosing which of the four possible inputs to yield "true" on.

Here's a challenge for you: see if you can come up with a formula that gives the number of ternary (or $$n$$-ary) truth functions that yield "true" on precisely $$k$$ inputs.

1. If looked at as relations between P and Q, half of them are symmetric and the other half are asymmetric.

A binary truth function is symmetric if and only if it yields the same thing on $$(T,F)$$ as it does on $$(F,T)$$, since these are the only two inputs where switching the truth vales of $$P$$ and $$Q$$ changes anything. There are just as many truth functions that yield the same result on these inputs as there are that yield different results on these inputs.

Again, I challenge you to generalize your observation to the ternary or $$n$$-ary case. How many ternary truth functions are symmetric on $$P$$ and $$Q$$? How many ternary truth functions are symmetric on $$P$$, $$Q$$, and $$R$$? In general, how many $$n$$-ary truth functions are symmetric on the first $$k$$ arguments?

1. Only the Proposition Q, the Biconditional, the Exclusive Disjunction, and the Negation of Q are total functions from P to Q.

This one also took me a minute to understand. You can rephrase it as follows "The Proposition $$Q$$, the Biconditional, the Exclusive Disjunction, and the Negation of $$Q$$ are the only truth functions that can yield either true or false regardless of the value of $$P$$."

A truth function $$f$$ has this property if and only if $$f(P, Q) = \neg f(P, \neg Q)$$ for all possible values of $$P$$ and $$Q$$, where $$\neg x$$ denotes the negation of $$x$$. If we assume that a function has this property, we only have to specify its values at $$(T,T)$$ and $$(F,T)$$ to determine its values at all four inputs. Since there are $$2 \times 2 = 4$$ ways to specify the values of a two-valued function at two inputs, there are precisely four functions with this property.

Once again, I challenge you to generalize your observation to the ternary and $$n$$-ary cases.

1. Proposition Q entails the Material Implication from P to Q. Proposition Q has less ordered pairs, 2, than the Material Implication from P to Q, 3. This seems analogous to being a member of a subset entailing being a member of that set's superset.

If $$Q$$ is true, then every proposition, including $$P$$, implies $$Q$$. And yes, the set of inputs that make Proposition $$Q$$ true is a subset of the set of inputs that make Material Implication true.

Also, is there something non-obviously special about the Material Implication function that makes it analogous to Logical Entailment?

There are two ways to think about these 16 truth functions. On one hand, you can think of them as purely algebraic objects without any deeper meaning—they are just mathematical functions that take in two arguments and return either a $$0$$ or a $$1$$. On the other hand, you can think of them as linguistic/semantic objects endowed with meaning—they are ways to take two propositions that make statements about the universe and combine them into a new proposition.