discrete math
alohaf
m6.pptxLogical 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.
In the algebra of real numbers, expressions can consist solely of constants like:
x =
in which case, x can be immediately evaluated to x = 2.
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
| a | b | a b |
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
| a | b | a b |
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
| p | p |
| T | F |
| F | T |
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
In the case of , we can compare the expression to the truth table, for only the rows where b is T (constantly T). Those rows are highlighted in yellow.
In those cases, the value of always matches the value of a.
Another way to say that is:
a determines the value of
or
| a | b | a b |
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
What about expressions like
or
Logical Constants (what about mixing logical constants and logical variables)
As with the previous slide, this outcome should be intuitive.
| a | b | a b |
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
In the case of
we can compare the expression to the truth table, only for the rows where b is F (constantly F). Those rows are highlighted in green.
In those cases, the value of is always F.
Another way to say that is:
a has no effect on the value of
or
Logical Constants (what about mixing logical constants and logical variables)
| a | b | a b |
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
How about this expression ?
will be True if either the left proposition is True or if the right proposition is True.
If the right proposition is always true, it doesn’t matter whether the left proposition is true or not.
This is confirmed by examining the rows of the table where b is T. (White rows in the table).
Therefore,
Logical Constants (what about mixing logical constants and logical variables)
| a | b | a b |
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
And finally,
by the same reasoning,
Logical Constants (what about mixing logical constants and logical variables)
De Morgan’s Laws
Negation Laws
Absorption Laws
Double Negation Law
Domination Laws
Complement Laws
Distributive Laws
Associative Laws
Commutative Laws
Idempotent Laws
Identity Laws
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)
Start with
If we write the p on the left as the resulting expression
will look like the right-hand side of the distributive law
use the identity law
(in “reverse”)
Prove the absorption law:
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)
Now, with
we can factor out the p from both AND expressions
to obtain
where can be replaced with T (according to the domination law) to give
and now apply the identity law to give
So...
QED
QED ( quod erat demonstrandum) (what was required to be proved)
use the distributive law (in “reverse”)
Logic (proving laws)
ok. catch your breath and get ready for the big one.
Logic (proving laws)
(One of) De Morgan’s Law is:
Make use of the complement laws. According to these two laws:
So, if we have any two propositions x and y such that these two statements are true:
that means (according to the complement laws) that
Notice that we make use of the fact that and are commutative and therefore use this form of these laws:
Do you see that this is equivalent to the complement laws given above?
Logic (proving De Morgan’s laws) (more complicated)
So, writing
in terms of p and q is to let
Then to prove these two statements
is to prove
and thus
Logic (proving De Morgan’s laws) (more complicated)
So, in this case, we want to prove
Let
Prove:
Use the third complement law (as listed earlier) to simplify left part
Logic (proving De Morgan’s laws) (more complicated)
and eliminate extra parentheses on right part from
gives
Use distributive property
Use associate property and commutative property to rearrange the anded statements
Use first complement law (as listed earlier) gives
Logic (proving De Morgan’s laws) (more complicated)
(from previous slide)
now apply the second domination law (as listed earlier) to get
or
Q.E.D.
So that proves the first of the two statements we need to prove.
Onward...
Logic (proving De Morgan’s laws) (more complicated)
Now we need to prove that
again, where
So, prove that
Use the double negation law to simplify the left part and eliminate extra parentheses in both parts, gives:
Use distributive law:
Logic (proving De Morgan’s laws) (more complicated)
From previous slide:
Use associative law and commutative law to rearrange anded statements gives:
Simplify, using complement law:
Use domination law (twice) gives:
or
Q.E.D.
Logic (proving De Morgan’s laws) (more complicated)
So we proved both these statements:
which means that
where
so, we proved that
which is what the De Morgan Law stated.
Yippee !!!
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.
| a | b | ~a | ~b | |||
| T | T | F | F | T | F | T |
| T | F | F | T | T | T | F |
| F | T | T | F | T | T | F |
| F | F | T | T | F | T | F |
The technique used to prove (one of) De Morgan’s Laws is called a formal proof.
An alternate technique is to demonstrate that an equality is or isn’t true by constructing the appropriate truth table.
Suppose somebody suggested that the following equality was true.
Logic (using truth tables)
De Morgan’s Laws are actually a specific example of a more general concept:
duality
In logic, the dual of a (valid) statement is formed by:
complementing all proposition variables
changing all to and all to
Example: The dual of
is
Logic (duality)
The dual of
is
in the left part, x and y are complemented and the changed to
in the right part, a is complemented to give ~a , ~b is complemented to give b (the complement of the complement) and the is changed to a
then the middle is changed to a . the quantity is complemented, giving , and the quantity is complemented, giving
Logic (duality – a more complicated example)
| Precedence | Name | Symbol | Comment |
| 1 | NOT | highest (performed 1st) | |
| 2 | AND | ||
| 3 | OR | ||
| 4 | IMPLICATION | ||
| 5 | BICONDITIONAL | lowest (performed last) |
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.
Example:
Write the parenthesized version of
Logic (operator precedence)
The AND, OR, NOT are called the basic functions.
Other functions are useful and can be derived from AND, OR, NOT
NOR:
NAND:
XOR: (exclusive OR)
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
| p | q | 1’s column | carry bit | ||||
| F | F | T | T | F | F | F | 0 |
| F | T | T | F | T | F | T | 0 |
| T | F | F | T | F | T | T | 0 |
| T | T | F | F | F | F | F | 1 |
Of course it’s possible. Somebody has already figured it out. That’s why computers can do arithmetic.
will produce the right values for the ones column.
will produce the right values for the carry
Since this is an actual truth table, let’s go back to using T and F, but remember T represents 1 and F represents 0.
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.
| p | q | 1’s column | carry bit | ||||
| F | F | T | T | F | F | F | 0 |
| F | T | T | F | T | F | T | 0 |
| T | F | F | T | F | T | T | 0 |
| T | T | F | F | F | F | F | T |
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
