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:
Which of the following are propositions? If they are, what are their truth values?
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.
|p||q||p → q||p ↔ q|
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.
Which of the following statements are correct?
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.
Match the following propositions and terms
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.
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.
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.
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.
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).
Let P(x) be "2x is even".
Statements with a for all can be easily proved false by showing one counter example: a value in D for which P is false.
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.
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.
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.
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?