İnteraktif Dersler

Logic and reasoning: connectives and quantifiers

Lecture notes

Definition

A statement

A statement is a sentence that is either true or false, never both. A question or a command is not a statement. Letters like and stand for statements.
Example
“7 is prime” is true and “9 is prime” is false, so both are statements. “Is 9 prime?” and “Write 9” are not.
Definition

AND: both must be true

(p AND q) is true only when both parts are true. In an algorithm it is a condition that an object passes only when it passes both tests.
2481039612pq
Example
Numbers 1 to 12: “even AND a multiple of 3” is true for 6 and 12 only, so for 2 numbers.
Definition

OR: at least one is true

(p OR q) is true when at least one part is true, also when both are. This “inclusive or” is the one used in logic and in algorithms.
2481039612pq
Example
Numbers 1 to 12: “even OR a multiple of 3” is true for 2, 3, 4, 6, 8, 9, 10 and 12: 8 numbers.
Definition

EITHER … OR: exactly one

Either or , written , is true when exactly one part is true, not both. It is the “or” of “tea or coffee” on a menu.
2481039612pq
Example
Numbers 1 to 12: “either even or a multiple of 3” is true for 2, 3, 4, 8, 9, 10: 6 numbers. The numbers 6 and 12 are left out.
Definition

IF … THEN

(IF p THEN q) is false in one case only: true and false. When is false the statement says nothing and counts as true.See also "Hence: what follows from a rule and a fact".
26104812pq
Example
“If a number is a multiple of 4, then it is even.” Of the numbers 1 to 12 only a multiple of 4 that is odd could break it, and there is none: the statement is true for all 12 numbers.
Definition

NOT: turns the value round

(NOT p) is true when is false and false when is true. Put NOT in front of a test to count the objects that fail it.
Example
“The number is even” is false for 7, so “NOT even” is true for 7. Among 1 to 12, NOT even gives 6 numbers: 1, 3, 5, 7, 9, 11.
Definition

Every, some, no

A quantifier says how many objects must pass a test. Every () means all of them. Some () means at least one, not “several”. No means none: not one object passes.
Example
List 2, 4, 6, 9. “Every number is even” is false (9 is not). “Some number is even” is true (2 is). “No number is even” is false.
Rule

A but not B

“ but not ” is : the object must pass the first test and fail the second. Do not write only and forget .
423pq
Example
A class of 12: 7 play chess, 5 have a bike, 3 do both. Chess but no bike: pupils.
Rule

Counting with AND and OR

To count with OR, add the two groups and take the overlap off once, because the pupils who do both were counted twice.
423pq
Example
12 pupils: 7 chess, 5 bike, 3 both. Chess OR bike: pupils. Neither: .
Rule

AND in an algorithm

The connective is the condition of the if inside a loop (for each takes the objects one by one). For AND the object goes through two decisions in a row, and one no sends it out.if (p AND q) then count ← count + 1
nn%2=0?n%3=0?c=c+1✔✔✘✘
Example
Numbers 4, 6, 7, 12, 15: “even AND a multiple of 3” keeps 6 and 12, so count = 2.
Rule

OR in an algorithm

For OR two roads lead to the same step: a yes at the first decision adds 1 at once, a no goes on to the second decision. The object counts once, even when both say yes.if (p OR q) then count ← count + 1
nn%2=0?n%3=0?c=c+1✘✔✔✘
Example
Numbers 4, 6, 7, 12, 15: “even OR a multiple of 3” keeps 4, 6, 12 and 15, so count = 4.
Rule

Counterexample and witness

One counterexample is enough to show that “every” is false. One witness is enough to show that “some” is true. To show the opposite you must check all the objects.
Example
“Every number in 3, 5, 7, 9 is prime.” Counterexample: , so the statement is false. “Some number in the list is even” has no witness, so it is false.
Rule

Loops for every and some

Every: start with a flag ok ← true and set it to false at the first object that fails; the loop can stop there. Some: start with found ← false and set it to true at the first object that passes; the loop can stop there.
Example
List 4, 6, 7, 10 and the statement “every number is even”:ok ← true. The number 4 passes, 6 passes, 7 fails: ok ← false, stop.print ok → false
Rule

Negating every and some

The negation turns “every” into “some … not” and “some” into “no”: the quantifier and the test are turned round.
Example
“Every pupil has a bike” becomes “At least one pupil has no bike”, not “No pupil has a bike”.
Rule

De Morgan’s laws

NOT turns AND into OR and OR into AND, and each part gets its own NOT.See also "The symbols ∧ ∨ ¬ ⇒ ⇔ and their order".
15273pq
Example
Days 1 to 7: lessons on 1, 3 and 5, cleaning on 2, 3 and 7. NOT (lesson AND cleaning) is true on 6 days, all except day 3. “No lesson OR no cleaning” gives the same 6 days.
Rule

Words, symbols, algorithm

One statement can be written in three languages: words, symbols and an algorithm. Symbols are short and have one meaning only; the algorithm shows how to check. for every, there is at least one, and, or, not, if … then.
Example
Words: every number in the list L is even.Symbols: , where means x is evenAlgorithm: ok ← true; for each x in L: if x is not even then ok ← false; print ok
Rule

The symbols ∧ ∨ ¬ ⇒ ⇔ and their order

Logic writes for and, for or, for not, for if … then and for if and only if. Without brackets the order is first, then , then , then , and last. When in doubt, use brackets. The tab Truth table of "Logic symbols: ∧ ∨ ¬ ⇒ ⇔ and truth tables" shows how your formula is read.
pTTTTFFFFqTTFFTTFFrTFTFTFTFp ∨ (q ∧ r)TTTTTFFF(p ∨ q) ∧ rTFTFTFFF
Example
is read as . That reading is true in 5 of the 8 rows; the reading is true in 3 rows. The two readings differ in 2 rows (lit in the table), for example for true with and false.
Definition

⇒ and ⇔: if … then, and if and only if

The implication is false only when is true and is false; it says the same as . The equivalence is true when and have the same value; it says and also . Two formulas say the same when is true in every row. In the tab Same or different you type two formulas and see the rows where they differ.
pTTFFqTFTFp ⇒ qTFTT¬p ∨ qTFTTp ⇔ qTFFT
Example
is true in 3 of the 4 rows and in 2 rows. The columns of and are the same, so these two formulas say the same.
Rule

A proof for every odd number

Algebra covers every odd number at once. An odd number is , so , which is odd again. This proves “the square of every odd number is odd”, which no list of checked numbers can do.See also "A reasoning: starting points, steps and conclusion".
Example
: and . The algorithm that checks 3, 5, 7 gives true, but only the algebra says something about 9, 11, 13 and every other odd number.
Rule

Hence: what follows from a rule and a fact

A conclusion follows from a rule and a fact only when it is true in every row where the rule and the fact are both true. Two steps are valid: from and to , and from and to . Two are mistakes: from to , and from to . In the tab A rule and a fact of "If … then … hence: what follows?" the application strikes the rows that the rule and the fact rule out.
pTTFFqTFTFp ⇒ qTFTTqTFTFpTTFF
Example
Rule: if it rains, the match is off. With the fact "the match is off" the rule and the fact are both true in 2 of the 4 rows: it rains in one of them and not in the other, so nothing follows about the rain. With the fact "it rains" only one row is left, and the match is off in it: the match is off follows.
pTTFFqTFTFp ⇒ qTFTTpTTFFqTFTF
Definition

Sufficient and necessary conditions

is a sufficient condition for when : every case with has . is a necessary condition for when : no case has without . If both hold, . Look for counterexamples: a case with but not breaks "sufficient", a case with but not breaks "necessary". Try the tab Numbers of "Necessary or sufficient?".
24810612AB
Example
For the numbers 1 to 30, is "a multiple of 6" (5 numbers) and is "even" (15 numbers). Every multiple of 6 is even, so is sufficient for . But 2 is even and not a multiple of 6 (10 even numbers are not), so is not necessary; is a necessary condition for .
Watch out!

Do not turn a condition round

"If then " and "if then " are two different sentences. When , then ; but does not make , because works too. Turning a rule round is the most common mistake with conditions. Test both sentences, one at a time, with a counterexample.
Example
The street is wet when it rains, so "it rains" is sufficient for "the street is wet". A wet street does not show that it rained: a street cleaner can wet it too (a counterexample). So "it rains" is not necessary for a wet street.
Definition

A reasoning: starting points, steps and conclusion

A reasoning is a list of lines. A starting point is a line you begin with; a definition is a starting point that says what a word means. A reasoning step is a line that follows from lines above it, and the conclusion is the last step. In the tab Take it apart of "Reasoning steps: starting points, steps and conclusion" every line gets its role and you see which lines it uses.
1If it rains, the match is off.starting point2It rains.starting point3So the match is off.conclusion← 1, 2small step
Example
The reasoning of the picture has 2 starting points (lines 1 and 2) and 1 reasoning step: line 3, which is the conclusion. It uses lines 1 and 2: from "if then " and it follows that .
Rule

Correct, complete and incomplete

A reasoning is correct when every step follows from the lines it uses. It is complete when every step is small enough to see at once. If a step jumps over a missing step, or cites too few lines, the reasoning is incomplete: nothing in it is wrong, but a step is left out. If a step does not follow, the reasoning is not correct. In Judge a reasoning every step gets its kind.
1If it rains, the match is off.starting point2If the match is off, we stay in.starting point3It rains.starting point4So we stay in.conclusion← 1, 2, 3a jump
Example
From "if it rains, the match is off", "if the match is off, we stay in" and "it rains", the step to "we stay in" cites 3 lines: it is a jump, so the reasoning is correct but incomplete. Add the step "so the match is off" (from lines 1 and 3): now every step cites at most 2 lines and the reasoning is correct and complete.
1If it rains, the match is off.starting point2If the match is off, we stay in.starting point3It rains.starting point4So the match is off.step← 1, 3small step5So we stay in.conclusion← 2, 4small step
Watch out!

A step that does not follow

A step is wrong when the lines it uses can all be true while the step itself is false. Check it with the rows of a truth table. A wrong step can still end in a true statement by luck, and a correct reasoning from a false starting point can end in a false one: correct is about the steps, true is about the starting points. The tab My own reasoning judges up to five lines that you type.
1If it rains, the match is off.starting point2The match is off.starting point3So it rains.conclusion← 1, 2does not follow
Example
From "if it rains, the match is off" and "the match is off" it does not follow that it rains. In the row with (it rains) false and (the match is off) true, both lines above are true and the conclusion is false: the row is .
Definition

Contradiction

A contradiction is a statement that is false in every row, like , or statements that cannot all be true together. To test statements, make a truth table with a column for every statement and look for a row where all of them are true. If there is none, they clash. In Statements that clash you type up to four statements; the application names the smallest group that cannot be true together.
pTFp ∧ ¬pFF
Example
, and cannot all be true: there are 0 rows of the 4 where all three are true. The clash needs the whole group of three: any two of them can be true together.
Definition

Paradox

A paradox looks acceptable but ends in a clash. A sentence about itself can have no value that fits: if says "this sentence is false", then , where means " is true", and no value of makes that true. A hidden mistake gives another kind: in the "proof" of 2 = 1 one line divides by , which is 0. A truth-teller, "this sentence is true", is not a paradox, because both values fit. The tab Paradoxes shows four classics.
pTF¬pFTp ⇔ ¬pFF
Example
For the liar, is true in 0 of the 2 rows, so no value fits. The truth-teller is true in both rows. In the "proof" of 2 = 1 with the first false line is line 5, , which says 6 = 3: it divided by .
pTFp ⇔ pTT
Tip

Test the four rows

Not sure about a connective? Write the four rows TT, TF, FT, FF of and and work out the statement in every row. Two statements that give the same four results are the same statement.
Example
Is the same as ? Row TF: the first gives T, the second gives F. They differ, so no.
Watch out!

Examples are not a proof

Checking many numbers and finding no counterexample does not prove “every”. The statement can still break at the next number. A list can only show that “every” is false or that “some” is true.
Example
is prime for . But gives , so “every value is prime” is false.
Watch out!

“Not every” is not “no”

The negation of “every” is not “no”. To break “every pupil has a bike” one pupil without a bike is enough; that does not mean nobody has a bike. Mixing the two up is the most common mistake with negation.
Example
Ada has no bike and Ben has one. “Every pupil has a bike” is false. “No pupil has a bike” is false too. “Some pupil has no bike” is true.
Watch out!

Everyday “or” is not always logic OR

In speech “or” often means either … or: “tea or coffee” is one of the two. Logic OR also accepts both. Before you write a condition, ask: may both be true?
Example
“Children under 12 or people over 65 pay half” allows a person who is both: OR. “With your cake you get tea or coffee” does not allow both: either … or.
Special case

Empty cases: true without a witness

If is false, “IF p THEN q” is true: nothing can break it. In the same way “every” over an empty list is true (there is no counterexample) and “some” over an empty list is false (there is no witness).
Example
“Every number in the empty list is even” is true, “some number in the empty list is even” is false. “If a number is both even and odd, then it is 100” is true: the condition never holds.

Exercises

is true and is false. Find the value of , , either or , and . Easy
Show solution
AND needs both true: is F.
OR needs at least one: is T.
Either … or needs exactly one: T.
IF p THEN q is false only for p true and q false: that is this row, so F.
NOT turns the T of p round: F.
Answer → F, T, T, F, F
Check: exactly one part is true, so OR and either … or are true and AND is false.
Choose AND, OR or either … or. (a) “You can log in when you know the user name ___ the password.” (b) “Children under 12 ___ people over 65 pay half price.” (c) “On Fridays you do swimming ___ football: you cannot do both.” Easy
Show solution
(a) Both are needed to log in: AND.
(b) One of the two is enough and a person may be both: OR.
(c) Exactly one of the two, not both: either … or.
Answer → (a) AND, (b) OR, (c) either … or
Check: put both parts true. (a) and (b) still work, (c) breaks its own rule.
How many numbers in the list 3, 6, 12, 14, 15, 20, 21 are a multiple of 3 AND greater than 10? Easy
Show solution
Multiples of 3: 3, 6, 12, 15, 21.
Of these keep the numbers greater than 10: 12, 15, 21.
Answer → 3 numbers
Check: 14 and 20 are greater than 10 but not multiples of 3, and 3 and 6 are the other way round: each fails one test.
For the list 2, 4, 6, 9 decide: (a) every number is even, (b) some number is even, (c) no number is even, (d) not every number is even. Easy
Show solution
(a) The number 9 is a counterexample: false.
(b) The number 2 is a witness: true.
(c) The number 2 is even, so “no” fails: false.
(d) “Not every” is true because 9 is not even: true.
Answer → (a) false, (b) true, (c) false, (d) true
Check: (d) is the negation of (a), so the two have opposite values.
In a class of 20 pupils, 11 play chess, 9 have a bike and 5 do both. How many play chess OR have a bike? How many play chess but have no bike? How many do neither? Medium
Show solution
OR: (the 5 who do both were counted twice).
Chess but no bike: .
Neither: .
645pq
Answer → 15, 6 and 5 pupils
Check: only chess 6, only bike , both 5 and neither 5 add up to .
Write the condition that counts the numbers greater than 9 that are not even, and use it on the list 5, 8, 10, 13, 16, 20, 25. What is count at the end? Medium
Show solution
“Greater than 9 but not even” is : if (n > 9 AND NOT (n is even)) then count ← count + 1.
Numbers greater than 9: 10, 13, 16, 20, 25.
Of these the odd ones are 13 and 25, so count = 2.
Answer → count = 2
Check: 5 and 8 are not greater than 9, and 10, 16 and 20 are even: each fails one test.
Write the negation of (a) “Every number in the list is prime” and (b) “Some pupil in the team plays chess”. For the list 3, 5, 9, 11 give the value of (a) and of its negation. Medium
Show solution
(a) NOT every is “some … not”: “Some number in the list is not prime”.
(b) NOT some is “no”: “No pupil in the team plays chess”.
In the list 3, 5, 9, 11 the number is not prime, so (a) is false.
The negation has the witness 9, so it is true.
Answer → (a) some number is not prime, (b) no pupil plays chess; (a) is false and its negation is true
Check: a statement and its negation always have opposite values.
What does this algorithm print for the list 4, 6, 8, 9?ok ← truefor each x in the list: if x is not even then ok ← falseprint okWhich statement does it test? Medium
Show solution
Start: ok is true. The numbers 4, 6 and 8 are even, so ok stays true.
The number 9 is not even: ok ← false. The flag never changes back.
The loop ends and prints false.
Answer → false; it tests “every number in the list is even”
Check: 9 is a counterexample, and one counterexample is enough to make “every” false.
Days 1 to 5: lesson on days 1 and 3, cleaning on days 2 and 3. On which days is the pool open under each rule? (a) no lesson AND no cleaning, (b) NOT (lesson OR cleaning), (c) no lesson OR no cleaning, (d) NOT (lesson AND cleaning). Which rules are the same? Hard
Show solution
No lesson: 2, 4, 5. No cleaning: 1, 4, 5.
(a) both: days 4, 5. (b) lesson OR cleaning is on 1, 2, 3, so NOT gives 4, 5.
(c) at least one of the two: days 1, 2, 4, 5.
(d) lesson AND cleaning is only on day 3, so NOT gives 1, 2, 4, 5.
Answer → (a) and (b): days 4, 5; (c) and (d): days 1, 2, 4, 5. So (a) = (b) and (c) = (d), De Morgan
Check: rule (a) needs both days to be free, so it opens fewer days than rule (c).
Show with algebra that the square of every odd number is odd, and check the result for . Why do the checked numbers 3, 5 and 7 not prove it? Hard
Show solution
Write an odd number as .
.
This is 2 times a whole number plus 1, so it is odd for every .
is : .
Three checked numbers say nothing about the others; only the algebra covers every .
Answer → is odd; for it is 121
Check: and .
A pupil checks for and gets the prime numbers 41, 43, 47. She says: “Every value of is prime.” Is she right? Test . Hard
Show solution
Three prime values are only three examples: they cannot prove “every”.
: .
, so 1681 is not prime.
One counterexample is enough: the statement is false.
Answer → No: gives
Check: now the statement has a counterexample, so its negation “some value is not prime” is true.
For the list 2, 4, 5, 8, 9, 12: for how many numbers is “IF the number is even THEN it is a multiple of 4” true? Which number breaks it? Hard
Show solution
The number 2 is even but not a multiple of 4: p true, q false, so the statement is false.
The numbers 4, 8 and 12 are even and multiples of 4: true.
The numbers 5 and 9 are not even: p is false, so the statement is true.
It is true for 5 of the 6 numbers.
Answer → true for 5 of the 6 numbers; the number 2 breaks it
Check: the statement is false exactly for the numbers that are even but not a multiple of 4, and only 2 is such a number.
Are you a teacher?

Start live lessons with these applications for your whole class. Free to try for one month.

Try it free

Fits these school years

Netherlands: Vwo · Mathematics C

Türkiye (MEB): Year 9 (MEB)

England (GCSE, A Level): Year 10 (GCSE), Year 11 (GCSE), Year 12 (A Level), Year 13 (A Level)

What the applications of this topic teach 8 applications

Connectives: and, or, either … or, if … then, not

  • Saying when AND, OR, either … or, IF … THEN and NOT are true
  • Seeing how a connective sorts objects in a table and Venn diagram
  • Writing one statement in words, symbols and pseudocode

Every, some, no: witness and counterexample

  • Saying what every, some, no and not every mean
  • Finding the counterexample that breaks “every”
  • Writing the negation of a statement with every or some

Logic in everyday rules: passwords, filters and timetables

  • Seeing AND, OR and NOT in passwords, search filters and timetables
  • Changing a rule and seeing which items it accepts
  • Checking De Morgan's law on own data

Logic symbols: ∧ ∨ ¬ ⇒ ⇔ and truth tables

  • Read and write the symbols ∧ ∨ ¬ ⇒ ⇔ and say in which order they are read.
  • Make the truth table of a formula in p, q and r and say whether it is always true, always false or neither.
  • Decide with truth tables whether two formulas say the same.

If … then … hence: what follows?

  • Say what follows from a rule "if p then q" and one fact, and when nothing follows.
  • Name the two valid steps and the two mistakes.
  • Test an argument with a truth table: the conclusion must be true in every row where all the premises are true.

Necessary or sufficient?

  • Say when A is a sufficient condition for B and when it is a necessary condition.
  • Find the counterexample that shows a condition is not sufficient or not necessary.
  • Say when a condition is both sufficient and necessary: "if and only if".

Reasoning steps: starting points, steps and conclusion

  • Name the starting points, definitions, steps and conclusion of a reasoning.
  • Say whether a reasoning is correct and complete, correct but incomplete, or not correct.
  • Find the step that does not follow in an argument from public debate.

Contradiction and paradox: statements that clash

  • Find out whether statements can all be true together, and name the smallest group that clashes.
  • Say what a contradiction is and recognise one in a truth table.
  • Describe a paradox: a sentence about itself that no value fits, or a proof with a hidden mistake.