Table of Contents
III. Theory and Mathematical Background – 40%
C. Discrete structures
1. Mathematical logic
a. Definition: Mathematical logic is based on formulas that are always true or false.
b. Three Americans (a scientist, a mathematician, and a logician) are traveling on a train in China. The scientist sees a green cow in the middle of a field. He says, “Wow, a green cow, the cows in China must be green.” The mathematician corrects him, “No, all we know is that there is one cow in China that is green.” The logician wakes up from his nap and corrects them both, “All we know is that there exists at least one side of one cow that is green in China.” The symbol $ is used to mean “there exists”. We use the symbol " to mean “for all”. An example of using these symbols is "n $(2n). Read: For all n, there exists a number that is 2n.
c. Boolean logic is based on T/F (true/false) statements. Truth tables are the most basic way to interpret Boolean functions. There are many basic operators in Boolean
|
Operator |
Symbol(s) |
Note |
|
OR (Inclusive or) |
Ú + |
One, the other, both are true |
|
AND |
^ • |
Both must be true |
|
NOT |
Ø |
Negates |
|
Exclusive OR (XOR) |
Å |
One or the other, not both |
|
Implies |
Þ |
If P then Q |
|
Bidirectional Implication (IFF) |
Û |
P if and only if Q |
|
OR |
Ú |
|
|
T |
T |
T |
|
T |
F |
T |
|
F |
T |
T |
|
F |
F |
F |
|
AND |
^ |
|
|
T |
T |
T |
|
T |
F |
F |
|
F |
T |
F |
|
F |
F |
F |
|
NOT |
Ø |
|
|
T |
|
F |
|
F |
|
T |
|
|
|
|
|
|
|
|
|
XOR |
Å |
|
|
T |
T |
F |
|
T |
F |
T |
|
F |
T |
T |
|
F |
F |
F |
|
Implies |
Þ |
|
|
T |
T |
T |
|
T |
F |
F |
|
F |
T |
T |
|
F |
F |
T |
|
IFF |
Û |
|
|
T |
T |
T |
|
T |
F |
F |
|
F |
T |
F |
|
F |
F |
T |
|
OR |
Ú |
||
|
T |
T |
T |
T |
|
T |
T |
F |
T |
|
T |
F |
T |
T |
|
T |
F |
F |
T |
|
F |
T |
T |
T |
|
F |
T |
F |
T |
|
F |
F |
T |
T |
|
F |
F |
F |
F |
|
AND |
^ |
||
|
T |
T |
T |
T |
|
T |
T |
F |
F |
|
T |
F |
T |
F |
|
T |
F |
F |
F |
|
F |
T |
T |
F |
|
F |
T |
F |
F |
|
F |
F |
T |
F |
|
F |
F |
F |
F |
|
XOR |
Å |
||
|
T |
T |
T |
T |
|
T |
T |
F |
F |
|
T |
F |
T |
F |
|
T |
F |
F |
T |
|
F |
T |
T |
F |
|
F |
T |
F |
T |
|
F |
F |
T |
T |
|
F |
F |
F |
F |
|
Implies |
Þ |
||
|
T |
T |
T |
T |
|
T |
T |
F |
F |
|
T |
F |
T |
T |
|
T |
F |
F |
T |
|
F |
T |
T |
T |
|
F |
T |
F |
F |
|
F |
F |
T |
T |
|
F |
F |
F |
F |
|
IFF |
Û |
||
|
T |
T |
T |
T |
|
T |
T |
F |
F |
|
T |
F |
T |
F |
|
T |
F |
F |
T |
|
F |
T |
T |
F |
|
F |
T |
F |
T |
|
F |
F |
T |
T |
|
F |
F |
F |
F |
