Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
[Offical] Assignment 6 and tutorials before/after Christmas
I’ll upload Assignment 6 tomorrow as usual. It will be due over Christmas.
Next week only the tutorial Tuesday 14:15 will take place and cover A6.
After Christmas tutorials will resume on January 11.
I have a question about problem 6.2. We shall create two bijections:
- “f mapping satisfying assignments of P to solutions of P’”
- “f’ the inverse of P”
So 1. is a bijection that maps from satisfying assignments of P to solutions of P’. Since it is a bijection, it also maps from solutions of P’ to satisfying assignments of P. That is the part I understand.
But I don’t understand what 2. is supposed to do. Should it map from P to the inverse of P (and vice versa)? If so: what is the inverse of a SAT/CSP problem? Is it the negated one? (And how should such a mapping then look like in detail? From satisfying assignment to the respective unsatisfying one in the negated formula?)
I would actually have thought that the first bijection is enough in order to show that SAT can be reduced to CSP. So I don’t know what the second bijection could be used for.
1 „Gefällt mir“
And a second thing, this time regarding 6.4: var(X) is a Prolog built-in predicate. See https://www.swi-prolog.org/pldoc/man?predicate=var/1. Are we allowed to call it “myVar(X)” instead? (To avoid confusion, wrong results and bad syntax highlighting if the editor assumes it is a built-in predicate.)
This is a typo. It should be f’ is the inverse of f.
I assume that resolves your confusion.
That wasn’t intentional. I’ve renamed it to vr.
1 „Gefällt mir“
Just to make sure I am not misinterpreting anything: So should f’ map unsatisfying assignments from P to non-solutions of P’?
Edit:
In case someone is reading this because he/she wants to understand the assignment:
If I have understood it correctly in the tutorial, f simply maps from satisfying assignments of P to solutions of P’. And f’ simply maps from solutions of P’ to satisfying assignments of P.
Tbh, I don’t think the term “bijection” is then used correctly in the assignment. We rather define 2 injections here. But whatever…
So we have a function f that maps satisfying assignments to solutions and f’ that maps unsatisfying assignments to non-solutions? Why not one function f that transforms any SAT to a CSP and we prove that they are equivalent?
How are we supposed to get the solutions especially for 6.3.1 if we weren’t able to attend this one Tuesdays turorial?
I attached you my notes of yesterday. Maybe they can help you a little bit. Besides the original problem we also looked at a more complicated problem (rightside of the notes).
Attachment:
assignment6_31_compressed.pdf: https://fsi.cs.fau.de/unb-attachments/post_165829/assignment6_31_compressed.pdf
2 „Gefällt mir“
a
Thank you, I’m sure your notes are as helpful as they could be. But without any explanation, it’s impossible to understand the approach, and I think the tutors know that, that’s why they said 6.3.1 is for the tutotial. That’s why I’d find it very disturbing to just cancel almost all tutorials in this week on short notice without any replacement. But at this point it looks like this is what happened.
Well it was also told at the biginning that Gloin sort of a requirement for this course. This stuff was taught in Gloin so i guess that’s why they went over this so quickly.
I announced we’re merging the tutorials because usually not many people attend before Christmas anyway.
Also, it was a convenient compromise to save a few tutor hours that we’ll still need for grading.
Since I didn’t receive any further inquiries, I assumed everything is alright.
Anyway, I’ve uploaded the solutions for 6.3.1 now.
No. Both f and f’ map solutions of one problem to solutions of the other.
Yes.
No. They are not only 2 injections. They are additionally bijections that are inverse to each other.
Could you also please tell where? thx
I also think its prettty tough, at least for all students from other fields who dont have any knowledge about the topic allready…
Are the tutorials next week gonna cover the topics again? Because i couldt participate at the only given tutorial.
Also i think its hard to say, that not too many are participating in the week before christmas, especially now with covid i think most of the students were reguarly studying until the Christmas Break.
At least for me its nearly impossible to get the point out of the notes, as the whole Logic proof theory is kind of abstract to me.
3 „Gefällt mir“
Ugh, I didn’t see my push to my website didn’t go through.
Since some people didn’t have a chance to attend a tutorial, I’ve extended the deadline until the end of the week.
Solutions posted