math Jeff Edmonds York University Assignment 2 MATH1090 Predicate Logic I hope you find the course exhilarating and life changing. My answers all fit on these pages. Q1 Independent 18 Q2 Tuples 16 Q3...

math
Jeff Edmonds
York University
Assignment 2
MATH1090
Predicate Logic
I hope you find the course exhilarating and life changing.
My answers all fit on these pages.
    Q1 Independent    18
    Q2 Tuples    16
    Q3 Matching    7*8+10
    Total    100
1
Independent
ie use only: " $   ⌐ 
Q1
Question 1:
Question 2:
Answer 1:
Prove the statement by giving a strategy
in which the prover always wins.
eg For "c, you can say let c be an a
itrary value
given to me by my adversary.
Answer 2:
Tuples
Here the relation Loves(b,g)
is True for 9 out of 16 of the tuples b,g.
                    
        F    T    T    F
        F    T    T    F
        T    F    T    F
        F    T    T    T
If I were to tell you that the following statement is true:
$x5 $x1 "x4 $x2 "x6"x8 $x3 "x7 α(x1,x2,x3,x4,x5,x6,x7,x8)
and tell you that each xi is chosen from the universe of n objects,
then
How many such tuples can be inputs to the relation α?
What is the maximum number these tuples can α be True for?
What is the minimum number these tuples can α be True for?
What is the maximum number these tuples can α be False for?
What is the minimum number these tuples can α be False for?
For which of these answer is the fraction more than a half?
Do we know if α is True for 0,0,0,0,0,0,0,0 or for 4,2,7,3,3,6,7,1?
Explain all your answers.
Q2
Tuples
$x5 $x1 "x4 $x2 "x6"x8 $x3 "x7 α(x1,x2,x3,x4,x5,x6,x7,x8)
Answer:
Q2
Matching Game
Q3
Matching Game
Q3
Game (Race):
Randomly choose two cards.
Find an icon that appears on both.
Matching Game
Q3
Game (Race):
Randomly choose two cards.
Find an icon that appears on both.
Matching Game
Q3
Game (Race):
Randomly choose two cards.
Find an icon that appears on both.
Matching Game
Q3
Game (Race):
Randomly choose two cards.
Find an icon that appears on both.
Our Universe is a set of these cards.
Let appears(i,c) state that icon i appears on card c.
Let $5 card c property(c) state that
there are exactly five cards in our universe
with the stated property.
Matching Game
Q3
Game (Race):
Randomly choose two cards.
Find an icon that appears on both.
For this game to be fun to play,
there is a necessarily property
about the deck of cards as a whole
that ensures that the pair of cards c1 & c2 chosen
will in fact contain the icon i being searched for.
State this property both in English and as a logic statement.
ie use only: " $   ⌐ 
Question 1:
Answer 1:
Matching Game
Q3
Consider the following universe consisting of
72 points p = x,y and
all possible lines y=mx+b that go through them.
Question 2:
Answer 2:
0
1
2
3
4
5
6
q=7
0
1
2
3
4
5
6
State a property similar to that in Question 1,
that holds about the universe of lines and points
that ensures something useful about pairs of point p1 & p2
and a found line L.
State this property both in English and as a logic statement.
ie use only: " $   ⌐ 
Matching Game
Q3
Question 3:
Answer 3:
0
1
2
3
4
5
6
q=7
0
1
2
3
4
5
6
Prove the statement from Question 2, by giving
a strategy in which the prover always wins.
Hint: Use (x2-x1)(y-y1)= (y2-y1)(x-x1) in your proof.
Hint: Use “Proof by picture” in your proof.
Matching Game
Q3
0
1
2
3
4
5
6
q=7
0
1
2
3
4
5
6
From the figure, we see that lines with slope
m=¼ are a little odd because they do not go
through as many points as we would like.
We will now move away from the model
in which x and y are integers in {0,1,…,q-1}
and instead consider a model
in which x and y are integers {0,1,…,q-1} mod q. Here q is prime.
"x&y{0,1,…,q-1}, x+y and xy are well defined
XXXXXXXXXXand if x≠0 then m=1/x is also well defined.
XXXXXXXXXXie "x{1,…,q-1}, $1 m{1,…,q-1}, mx=1
For example, when q=7 we have
XXXXXXXXXX=8=8-7=1 and 42=8=8-7=1.
XXXXXXXXXXRea
anging the last equation gives that ¼=2.
In fact, all of alge
a in this world works as it does with the reals!
13
Matching Game
Q3
0
1
2
3
4
5
6
q=7
0
1
2
3
4
5
6
Color green all points in the line y=2x+4 (mod7)
Explain at least one example.
Question 4.1:
Answer 4.1:
Color green all points in the line y=¼x+4 (mod7)
Explain at least one example.
Question 4.2:
Answer 4.2:
Can the same two points
have two different lines
going through them
Matching Game
Q3
0
1
2
3
4
5
6
q=7
0
1
2
3
4
5
6
Each line L is specified by an equation
XXXXXXXXXXy=mx+
The possible values of the y-intercept b is:
b{0,1,…,6}
The possible values of the slope m is:
m{0,1,…,6, }.
The number of lines in our universe is:
78=56 icon/lines.
Given any point p,
there are 8 lines L passing through it.
These co
espond to the 8 possible slopes m
m{0,1,…,6,∞}.
Free Answers:
∞
y=mx+
x=2
Matching Game
Q3
0
1
2
3
4
5
6
q=7
0
1
2
3
4
5
6
Free Answers:
y=mx+
x=2
One of my religions is to balance units.
XXXXXXXXXXeg 5 (hrs)  100 (km/hr) = 500 (km)
Form a bipartite graph.
XXXXXXXXXXA node on the left for each of the 77 points.
XXXXXXXXXXA node on the right for each of the 87 lines.
XXXXXXXXXXAn edge point,line if the point is on the line
778 point,line edges
= 77 (points)
= 87 (lines)
…
…
77
87
8
7
 8 (lines/point)
 7 (point/line)
Matching Game
Q3
0
1
2
3
4
5
6
q=7
0
1
2
3
4
5
6
Question 5:
Answer 5:
State a property similar to that in Question 1 & 2,
that holds about our universe of lines and points
that ensures something useful about a line L,
and integer value x{0,1,…,q-1},
and a found integer value y{0,1,…,q-1}.
State this property both in English and as a logic statement.
ie use only: " $   ⌐ 
m  ∞
Matching Game
Q3
0
1
2
3
4
5
6
q=7
0
1
2
3
4
5
6
Question 6:
Show how your answer to Question 4 is in fact
a proof of your answer to Question 5.
Answer 6:
Matching Game
Q3
0
1
2
3
4
5
6
q=7
0
1
2
3
4
5
6
Question 7:
Answer 7:
Your answer to Question 5 proves another fun
property that holds about our universe
that ensures something useful about lines L
and the number of point pj found in them.
State this property both in English and as a logic statement.
ie use only: " $   ⌐ 
Including
m=∞
19
Matching Game
Q3
0
1
2
3
4
5
6
q=7
0
1
2
3
4
5
6
One point of formal proofs is
to prove theorems
with as few assumptions as possible
about the nature of the objects
we are talking about
so that we can find a wide range
of strange new objects
for which the same theorems are true.
Matching Game
Q3
0
1
2
3
4
5
6
q=7
0
1
2
3
4
5
6
Repeat your logic statement from Questions 1 & 2.
Hopefully, you see the parallel between them.
Use this connection to design
a set of cards with cute pictures on each
with which you can play this card game.
How would you do this?
Complete these numbers
Question 8:
? icon,card edges
= ? (cards)  ? (icons/card)
= ? (icons)  ? (cards/icon)
Matching Game
Q3
0
1
2
3
4
5
6
q=7
0
1
2
3
4
5
6
Answer 8: