Discrete Structures
CSCE 121
Chapter 1: Logic
Logic
➢ The rules of logic are used to distinguish between
valid and invalid mathematical arguments.
➢ These rules are used in the design of computer
circuits, the construction of computer programs, and
the verification of the correctness of programs.
Logic
➢ Topics
1. Propositional logic.
2. Propositional Equivalence.
3. Predicates and Quantifiers.
4. Nested Quantifiers.
Logic
Propositions Logic
• Definition: A proposition is a declarative statement that
can be either true or false
• Example: examples for proposition are
– “Riyad is a capital of KSA.”
– “Ali is a professor.”
– “3 = 2 + 1”
– “3 = 2 + 2”
• Not propositions:
– “Are you Omer?”
– “x = 7” (either true or false).
– What time is it? (not declarative sentence)
Logic
Propositions Logic
➢We use propositional variables to refer to propositions.
Usually are lower case letters starting with p (i.e. p, q,r etc.)
➢A propositional variable can have one of two values: true
(T) or false (F)
➢Example:
p = “7 is a prime number”
– q = “Today is my exam”
Logic
Propositions Logic
➢ Many mathematical statements are constructed by
combining one or more propositions. New propositions, called
compound propositions.
➢Compound propositions are formed from existing
propositions using logical operators.
➢A truth table is a listing of all possible combinations of the
individual proposition statement as true or false, along with
the resulting truth value of the compound statements.
Logic
Propositions Logic
Truth Table
P p q p q r
T T T T T T
F T F T T F
F T T F T
F F T F F
F T T
F T F
F F T
F F F
Logic
Propositions Logic
(1) Logical operators: Not
Definition: For the proposition p, the negation is the opposite
of the truth value of p and denote by ¬ p.
p ¬p
➢The negation of p read “not p”. T F
F T
➢Examples: “Today is Sunday”
p = “Today is Sunday”
¬p = “Today is not Sunday”
➢q=Rakan’s PC runs Linux
¬q = Rakan’s PC does not run Linux
Logic
Propositions Logic
(2) Logical operators: And (conjunction)
Definition: For propositions p and q ,the conjunction of p and
q is true if both operands are true and is false otherwise.
➢ The conjunction of p and q denoted by p ^ q p q p∧q
and read “p and q”. T T T
➢ Example: Today is Sunday and today is my T F F
exam. F T F
➢ p=Today is Sunday, It is true only when it F F F
q = today is my exam is Sunday and it is
p^q my exam .
➢ In some times, we used “ But “instead of AND.
➢ Example: The sun is shining but it is raining .
Logic
Propositions Logic
(3) Logical operators: Or (disjunction)
Definition: For propositions p and q, the disjunction of p and
q is false when both operands are false and is true
otherwise. p q p∨q
➢ The disjunction of p and q denoted by
p ∨ q and read “p or q”. T T T
➢ Examples: Today is the lecture of ICS T F T
251 or ICS 252. F T T
➢ p=Today is the lecture of ICS 251, F F F
q = the lecture of ICS 252
p∨q
Logic
Propositions Logic
(4) Logical operators: Exclusive Or
Definition: For propositions p and q, the exclusive or of p
and q is true if exactly one of p and q is true and is false
otherwise. p q p⊕q
➢ The exclusive or of p and q denoted by p ⊕ T T F
q or p XOR q and read “p exclusive or q”. T F T
F T T
➢ p⊕q ≡ (p ∨ q) ∧ ¬(p ∧ q) Prove F F F
One of p and q is
To exclude both (p
true (may be
and q) are true
both)
Logic
Propositions Logic
(4) Logical operators: Exclusive Or
➢ Examples: Today is Sunday or today is my exam, but not
both.
➢ Today is Sunday, today is my exam, not both
➢ p =Today is Sunday, q = today is my exam,
➢ p ∨ q = Today is Sunday or today is my exam
➢ ¬(p ∧ q) = but not both
➢ p⊕q ≡ (p ∨ q) ∧ ¬(p ∧ q)
➢ HW: convert the following statement.
(1) take the blue ball or red one but not both.
(2) A person can be either Male or Female but not the both.
Logic
Inclusive Or versus Exclusive Or
● Do these sentences mean inclusive or exclusive or?
1. Experience with C++ or Java is required
●2. Lunch includes soup or salad
●3. To enter the country, you need a passport or a
driver’s license
4. Coffee or tea comes with dinner.
5. you can pay using U.S dollars or euros.
Logic
Propositions Logic
(5) Conditional operator: if then (implication) (→)
Definition: For propositions p and q, the conditional
statement of p → q is false when p is true and q is false,
and true otherwise.
p q p→q
➢ The implication of p and q denoted by p → q
T T T
and read “if p then q”.
• p implies q T F F
• If p, q F T T
• p only if q F F T
• p is sufficient for q
• q if p
• q whenever p
• q is necessary for p
Logic
Propositions Logic
(5) Conditional operator: if then (implication) (→)
➢Example : “If today is Sunday, then today is my exam”
p → q
➢If you get 90% on the final, then you will get an A.
p → q
p→q =¬p∨q
The hypothesis The conclusion
(antecedent) (consequence)
Logic
Propositions Logic
(5) Conditional operator: if then (implication) (→)
➢Example : Let p = “Tariq do hard at study” and q = “Tariq will
get high mark”. Convert these statements using if then.
➢The state: p → q = “If Tariq do hard at study, he will get high
mark”
Logic
Propositions Logic
(5) Conditional operator: if then (implication) (→)
We can form new conditional statements starting
with a conditional statement. There are three related
statements with special names.
Conditional Inverse Converse Contrapositive
p q ¬p ¬q p→q ¬p→¬q q→p ¬q→¬p
T T F F T T T T
T F F T F T T F
F T T F T F F T
F F T T T T T T
Logic
Propositions Logic
(5) Conditional operator: if then (implication) (→)
➢Example : Let “if it is raining, then the home team wins””. Find the converse ,
contrapositive , and inverse of p → q.
➢Sol: p= it is raining & q= the home team wins
➢The converse of p → q is q → p
“if the home team wins, then it is raining”
➢The contrapositive of p → q is ¬q → ¬p “if the home
team not win, then it is not raining” or
“if it is raining, then the home team wins”(original statement)
➢The inverse of p → q is ¬p → ¬q “if it is
not raining, then the home team does not win”
➢Example : Apply the previous question on “I come to class whenever there is a
quiz.”
Logic
Propositions Logic
(6) Conditional operator: Bi-conditional (↔)
Definition: For propositions p and q, a bi-conditional
statement p ↔ q, is true when p and q have the same truth
value and is false Otherwise. p q p q
➢ The implication of p and q denoted by p ↔ T T T
q and read “p if and only if q ” or T F F
“(if p then q) and (if q then p)” F T F
p→q and q→p F F T
➢ Note that a bi-conditional has the opposite
truth values of the exclusive or.
Logic
Propositions Logic
(6) Conditional operator: Bi-conditional (↔)
Example : Let p = “You take this class” and q = “You get a grade”
Then p↔q is
“You take this class if and only if you get a grade” or
“If you take this class, then you get a grade and if you get a grade
then you take (took) this class”
➢let the p is ” you can take A+” and q is “your marks grater than or
equal to 95”
➢Then p↔q is
“ You can take A+ if and only if your marks grater than
or equal to 95”
Logic
Propositions Logic
Boolean operators summary
not not and or xor conditional Bi-conditional
p q ¬p ¬q p∧q p∨q p⊕q p→q p↔q
T T F F T T F T T
T F F T F T T F F
F T T F F T T T F
F F T T F F F T T
Logic
Propositions Logic
Questions
Q1) Determine whether the following statements is propositional or
not (give reason). If the statement is propositional then determine
the value of this propositional statement.
1)5 + 2 = 8. (Yes. F)
2)It is raining today. (Yes. either T or F)
3)How are you? (No, a question is not a proposition, “what time is it”)
4)x + 5 = 3 (No, since x is not specified, neither true nor false)
5)2 is a prime number. (Yes, T)
6)X+1=2 (No, neither True nor false)
7)Answer this question. (No)
Logic
Propositions Logic
Questions
Q2) What is the negation of each of these proposition?
1)Today is Thursday.
2)There is no pollution in New Jersey.
3)2+1=3.
4)The summer in Main is hot and sunny.
Q3) Let p and q be the propositions
p: I bought a lottery ticket this week.
q: I won the million dollar jackpot on Friday.
Express each of these propositions as English sentence.
(1) ¬ p (2) p V q (3) p exclusive or q (4) ¬ p ^ ¬ q
Logic
Propositions Logic
Questions
Q4) Given :
● p = “It is below freezing”
● q = “It is snowing”
Write the following propositions using p and q and logical connections.
1)It is below freezing and it is snowing
2)It is below freezing but not snowing
3)It is not below freezing and it is not snowing p∧q
4)It is either snowing or below freezing (or both)
p∧¬q
5)If it is below freezing, it is also snowing
6)It is either below freezing or it is snowing, ¬p∧¬q
but it is not snowing if it is below freezing p∨q
7)That it is below freezing is necessary and p→q
8) sufficient for it to be snowing
(p∨q)∧(p→¬q)
p↔q
Logic
Propositions Logic
Questions
Q5) Let “I go to the beach the beach whenever it is a sunny
summer day”. Find the converse , contrapositive , and
inverse of p → q.
Q6) Determine whether these bi-conditionals are true or false.
a)2+2=4 if and only if 1+1=2
b)1+1=2 if and only if 2+3=5
c)1+1=3 if and only if monkeys can fly.
d)0>1 if and only if 2>1
Logic
Propositions Logic
Questions
Q7) Determine whether these conditionals are true or
false.
a)If 1+1=2, then 2+2=5 (false)
b)if 1+1=3, then 2+2=4
c)1+1=3, then 2+2=5
Logic
Propositions Logic
Questions
Q8) Translate the following statements to propositions using
p and q and logical connections.
a)I have neither given nor received help on this exam.
b)You can access the Internet from campus only if you are a
computer science major or you are not a freshman.
c)You cannot ride the roller coaster if you are under 4 feet tall
unless you are older than 16 years old.
Let p = “I have given help on this exam” a → (c ∨ ¬ f)
Let q = “I have received help on this
exam”
(f ∧ ¬ s) → ¬ r
¬p∧¬q
r → (¬ f ∨ s)
Precedence of operators
● Just as in algebra, operators have precedence
● 4+3*2 = 4+(3*2), not (4+3)*2
● Precedence order (from highest to lowest):
¬∧∨→↔
● The first three are the most important
● This means that p ∨ q ∧ ¬r → s ↔ t
yields: (p ∨ (q ∧ (¬r)) → s) ↔ (t)
● Not is always performed before any other operation
Bit Operations
Computer representation of True and False
We need to encode two values True and False:
• Computers represents data and programs using 0s and 1s
• Logical truth values – True and False
• A bit is sufficient to represent two possible values:
– 0 (False) or 1(True)
• A variable that takes on values 0 or 1 is called a Boolean
variable.
• Definition: A bit string is a sequence of zero or more bits.
The length of this string is the number of bits in the string.
Bit Operations
p q p^q p˅q
1 1 1 1
1 0 0 1
0 1 0 1
0 0 0 0
