Transcript Lecture slides

Conceptual Foundations of
Computing
Lecture 1
Statements
A Statement (or proposition) is a sentence that is true or false but not both.
Compound Statements
Compound statements are made by joining simple statements together
using logical operators, like “not”, “and” and “or”.
Negation
If p is a statement variable, the negation of p is “not p” or “It is not the case
that p” and is denoted by ~p. It has opposite truth value from p: if p is true, ~p
is false; if p is false, ~p s true.
Conjunction
If p and q are statement variables, the conjunction of p and q is “p
and q”, donated by p Λ q. It is true when, and only when, both p
and q are true. If either p or q is false, or if both are false, p & q is
false.
Logic on Excel
Excel has logical functions. The following set of results for the “p and q” column
where generated using the table entry in cell C2 “= AND(A2,B2)” (and duplicating it
down the column.
Disjunction
If p and q are statement variables, the disjunction of p and q is “p or q”,
denoted by p V q. It is true when either p is true or q is true or both p and q are
true; it is false only when both p and q are false.
Evaluating Compound Statements
A statement form (or propositional form) is an expression made up of statement
variables (such as p, q, r) and logical connectives (such as ~, Λ and V) that becomes a
statement when actual statements are substituted for the component statement
variables. The Truth table for a given statement form displays the truth values that
correspond to all possible combinations of truth values for its component statement
variables.
Example “Exclusive Or” (XOR)
Truth Table for (p Λ q) V ~r
Exercise
Extend pervious truth table…
Develop a column for (p Λ q) V (p Λ ~r) and a column for p Λ (q V ~r).
Notice anything about these two columns?
Logical Equivalence
Two statement forms are called logically equivalent if, and only if, they have identical
truth values for each possible substitution of statements for their statement variables.
The logical equivalence of statement forms P and Q is denoted by writing P  Q
.
Two statements are called logically equivalent if, and only if, they have logically
equivalent forms when identical component statements variables are used to replace
identical component statements.
Logical Equivalence Example
The Distributed laws (page 14 of Textbook) tell us that:
p Λ (q V r) ≡ (p Λ q) V (p Λ r)
p V (q Λ r) ≡ (p V q) Λ (p V r)
And, consequently (substituting ~r for r):
p Λ (q V ~r) ≡ (p Λ q) V (p Λ ~r)
Double negative Property: ~ (~ p)  p
Two negatives make a positive:
“I was not absent”
(-1) * (-1) = 1
Showing Nonequivalence
De Morgan’s Laws
The negation of an and statement is logically the equivalent to the or statement
in which each component is negated.
~(p Λ q) ≡ ~p V ~q
The negation of an or statements is logically equivalent to the and statement in
which each component is negated.
~(p V q) ≡ ~p Λ ~q
One of De Morgan’s Laws
Tautologies and Contradictions
A tautology is a statement form that is always true regardless of the truth values
of the individual statements substituted for its statement variables. A statement
whose form is a tautology is a tautological statement.
A contradiction is a statement form that is always false regardless of the truth
values of the individual statements substituted for its statement variables. A
statements whose form is a contradiction is a contradictory statement.
Logical Equivalence Involving T and C
Simplifying Statement Forms
~ (~ p  q)  ( p  q)  (~ (~ p) ~ q)  ( p  q) by De Morgan's Theorem
 ( p  ~ q )  ( p  q)
by the double negative law
 p  (~ q  q)
 p  ( q  ~ q)
 pc
by the distributive law
by the commutative law for 
by the negation law
p
by the identity law
This is logic’s equivalent of simplifying maths problems:
x = 6(y + 5) + 2
= (6y + 30) + 2
= 6y + 32
Conditional Statements
Introduction
When you make a logical inference or deduction, you reason from a
hypothesis to a conclusion. Your aim is to be able to say,
“If such and such is known, then something or other must be the case.”
If 4,686 is divisible by 6 then, 4,686 is divisible by 3.
We can do this because we Know that 6 = 2 * 3.
Example
“If you show up for work on Monday, then you
will get the job”.
• When is this statement false?
• When do you get the job?
• What happens if you do not turn up? Is the
statement true or false if you do not show?
Conditional Statements
If p and q are statement variables, the “conditional of p by q” is “if p then q” or “p
implies q” and is donated by p → q. It is false when p is true and q is false;
otherwise it is true. We call p the hypothesis (or antecedent) of the conditional and
q the conclusion (or consequent).
Conditional Statements
From page 18 of the Textbook:
A conditional statement that is true by virtue of the fact that its hypothesis is false is
often called vacuously true or true by default. Thus the statement “If you show up
for work on Monday morning, then you will get the job” is vacuously true if you do
not show up for work on Monday.
Logical Equivalences involving →
Suppose you know the truth of r follows from the truth of p and also follows from
the truth of q. Then no matter whether p or q is the case, the truth of r must follow.
The “division into cases” method of analysis (simplification?) is based upon this idea.
p  q  r  ( p  r )  (q  r )
IF-Then as Or
If then statements can be rewritten in terms of not and or operators:
p q  ~ pq
Negation of a Conditional Statement
The negation of “If p then q” is logically equivalent to “p and not q”.
~ ( p  q)  p  ~ q
Also working symbolically.
We start with
p q  ~ pq
and negate both sides
~ ( p  q )  ~ (~ p  q )
 ~ (~ p )  (~ q )
 p ~q
The Contrapositive of a CS
The contrapositive of a conditional statement of the form “If p then q” is
If ~q then ~p
Symbolically,
the contrapositive of p
→
q
is ~q
→
~p
A conditional statement is logically equivalent to its contrapositive:
p
→
q ≡ ~q
→
~p
Converse and Inverse
Suppose a conditional statement of the form “If p then q” is given.
The converse of this statement is “If q then p”.
The inverse of this statement is “If ~p then ~q”.
Symbolically,
the converse of p
the inverse of
p
→
→
q
is
q
q
is ~p
→
→
p
~q
Exercise: Are these statements logically equivalent?
Converse and Inverse
contrapositive: p
converse: p
inverse:
p
→
→
→
q ≡ ~q
→
~p
q
is not logically equivalent to
q
q
is not logically equivalent to ~p
→
→
p
~q
It is a common mistake to read a conditional statement as its converse.
To pass this course you must pass the exam.
p: pass the course
q: pass the exam
p→ q
If you pass the course then you must (have) pass(ed) the exam.
A student may mistakenly take the statement to mean:
q→ p
If you pass the exam then you pass the course.
However, there may be other conditions that must be met to pass the course.
Only If and the Biconditional
“p if q” means:
p is True if q is True
if q then p
q→ p
“p only if q” means:
p is True only if q is True
if ~q then ~p
~q → ~p
p→ q
(contrapositive)
“p if and only if q” means:
“p if q” and “p only if q”
(q → p) ˄ (p → q)
also known as biconditional of p and q
p↔ q
Biconditional, Converse and Inverse
A conditional statement with form p → q, like “you pass the course only if you pass
the exam”, may mistakenly read as the biconditional statement p ↔ q, “you pass
the course if and only if you pass the exam”.
The biconditional “p if an only if q” is (q → p) ˄ (p → q).
If this statement is True, then the following statements are all True:
p→ q
q → p (converse of p → q)
~p → ~q (inverse of p → q; contrapositive of q → p)
Reading a conditional statement as a biconditional can result in the statement
being represented by its converse.
Note: We will study methods of valid argument (deducing new True statements
from a set of given True statements) next week.
Precedence of Logical Operators
The five logical operators have the following precedence (order of application).
Remember to use brackets() to change this order.
1.
~
2. Λ, V
3.
→, ↔
Evaluate “negation” first
Evaluate “and” and “or” second
Use brackets when both are present.
Evaluate “conditional” and “biconditional” third.
Use brackets when both are present.
Necessary and Sufficient Conditions
In mathematics and computing we often talk about necessary and sufficient
conditions.
p is a sufficient condition for q
means
“If p then q”.
p is a necessary condition for q
means
“if not p then not q”.
~p → ~q
q → p (contrapositive)
“if q then p”
passing the exam is a necessary condition for passing the course
to pass the course you must pass the exam
p is a necessary and sufficient condition for q
means “if p then q” and “if q then p”
this is the biconditional of p and q: p ↔ q
Something to think about…
p: It is Wednesday.
q: It is raining.
If p is False, what is the value of p → q ?
p → q is only False when p is True and q is False.
So, if p is False, p → q is True.
So, “It is Wednesday implies it is raining.” is True?
Do you feel comfortable about that?
More on this next week.