Discrete Structure
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