Originally published by Robert Beisert at fortcollinsprogram.robert-beisert.com

CS 101 – Logic Part 2

For part 1, see CS 101 – Introduction to Logic

Solution to last week’s problem

In our last post, we considered the following problem:

[code language=”c”]

int i=0;
int j=1;
int k=2;
int m=4;

//Example 5

if( m == k * k || i == 1 && j == 1)
printf("What’s the result?");

[/code]

It turns out that boolean (read: computer binary) logic also operates on the Order of Operations.

AND is analogous to * (multiplication), while OR is analogous to + (addition).

Thus, we evaluate the above as

[code language=”c”]

if  (    (i == 1 && j == 1) || (m == k * k)   )

[/code]

There are a few other things we need to know about boolean logic.

XOR: A Complicated Operation

We discussed how XOR is the Either-Or relationship. This relationship can be reduced to a combination of AND and OR relationships in the following way:

a && !b   ||   b && !a

A and not B      OR      B and not A

This is highly significant for hobbyist hardware, but is also useful for formulating proofs.

Truth Tables

The final thing that you absolutely must know about boolean logic is that we can use “truth tables” to better understand our syllogisms. Below are a few classic tables. I apologize for the poor formatting, but WordPress is not excellent for generating tables.

OR

A

!A

B

1 (TRUE)

1 (TRUE)

!B

1 (TRUE)

0 (FALSE)

 

AND

A

!A

B

1 (TRUE)

0 (FALSE)

!B

0 (FALSE)

0 (FALSE)

 

XOR

A

!A

B

0 (FALSE)

1 (TRUE)

!B

1 (TRUE)

0 (FALSE)

 

The premise is simple. You create a table with all the conditions for your test, then you fill in whether it is true or not for each case.

This is very useful to generate a deeper understanding of boolean logic, but starts to become more difficult as the problem set increases.