Module 7 : Discrete Mathematics
701 : Logic & Truth Tables
O B J E C T I V E
We're going to use Maple to create truth tables for logical expressions. To do this we are going to define some custom built functions.
S E T U P
In this project we will use the following command packages. Type and execute this line before begining the project below. If you re-enter the worksheet for this project, be sure to re-execute this statement before jumping to any point in the worksheet.
> restart;; with(plots):
Warning, the name changecoords has been redefined
___________________________________________________________________________________
A. Propositions and Tables
These will be the logical propositions. They are essential binary valued functions which will help generate the full range of possible coombinations of true and false in our truth tables.
Here is table of all of the possible permutgations of values for p, g, r, and s
A := array( [[ p(k), q(k), r(k), s(k)] $ k = 0..15] );
> p := x -> irem(x, 2):
> q := x -> irem( iquo(x, 2),2 ):
> r := x -> irem( iquo(x, 4),2 ):
> s := x -> irem( iquo(x, 8),2 ):
We are using number for logical value - 0 for false and 1 for true. In this way we create a binary table which is equivalent to a truth table. The first column has the values of p, the second column has the values of q, and so forth. Note that each row has a unique pattern of 0's and 1's that is not exactly the same as any other row.
> A := array( [[ p(k), q(k), r(k), s(k)] $ k = 0..15]);
With numbers we can see the patterns easier and its also easier to use numeric functions to compute the result. If you would like to see a customary truth table you can copy and paste the following instruction after each binary table is created.
> Truth_Table := A: for i from 1 to linalg[rowdim](A) do for j from 1 to linalg[coldim](A) do if( A[i,j] =1) then Truth_Table[i,j] := 'True'; else Truth_Table[i,j] := 'False'; fi; od; od; evalm(Truth_Table);
This will create a table with "True" and "False" in place of 0's and 1's. If you prefer to see "T" and "F", you can change True to T and False to F in the commands above. For the remainder of this project we will create binary tables. Again, you can copy and paste the commands above after the creation of any binary table below to convert it to a true Truth Table.
B. Negations and Connetors
We will also define these special functions to perform logical operations. Make sure to capitalize these names.
> NOT := x -> irem ( x + 1, 2):
> AND := (x,y) -> irem ( x*y, 2):
> OR := (x,y) -> max( x, y):
> XOR := (x,y) -> irem( x+ y,2):
The negation operator, NOT, converts a logical expression to its opposite : true to false, and false to true. Here is a table showing p, q, not(p), and not(q).
Note that the first and third columns are opposite and so are the second and the fourth columns.
> A := array( [[p(k), q(k), NOT(p(k)), NOT(q(k)) ] $ k = 0..3] );
The connectives AND, OR, and XOR combine two logical propositions in various ways.
Note that we are converting these logical statements into a functioin like notatioin to evaluate in the truth tables.
AND : p and q = AND(p, q) is true only if both p and q are true
OR : p or q = OR(p,q) is true if either p or q or both are true.
Exclusive Or : p xor q = XOR(p, q) is true only if p or q but not both are true
Lets see what the truth table looks like for these three connectives
The first column has the values of p. The second column has the values of q. The next columns have the values of (p and q), (p or q) , and (p xor q).
>
> A := array( [[p(k), q(k), AND(p(k),q(k)), OR(p(k)),XOR(p(k), q(k)) ] $ k = 0..3] );
C. Using Truth Table To Test Logical Equivalencies
One of the main values of truth tables is to test if two logical statements are equivalent
Lets test the proposition : not( p or q) = not(p) and not(q). We convert the left and right sides of this equation into the function notation we defined above
Since the two columns are exactly the same, the proposition is true. This is the abbreviated from of the truth table just showing the final results.
> A := array( [[ NOT( OR(p(k), q(k) ),AND( NOT(p(k)), NOT(q(k)) ) )] $ k = 0..3] );
You can also include the original propositions and intermediate steps. This makes it easier to see everything which contributes to the final results.
The columns are p, q, (p or q), not( p or q), not(p) , and not(p)and not(q). To test the equivalency note that the 4th and 8th columns are identical.
> A := array( [[p(k), q(k), OR(p(k), q(k)), NOT( OR(p(k), q(k) )), NOT(p(k)), NOT(q(k)), AND( NOT(p(k)), NOT(q(k))) ] $ k = 0..3] );
D. Using Truth Tables To Test Logical Implications
An implication is written either in words : if p then q, or symbolically, p -> q. A biconditional is written p if and only if q, or p <-> q. We can define an implication and biconditional function.
> IF_THEN := (x,y) -> OR (NOT(x), y):
> IF_ONLYIF := (x,y) -> NOT( XOR(x,y) ):
We can create a truth table for the implication
> A := array( [ [p(k), q(k), IF_THEN( p(k), q(k)) ] $ k = 0..3] );
How does the converse (if q then p) compare to the original implication (if p then q)? Are they the logically equivalent?
You can see they are different! This means they are not logically equivalent.
> A := array( [[ IF_THEN( p(k), q(k) ), IF_THEN( q(k), p(k)) ] $ k = 0..3] );
How does the contrapositive (if not(a) then not(p)) compare to the origival implication? Are they the equivalent?
These are logically the same.
> A := array( [[ IF_THEN( p(k), q(k) ), IF_THEN( q(k), NOT(p(k))) ] $ k = 0..3] );
E. Maple's Built - In Logic Functions
Maple also has logic features built in which allow us to test the validity of logical equations directly.
Here we use logical functions, and define two logical statements A and B. evalb() is used to evaluate an expression as a Boolean.
> A := not(p or q);
> B := not(p) and not(q);
> evalb(A = B);
The evalb() command is used to test if the two statements are equivalent logically. Here are two more examples from above.
> A := not( p or q);
> B := not( p) and not( q);
> evalb(A=B);
> A := p or not(q);
> B := not(p) and q;
> A := ( a and b) or ( c and d);
> B := ( a or b) and ( c or d);
F. Built - In Logic Functions
Above, when we considered logical expressions, we are not assuming that the propositions p and q have any particular values. In fact we want to make sure that two statements using p and q are the same for all combinations of values of p and q. In other cases, we might have propositions which are assigned values and want to be able to work with them. You could make an analogy to algebra where you might work with variables wuch as x and y without having any particular value, while at other times you might need to plug in particular values for x and y,
We can define variables to have logical values such as true or false.
> a := true; b:= false;
This can also be done in an implied way.
In this case, 5 is not greater than 9, so a is false, but 5 is indeed greater than 1, so b is true.
> a := (5 > 9); b:= (5 > 1);
We can evaluate three boolean variables using the evalb command.
> evalb(a);
> evalb(b);
We can also evaluate boolean expressions. We can use the same operators and connectives ( not, or, and).
The evalb command evaluates the expression as a boolean (logical) expression and 'computes' a value of true or false
.
> evalb( not(a));
> evalf( a or b);
> evalf(a and b);
