The Truth Table

Background

As we all know, we use a logical operator in a WHERE clause. It means each of us are consciously or unconsciously familiar with propositional logic. In propositional logic, we only have two values for each variable: True or False (1 or 0), therefore, any logic statement can be analyzed using a table which lists all possible values of the variable: a Truth Table.

Since each variable can take only two values, a statement with "n" variables requires a table with 2^n rows which is difficult to construct when the number of variables are more than 4.

Truth Table

 
create PROC Usp_BuildTruthTable ( @variables xml,
                                 @expressions xml)
AS
DECLARE @docHandle int,
        @SELECT varchar(8000),
        @FROM  varchar(8000),
	    @SQL nvarchar(4000)
EXEC sp_xml_preparedocument @docHandle OUTPUT, @variables

SELECT @FROM=isnull( @FROM +char(13)
     +' cross join  (select cast(0 as bit)union all 
	  select cast(1 as bit) ) as '+value+'('+value+')'+char(13) 
	  ,  ' (select cast(0 as bit) union all select  cast( 1 as bit) ) as' 
	  +value+'('+value+')')
FROM OPENXML(@docHandle, N'/Variables/var') 
with (value  char(1)    )
EXEC sp_xml_removedocument @docHandle 

--constructing the Select Clause     
EXEC sp_xml_preparedocument @docHandle OUTPUT, @expressions

SELECT       @SELECT=isnull(@SELECT+' ,['+col+']='+col, '['+col+']='+col)
 FROM OPENXML(@docHandle, N'/expressions/exp') 
WITH (col VARCHAR(8000) '@val')  

    SET @SQL='select *,'+@SELECT+ '  from '+char(13) +@FROM
   EXEC( @SQL)
EXEC sp_xml_removedocument @docHandle 

As you can see it accepts two parameters which are declared as XML data type that is new to SQL Server 2005. If you are not familiar with the XML procedure which I used in the Usp_BuildTruthTable, you can refer to BOL documentations.

The main core of stored procedure is the statement "(select cast(0 as bit)union all select cast(1 as bit) )", which assigns all the possible values to the variables and the CROSS JOIN that is used to produce all possible combinations of variables. The @SELECT will evaluate the expression, and the logic behind this is simple: SQL Server has a bitwise operator, so it can evaluate bitwise expressions. This is the reason that I converted zero and one to the bit data type. There are 4 bitwise operators in SQL SERVER:

Now I want to show you how to use these bitwise operators in logical connectives:

You have to pass variables and expressions with the following format:

<Variables>
<var value="VAR1" />
.
.
.
<var value=" VARn" /> 
</Variables>

<expressions>
<exp val="EXP1" />
.
.
.
<exp val="EXPn" />
</expressions>

Note: you have to use "& amp;" (remove th space between the & and amp) instead of & or else you get the following error:

.Net SqlClient Data Provider: Msg 9421, Level 16, State 1, Procedure Usp_BuildTruthTable, 
Line 0
XML parsing: line 3, character 15, illegal name character

To test the stored procedure, run the following snippet:

exec usp_BuildTruthTable '<Variables> 
<var value="a" /> 
<var value="b" /> 
</Variables>'  ,
'<expressions>
<exp val="~a" />
 <exp val="a & amp; b" />
<exp val="(a | b)" />
<exp val="(a ^ b)" />
<exp val="(~a | b)" />
<exp val="(~a | b)& amp; (~b | a)" />
</expressions>   '

Note: Remove the space between the & and amp in the code.

Here is the result:

a     b     ~a    a & b (a | b) (a ^ b) (~a |b) (~a | b)& (~b | a)
----- ----- ----- ----- ------- ------- ------- ------------------
0     0     1     0     0       0       1       1
0     1     1     0     1       1       1       0
1     0     0     0     1       1       0       0
1     1     0     1     1       0       1       1

Let's check a complicated expression:

((P imp Q) and (Q imp R)) imp (P imp R) == ~ ((~P |Q) & (~Q | R)) | (~P | R)

exec usp_BuildTruthTable 
'<Variables>
<var value="P" /> 
<var value="Q" /> 
<var value="R" /> 
</Variables>' ,
'<expressions>
<exp val="~((~p |Q) & amp;  (~Q |R)) | (~P|R)" />
</expressions>   '

And here is the result:

P     Q     R     ~((~p |Q) &  (~Q |R)) | (~P|R)
----- ----- ----- ------------------------------
0     0     0     1
0     1     0     1
1     0     0     1
1     1     0     1
0     0     1     1
0     1     1     1
1     0     1     1
1     1     1     1