https://edu.gcfglobal.org/en/computerbasics/about-this-tutorial/content/
Introduction
Discrete Mathematics deals with discrete objects. Discrete objects are those objects that
can be counted and are not connected for e.g. houses, trees, desks, integers, etc. So
dealing with these discrete objects requires different concepts like counting techniques,
knowledge of different discrete structures that are needed to understand what exactly
discrete structure is like sets, relations, graphs, etc. we start our quest with foundation and
go in depth later.
Logic
Logic is a language for reasoning. Since logic can helps us to reason the mathematical
models it needs some rules associated with logic so that we can apply those rules for
mathematical reasoning. There are lots of applications of logic in the field of computer
science for e.g. designing circuits, programming, program verifications, etc.
Propositions and Propositional Calculus
Proposition is a fundamental concept in logic. Proposition is a declarative sentence that is
either true or false, but not both. See the examples below:
2 + 2 = 5. (False), 7 - 1 = 6. (True)
It is hot today. (If it is hot then true)
Kathmandu is the capital of Nepal. (True)
All the above examples are either true or false.
Try to analyze the sentences below:
x > 5, Come here, Who are you?, 3 + 4
The above sentences are not propositions since we cannot say whether they are true or
false.
Propositions are denoted conventionally by using small letters like p, q, r, s …. The truth
value of proposition is denoted by T for true proposition and F for false proposition.
Reminder: p, q ,r ,s … are not actual propositions but they are propositional variables
i.e. place holders for propositions.
The logic that deals with propositions is called propositional logic or propositional
calculus
Logical Operators/Connectives
Logical operators are used to construct mathematical statements having one or more
propositions by combining the propositions. The combined proposition is called
compound Proposition. The truth table is used to get the relationship between truth values
of propositions. Here we present the logical operators along with their behavior in truth
table:
Negation (not)
Given a proposition p, negation operator (¬) is used to get negation of p denoted by ¬p
called “not p”.
Example: Negation of the proposition “ I love birds” is “ I do not love birds” if the
sentence I love birds is denoted by p then its negation is denoted by ¬p.
Truth table
p ¬p
T F
F T
Conjunction (and)
Given two propositions p and q, the proposition “p and q” denoted by p∧q is the
proposition that is true whenever both the propositions p and q are true, false otherwise.
The proposition that is obtained by the use of “and” operator is also called conjunction of
p and q.
Example: If we have propositions p = “Ram is intelligent” and q = “Ram is diligent” the
conjunction of p and q is Ram is intelligent and diligent. This proposition is true only
when Ram is intelligent and he is diligent also, false otherwise.
Truth Table
p q p∧q
T T T
T F F
F T F
F F F
Disjunction (or)
Given two propositions p and q, the proposition “p or q” denoted by p∨q is the
proposition that is false whenever both the propositions p and q are false, true otherwise.
The proposition that is obtained by the use of “or” operator is also called disjunction of p
and q.
Example: If we have propositions p = “Ram is intelligent” and q = “Ram is diligent” the
disjunction of p and q is Ram is intelligent or he is diligent. This proposition is false only
when Ram is not intelligent and not diligent, true otherwise.
Truth Table
p q p∨q
T T T
T F T
F T T
F F F
Exclusive or (Xor)
Given two propositions p and q, the proposition exclusive or of p and q denoted by p ⊕ q
is the proposition that is true whenever only one of the propositions p and q is true, false
otherwise. As opposed to the disjunction above which is inclusive the general meaning of
the English sentence can be used to know whether the “or” used is inclusive or exclusive.
Example: If we have propositions p = “Ram drinks coffee in the morning” and q = “Ram
drinks tea in the morning” the exclusive or of p and q is Ram drinks coffee or tea in the
morning.
Truth Table
p q p ⊕ q
T T F
T F T
F T T
F F F
Download the pdf file to get all the unit wise notes.
Try to save your valueable time!
cloud_download
Click Here!