Matematica discreta: logica, predicati e quantificatori da Bemacs

Matematica discreta

Discrete mathematics
Logic
Mathematics Mod. II
30400 BEMACS
Class 25
D Fein
A.Y. 2024-2025
Lesson 2

• Predicates

. Quantifiers
· Rules of inference
· Valid arguments

Risposta all'apertura di ieri

A
Z
BAn answer to yesterday's opener (1/2)
An island has two types of inhabitants, knights, who always tell the
truth, and knaves, who always lie.
You encounter two people, Amanda and Bob.
Amanda declares, "Bob is a knight" and Bob asserts, "The two of us are
opposite types."
What are Amanda and Bob?An answer to yesterday's opener (2/2)

Logica dei predicati

Predicate logic
"Student x earned 31 in mathematics."
. The truth value of the above statement depends on x, and is called a
propositional function, denoted by p(x).
· The rules of propositional logic will not satisfy. We need predicate
logic.
. In the statement, x is the variable while the property "earned 31 in
mathematics" is the predicate.
Example
What would a computer program do with the following:
"If x > 10 then x := x - 1"

Funzioni proposizionali

Definizione di funzione proposizionale

Propositional functions
Definition
Consider a set A. A propositional function defined on A is an expression
p(x) that is either true or false for each x E D.
D is the domain of p(x) and the truth set denoted To is the set of all
elements in D for which p(x) is true. i.e.,
Tp = {x: x E D, p(x) is true}
We usually abbreviate as
Tp = {x:p(x)}

Esempio di funzione proposizionale

Example
Given D = N, and p(x) == x +2 > 7, what is p(1)?p(5)?
Write the truth set.

Insiemi di verità

Truth sets - example
Let p(x) be the statement "x + 2 > 5"
Is p(x) a propositional function on:
· N
· M = {-1,-2,-3}
· C
In each affirmative case, write the truth set.

Tabelle di appartenenza

Membership tables
Set identities can be proven using the same tools we have used to prove
logical identities, using membership tables. We indicate that an element is in
a set with a 1, and a 0 if it is not.
Example
Prove De Morgan's law for sets (A n B)c = AC U BC

Esempio di tabella di appartenenza

A
B
AC
BC
AC U BC
AnB
(AnB)c
1
1
1
0
0
1
0
0

Legge distributiva

Example - distributive law of n over U
Example
Show that A n (BU C) = (An B) U (ANC)
A
B
C
BUC
An (BUC)
AnB
Anc
(AnB) U (Anc)
1
1
1
1
1
0
1
0
1
1
0
0
0
1
1
0
1
0
0
0
1
0
0
0

Un paradosso (di Russell)

A paradox (Russell's, in fact)
Consider a group of barbers who shave only those men who do not
shave themselves. Suppose there is a barber in this collection who does
not shave himself; then by the definition of the collection, he must
shave himself. But no barber in the collection can shave himself. (If so,
he would be a man who does shave men who shave themselves.)
(Scientific American)
Let S be the set that contains a set x if the set x does not belong to
itself, i.e., S = {x: x ¢ x}.
1. Show that assuming S is a member of S leads to a contradiction.
2. Show that assuming S is not a member of S leads to a
contradiction.
For your viewing pleasure.

Calcolo dei predicati

Predicate calculus
Consider a propositional function p(x) defined on a set D.
1. Suppose p(x) is always true. Then, its truth set is
Tp = {x: p(x)} = D
In this case, we use the universal quantifier V, and we write Vx p(x).
2. Suppose p(x) is sometimes true. Then, its truth set is
Tp = {x: p(x)} # Ø
In this case, we use the existential quantifier 3, and we write Ex p(x).
3. Suppose p(x) is true exactly once. Then, its truth set is
Tp = {x: p(x)} = {x0}
In this case, we use the universal quantifier V, and we write =! x p(x).

Esempio di quantificatori

Example
Express the following statements using quantifiers.
All lions are fierce.
Some lions do not drink coffee.
Some fierce creatures do not drink coffee.
Lewis Carroll
(pseudonym for
Charles Dodgson)
(1832-1898)

Negazione dei quantificatori

Negating quantifiers
What is the negation of the statement "Every tweedledee wears polka-
dots."
De Morgan's laws for quantifiers state the following:
. - Vx p(x) =Ex -p(x)
2. - Exp(x) = Vx -p(x)
Example
Show that -Vx (p(x) => q(x)) == x(p(x) A-q(x)).

Quantificatori annidati

Nested quantifiers
You have already seen these!
Example
What is the following statement, containing nested quantifiers,
defining?
VE > 038 > 0Vx(0< |x -a] < 8 => f(x) - L|

Prove, argomenti e inferenza

Proofs, arguments, and inference
. The truth of new mathematical properties is established by proof.
· Proofs are valid arguments.
· An argument is a sequence of statements (premises) ending in a
conclusion.
. Valid means that the conclusion must follow from the truth of the
premises.
. i.e., an argument is valid if and only if it is impossible for all the premises to be
true, but the conclusion is false.
· Rules of inference are a set of basic tools that allow us to deduce new
statements from given statements.

Forma dell'argomento

Argument form
The validity of an argument is irrespective of the actual propositions
but is a feature of the argument form, a sequence of propositions
involving propositional variables ending in a conclusion.
So, the argument form with premises p1, P2, ... , Pn and conclusion q is
valid when the following is a tautology:
(P1 AP2 A ... A Pn) => q

Argomenti validi

Esempi di argomenti validi

Valid arguments
Is the following argument valid?
"If I have the flu, I will have a fever. I have a fever. Therefore, I have the
flu."
How about this one?
"If I am a cat, I like to sleep a lot. I like to sleep a lot. Therefore, I am a
cat."

Struttura degli argomenti validi

Valid arguments
Is the following argument valid?
"If I follow a rainbow, I will find a leprechaun. If I find a leprechaun, it
will lead me to a pot of gold. Therefore, if I follow a rainbow, I will be
led to a pot of gold by a leprechaun."
. The validity of an argument is dependent on its structure.
· The conclusion in a valid argument, however, may still be false if one
or more of the premises is false.

Forma dell'argomento precedente

Valid arguments
The form of the argument on the previous slide is:
.. per
The argument (called hypothetical syllogism) may also be written as
p=q,q=rFp=r
and it is valid since the proposition
((p = q) A (q= r)) = (p=r)
is a tautology. [Verify this OYO.]

Modus ponens

Modus ponens
Showing that the following argument form (modus ponens/affirming
the antecedent) is valid:
p
p =>q
.. q
d
q
p= q
PA (p => q)
(p A (p => q)) = q
T
T
T
F
F
T
F
F
We could have omitted the
final two columns. Note that
the columns p and p => q
are true simultaneously only
in the first row. And this
occurs when q is true.

La validità non è tutto

Validity isn't everything!
Consider the following argument:
2
If V2 > 2, then
2'
2
9
(V2)
=2>
-
=
2
3
2
4
312
2
V2
>
We know that
V2 >
3
-. Consequently,
2
· The form of the argument is valid! (It is modus ponens.)
. But since one of the premises is false, we cannot conclude that the
conclusion is true!

Esempio di modus tollens

Example - modus tollens
Show that the following argument form (modus tollens/denying the
consequent) is valid:
bL
p => q

Regole di inferenza

Regole di inferenza (1/2)

Rules of inference (1/2)
Modus ponens is one of many rules of inference. (Specifically, it is a
syllogism, since it consists of two premises followed by a conclusion.)
Following are some of the more common rules that serve as building
blocks when constructing more complicated valid argument forms.
d
p=q
.. q
Modus ponens
ger
.. per
Hypothetical
syllogism
bL
Modus tollens
pv q
Disjunctive
syllogism
.. q

Regole di inferenza (2/2)

Rules of inference (2/2)
Here are another few common rules of inference. OYO, show these
(and the previous) are valid argument forms.
p
.. pv q
Addition
d
q
.. paq
Conjunction
paq
Simplification
.. p
pvq
pvr
.. q vr
Resolution
The conclusion in the resolution rule,
q Vr, is called the resolvent.

Esempio di regole di inferenza

Example
Show that the hypotheses "Manuela is skiing, or it is not snowing" and
"It is snowing, or Michele is playing soccer" imply that "Manuela is
skiing, or Michele is playing soccer."

Costruire argomenti

Costruire argomenti (1/2)

Building arguments (1/2)
Consider the following argument.
Hypotheses: "It is not sunny this afternoon and it is colder than
yesterday. We will go swimming only if it is sunny. If we do not go
swimming, then we will take a canoe trip. If we take a canoe trip, then
we will be home by sunset."
Conclusion: "We will be home by sunset."
Writing the argument form, using p, q, r, s, t to denote the respective
simple propositions:
PAq, r=>p,-r=s, s=trt

Costruire argomenti (2/2)

Building arguments (1/2)
Instead of using a truth table (too
many rows!), we work as follows.
r => p
ras
s=> t
t
Step
Reason
Premise
Simplification (1)
r = p
Premise
-r
Modus tollens (2,3)
Premise
S
Modus ponens (4,5)
s= t
Premise
t
Modus ponens (6,7)

Pratica

Practice
Premises: "If you send me an email, then I will finish writing the
program. If you do not send me an email, then I will go to sleep early. If
I go to sleep early, then I will wake up feeling rested."
Conclusion: "If I do not finish writing the program, then I will wake up
feeling rested."
Show that the premises lead to the conclusion.

Fallacia - affermare il conseguente

Fallacia - affermare il conseguente (1/2)

Fallacy - affirming the consequent (1/2)
The following arguments (affirming the consequent) are fallacies. Why?
If you do every practice problem, then you will learn discrete
mathematics. You learned discrete mathematics. Therefore, you did
every practice problem.
Jacopo and Dovid are colleagues. They know that if they do a good job
on a project, they will get a bonus. Last Monday, Jacopo came up to
Dovid and tells him they got a bonus. Dovid congratulates Jacopo,
saying "We must've done a good job on the project!"

Fallacia - affermare il conseguente (2/2)

Fallacy - affirming the consequent (2/2)
The argument form is as follows:
q
.. p
d
q
P=q
q A (p = q)
(q (p => q)) =p
T
T
T
F
F
T
F
F

Esercizio pratico

Practice
Determine if the following are valid arguments or fallacies.
1. p= q, ph-q
2. p == q, r=q, rkp
3. If two sides of a triangle are equal, then the opposite angles are
equal. Two sides of a triangle are not equal. Therefore, the opposite
angles are not equal.