Logic for CS
Chapter 0
Logic studies the rules of deduction (=gevolgtrekking).
Speci cation: identifying the task to be solved, as well as what constitutes a solution (abstract
description of what a program must do);
Implementation: devising a solution to the task which respects the speci cation (a program that exhibits
the behavior desired by the speci cation);
Veri cation: a proof that an implementation adheres to its speci cation.
To prove something can be done, it su ces to nd 1 successful solution. To prove something cannot be
done, there are way too many combinations to try.
Chapter 1: Propositions
Proposition is a statement that may be true or false.
A propositional formula that always holds is known as a tautology.
A propositional formula that is false regardless of the truth values of its atomic proposition is known as a
contradiction.
A statement that doesn’t change is called an invariant.
The rst statement expresses an option. → A deduction/inference is made to infer the truth of a third
statement from the rst statement. (These two rst statements are premises). → It’s followed by the
conclusion.
Propositional variables such as P, Q, R,… represent unknown propositions (just like variables such as x, y
and z represent unknown numbers in math).
Propositional connectives
￢ negation not p
∧ conjunction p and p
∨ inclusive sense of p or q
disjunction
⨁ exclusive sense of p xor q
disjunction
implication if p then q / p implies q / p only if q /
q is a necessary condition for p
equivalence p if, and only if, q / p is equivalent to q
Logical implication: think about example : “when the re alarm goes o , we all leave the classroom”. p q
is only false when p is true and q is false.
Page 1 of 17
fifi fi fi fi ffi fi fi fi ff fi
,A statement written in propositional logic is called a propositional formula and is either:
• an atomic formula, typically represented by a variable name such as P, Q, R, …;
• two special atomic propositional formula: true and false.
• a compound formula, in which case it is build up using the above propositional connectives.
Parentheses and Precedences
To reduce the need for parentheses, we will consider ￢ as binding more tightly than ∧, which will bind more
tightly than ∨, which will bind more tightly than , which will bind more tightly than . Apart from this, the
connectives will be applied right-to-left.
Syntax Tree
The syntax tree makes it clear how the expression should be parsed, without the need for parentheses or
precedence rules to tell the reader how to interpret the formula.
(P ∨ Q) ￢(P ∧ Q) corresponds to the following syntax tree:
Truth Tables
One way of de ning the meaning of the connectives, is by using truth tables. An example, with implication:
p q p q
F F T
F T T
T F F
T T T
Chapter 2: Sets
A set is a collection of objects which typically share a property.
The objects of a collection are referred to as its elements or members. The number of objects in a set A
is referred to as cardinality.
Simple sets can be de ned by listing all their elements, for example:
• { 3, 12, 25 }
• { 0,2,4,…,50 } for all even numbers under 50.
Creating a list by describing the property that the elements share (set-builder notation):
{ x : x has property P }
P is called a predicate.
Page 2 of 17
fi fi
, Elements
We write |A| to refer to the number of elements in the set A, the cardinality (sometimes also written as #A).
Membership
If x is an element of the set A, we write x ∈ A
If x is not an element of the set A, we write x ∉ A
Set inclusion
When all elements of a set A are also elements of a set B, we say that A is a subset of B, written as A ⊆ B.
B is a superset of A (B ⊇ A). This is called set inclusion.
If A ≠ B, but A is a subset of B, A is called a strict subset written as A ⊂ B. All elements of A are in B, but B
has got more elements.
The subset relation is re exive, antisymmetric and transitive (see chapter 7).
Equality
Two sets are equal if, and only if, they have the same elements. The order of elements in a set doesn’t
matter.
{ 3, 7, 14 } = { 7, 14, 3, 7, 3 }
{ Joel, Felix, Oskar } ≠ { Joel, Felix, Oskar, Amanda }
A useful graphical way of depicting sets, and in particular the relationship between them, is by so-called
Venn diagrams. The rectangle represents some understood universal set U (universe of discourse). ∅ ⊆ A
(empty list is contained by any other list).
Russell’s Paradox
Normally a set will not be a member of itself, but there is nothing to preclude us considering abnormal sets
that are elements of themselves. Consider the set of normal sets; thus all sets which do not contain itself:
R = { A : A ∉ A }.
Is R a normal set? Thus, do we have R ∈ R?
Suppose R ∈ R; then we need to satisfy the property required of being an element of R, thus R ∉ R.
Support R ∉ R; then we must not satisfy the property required of bering an element of R, thus R ∈ R.
Operations on Sets
A∩B intersection1 consists of elements in both sets A and B
A∪B union consists of elements in either set A or B (or
both)
Ā complement the complement of set A consists all of
those elements of the universe of discourse
which are not in A
A\B di erence consists of those elements which are in A
but are not in B
A▽B symmetric di erence consists of those elements that are not in
both A and B
1Two sets A and B are called disjoint if they do not have any elements in common.
It is also possible to say: A ∪ B = ⋃{A, B} and A ∩ B = ⋂{A, B}.
Page 3 of 17
ff
ff fl
Chapter 0
Logic studies the rules of deduction (=gevolgtrekking).
Speci cation: identifying the task to be solved, as well as what constitutes a solution (abstract
description of what a program must do);
Implementation: devising a solution to the task which respects the speci cation (a program that exhibits
the behavior desired by the speci cation);
Veri cation: a proof that an implementation adheres to its speci cation.
To prove something can be done, it su ces to nd 1 successful solution. To prove something cannot be
done, there are way too many combinations to try.
Chapter 1: Propositions
Proposition is a statement that may be true or false.
A propositional formula that always holds is known as a tautology.
A propositional formula that is false regardless of the truth values of its atomic proposition is known as a
contradiction.
A statement that doesn’t change is called an invariant.
The rst statement expresses an option. → A deduction/inference is made to infer the truth of a third
statement from the rst statement. (These two rst statements are premises). → It’s followed by the
conclusion.
Propositional variables such as P, Q, R,… represent unknown propositions (just like variables such as x, y
and z represent unknown numbers in math).
Propositional connectives
￢ negation not p
∧ conjunction p and p
∨ inclusive sense of p or q
disjunction
⨁ exclusive sense of p xor q
disjunction
implication if p then q / p implies q / p only if q /
q is a necessary condition for p
equivalence p if, and only if, q / p is equivalent to q
Logical implication: think about example : “when the re alarm goes o , we all leave the classroom”. p q
is only false when p is true and q is false.
Page 1 of 17
fifi fi fi fi ffi fi fi fi ff fi
,A statement written in propositional logic is called a propositional formula and is either:
• an atomic formula, typically represented by a variable name such as P, Q, R, …;
• two special atomic propositional formula: true and false.
• a compound formula, in which case it is build up using the above propositional connectives.
Parentheses and Precedences
To reduce the need for parentheses, we will consider ￢ as binding more tightly than ∧, which will bind more
tightly than ∨, which will bind more tightly than , which will bind more tightly than . Apart from this, the
connectives will be applied right-to-left.
Syntax Tree
The syntax tree makes it clear how the expression should be parsed, without the need for parentheses or
precedence rules to tell the reader how to interpret the formula.
(P ∨ Q) ￢(P ∧ Q) corresponds to the following syntax tree:
Truth Tables
One way of de ning the meaning of the connectives, is by using truth tables. An example, with implication:
p q p q
F F T
F T T
T F F
T T T
Chapter 2: Sets
A set is a collection of objects which typically share a property.
The objects of a collection are referred to as its elements or members. The number of objects in a set A
is referred to as cardinality.
Simple sets can be de ned by listing all their elements, for example:
• { 3, 12, 25 }
• { 0,2,4,…,50 } for all even numbers under 50.
Creating a list by describing the property that the elements share (set-builder notation):
{ x : x has property P }
P is called a predicate.
Page 2 of 17
fi fi
, Elements
We write |A| to refer to the number of elements in the set A, the cardinality (sometimes also written as #A).
Membership
If x is an element of the set A, we write x ∈ A
If x is not an element of the set A, we write x ∉ A
Set inclusion
When all elements of a set A are also elements of a set B, we say that A is a subset of B, written as A ⊆ B.
B is a superset of A (B ⊇ A). This is called set inclusion.
If A ≠ B, but A is a subset of B, A is called a strict subset written as A ⊂ B. All elements of A are in B, but B
has got more elements.
The subset relation is re exive, antisymmetric and transitive (see chapter 7).
Equality
Two sets are equal if, and only if, they have the same elements. The order of elements in a set doesn’t
matter.
{ 3, 7, 14 } = { 7, 14, 3, 7, 3 }
{ Joel, Felix, Oskar } ≠ { Joel, Felix, Oskar, Amanda }
A useful graphical way of depicting sets, and in particular the relationship between them, is by so-called
Venn diagrams. The rectangle represents some understood universal set U (universe of discourse). ∅ ⊆ A
(empty list is contained by any other list).
Russell’s Paradox
Normally a set will not be a member of itself, but there is nothing to preclude us considering abnormal sets
that are elements of themselves. Consider the set of normal sets; thus all sets which do not contain itself:
R = { A : A ∉ A }.
Is R a normal set? Thus, do we have R ∈ R?
Suppose R ∈ R; then we need to satisfy the property required of being an element of R, thus R ∉ R.
Support R ∉ R; then we must not satisfy the property required of bering an element of R, thus R ∈ R.
Operations on Sets
A∩B intersection1 consists of elements in both sets A and B
A∪B union consists of elements in either set A or B (or
both)
Ā complement the complement of set A consists all of
those elements of the universe of discourse
which are not in A
A\B di erence consists of those elements which are in A
but are not in B
A▽B symmetric di erence consists of those elements that are not in
both A and B
1Two sets A and B are called disjoint if they do not have any elements in common.
It is also possible to say: A ∪ B = ⋃{A, B} and A ∩ B = ⋂{A, B}.
Page 3 of 17
ff
ff fl
