nd

Logic (2 part)

1
 Equivalent Statements
P Q ¬(P∧Q) (¬P)∨(¬Q) ¬(P∧Q)↔(¬P)∨(¬Q)

T T F F T
T F T T T
F T T T T
F F T T T
The statements ¬(P∧Q) and (¬P) ∨ (¬Q) are logically
equivalent, since they have the same truth table, or put
it in another way, ¬(P∧Q) ↔(¬P) ∨ (¬Q) is always true.
2
 Tautologies and Contradictions
A tautology is a statement that is always true.
Examples:
– R∨(¬R)
– ¬(P∧Q) ↔ (¬P)∨(¬ Q)
A contradiction is a statement that is always false.
Examples:
– R∧(¬R)
– ¬(¬(P ∧ Q) ↔ (¬P) ∨ (¬Q))
The negation of any tautology is a contradiction, and
the negation of any contradiction is a tautology.

CSE 121: Discrete Mathematics 3

 Equivalence
Definition: two propositional statements
S1 and S2 are said to be (logically)
equivalent, denoted S1 ≡ S2 if
– They have the same truth table, or
– S1 ⇔ S2 is a tautology
Equivalence can be established by
– Constructing truth tables
– Using equivalence laws (Table 5 in Section 1.2)

CSE 121: Discrete Mathematics 4

 Equivalence
Equivalence laws
– Identity laws, P ∧ T ≡ P,
– Domination laws, P ∧ F ≡ F,
– Idempotent laws, P ∧ P ≡ P,
– Double negation law, ¬ (¬ P) ≡ P
– Commutative laws, P ∧ Q ≡ Q ∧ P,
– Associative laws, P ∧ (Q ∧ R)≡ (P ∧ Q) ∧ R,
– Distributive laws, P ∧ (Q ∨ R)≡ (P ∧ Q) ∨ (P ∧ R),
– De Morgan’s laws, ¬ (P∧Q) ≡ (¬ P) ∨ (¬ Q)
– Law with implication P → Q ≡ ¬ P ∨ Q

CSE 121: Discrete Mathematics 5

 Exercises
• Show that P → Q ≡ ¬ P ∨ Q: by truth table
• Show that (P → Q) ∧ (P → R) ≡ P → (Q ∧ R):
by equivalence laws (q20, p27):
– Law with implication on both sides
– Distribution law on LHS

CSE 121: Discrete Mathematics 6

 Summary, Sections 1.1, 1.2
•Proposition
– Statement, Truth value,
– Proposition, Propositional symbol, Open proposition
•Operators
– Define by truth tables
– Composite propositions
– Tautology and contradiction
•Equivalence of propositional statements
– Definition
– Proving equivalence (by truth table or equivalence
laws)
CSE 121: Discrete Mathematics 7
 Propositional Functions & Predicates
Propositional function (open sentence):
statement involving one or more variables,
e.g.: x-3 > 5.
Let us call this propositional function P(x), where
P is the predicate and x is the variable.
What is the truth value of P(2) ? false
What is the truth value of P(8) ? false
What is the truth value of P(9) ? true
When a variable is given a value, it is said to be
instantiated
Truth value depends on value of variable
CSE 121: Discrete Mathematics 8
 Propositional Functions
Let us consider the propositional function
Q(x, y, z) defined as:
x + y = z.
Here, Q is the predicate and x, y, and z are the
variables.
What is the truth value of Q(2, 3, 5) ? true
What is the truth value of Q(0, 1, 2) ? false
What is the truth value of Q(9, -9, 0) ? true
A propositional function (predicate) becomes a
proposition when all its variables are instantiated.
CSE 121: Discrete Mathematics 9
 Propositional Functions
Other examples of propositional functions
Person(x), which is true if x is a person
Person(Socrates) = T
Person(dolly-the-sheep) = F
CSCourse(x), which is true if x is a
computer science course
CSCourse(CMSC201) = T
CSCourse(MATH155) = F
How do we say
All humans are mortal
One CS course
CSE 121: Discrete Mathematics 10
 Universal Quantification
Let P(x) be a predicate (propositional function).

Universally quantified sentence:

For all x in the universe of discourse P(x) is true.

Using the universal quantifier ∀:

∀x P(x) “for all x P(x)” or “for every x P(x)”

(Note: ∀x P(x) is either true or false, so it is a

proposition, not a propositional function.)

CSE 121: Discrete Mathematics 11

 Universal Quantification
Example: Let the universe of discourse be all
people
S(x): x is a UMBC student.
G(x): x is a genius.
What does ∀x (S(x) → G(x)) mean ?
“If x is a UMBC student, then x is a genius.” or
“All UMBC students are geniuses.”
If the universe of discourse is all UMBC students,
then the same statement can be written as
∀x G(x)

CSE 121: Discrete Mathematics 12

 Existential Quantification
Existentially quantified sentence:
There exists an x in the universe of discourse
for which P(x) is true.

Using the existential quantifier ∃:

∃x P(x) “There is an x such that P(x).”
“There is at least one x such that P(x).”

(Note: ∃x P(x) is either true or false, so it is a

proposition, but no propositional function.)

CSE 121: Discrete Mathematics 13

 Existential Quantification
Example:
P(x): x is a UMBC professor.
G(x): x is a genius.

What does ∃x (P(x) ∧ G(x)) mean ?

“There is an x such that x is a UMBC professor

and x is a genius.”
or
“At least one UMBC professor is a genius.”

CSE 121: Discrete Mathematics 14

 Quantification
Another example:
Let the universe of discourse be the real numbers.

What does ∀x∃y (x + y = 320) mean ?

“For every x there exists a y so that x + y = 320.”

Is it true? yes

Is it true for the natural numbers? no

CSE 121: Discrete Mathematics 15

 Disproof by Counterexample
A counterexample to ∀x P(x) is an object c so
that P(c) is false.

Statements such as ∀x (P(x) → Q(x)) can be

disproved by simply providing a counterexample.

Statement: “All birds can fly.”

Disproved by counterexample: Penguin.

CSE 121: Discrete Mathematics 16

 Negation

¬(∀x P(x)) is logically equivalent to ∃x (¬P(x)).

¬(∃x P(x)) is logically equivalent to ∀x (¬P(x)).

See Table 2 in Section 1.3.

This is de Morgan’s law for quantifiers

CSE 121: Discrete Mathematics 17

 Negation
Examples
Not all roses are red
¬∀x (Rose(x) → Red(x))
∃x (Rose(x) ∧ ¬Red(x))

Nobody is perfect
¬∃x (Person(x) ∧ Perfect(x))
∀x (Person(x) → ¬Perfect(x))

CSE 121: Discrete Mathematics 18

 Nested Quantifier
A predicate can have more than one variables.
– S(x, y, z): z is the sum of x and y
– F(x, y): x and y are friends
We can quantify individual variables in different
ways
– ∀x, y, z (S(x, y, z) → (x <= z ∧ y <= z))
– ∃x ∀y ∀z (F(x, y) ∧ F(x, z) ∧ (y != z) → ¬F(y, z)

CSE 121: Discrete Mathematics 19

 Nested Quantifier
Exercise: translate the following English
sentence into logical expression
“There is a rational number in between every
pair of distinct rational numbers”

Use predicate Q(x), which is true when x

is a rational number
∀x,y (Q(x) ∧ Q (y) ∧ (x < y) →
∃u (Q(u) ∧ (x < u) ∧ (u < y)))

CSE 121: Discrete Mathematics 20

 Summary, Sections 1.3, 1.4
• Propositional functions (predicates)
• Universal and existential quantifiers,
and the duality of the two
• When predicates become propositions
– All of its variables are instantiated
– All of its variables are quantified
• Nested quantifiers
– Quantifiers with negation
• Logical expressions formed by
predicates, operators, and quantifiers
CSE 121: Discrete Mathematics 21