Discrete Structures (Mathematics)

Topic: Logic of Compoud Statements

What are discrete Structures?

• Discrete mathematics is the part of mathematics devoted

to the study of discrete objects (Kenneth H. Rosen, 6th
edition).

• Discrete mathematics is the study of mathematical

structures that are fundamentally discrete rather
than continuous (wikipedia).

Problems from Ex 2.1

Discrete vs Continuous
• Examples of discrete Data

– Number of boys in the class.

– Number of candies in a packet.
– Number of suitcases lost by an airline.

• Examples of continuous Data

– Height of a person.
– Time in a race.
– Distance traveled by a car.

Problems from Ex 2.1

Applications
• How can a circuit that adds two integers be designed?
• How many ways are there to choose a valid password on a
computer?
• What is the shortest path between two cities using transportation
system?
• How can I encrypt a message so that no unintended recipient can
read it?
• How many valid internet addresses are there?
• How can a list of integers be sorted so that the integers are in
increasing order?

Problems from Ex 2.1

Todays Lecture
• Propositional Logic

• Logic of Compound Statements

• Conditional Statements

• Logical Equivalences

• Valid and Invalid Arguments

Problems from Ex 2.1

 Propositional Logic
Proposition: A proposition (or Statement) is a declarative sentence (that
is, a sentence that declares a fact) that is either true or
false, but not both.
Examples
1. Is the following sentence a proposition? If it is a proposition, determine
whether it is true or false.
Almaty is the capital of Kazakhstan.

This makes a declarative statement, and hence is a

proposition. The proposition is False (F).

Problems from Ex 2.1

Propositions Cont….

2. Is the following sentence a proposition? If it is a proposition, determine

whether it is true or false.

Can Alinur come with you?.

This is a question not the declarative sentence and hence not a

proposition.

3. Is the following sentence a proposition? If it is a proposition,

determine whether it is true or false.

Take two aspirins.

This is an imperative sentence not the declarative sentence and

therefore not a proposition.

Problems from Ex 2.1

Propositions Cont…

4. Is the following sentence a proposition? If it is a proposition,

determine whether it is true or false.

x+ 4 > 9.

Because this is true for certain values of x (such as x = 6) and false for
other values of x (such as x = 5), it is not a proposition.
5. Is the following sentence a proposition? If it is a proposition,
determine whether it is true or false.

He is a University student.

Because truth or falsity of this proposition depend on the reference

for the pronoun he. it is not a proposition.

Problems from Ex 2.1

Notations

• The small letters are commonly used to denote the

propositional variables, that is, variables that represent
propositions, such as, p, q, r, s, ….

represents some statement

• The truth value of a proposition is true, denoted by T or 1,

if it is a true proposition and false, denoted by F or 0, if it
is a false proposition.

Problems from Ex 2.1

Compound Propositions
Producing new propositions from existing propositions.

Logical Operators or Connectives

1. Not 
2. And ˄
3. OR ˅
4. Exclusive OR 
5. Implication 
6. Biconditional 

Problems from Ex 2.1

Operator (NOT, )
Let p be a proposition. The negation of p, denoted by  p (also
denoted by ~p), is the statement
“It is not the case that p”.
The proposition  p is read as “not p”. The truth values of the negation
of p,  p, is the opposite of the truth value of p.

p p

true false

false true

Problems from Ex 2.1 Truth Table (NOT)

Examples
1. Find the negation of the following proposition

p : Today is Friday.
The negation is
 p : It is not the case that today is Friday.

This negation can be more simply expressed by

 p : Today is not Friday.

Problems from Ex 2.1

Cont…

2. Write the negation of

“6 is negative”.
The negation is

“It is not the case that 6 is negative”.

or “6 is nonnegative”.

Problems from Ex 2.1

Conjunction (AND, )
Let p and q be propositions. The conjunction of p and q, denoted by
p˄q, is the proposition “p and q”.
The conjunction p˄q is true when p and q are both true and is false
otherwise.

p q pq

true true true

true false false

false true false

false false false

Truth Table (AND)

Problems from Ex 2.1
 Examples
1. Find the conjunction of the propositions p and q, where

p : Today is Friday.
q : It is raining today.
The conjunction is

p˄q : Today is Friday and it is raining today.

Problems from Ex 2.1

Disjunction (OR, ˅ )
Let p and q be propositions. The disjunction of p and q, denoted by
p˅q, is the proposition “p or q”.
The disjunction p˅q is false when both p and q are false and is true
otherwise.

p q pq

true true true

true false true

false true true

false false false

Truth Table (OR)

Problems from Ex 2.1
Examples

1. Find the disjunction of the propositions p and q, where

p : Today is Friday.
q : It is raining today.
The disjunction is

p˅q : Today is Friday or it is raining today.

Problems from Ex 2.1

Translating English to Logic
I did not buy a lottery ticket this week or I bought a lottery ticket and won
the million dollar on Friday.
Let p and q be two propositions
p: I bought a lottery ticket this week.
q: I won the million dollar on Friday.

In logic form
 p  (p  q)

Problems from Ex 2.1

 Conditional Statements (Implication)
Let p and q be propositions. The conditional statement p  q, is
the proposition “If p, then q”.
The conditional statement p  q is false when p is true and q is
false and is true otherwise.

where p is called hypothesis, antecedent or premise.

q is called conclusion or consequence

conclusion

Example: If Alinur lives in Almaty, then he lives in Kazakhstan.

hypothesis
Problems from Ex 2.1
 Truth Table (if – then, Symbol: )

P Q PQ

true true true

true false false

false true true

false false true

Alternatively: p is a necessary condition for q also means “if p then q.”

Problems from Ex 2.1

Biconditional Statements

Let p and q be propositions. The biconditional statement pq, is

the proposition “p if and only if q”.
The biconditional (bi-implication) statement p  q is true when p
and q have same truth values and is false otherwise.

P Q PQ
true true true
true false false
false true false
false false true
Problems from Ex 2.1
 Examples
p q

1. Tomorrow is Wednesday if and only if today is Tuesday.

2. x2 - 4 = 0 if and only if x = ± 2.
3. An angle is right if and only if it measures 90o
4. I will pass if and only if I study hard.

Alternatively: p is a necessary and sufficient condition for q means “p if, and only
if, q.”

Problems from Ex 2.1

Interpreting Necessary and sufficient conditions

Example: Consider the proposition

‘if John is eligible to vote then he is at least 18 year old’.
The truth of the condition ‘John is eligible to vote’ is
sufficient to ensure the truth of the condition ‘John is at least
18 year old’.
In addition, the condition ‘John is at least 18 year old’ is
necessary for the condition ‘John is eligible to vote’ to be
true. If John were younger than 18, then he would not
eligible to vote.

Problems from Ex 2.1

 Composite Statements
Statements and operators can be combined in any way to form new
statements.

P Q P Q (P)(Q)
true true false false false
true false false true true
false true true false true
false false true true true

Problems from Ex 2.1

 Equivalent Statements, Symbol ≡
Two statements are called logically equivalent if and only if they have identical
truth tables

The statements  (PQ) and ( P)  ( Q) are logically equivalent, because

 (PQ)(P)(Q) is always true.

P Q (PQ) (P)(Q) (PQ)(P)(Q)

true true false false true

true false true true true

false true true true true

false false true true true

Problems from Ex 2.1
 Activity

• Show that
p→q≡ ¬pq

This shows that a conditional proposition is simple a

proposition form that uses a not and an or.

• Show that
¬ (p → q) ≡ p  ¬q
This means that negation of ‘if p then q’ is logically
equivalent to ‘p and not q’.

Problems from Ex 2.1

Solution

p q p  q ¬ p  q ¬ (p  q) p¬q
T T T T T T
T F F F F F
F T T T T T
F F T T T T

From the above table it is obvious that conditional proposition

is equivalent to a “not or proposition” and that its negation is
not of the form ‘if then’.

Problems from Ex 2.1

 Valid and Invalid Argument

An argument is a sequence of statements such that

• all statements but the last are called hypotheses
• the final statement is called the conclusion
• the symbol ∴ read “therefore” is usually placed just
before the conclusion.
p∧~q →r
p∨q Example
An argument is said to be
of argument
q→p valid if whenever all
∴r hypotheses are true, the
conclusion must be true

Problems from Ex 2.1

Valid Argument

Problems from Ex 2.1

Invalid Argument

Problems from Ex 2.1

Practice Exercises of the Text Book
Discrete Mathematics with Applications, 4th edition (International Edition)

Ex 2.1,2.2, and 2.3

What we Discussed

• Propositions
• Logical Connectives
• Truth Tables
• Compound propositions
• Translating English to logic and logic to English.
• Valid and Invalid Statements

Problems from Ex 2.1

 Laws of Logic
1. Commutative laws
pq≡ qp ; pq≡qp
2. Associative laws

p  (q  r) ≡ (p q)  r ; p(q r) ≡ (p  q)r

3. Distributive laws
p  (q  r ) ≡ (p  q)  (p  r)
p  (q  r) ≡ (p  q)  (p  r)
4. Identity laws
pt≡p ;pc≡ p

5. Negation laws
p¬p ≡ t ; p  ¬p ≡ c

6. Double negation law

¬(¬p) ≡ p

Problems from Ex 2.1

Laws of Logic

7. Idempotent laws
p  p ≡ p ; pp ≡ p
8. Universal bound laws
pt≡t ;pc≡ c

9. Absorption laws
p (pq) ≡ p ; p (p  q) ≡ p

10. Negation of t and c

¬t ≡ c ; ¬c ≡ t
Problems from Ex 2.1
Discrete Mathematics

Topic: Logic of Compoud Statements

Write the statements in symbolic form using the symbols ,  , ˅ and ˄ ` and
the indicated letters to represent component statements.

1. Let s = “stocks are increasing” and i = “interest rates are steady.”

a. Stocks are increasing but interest rates are steady.
b. Neither are stocks increasing nor are interest rates steady.

2. Let p = “x > 5,” q =“x = 5,” and r = “10 > x.”

a. x ≥ 5
b. 10 > x > 5
c. 10 >x ≥ 5

Problems from Ex 2.1

3. Write truth tables for the statement ,  (p ˄ q) v ( p v q).

4. Verify the logical equivalence, p ˄ ( q v p) ≡ p .

Problems from Ex 2.1

5. Write each of the following three statements in symbolic form and
determine which pairs are logically equivalent. Include truth tables and a few
words of explanation.

a) If it walks like a duck and it talks like a duck, then it is a duck.

b) Either it does not walk like a duck or it does not talk like a duck, or it is a

duck.

c) If it does not walk like a duck and it does not talk like a duck, then it is not

a duck.

Solution: Let p represent "It walks like a duck," q represent "It talks like a
duck," and r represent "It is a duck."

Problems from Ex 2.2

 Truth Table

Problems from Ex 2.1

Rewrite the statements in if-then form.

1. Payment will be made on fifth unless a new hearing is granted.

If a new hearing is not granted, payment will be made
on the fifth.
2. Ann will go unless it rains.
If it doesn't rain, then Ann will go.
3. This door will not open unless a security code is entered.
If a security code is not entered, then the door will not
open.

Problems from Ex 2.2

Use truth tables to determine whether the argument forms are valid

p˄q→~r
p ˅ ~q
~p→p
∴ ~r

Problems from Ex 2.3