How can i determine which two-place truth functions can be represented using a logical statement built out of a subset of two logical connectors in $ \{\rightarrow, \wedge, \vee ,\equiv \}$ ?
for example $\{\rightarrow, \wedge\}$
$\begingroup$
$\endgroup$
2
-
$\begingroup$ Since any formula is made of subformulas, it's enough to verify that you can write $A\to B, A\land B, A\lor B$ and $A\equiv B$ using only $\to$ and $\land$. This can be formalized using induction on the complexity of formulas. $\endgroup$ – Git Gud May 22 '14 at 17:21
-
$\begingroup$ I want to be able to determine exactly which truth function \ truth table out of the $2^2^n$ (for $n=2$) is possible to represent using a logical statement built only from those connectors. $\endgroup$ – dave May 22 '14 at 17:56
Add a comment
|
$\begingroup$
$\endgroup$
6
For any two place truth function X, we can write it's truth table as follows:
p q X(p, q)
0 0 ?1
0 1 ?2
1 0 ?3
1 1 ?4
where, of course, ?1, ?2, ?3, and ?4 belong to {0, 1}. Notice that all wffs of propositional logic can get built up from the variables and the connectives. For example (using Polish notation) the wff CKpqNDrArs can get built up via the sequence (p, q, Kpq, r, r, s, Ars, DrArs, NDrArs, CKpqNDrArs). Thus, we can build up any wff using say two (or 1 or 3 or 4) connectives in this way, and see how their truth tables work and see if the columns of the truth tables end up repeating or if we get new columns. For instance... if we just have implication "C", we can write
p q Cpq CpCpq Cpp Cqp Cqq CqCpq CCpqp CCpqq CCpqCpq
0 0 1 1 1 1 0 0
0 1 1 1 1 0 0 1
1 0 0 0 1 1 1 1
1 1 1 1 1 1 1 1
I've left some blank, since they have duplicate values to something else we already have. I generated this example (by hand) by using (p, q, Cpq) as the initial set and finding all possible substitutions in Cxy from that set. Then leaving only those columns which are not a duplicate of some other column, we can use each wff above the column to see if we get a new column not in our list. Eventually, since the number of possible columns is finite, we can eventually see which truth functions can get represented (and we also could prove that using the set of all formulas above the column, as I used the initial set above, that on the next step we'll only get a column that we already have. Since this procedure can generate all formulas in two variables, it will follow that no other binary truth-function can get generated using just the connectives we've selected).
answered May 22 '14 at 18:28
-
$\begingroup$ "since the number of possible columns is finite" can you explain that? is there a known solutions to this problem? $\endgroup$ – dave May 22 '14 at 20:11
-
$\begingroup$ I understand that i can prove in some cases that some truth-functions cannot be generate, and show one-by-one that the others can be generated. but i thought maybe there are known solutions for those ${4}\choose{2}$ sets of logical connectors, or maybe a better way. $\endgroup$ – dave May 22 '14 at 20:18
-
1$\begingroup$ The column has four entries ?1, ?2, ?3, and ?4. Each of those belong to {0, 1}. Thus, ?1 is either 0 or 1, ?2 is either 0 or 1, ?3 is either 0 or 1, and ?4 is either 0 or 1. So, the column can get represented as a quadruple (?1, ?2, ?3, ?4) and such a quadruple can represent a column. Do you see how we always have a finite set of quadruples when all elements of each quadruple comes from a finite set of elements? If not, do you see how we always have a finite set of quadruples when each element of the quadruple belongs to {0, 1}? $\endgroup$ – Doug Spoonwood May 22 '14 at 20:49
-
$\begingroup$ infinite columns with the same truth table, because there is infinite logical statements... $\endgroup$ – dave May 22 '14 at 20:54
-
$\begingroup$ I agree that we may be able to generate at most 16 functions, but unless i find them all or prove i cant, this procedure is infinite $\endgroup$ – dave May 22 '14 at 20:57
