# MACM 101 Lecture 8: Lecture 8

15 views2 pages
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 (distribung ˥ over ˄)
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 contradicon.
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
Unlock document

This preview shows half of the first page of the document.
Unlock all 2 pages and 3 million more documents.

# Get access

\$10 USD/m
Billed \$120 USD annually
Homework Help
Class Notes
Textbook Notes