Logic Calculation part 1

Mathcalc8 had developed a logic module that can perform 'Propositional Logic' verfication. There is two posts on the subject of logic. In part one of this post, we will show you the idea that lead to the development of the logic module and we will convince you that logic can be reduced to a set of normal arithmetic/multiplication calculation. All calculations in this post are done by Mathcalc8's list arithmetic and multiplication. In part two, we would demonstrate the usage of logic module. There are five basic elements for propositional logic :

1. Element 1 : it represents 'truth' verbally or number 1 numerically.
2. Element 0 : it represents 'false' verbally or number 0 numerically.
3. Logic operation ~ : meaning 'NOT' or negation.
4. Logic operation Λ : meaning 'AND'.
5. Logic operation V : meaning 'OR'.

All grammatically correct propositional logic formula are called well-formed formula (wff). The simplest wff is just a symbol.
Below is an valid wff :

X

The symbol 'X' is a shortcut for a sentence or statement. For example, 'X' can represents the sentence 'Peter is a man' or it can represents 'Tomorrow is Monday' etc. For simplicity, we will just call this kind of single symbol a logic variable. If an wff or a logic variable is given a value, it can only be either 0 or 1.
In order to use Mathcalc8 to do logic calculation, we need to convert the logic operations ~, Λ and V into their arithmetic formulation. First, we begin with logic operation ~ :
Below is the truth table for logic operation ~. x is a logic variable :

x	~x
0	1
1	0

There are two possible values for x, 0 and 1. The truth table list all the possible inputs and their outcomes.
The arithmetic formula that represent this operation is :

~x = 1 - x

For the symbol '=' here in this equation, we means on all possible combination of logical states, both the right-handed and left-handed side formula gave same logical values. It can be easily verified that ~x and 1-x got the same values for either x is 0 or x is 1. When x is 0, ~x gives 1, 1-x gives 1. When x is 1, ~x gives 0 and 1-x gives 0 also. The minis sign '-' here acted as standard arithmetic operation.
Next, we will convert the logic operation 'Λ' into an arithmetic formula. Below is the truth table of Λ :

x	y	x Λ y
0	0	0
0	1	0
1	0	0
1	1	1

Here, two logic variables x and y are used, so there are four possible logical combination (00, 01, 10, 11) to be evaluated. From the table, it can be seen that the operation is just bear the same result as obtained from arithmetic multiplication between x and y :

x Λ y = xy

To verify this :

Input 1 : xx=(0,0,1,1)
 

Input 2 : y=(0,1,0,1)
 

Input 3 : xx*y
Ans. 0, 0, 0, 1
 

The next operation is 'V'. Its truth table is :

x	y	x V y
0	0	0
0	1	1
1	0	1
1	1	1

It can be seen that the formula for this operation is :

x V y = x + y - xy

There may exist other formula that give same result but we think the above formula is the simplest.
To verify this :

Input 4 : xx+y-xx*y
Ans. 0, 1, 1, 1
 

Now we had converted all the basic operations ~, Λ and V into arithmetic formula. This means that from now on, we can try to use arithmetic formula to replace all wffs and do verification as we do normal arithmetic calculation ! Actually, we found that the method worked quite well.
Let's try several useful basic rules of propositional logic :

1. x Λ x = x

Input 5 : xx=(0,1)
 

Input 6 : xx*xx
Ans. 0, 1
 

So, this is equal to xx. Or in arithmetic form :

x Λ x = xx = x

This means that when we multiply x by x, it gives x. In general arithmetic calculation, this rule is wrong but it is true when x only takes 0 or 1. This rule gives us a powerful simplification when we do more complicated calculation afterwards.

2. ~x Λ x = 0

Input 7 : (1-xx)*xx
Ans. 0, 0
 

By arithmetic calculation :

~x Λ x = (1 - x)x = x - xx = x - x = 0

3. ~~x = x
By arithmetic calculation :

 
~~x = 1-(1-x) = 1 - 1 + x = x

Before we proceed further, we need to introduce a new logic operation '→'. This logic operation can be constructed from the basic operators ~, Λ and V. When we use the phase, if x, then y, it is using this logic operation, meaning x → y. Since the if-then phase of reasoning is the most basic thinking related to our daily life, '→' is indeed a very important logic operation.
Below is the truth table represents '→' :

x	y	x → y
0	0	1
0	1	1
1	0	0
1	1	1

To construct a logical formula, let us focus on the last column that gives value of 1. For example, on the first row, when x = 0 and y = 0, x → y gives 1. For this row, we can write a logic term to represents this row's result : ~x Λ ~y. This term, called minterm, is equal to 1 only when x = 0 and y = 0. So, a general logical formula for x → y can be constructed by using 'OR' to gather all these minterms. Below is the resulting formula :

x → y = (~x Λ ~y) V (~x Λ y) V (x Λ y)

When x = 0 and y = 0, the first minterm gives 1 and because the formula uses 'OR' operation, so no matter what the values of other minterms are, the formula would gives 1. This then guarantee the first row gives 1. The same is true for the second and fourth row since we all includes its minterms. The only one missing is the third row. So, whenever x = 1 and y = 0, since all other minterms gives 0, the formula resulted in 0.
Now, we try to convert it to an arithmetic formula :

(1-x)(1-y) V (1-x)y V xy = (1-x)(1-y) V ((1-x)y + xy - (1-x)yxy)
                         = (1-x)(1-y) V ((1-x)y + xy)
                         = (1-x)(1-y) V y
                         = (1-x)(1-y) + y - (1-x)(1-y)y
                         = (1-x)(1-y) + y
                         = 1-x-y+xy + y
                         = 1-x+xy

Therefore the simplified arithmetic formula is :

x → y = 1 - x + xy

There is a similar method that can be used to find a logic formula for a given truth table. This time, we look at the last column that gives value of 0 instead of 1. For example, on the third row, when x = 1 and y = 0, x → y gives 0. For this row, we can write a logic term to represents this row's result : ~x V y. This term, called maxterm, is equal to 0 only when x = 1 and y = 0. So, a general logical formula for x → y can be constructed by using 'AND' instead of 'OR' to gather all these maxterms.
Since there is only one maxterm for x → y :

x → y = ~x V y

It can be easily showed that this gives the same arithmetic formula as before :

~x V y = (1 - x) V y
       = 1 - x + y - (1 - x)y
       = 1 - x + y - y + xy
       = 1 - x + xy

To verify this by Mathcalc8 :

Input 8 : xx=(0,0,1,1)
 

Input 9 : y=(0,1,0,1)
 

Input 10 : 1-xx+xx*y
Ans. 1, 1, 0, 1
 

Now, as we had got the formula for → relation, we can use the formula to prove some logical tautolgy (ie. a logical formula that is alway true) . Below is an example :

Verify that : (x → y) → (~y → ~x) is a tautolgy

To verify the above logical formula to be true. The calculation is shown as follows :

(x → y) → (~y → ~x) 

= 1 - (x → y) + (x → y)*(~y → ~x)
= 1 - (1 - x + xy) + (1 - x + xy)*(1 - (1 - y) + (1 - y)*(1 - x))
= x - xy + (1 - x + xy)*(1 - x + xy)
= x - xy + (1 - x + xy - x + x - xy + xy - xy + xy)
= 1 

To summarise : We had developed an arithmetic/multiplication formulation to logic. This formulation is not the same as Boolean algebra. In Boolean algebra, '+' is defined as logic operation 'OR' and '*' is defined as 'AND'.