CSCI 1900 Discrete Structures

Statement of Proposition
Statement of proposition – a declarative sentence that is either true or false, but not both
Examples:
The earth is round: statement that is true
2+3=5: statement that is true
Do you speak English? This is a question, not a statement

More Examples of Statements of Proposition
3-x=5: is a declarative sentence, but not a statement since it is true or false depending on the value of x
Take two aspirins: is a command, not a statement
The temperature on the surface of the planet Venus is 800oF: is a declarative statement of whose truth is unknown to us
The sun will come out tomorrow: a statement that is either true or false, but not both, although we will have to wait until tomorrow to determine the answer

Logical Connectives and Compound Statements
x, y, z, … denote variables that can represent real numbers
p, q, r,… denote prepositional variables that can be replaced by statements.
p: The sun is shining today
q: It is cold

Negation
If p is a statement, the negation of p is the statement not p
Denoted ~p
If p is true, ~p is false
If p is false, ~p is true
~p is not actually connective, i.e., it doesn’t join two of anything
not is a unary operation for the collection of statements and ~p is a statement if p is

Examples of Negation
If p: 2+3 >1 then If ~p: 2+3 <1
If q: It is cold then ~q: It is not the case that it is cold, i.e., It is not cold.

Conjunction
If p and q are statements, then the conjunction of p and q is the compound statement “p and q”
Denoted p∧q
p∧q is true only if both p and q are true
Example:
p: ETSU parking permits are expensive
q: ETSU has plenty of parking
p∧q = ?

Disjunction
If p and q are statements, then the disjunction of p and q is the compound statement “p or q”
Denoted p∨q
p∨q is true if either p or q are true
Example:
p: I am a male
q: I am under 40 years old
p∨q = ?

Exclusive Disjunction
If p and q are statements, then the exclusive disjunction is the compound statement, “either p or q may be true, but both are not true at the same time.”
Example:
p: It is daytime
q: It is night time
p∨q (in the exclusive sense) = ?

Inclusive Disjunction
If p and q are statements, then the inclusive disjunction is the compound statement, “either p or q may be true or they may both be true at the same time.”
Example:
p: It is cold
q: It is night time
p∨q (in the inclusive sense) = ?

Exclusive versus Inclusive
Depending on the circumstances, some disjunctions are inclusive and some of exclusive.
Examples of Inclusive
“I have a dog” or “I have a cat”
“It is warm outside” or “It is raining”
Examples of Exclusive
Today is either Tuesday or it is Thursday
Pat is either male or female

Compound Statements
A compound statement is a statement made from other statements
For n individual propositions, there are 2n possible combinations of truth values
A truth table contains 2n rows identifying the truth values for the statement represented by the table.
Use parenthesis to denote order of precedence
∧ has precedence over ∨

Truth Tables are Important Tools for this Material!

Compound Statement Example
(p ∧ q) ∨ (~p)

Quantifiers
Back in Section 1.1, a set was defined
{x | P(x)}
For an element t to be a member of the set, P(t) must evaluate to “true”
P(x) is called a predicate or a propositional function

Computer Science Functions
if P(x), then execute certain steps
while Q(x), do specified actions

Universal quantification of a predicate P(x)
Universal quantification of predicate P(x) = For all values of x, P(x) is true
Denoted ∀x P(x)
The symbol ∀ is called the universal quantifier
The order in which multiple quantifications are considered does not affect the truth value (e.g., ∀x ∀y P(x,y) ≡ ∀y ∀x P(x,y) )

Examples:
P(x): -(-x) = x
This predicate makes sense for all real numbers x.
The universal quantification of P(x), ∀x P(x), is a true statement, because for all real numbers, -(-x) = x
Q(x): x+1<4
∀x Q(x) is a false statement, because, for example, Q(5) is not true

Existential quantification of a predicate P(x)
Existential quantification of a predicate P(x) is the statement “There exists a value of x for which P(x) is true.”
Denoted ∃x P(x)
Existential quantification may be applied to several variables in a predicate
The order in which multiple quantifications are considered does not affect the truth value

Applying both universal and existential quantification
Order of application does matter
Example: Let A and B be n x n matrices
The statement ∀A ∃B A + B = In
Reads “for every A there is a B such that A + B = In”
Prove by coming up for equations for bii and bij (j≠i)
Now reverse the order: ∃B ∀A A + B = In
Reads “there exists a B such that for all A A + B = In”
THIS IS FALSE!

Assigning Quantification to Proposition
Let p: ∀x P(x)
The negation of p is false when p is true and true when p is false
For p to be false, there must be at least one value of x for which P(x) is false.
Thus, p is false if ∃x ~P(x) is true.
If ∃x ~P(x) is false, then for every x, ~P(x) is false; that is ∀x P(x) is true.

Okay, what exactly did the
previous slide say?
Assume a statement is made that “for all x, P(x) is true.”
If we can find one case that is not true, then the statement is false.
If we cannot find one case that is not true, then the statement is true.
Example: ∀ positive integers, n,
P(n) = n2 + 41n + 41 is a prime number.
This is false because ∃ an integer resulting in a non-prime value, i.e., ∃n such that P(n) is false.

Discrete Structures
Conditional Statements
Section 2.2

Conditional Statement/Implication
"if p then q"
Denoted p ⇒ q
p is called the antecedent or hypothesis
q is called the consequent or conclusion
Example:
p: I am hungry
q: I will eat
p: It is snowing
q: 3+5 = 8

Conditional Statement/Implication (continued)
In English, we would assume a cause-and-effect relationship, i.e., the fact that p is true would force q to be true.
If “it is snowing,” then “3+5=8” is meaningless in this regard since p has no effect at all on q
At this point it may be easiest to view the operator “⇒” as a logic operationsimilar to AND or OR (conjunction or disjunction).

Truth Table Representing Implication
If viewed as a logic operation, p ⇒ q can only be evaluated as false if p is true and q is false
This does not say that p causes q
Truth table

Examples where p ⇒ q is viewed as a logic operation
If p is false, then any q supports p ⇒ q is true.
False ⇒ True = True
False ⇒ False = True
If “2+2=5” then “I am the king of England” is true

Converse and contrapositive
The converse of p ⇒ q is the implication that q ⇒ p
The contrapositive of p ⇒ q is the implication that ~q ⇒ ~p

Converse and Contrapositive Example
Example: What is the converse and contrapositive of p: "it is raining" and q: I get wet?
Implication: If it is raining, then I get wet.
Converse: If I get wet, then it is raining.
Contrapositive: If I do not get wet, then it is not raining.

Equivalence or biconditional
If p and q are statements, the compound statement p if and only if q is called an equivalence or biconditional
Denoted p ⇔ q

Equivalence Truth table
The only time that the expression can evaluate as true is if both statements, p and q, are true or both are false

Proof of the Contrapositive
Compute the truth table of the statement
(p ⇒ q) ⇔ (~q ⇒ ~p)

Tautology and Contradiction
A statement that is true for all of its propositional variables is called a tautology. (The previous truth table was a tautology.)
A statement that is false for all of its propositional variables is called a contradiction or an absurdity

Contingency
A statement that can be either true or false depending on its propositional variables is called a contingency
Examples
(p ⇒ q) ⇔ (~q ⇒ ~p) is a tautology
p ∧ ~p is an absurdity
(p ⇒ q) ∧ ~p is a contingency since some cases evaluate to true and some to false.

Contingency Example
The statement (p ⇒ q) ∧ (p ∨ q) is a contingency

Logically equivalent
Two propositions are logically equivalent or simply equivalent if p ⇔ q is a tautology.
Denoted p ≡ q

Example of Logical Equivalence
Columns 5 and 8 are equivalent, and therefore, p “if and only if” q

Additional Properties
(p ⇒ q) ≡ ((~p) ∨ q)

Additional Properties
(p ⇒ q) ≡ (~q ⇒ ~p)

CSCI 1900
Discrete Structures
Methods of Proof
Reading: Kolman, Section 2.3

Past Experience
Up to now we’ve used the following methods to write proofs:
Used direct proofs with generic elements, definitions, and given facts
Used proof by cases such as when we used truth tables

General Description of Process
p ⇒ q denotes "q logically follows from p“
Implication may take the form (p1 ∧ p2 ∧ p3 ∧ … ∧ pn) ⇒ q
q logically follows from p1, p2, p3, …, pn

General Description (continued)
The process is generally written as:
p1
p2
p3
:
:
pn
∴q

Components of a Proof
The pi's are called hypotheses or premises
q is called the conclusion
Proof shows that if all of the pi's are true, then q has to be true
If result is a tautology, then the implication p ⇒ q represents a universally correct method of reasoning and is called a rule of inference

Example of a Proof based
on a Tautology
If p implies q and q implies r, then p implies r
p ⇒ q
q ⇒ r
∴p ⇒ r
By replacing the bar under q ⇒ r with the “⇒”, the proof above becomes ((p ⇒ q) ∧ (q ⇒ r)) ⇒ (p ⇒ r)
The next slide shows that this is a tautology and therefore is universally valid.

Tautology Example (continued)

Equivalences
Some mathematical theorems are equivalences, i.e., p ⇔ q.
The proof of such a theorem is equivalent with proving both p ⇒ q and q ⇒ p

modus ponens
form (the method of asserting):
p
p ⇒ q
∴q
Example:
p: a man used the toilet
q: the toilet seat is up
p ⇒ q: If a man used the toilet, the seat was left up
Supported by the tautology (p ∧ (p ⇒ q)) ⇒ q

modus ponens (continued)

Invalid Conclusions from Invalid Premises
Just because the format of the argument is valid does not mean that the conclusion is true. A premise may be false. For example:
Acorns are money
If acorns were money, no one would have to work
∴No one has to work
Argument is valid since it is in modus ponens form
Conclusion is false because premise p is false

Invalid Conclusion from Invalid Argument
Sometimes, an argument that looks like modus ponens is actually not in the correct form. For example:
If tuition was free, enrollment would increase
Enrollment increased
∴Tuition is free
Argument is invalid since its form is:
p ⇒ q
q
∴p

Invalid Argument (continued)
Truth table shows that this is not a tautology:

Indirect Method
Another method of proof is to use the tautology:
(p ⇒ q) ⇔ (~q ⇒ ~p)
The form of the proof is:
~q
~q ⇒ ~p
∴p

Indirect Method Example
p: My e-mail address is available on a web site
q: I am getting spam
p ⇒ q: If my e-mail address is available on a web site, then I am getting spam
~q ⇒ ~p: If I am not getting spam, then my e-mail address must not be available on a web site
This proof says that if I am not getting spam, then my e-mail address is not on a web site.

Another Indirect Method Example
Prove that if the square of an integer is odd, then the integer is odd too.
p: n2 is odd
q: n is odd
~q ⇒ ~p: If n is even, then n2 is even.
If n is even, then there exists an integer m for which n = 2×m. n2 therefore would equal (2×m)2 = 4×m2 which must be even.

Proof by Contradiction
Another method of proof is to use the tautology (p ⇒ q) ∧ (~q) ⇒ (~p)
The form of the proof is:
p ⇒ q
~q
∴~p