A statement is a sentence that is either true or false, never both. A question or a command is not a statement. Letters like p and q 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∧q (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.pTTFFqTFTFp∧qTFFF
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∨q (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.pTTFFqTFTFp∨qTTTF
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 p or q, written p⊕q, is true when exactly one part is true, not both. It is the “or” of “tea or coffee” on a menu.pTTFFqTFTFp⊕qFTTF
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
p→q (IF p THEN q) is false in one case only: p true and q false. When p is false the statement says nothing and counts as true.pTTFFqTFTFp→qTFTTSee also "Hence: what follows from a rule and a fact".
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
¬p (NOT p) is true when p is false and false when p is true. Put NOT in front of a test to count the objects that fail it.pTF¬pFT
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
“p but not q” is p∧¬q: the object must pass the first test and fail the second. Do not write only ¬q and forget p.
Example
A class of 12: 7 play chess, 5 have a bike, 3 do both. Chess but no bike: 7−3=4 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.∣p∨q∣=∣p∣+∣q∣−∣p∧q∣
Example
12 pupils: 7 chess, 5 bike, 3 both. Chess OR bike: 7+5−3=9 pupils. Neither: 12−9=3.
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
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
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: 9=3×3, 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.¬∀xP(x)≡∃x¬P(x)¬∃xP(x)≡∀x¬P(x)
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.¬(p∧q)≡¬p∨¬q¬(p∨q)≡¬p∧¬qSee also "The symbols ∧ ∨ ¬ ⇒ ⇔ and their order".
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: ∀x∈L:P(x), where P(x) 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.
Example
p∨q∧r is read as p∨(q∧r). That reading is true in 5 of the 8 rows; the reading (p∨q)∧r is true in 3 rows. The two readings differ in 2 rows (lit in the table), for example for p true with q and r false.
Definition
⇒ and ⇔: if … then, and if and only if
The implication p⇒q is false only when p is true and q is false; it says the same as ¬p∨q. The equivalence p⇔q is true when p and q have the same value; it says p⇒q and also q⇒p. Two formulas say the same when A⇔B is true in every row. In the tab Same or different you type two formulas and see the rows where they differ.
Example
p⇒q is true in 3 of the 4 rows and p⇔q in 2 rows. The columns of p⇒q and ¬p∨q 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 n=2k+1, so n2=4k2+4k+1=2(2k2+2k)+1, 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
k=3: n=7 and n2=49=2×24+1. 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 p⇒q and p to q, and from p⇒q and ¬q to ¬p. Two are mistakes: from q to p, and from ¬p to ¬q. 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.
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.
Definition
Sufficient and necessary conditions
A is a sufficient condition for B when A⇒B: every case with A has B. A is a necessary condition for B when B⇒A: no case has B without A. If both hold, A⇔B. Look for counterexamples: a case with A but not B breaks "sufficient", a case with B but not A breaks "necessary". Try the tab Numbers of "Necessary or sufficient?".
Example
For the numbers 1 to 30, A is "a multiple of 6" (5 numbers) and B is "even" (15 numbers). Every multiple of 6 is even, so A is sufficient for B. But 2 is even and not a multiple of 6 (10 even numbers are not), so A is not necessary; B is a necessary condition for A.
Watch out!
Do not turn a condition round
"If A then B" and "if B then A" are two different sentences. When x=3, then x2=9; but x2=9 does not make x=3, because x=−3 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.
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 p then q" and p it follows that q.
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.
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.
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.
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 p (it rains) false and q (the match is off) true, both lines above are true and the conclusion is false: the row is p=F,q=T.
Definition
Contradiction
A contradiction is a statement that is false in every row, like p∧¬p, 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.
Example
p∨q, ¬p and ¬q 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 S says "this sentence is false", then p⇔¬p, where p means "S is true", and no value of p makes that true. A hidden mistake gives another kind: in the "proof" of 2 = 1 one line divides by a−b, which is 0. A truth-teller, "this sentence is true", is not a paradox, because both values fit. The tab Paradoxes shows four classics.
Example
For the liar, p⇔¬p is true in 0 of the 2 rows, so no value fits. The truth-teller p⇔p is true in both rows. In the "proof" of 2 = 1 with a=b=3 the first false line is line 5, a+b=b, which says 6 = 3: it divided by a−b=0.
Tip
Test the four rows
Not sure about a connective? Write the four rows TT, TF, FT, FF of p and q and work out the statement in every row. Two statements that give the same four results are the same statement.
Example
Is ¬(p∧q) the same as ¬p∧¬q? 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
n2+n+41 is prime for n=0,1,2,…,39. But n=40 gives 1681=41×41, 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 p 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
p is true and q is false. Find the value of p∧q, p∨q, either p or q, p→q and ¬p. Easy
Show solution
AND needs both true: p∧q is F.
OR needs at least one: p∨q 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: 11+9−5=15 (the 5 who do both were counted twice).
Chess but no bike: 11−5=6.
Neither: 20−15=5.
Answer → 15, 6 and 5 pupils
Check: only chess 6, only bike 9−5=4, both 5 and neither 5 add up to 6+4+5+5=20.
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 p∧¬q: 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 9=3×3 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 n=11. Why do the checked numbers 3, 5 and 7 not prove it? Hard
Show solution
Write an odd number as n=2k+1.
n2=(2k+1)2=4k2+4k+1=2(2k2+2k)+1.
This is 2 times a whole number plus 1, so it is odd for every k.
n=11 is k=5: 2(2×25+10)+1=121=112.
Three checked numbers say nothing about the others; only the algebra covers every k.
Answer → n2=2(2k2+2k)+1 is odd; for n=11 it is 121
Check: 112=121 and 2×60+1=121.
A pupil checks n2+n+41 for n=0,1,2 and gets the prime numbers 41, 43, 47. She says: “Every value of n2+n+41 is prime.” Is she right? Test n=40. Hard
Show solution
Three prime values are only three examples: they cannot prove “every”.
n=40: 1600+40+41=1681.
41×41=1681, so 1681 is not prime.
One counterexample is enough: the statement is false.
Answer → No: n=40 gives 1681=41×41
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.
Interactive applications for this topic
Free applications open with a free student account. Teachers can use all applications in a live lesson.