# Logical Constants

Theorems

DeMorgan’s Laws

Derived functions

Thinking ahead Binary arithmetic

Logic Part 2

Or, an expression can consist only of variables like:

y = (x + y) / z

which can be simplified no further, and cannot be evaluated until we have values for x, y, and z.

Logical Constants

In real number algebra, there are certain constants that are of special interest.

Namely, 0 and 1, which are expressed as these commonly used properties:

Axiom of 1 ( 1 is the identity element for multiplication)

Axiom of 0 ( 0 is the identity element for addition)

Multiplication property of zero

An expression can contain a mixture of constants and variables such as

y = 13 / x

or

y = 55 + x

Logical Constants

T (for true) and F (for false) are logical constants.

Logical expressions involving only constants have already been given in the form of truth tables for the basic operations NOT, AND, OR

Are there constants and similar properties in logic ?

yes !!

Logical Constants

Logical Constants (what about mixing logical constants and logical variables)

As with the previous slide, this outcome should be intuitive.

Logical Constants (what about mixing logical constants and logical variables)

Logical Constants (what about mixing logical constants and logical variables)

Logical Constants (what about mixing logical constants and logical variables)

Logical Properties (Laws)

In the study of logic, you will eventually see mention of these laws.

These laws are somewhat philosophical in nature, and even more fundamental that the list of logic laws.

There are three fundamental laws of logic. Suppose P is any indicative sentence, say, “It is raining.”

The law of identity: P is P

The law of non-contradiction: P is not ~P

The law of the excluded middle: Either P or non-P

Three Fundamental Laws of Logic (an aside)

Many books “leave the proof to the reader” , which seems pointless, because part of what the student is trying to learn, is how to prove laws.

So, here are a couple examples.

Logic (proving laws)

Logic (proving laws)

ok. catch your breath and get ready for the big one.

Logic (proving laws)

Logic (proving De Morgan’s laws) (more complicated)

Logic (proving De Morgan’s laws) (more complicated)

Logic (proving De Morgan’s laws) (more complicated)

Logic (proving De Morgan’s laws) (more complicated)

Logic (proving De Morgan’s laws) (more complicated)

Logic (proving De Morgan’s laws) (more complicated)

Logic (proving De Morgan’s laws) (more complicated)

Logic (proving De Morgan’s laws) (more complicated)

Compare column 5 to column 7.

The values in every row do not match, so the equality is not true.

Logic (using truth tables)

Logic (duality)

Logic (duality – a more complicated example)

Most authors tend to use parentheses to be very clear about the intended order of operations.

In the absence of parentheses, the logical precedence will determine the order:

Logic (operator precedence)

Know that it is not possible to negate a compound logical expression without using parentheses.

Logic (operator precedence)

Logic (derived functions)

p 0 0 1 1

+ q + 0 + 1 + 0 + 1

—– —– —– —– —–

0 1 1 10

Reformat addition table so

it looks like truth table

p | q | 1’s column p + q | carry bit p + q |

0 | 0 | 0 | 0 |

0 | 1 | 1 | 0 |

1 | 0 | 1 | 0 |

1 | 1 | 0 | 1 |

The addition table represents the sums shown below.

Bits in top row of table represent bits in augend.

Bits in left column of table represent bits in addend

+ | 0 | 1 |

0 | 0 | 1 |

1 | 1 | 10 |

If you have learned to count and add in the binary number system, you will understand that the following table is the addition table for (single bit) binary addition, where 0 and 1 are the only two digits used in binary.

Thinking ahead

If we equate

0 to False

and

1 to True

can we build two logical expressions that will generate the values in column 3 and 4 of the table ?

There was a reason we formatted the

addition table to look like a truth table.

p | q | 1’s column p + q | carry bit p + q |

0 | 0 | 0 | 0 |

0 | 1 | 1 | 0 |

1 | 0 | 1 | 0 |

1 | 1 | 0 | 1 |

Thinking ahead

Thinking ahead

p | q | 1’s column p + q | carry bit p + q |

0 | 0 | 0 | 0 |

0 | 1 | 1 | 0 |

1 | 0 | 1 | 0 |

1 | 1 | 0 | 1 |

Juxtapose the two tables so it’s easy to see the logical expressions agree with the bits in the addition table.

Thinking ahead

The truth table on the previous slide implements what is called a half adder.

A half adder generates a carry bit, but does not include it into the sum of the augend bit and the addend bit.

A full adder does incorporate the carry bit.

You will see a logic gate implementation of a full adder in the next session.

Thinking ahead (conclusion)

Next: Implementing logic with discrete gates.

Logic The End