13 Aug 2016

School

Department

Course

Professor

Any logical expression can be written as an equivalent expression in terms of only the symbols ¬,˅,˄.

In fact, we don’t even need ˄. Suppose I conducted a survey of some of the students in MACM.

Consider all of the male students with black hair. I gave the survey to anyone who did not fit this

description.

Let p(x) : x is a male

q(x) : x has black hair

I gave the survey to x, when ˥(p(x) ˄ q(x)) is true. Is there another way to express ˥(p(x) ˄ q(x)) using

only ˥ and ˅.

˥p(x) ˅ ˥q(x)

If we didn't want males with black hair, then who did we want? We wanted anybody who was not

male OR who didn't have black hair i.e. ˥p(x) ˅ ˥q(x)

These two expressions amount to the same thing, truth value for truth value. Wherever all of the

truth values match like this, they are said to be logically equivalent.

˥(p(x) ˄ q(x)) <=> ˥p(x) ˅ ˥q(x) [ <=> : "logically equivalent to" ]

Which is DeMorgan's Law (distribung ˥ over ˄)

Negating both sides, we get

p(x) ˄ q(x) <=> ˥(˥p(x) ˅ ˥q(x))

Which is a rule to replace ˄ by ˥ and ˅.

Truth Tables

Suppose we want to determine how a logical expression behaves, depending on the truth values of

its inputs (p + q). A truth table shows the truth value of the expression for all possible combinations

of inputs.

p

q

˥p

˥q

p˄q

p˅q

p(+)q

p->q

˥(p˄q)

˥p˅˥q

0

0

1

1

0

1

0

1

1

1

0

0

0

0

0

1

0

0

0

1

0

1

1

1

0

1

1

0

1

1

0

1

1

1

1

0

1

1

1

0

Definition: Two expressions are logically equivalent exactly when their columns in the truth table

are identical. Furthermore, an expression which evaluates to true for every set of inputs is called

tautology. Similarly, if false for every input, then it’s a contradiction. But if it is neither a tautology

nor a contradiction, it’s a contingency.

In Grimaldi, tautology and contradiction are denoted by T0and F0

E.g. Show that p˅˥p is a tautology while p˄˥p is a contradicon.

Solution: truth table

P

˥p

p˅˥p

p˄˥p

0

1

1

0

Lecture 8

January 22, 2016

10:30 AM

Lecture Notes Page 1