The goal is to give you an idea of many types of problems that are
available.
There is much more material than we can cover today, but you can continue at
home.
Some background topics such as how to use parentheses ( and ) must be
introduced, but they are not our focus.
They are touched only briefly.
Of course you want to find correct answers, but please also try wrong
answers to see what happens!
Play with the problems!
Type in wrong answers and try to understand why the feedback tool replies as
it does!
The feedback tool is a prototype, so please do tolerate minor problems.
Suggestions for improvement are welcome!
The tool is free for non-commercial use, but if you will use it heavily,
please ask first.
And, or, not, and parentheses
We first use the following operators:
symbol
read
type as
∧
and
/\
∨
or
\/
¬
not
!
You may also literally write “and”, or even copy and paste the symbol “∧”.
Of course, the same applies to the other symbols.
Please notice that “first ∨ second” really means “first or second or both”!
Let B mean that Bern is a nice city, G that
Geneva is a nice city, and Z that Zürich is a nice city.
Express the following claims.
How about “Both Bern and Zürich are nice”?
Does it mean the same as or different from “Both Zürich and Bern are nice”?
Try it on the above and see whether it is correct!
helpYou should try
“B ∧ Z”.
We now continue expressing claims.
Please think about “It is not the case that both Bern and
Geneva are nice” and “Bern or Geneva is bad”.
Do they mean the same?
Try the answer of one in the answer box of the other!
Often a claim can be expressed in a simpler form.
For instance,
this is true if and only if
this is true
Z ∨ Z
Z
G ∨ (¬G ∧ B)
G ∨ B
B ∧ ¬B
F
In mathematics, a claim may be undefined.
For instance,
x
0
= 1 is undefined.
It is important in programming and computer science to deal appropriately with
undefined claims, and the feedback tool can largely do so.
Unfortunately, the possibility of undefined claims is usually ignored in
logic.
Therefore, to keep things simple, today we mostly ignore the possibility of
undefined claims.
In the last example, F means that the claim never holds.
Indeed, Bern cannot be nice and not nice simultaneously.
A claim that always holds can be simplified to T.
symbol
read
type as
F
false
FF
T
true
TT
Be sure not to type F and T as F and T!
The latter mean, for instance, that Frankfurt is nice and Torino is nice.
We use “⇔” to denote “simultaneously true”.
So the above examples can be re-written as follows:
Z ∨ Z
⇔
Z
G ∨ (¬G ∧ B)
⇔
G ∨
B
B ∧ ¬B
⇔
F
Express the following in a simpler form.
Reasoning operators
A counterexample to a claim on one variable is a value of the
variable that makes the claim not hold.
For instance, x = −8 is a counterexample to x + 5 ≥ 0.
Please give counterexamples to the following claims.
If there are many counterexamples, you may choose yourself which one you give.
Because of a technical limitation of the current version
of the tool, here it can only deal reliably with numbers from 0 to 10.
(🤓 I will fix it soon, trust me! 🤔)
Therefore, these problem types cannot yet be assigned to pupils, but you
teachers can live with it.
So please only use integers between 0 and 10 (inclusive) as
counterexamples.
A claim is correct if and only if it has no counterexamples.
A reasoning step is of one of the following three forms:
form
counterexample: a value of the variable that
makes
claim1 ⇒ claim2
claim1 hold but claim2 not hold
claim1 ⇐ claim2
claim2 hold but claim1 not hold
claim1 ⇔ claim2
one of claim1 and claim2 hold, and the other not hold
Reasoning steps can be chained, like in claim1 ⇔ claim2 ⇒ claim3.
(However, having both ⇒ and ⇐ in the same chain usually does not make sense.)
A reasoning step is correct if and only if it has no
counterexamples.
Give counterexamples to the following reasoning steps.
Now you may use also negative numbers and numbers bigger than 10.
(On the other hand, now the feedback is less easy to interpret.)
Are the following reasoning steps correct?
symbol
read
type as
⇒
implies
==>
⇐
is implied by
<==
⇔
if and only if
<=>
Type the right reasoning operator.
If more than one is right, type the most informative one.
Implication and logical equivalence
Two propositional operators look like reasoning operators.
symbol
read
type as
→
if then
-->
↔
both truth or both
false
<->
Express the following claims.
The differences between ⇔ and ↔, or between ⇒ and →, are a long story.
Let us just show with an example one difference.
(You may modify the example and try again, but please be aware that here the
tool computes everything modulo 21.
This is yet another imperfection.)
Logical Symbols and Equations
We show some examples to illustrate how logical symbols are useful when
solving equations.
Logical symbols are nice for expressing more or less than one roots.
Solve the following equations.
Please notice how /* and */ were used to add comments
to the output, and /**/ to introduce line breaks.
This kind of splitting to cases is, however, not good for difficult
problems, because it forces both cases solved in parallel, or at least one
case being carried along while the other is solved.
Perhaps sometime in the future the tool makes it possible to solve them
separately.
Quantifiers
The most important data structure in programming is an array.
It is like a row of boxes numbered consecutively.
The numbers of the boxes are indices.
Here is an array of characters:
We will, however, work on arrays of numbers.
Here is an example:
It is often necessary to express complicated things about arrays.
It is possible with quantifiers:
symbol
read
type as
∀
for each
AA
∃
there is
EE
Here are some examples on an array A whose indices are 1, …,
n:
Every element is 1:
∀ i; 1 ≤ i ≤ n: A[i] = 1
It is sorted in increasing order:
∀ i; 1 ≤ i < n: A[i] ≤
A[i + 1]
Some element occurs at least twice:
∃ i: ∃ j; 1 ≤ i < j ≤ n:
A[i] = A[ j]
The smallest element is unique:
∃ i; 1 ≤ i ≤ n: ∀ j; 1 ≤ j ≤ n ∧
i ≠ j: A[i] < A[ j]
Express the following claims on an array A whose
indices are 1, …, n.
Express the following claims as briefly as you can.
It may require a lot of thinking!
You may proceed in steps.
Now remove <=> FF from the above and try
again, to see a message telling that your answer is mathematically correct but
not as brief as wanted.