## Shaheen Islam

### Abstract Truth Functions

Truth Functions and Truth Functional

Take a set with two elements. The elements have to be distinct and that’s all. Usually these two elements are designated by T and F, sometimes by 0 and 1, or by any other marks you prefer (provided that the marks are of distinct types). We shall designate the very set by 2, i.e. in terms of set language 2 = {T, F} 1. How many functions are there from 2 to itself 2 ? We can think of four such functions 3.

As the outputs are always same the first two can be called constant functions. The third one is known as the identity function as its inputs and outputs are always identical. We can call the fourth abstract negation.

How many functions are there from 2 × 2 × ... × 2 (till n times) to 2 (i.e. itself) ? 4 The answer is that there are 22 n , or more precisely 22n ) , of them 5. If the functions are binary 6 then there are 16 (= 22 2) such functions. Here are 5 of them

p

q

p &2 q

p2 q

p 2 q

p 2 q

p 2 q

T

T

T

T

T

F

F

T

F

F

T

F

T

F

F

T

F

T

T

T

F

F

F

F

F

T

T

T

Exercise 1: Find out the other 11 binary functions.

Let us call them abstract truth functions (or just truth functions for short); we therefore write a little subscript 2 to remember that. The reason for calling them so is that they are not exactly sentential functions, rather they are just two-valued functions. Though p, q ... are sentential variables, our concern is regarding the truth-values of the sentences rather than the sentences themselves (or the meaning of the sentences)1. What is important with the truth-values is just the distinction between any two items. But the word “truth function” has a relevance with the notion of truth functionality. Let us take another function Tv which gives you the truth-value of a sentence as an output when the very sentence is taken as the input of the function. So if A is sentence then

Tv (A) will be either true (T ) or false (F). Now take a sentential connective say

. . . and .. .. .. or in short . . . & .. .. .. 2 . If A and B are two sentences then interestingly we get the following equation

Tv (A&B) = Tv (A)&2Tv (B)

Intuitively, what all this means is that the truth value of the whole expression “A&B” can be worked out from the truth values of its (immediate) components “A” and “B”. The connective is thus known as truth-functional 3. If you cannot work out the truth-value of a compound from the truth values of the component(s) then the main connective of the very expression becomes non-truth-functional. A very good test to find out whether a connective is non-truth-functional is to find out an instance when with same truth values of the component(s) the compound can have any of the truth-values. Such instance shows you that the truth-value(s) of the component(s) are not enough (or even irrelevant) to determine the truth-value of the compound. To know the truth-status of the compound we then need more info in addition to (or quite different info than) that pertaining to the truth-status of the component(s). On the other hand if the connective is truth-functional than you must be able to get a (characteristic) truth table corresponding to that connective .

The beauty of truth-functions (or, if you prefer, of “binary logic”) is that with only few truth-functions you can define any other truth-functions of any arity. For example p q means (i.e. can be defined by) ̴pq and p & q means ̴( ̴p̴q) 4. Take a truth functional compound F ( p1, p2 ,... pn ) . You will then get a characteristic truth table corresponding to that. If the compound is truth functionally false (i.e. a “contradiction” ) then you can define it as follows
F ( p1, p2 ,... pn ) =def p1& ̴p1& p2 & ...& pn 5. But if it is not truth functionally false then in the truth table there will be rows with T under the main connective. Say these rows are R1, R2, ..., Rm (m 2n ). Corresponding to each row Ri, take the compound

*Ri =def α1& α2 & ...& αn so that for each αj (1 j n)
pj if the truth value of pj is T

αj=

̴pj if the truth value of pj is F

For example say Rk ,the k th row (k 2n ) is like this

main connective

p1 p2 p3 p4 ... pn F ( p1, p2 ,... pn )
. . . . ... . .
T F F T T
T the value is here T

. . . . ... . .

*Rk is then p1 & ̴p2& ̴p3& p4& ... & pn
We now define

F ( p1, p2 ,... pn ) =def *R1 *R2 ...*Rn 6

As *Ri is defined only in terms of “ ̴” and “ & F ( p1, p2 ,... pn ) is defined only in terms of ̴”, “&”, and “” . Thus any truth functional connective can be defined in terms of ̴”, “&”, and “” . Now again “&”can be defined in terms of of “ ̴” and “” or “”can be defined in terms of of “ ̴” and “&” . So again any truth functional sentence can be defined either by ̴” and “” or by ̴” and “&” . Interestingly any of these three expressions can be defined only by the connectives

Neither . . . nor .. .. ..” ( or “. . . .. .. ..” for short) or “Not both . . . and .. .. ..” ( or “. . . .. .. ..” for short). See these definitions

̴p =def pp =def pp
p
& q =def ( pp)(qq ) =def (pq)(pq)

p q =def ( pq)(pq ) =def (pp)(qq)

Thus any truth functional compound can have a monolithic definition either exclusively in terms of “” (down stroke) or exclusively in terms of “” (up stroke).

Exercise 2: Verify the above three definitions in terms of the truth-tables of the corresponding equivalences.

Exercise 3: Define material conditional in terms of any of these strokes. (Hint: First define material definition in terms of either “ ̴” and “&” or in terms of “ ̴” and “” and then define the outcome by strokes)

Exercise 4: Define the strokes in terms of “ ̴”, “&”, or “”(Hint: p 40 of the text).

1 At the very outset we can take the variables p, q ... just as truth-value holders rather than sentence holders.

2 Note we are not using the little subscript 2 ” now, since we are talking about the very sentential connective rather than an abstract truth function. We are going for precision.

3 Generally, if F ( p1,p2 ,..., pn ) is an n-ary sentential connective and if we get an n-ary truth function F2 so that

Tv (F ( p1,p2 ,... pn ) ) = F2 (Tv ( p1), Tv (p2), ...,(Tv (pn ) ) then F is truth-functional. Following our text we can call F2 as the characteristic truth function of F. Thus &2 is the characteristic truth function of &. Such subtle distinction between a truth-functional connective and its characteristic truth function is often ignored in the literature.

4 We are now back to the usual practice, ignoring the difference between a connective and its characteristic truth-function and the difference between a sentence and its truth-value.

5 We are ignoring the strict well-formed-formula rules , which requires that there should be proper grouping in terms of parentheses

6 The two expressions F ( p1, p2 ,... pn ) and *R1 *R2 ...*Rn are equivalent. The latter is known as disjunctive normal form.