cs122

Tutorial 2 Propositions and Predicates

Propositions

Related Chapter: Study Rosen 1.1

A proposition is a statement with a Boolean or truth (False or True, F or T, O or 1) value. The following are examples of propositions:

The grass is green
It is raining
The grass is wet

Propositional variables, such as p, q, r..., represent propositions and take truth values. A truth table has columns with truth values for propositional variables and propositions. In truth tables we will make true = 1 and false = 0, and we will always order the rows of our tables in increasing (lexicographical) order of the propositional variables:

pqp∧q
000
010
100
111
In the truth table above the first two columns have propositional variables p and q and the third has the proposition p∧q.

Quick Test

Which of the following are propositions? If they are, what are their truth values?

1. Do not pass go.
Not a proposition
A Proposition, false
A proposition, true

2. What time is it?
Not a proposition
A Proposition, false
A proposition, true

3. There are no black flies in Maine.
Not a proposition
A Proposition, false
A proposition, true

4. The moon is made of green cheese
Not a proposition
A Proposition, false
A proposition, true

5. 2n >= 100
Not a proposition
A Proposition, false
A proposition, true

So, a proposition variable is an identifier that can take truth values. A compound proposition is an expression in proposition variables, truth values and logical operators (∧, ∨, ¬, →, ↔, ⊕). A tautology is a compound proposition that is always true (true for all combinations of values of the variables). A contradiction is always false. A compound proposition is satisfiable if there is at least one truth assignment to the variables that makes the proposition true.

Conditional and Biconditionals

pqp → qp ↔ q
0011
0110
1000
1111

p → q stands for "if p then q" or "p implies q". p → q is only false when p=true and q=false!

Think of it like this: if it is raining (p) the grass is wet (q), so p = true and q = true makes p → q true. If it is not raining (¬p) the grass can be wet (Q) e.g. because we are sprinkling the lawn or the grass can be dry (¬ q), so p = false makes p → q true no matter what the truth value of q is. It is raining (p) and the grass is not wet (¬q) is the only case that makes p → q false. This may seem unintuitive at first. Still it is very important to get familiar with this. Check that ¬ p ∨ q has the same truth table as p → q.

p ↔ q stands for "p if and only if q", or "if p then q and conversely", notation: p iff q.

Quick Test

Which of the following statements are correct?

6. The biconditional p ↔ q is the proposition "p if and only if q"
Yes
No

7. The biconditional p ↔ q is true when p and q have the same truth values
Yes
No

8. The biconditional p ↔ q is the same as "if p then q"
Yes
No

9. The biconditional p ↔ q means "if p then q and conversely"
Yes
No

Equivalences

Related Chapter: Rosen 1.2

A tautology is a proposition that is always true (whatever the truth values of its variables). For instance, p ∨ ¬p is a tautology. A contradiction is always false whatever the truth values of its variables. For instance, p ∧ ¬p is a contradiction. A contingency is neither a tautology nor a contradiction, for instance p ∨ q is a contingency. A proposition is satisfiable if there is at least one truth assignment to its variables that makes it true. For instance p=true and q=false makes p ∨ q true, so p ∨ q is satisfiable.

Quick Test

Match the following propositions and terms

10. p ∨ q → p
Tautology
Contradiction
Contingency

11. (p ∧ q) → p
Tautology
Contradiction
Contingency

12. p ^ false
Tautology
Contradiction
Contingency

13. Is p ∨ q → p satisfiable?
no
yes

14. Is (p ∧ q) → p satisfiable ?
no
yes

15. Is p ^ false satisfiable?
no
yes

Two compound propositions p and q are equivalent, notation p ≡ q, if p ↔ q is a tautology, in other words if their truth tables are equivalent.

Self Check

Show by truth table that p → q ≡ ¬p ∨ q

This is a very important equivalence, it allows you to remove implication from a proposition and turn it into an expression with not and or. Study Rosen 1.2 tables 6,7, and 8 to learn a number of useful equivalences.

Predicates

Study Rosen 1.3 and the lecture notes "PropositionsPredicates"

Propositions are truth valued expressions where the constituents are truth valued variables, Boolean values (T and F) and Boolean operators. Not all logical statements can be expressed using propositions. Examples are

There is an x > 0 divisible by 15

Everybody loves somebody

x > 5

A predicate refers to a property applied to (a number of) subjects or variables. In x>5 the property is "is greater than 5", the variable is "x". Formally we say "let P(x) denote x>5". Once a value has been assigned to the variable(s), the statement P(x) gets a truth value.

Quick Check

Let R(x,y) denote "x beats y in Roshambo" (rock sissors paper: rock smashes scissors, scissors cuts paper, paper covers rock). What are the truth values for

16. R(paper,rock)
F
T

17. R(paper,scissors)
F
T

18. R(scissors, rock)
F
T

Preconditions and postconditions in programs are predicates. They can be used to verify the correctness of a program. Our programming practice is to state, using predicates in terms of the program variables, that "if predicate PRE is true before a program fragment is executed, then predicate POST will be true after that fragment is executed".

This allows us to separate concerns and concentrate on one part of the program at the time. In the case of a method, the PRE POST pair is a form of a contract that the method has with its callers: if the caller makes PRE true, then the called method makes POST true after its execution. Notice that if PRE is not true, anything can happen. This is exactly what implication means: if PRE is true, then POST must be true, if PRE is false, then POST can be true or false.

Quantifiers

Quantifiers express a range of elements for which a predicate holds. In English we use phrases like "all", "there is", "some" etc., as in "all people are mortal", "some people like bananas", etc.

In logic we use essentially two forms: "there is" and "for all" (that we can negate (later)). A domain D is the range of values that a variable can take. D is sometimes called the domain of discourse. For programming, useful domains are boolean, char, int, float, double, i.e. the primitive data types of our programming language.

Universal quantifier: ∀ x ∈ D P(x) means: for all x in domain D, P(x) is true.

Existential qantifier: ∃ x ∈ D P(x) means: there is an x in domain D, such that P(x) is true. When we write P(x) without a quantifier in front of it we mean ∀ x ∈ D P(x).

Quick Check

Let P(x) be "2x is even".

19. For which domain is P true?
The real numbers
The integers

Counter Examples

Statements with a for all can be easily proved false by showing one counter example: a value in D for which P is false.

Quick Check

Let D be the domain R: the real numbers.

20. Which values provide a counter example for: ∀ x ∈ D x≥0
-15.5
0

Where it is easy to show the falsehood of a predicate with a universal quantifier by giving one counter example, it is easy to show that a predicate with an existential quantifier is true, by giving one example.

Quick Check

21. Which of the following are valid examples for: ∃ x ∈ Z x2>x
1
2.5
3

Logical equivalences involving quantifiers

Statements involving predicates and quantifiers are (logically) equivalent iff (remember iff)? It means if and only if or ↔) they have the same truth value no matter which predicates are substituted into these statements or which domain of discourse is used for the variables. Notation S ≡ T. The following equivalence is discussed in example 19, Rosen 1.3.: ∀x(P(x) ∧ Q(x)) ≡ ∀x P(x) ∧ ∀x Q(x))

Study the equivalences in the slides.

Equivalences and negations

There are two important equivalences involving negations:

1. ¬ ∀x P(x) ≡ ∃ x ¬ P(x)

In words: if it is not true that for all x P(x) holds, then there is an x for which not P(x) holds.

2. ¬ ∃x P(x) ≡ ∀ x ¬ P(x)

In words: if there is no x for which P(x) holds, then for all x not P(x) holds.

Quick Check

What is the negation of the following statement?

22. "All Americans eat cheeseburgers"
No Americans eat cheeseburgers
There is an American who does not eat cheeseburgers
All Americans eat no cheeseburgers

Be careful with English versions of these equivalences and predicates when negations are used. What for instance is meant by: "nothing is too much for my little darling"?

Are you ready to take quiz 2?