Week 1 Lecture 2 (Fri) - Logically correct arguments in propositional logic

Question 1

What makes an argument logically correct?

Answer 1

If in every situation that makes all premises true, the conclusion is true as well.

Question 2

What is a situation?

Answer 2

a row in the truth table of p1,p2,…,pn,q

Question 3

How can we conclude an argument as incorrect?

Answer 3

find one situation where all premises are true, but the conclusion is false.

Question 4

Why are rules of inference convenient?

Answer 4

Sometimes truth tables can be long/excessive/take time to draw out. These rules establish the correctness of some simple argument forms.

Question 5

When “x>3”, P(x), what do the “P” and “x” represent?

Answer 5

P is the predicate (property) “greater than 3” and x is the variable.

Question 6

When does P(x) become a proposition?

Answer 6

By assigning a value (a concrete entity) to its variable, P (x) becomes a proposition that has a truth value.

Question 7

How would you formalize formalise a statement like “x = y + 4”? How would you describe this predicate?

Answer 7

Q(x,y) - x and y are the variables, Q is the predicate joining two variables. Q is a binary predicate.

Question 8

What are the two ways of forming a proposition from a predicate P(x)?

Answer 8

1. assigning a concrete value to x

2. Quantification.

Question 9

What is Quantification?

Answer 9

Quantification expresses the extent to which a predicate is true over a range of entities, called the domain.

Question 10

How do you denote the universal quantification of P (x) for a particular domain?

Answer 10

∀xP(x).

Question 11

What is the universal quantification of P(x)?

Answer 11

“P (x) is true for all values of x from the domain.”

Question 12

What happens to truth value of ∀x P (x) is we change the domain?

Answer 12

It might also change.

Question 13

universal instantiation:

Answer 13

For each and every entity c in the domain we have a correct inference rule of the form

Question 14

How do you denote existential quantification of P (x) for a particular domain?

Answer 14

∃x P (x).

Question 15

What does ∃x P (x) mean?

Answer 15

The proposition “there exists a value for x in the domain such that P (x) is true.”

Question 16

When do you call a proposition a theorem?

Answer 16

When a proposition can be shown true and important enough.

Question 17

What is a proof of theorem t?

Answer 17

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.

Question 18

What is an axiom?

Answer 18

A proposition whose truth we simply assume.

Question 19

What do many theorems assert?

Answer 19

Many theorems assert that a property holds for all entities in a domain,
such as the integers or the natural numbers

Question 20

What is a conjecture?

Answer 20

A statement many believe to be true, but so far nobody can find proof for.

Question 21

examples of conjectures include:

Answer 21

The Goldbach and Collatz conjectures

Question 22

Step by step of general direct proof:

Answer 22

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)

Question 23

FOR EXAMPLE: Theorem: “If n is an odd integer, then n2 is odd.” Give proof:

Answer 23

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.

Question 24

EXERCISE: Show that at least 4 of any 22 dates in the calendar must fall on the same day of the week.

Answer 24

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.