Week 1 Lecture 2 (Fri) - Logically correct arguments in propositional logic Flashcards
What makes an argument logically correct?
If in every situation that makes all premises true, the conclusion is true as well.
What is a situation?
a row in the truth table of p1,p2,…,pn,q
How can we conclude an argument as incorrect?
find one situation where all premises are true, but the conclusion is false.
Why are rules of inference convenient?
Sometimes truth tables can be long/excessive/take time to draw out. These rules establish the correctness of some simple argument forms.
When “x>3”, P(x), what do the “P” and “x” represent?
P is the predicate (property) “greater than 3” and x is the variable.
When does P(x) become a proposition?
By assigning a value (a concrete entity) to its variable, P (x) becomes a proposition that has a truth value.
How would you formalize formalise a statement like “x = y + 4”? How would you describe this predicate?
Q(x,y) - x and y are the variables, Q is the predicate joining two variables. Q is a binary predicate.
What are the two ways of forming a proposition from a predicate P(x)?
- assigning a concrete value to x
2. Quantification.
What is Quantification?
Quantification expresses the extent to which a predicate is true over a range of entities, called the domain.
How do you denote the universal quantification of P (x) for a particular domain?
∀xP(x).
What is the universal quantification of P(x)?
“P (x) is true for all values of x from the domain.”
What happens to truth value of ∀x P (x) is we change the domain?
It might also change.
universal instantiation:
For each and every entity c in the domain we have a correct inference rule of the form
How do you denote existential quantification of P (x) for a particular domain?
∃x P (x).
What does ∃x P (x) mean?
The proposition “there exists a value for x in the domain such that P (x) is true.”
When do you call a proposition a theorem?
When a proposition can be shown true and important enough.
What is a proof of theorem t?
A proof of a theorem t is a sequence of propositions ending with t such that each and every of the premises is
• either an axiom (= a proposition whose truth we simply assume),
• or can be obtained from earlier premises in the sequence by a logically
correct argument.
What is an axiom?
A proposition whose truth we simply assume.
What do many theorems assert?
Many theorems assert that a property holds for all entities in a domain,
such as the integers or the natural numbers
What is a conjecture?
A statement many believe to be true, but so far nobody can find proof for.
examples of conjectures include:
The Goldbach and Collatz conjectures
Step by step of general direct proof:
This technique is used to prove theorems of the form ∀x A(x) → B(x):
• First, we choose an arbitrary entity from the domain. It is important that this
entity is indeed arbitrary, meaning we do not use any specifics about it.
No matter what is the domain, we need to use some ‘pointer’ to refer to this chosen entity. We can denote it with whatever symbol we want: c, x, ⋆, , . . .
• Then, we prove the conditional statement A → B for this arbitrary by a direct proof:
We assume that A is true, and use axioms, definitions, and previously proven theorems, together with rules of inference, to show that then B must also be true.
• Then we apply the rule of universal generalisation: (cf. lecture slide 41)
FOR EXAMPLE: Theorem: “If n is an odd integer, then n2 is odd.” Give proof:
Proof: Let n be an arbitrary integer, and assume that n is odd. By the definition of being odd, n = 2k+1 for some integer k. So n2 = (2k + 1)2 = 4k2 + 4k + 1 = 2(2k2 + 2k) + 1. As 2k2 + 2k is an integer, by the definition of being odd, it follows that n2 is odd.
EXERCISE: Show that at least 4 of any 22 dates in the calendar must fall on the same day of the week.
proof by contradiction -
Let p be: “At least 4 of 22 chosen dates fall on the same day of the week.” Suppose that ¬p is true. This means that at most 3 of the 22 dates fall on the same day of the week. Because there are 7 days of the week, this implies that at most 21 dates could have been chosen, as for each of the days of the week, at most 3 of the chosen dates could fall on that day. This contradicts the premise that we have 22 dates under consideration. That is, if q is the statement that 22 dates are chosen, then we have shown that ¬p → (q ∧ ¬q) is true.
