Original subtitles

hi okay so we're gonna move on now to satin's transformation and for this we have two sets

of materials for you so one of them is the lecture slides here like your notes i meant

and the second one is the lecture slides here so the lecture slides

well that's um divided into two parts the first spot is going to be a little overview of satin

transformation it gives you some intuition of how it works uh with some animation as well but

the second part will be on the pll algorithm itself so we're gonna go through the lecture

slides and i'm just gonna pull it up here so i have this in keynotes um so let's go through that

so yeah so the first thing we're going to do now is we're going to look at

saturn's transformation so the motivation is that last time we have looked at um

the following theorem that every formula can be converted into both cnf and dnf yeah

but if you remember how it works this gives you an exponential blow up in general

and here is uh in fact um a little example where the little example of formula where

the um the equivalent formula in dnf has to be at most exponential size yeah so um uh i'm not

gonna give you a proof for that but yeah so this is uh something that i'm just going to leave it

for you for homework and we will try to go through this at some point in one of the

following um one of the following lectures okay so um now that we know assuming this we know that

um the transformation the knife transformation uh using distributivity yeah that we saw before using

um using boolean algebra axioms yeah will inevitably give you something

that is of exponential size yeah so the in fact yeah so the this uh this

proposition here says that this is unavoidable so you cannot find an equivalent formula in dnf

that is of size that has to be of size that is of size better than exponential and in fact

the same thing can be proven if you want to go from a formula to cnf because if you remember

or and and they are dual yeah so you can actually in fact um also show the same thing using um

we can also show the same thing here for the cnf um normal form okay so

now if you remember resolution we've seen that resolution only works on cnn formulas yeah

and in fact modern set solvers also work on cna formulas yeah and

one way to achieve this is that is one way to avoid this exponential blow up yeah

to is to perform the so-called side since transformation yeah so this is important

because if you want to be able to just only work on cnn formulas it is important to know that this

um normal form yeah is general enough yeah that's uh if you have a formula it doesn't require you to

transform it into something that's exponentially large before you can actually process it

so this is an extremely important um [Music] this is an extremely important prerequisite if you want

to be able to make this kind of resolution and all the uh modern sets all this work and if you

um you've done a bit of uh programming in c3 yeah and as you see i've noticed like okay i don't have

to actually in fact convert anything to cnf or anything yeah so but um z3 does this explicit uh

implicitly for you okay but this is that is not the case for modern set solvers yeah well i mean

for some modifications they do this uh titan's transformation automatically for you but in most

cases you do need to actually do it yourself and import in fact it is important for you to know um

how this work but you know saturn transformation is actually not very complicated but the key thing

about sizes transformation is that it does not produce a formula so this transformation

does not produce a formula that is equivalent to the original formula but it produces a formula

that preserves satisfiability that is the output is satisfiable if only the input is satisfiable

and in order to do that we actually have to as you will see the set of variables of

these two formulas will actually not be the same right so let's take a look at

some examples how to do this so here is the crux of the reduction we're going to show this

by a little picture a little example with some pictures so here's a formula um that is

not in that it's not in cnf but it is close to uh cnf so i mean here i depict the um

parse tree of the formula but um so if you in case you forgot how um the notion of parse tree

formula so i can i'll just write it out for you it's very intuitive here so um at the top here

you have a conjunction of guys yeah and each of the sub formula consists of this bit that

bit and that bit okay so let me write it down so you have conjunction of three sub formulas

so the first one is hold on a second so you have um

not p or yeah so that's the first conjunct and second conjunct is rp

and then the third conjunct is not b or not q

right okay so that's uh if you take a look at this this is not really in cnf yet because of

the because of this right so this is not because of this thing here this

the first conjunct is not yet a clause so um how do we turn this into a clause so you can of course

do the knife transformation and distributivity but we're not going to do that we'll show you how

to use the titan's transformation here and this can be of course generalized to other examples

so the first thing you need to do for scientist transformation is you need to find a minimal

non-literal sub formula so that is you want to find out you remember the notion of sub

formula before right so you want to find a sub formula a minimum sub formula that

is as small as possible but it should not be a literal okay so it has to at least contain

it has to at least contain an n or an or and the first um and a minimalist non-literal sub formula

well they're actually um um as you take a look as you see here there are um in fact there are

three types of non-literal sub-formula a minimal non-literals of formulas and these are namely

this one here one two three yeah these are the three non-literal uh minimal non-literal

subformulas so minimal here so this literally means you have to have a conjunction or a disjunct

conjunction of literals or disjunction of literals and you have to at least have one um have you have

to at least have one binary operation here okay and um for our argument's sake here because if you

take a look at this the closest this is almost a sienna formula yeah because but only because

of the first minimal non-literal subformula here then this is actually not yet a cnf

right in cnf so we pick that one right we pick this guy and what we're gonna do next is we're

gonna introduce a new variable yeah let's call it x and we're gonna say that x is true if and only

if this minimal non-linear subformula is true okay so you will say so we'll introduce a new variable

and assert that this is equivalent to this guy here okay so we will um do that and if you take

a look at this if and only if statement that it is equivalent yeah so this would look like um

the formula is uh what was it again um i almost forgot let's take a look

a little bit uh r and not q

okay r not q so you want to say like x if only if

r and not q yeah and if you take a look at this accident leave r not q this is pretty much

equivalent to a conjunction of this so um if you expand this if and only if you into

into if you remove the iphone leaf you basically get the conjunction of f1 and f2 and f3 okay

so uh you just simply have to assert this if only statement yeah

then you just simply have to put it at the top here because you have the when i set

top means top level which is here yeah so you have to put it here and you just have to say

x if and only if r and not q and of course each of this thing you convert into a conjunction of these

three guys f1 f2 and f3 and yeah that's pretty much it so if uh have a look here this guy here

that we just have replaced this is no longer this is you you don't this is actually now

just a single variable yeah so you don't uh you don't have some form you don't have a minimal non

literal um sub formula anymore it's just a single variable now so the um the original formula itself

that is uh uh excluding f1 f1 and f3 actually gets smaller each time when you do this replacement

right so that's pretty much um what you do and this has to result in something that is equivalent

uh equivalent in the sense that um uh something that is uh that that preserves satisfiability

because what you're really doing here is that you take the original formula and you just replace it

replace a particular subformula okay it's gone and then you just basically

say that this particular uh you replace it with a new variable and you just have to

somehow axiomatize this new variable you just say that this new variable is true if and only

if this is a formula is true right so this is um intuitively how it works of course this requires a

proof and we'll go through some the reason why this is the case there is the proof for that

in a bit of details uh later on but before that let's take a look at some um some question here

how big is the size of the output formula if you do the following yeah so this uh of

course requires you to think a little bit about it yeah so you do in this case here yeah so you

only you have just done one step right you have only done one step uh of this replacement if

only introduced a single variable but what can you say here about the resulting formula well

in general if you have a formula that is more complex than this you will you might

have to do this for every minimal non-literal subformula and at some point if you keep doing

this of course we will get into a a single the case of a single literal yeah so um this

procedure will eventually terminate at some point because the original formula that is of course

excluding the new conjuncts that we just introduced just now f1 after and f3 here

this will be this will this will get reduced each time but what can you see now from the

um from the from the construction here or from the transformation if you keep doing this thing let's

say you have formula of um let's say you have um n boolean operators uh binary boolean operators

so if you if you have that you will have to at most perform

and and times of this of this replacement right and each time you perform this replacement

you will introduce uh three coin jones well sometimes you might you might have to you

might have to um so yeah we have not gone through the case of or but i will say that it's uh it's

very similar in fact this will be less you have to introduce i think only two conjuncts instead yeah

but as you see here you each time you do this you only you remove one part of the you remove a sub

formula a minimal sub formula that is something of size um so it has to be of a constant size yeah

and you then have to replace this with the formula of a constant size as well yeah so

and then you have to do this n times yeah so um because it's you do it n times then this has to

be linear basically right so um the increase here is actually linear so the resulting the resulting

formula yeah after it's saturn's transformation has to be linear in the size of the um

of the original formula and also um you you also have a you can also ask me the following question

for example like okay so this resulting uh this at the moment here this resulting formula this is

this uh what do we need to do anything more here so the answer is yes you can do more thing here

you can actually keep going and apply saturn's transformation but um here as you

see here this is already in cnf so you can stop as soon as you hit the cnf okay

so um that's pretty much the general overview of that of the of saturn's transformation

yeah with a picture and also i told you the size is uh is linear but let's go through some

details now um just so that you get well i guess you can get a bit more intuition and also the

you can also see why this is uh this relief is of satisfiability so for this i need to go um switch

to a different window so let's open this up so this is the node from

here yeah and i'm gonna open this in a different window which is this one

okay

right so let's go through a bit more details on titan's transformation

so firstly

remember we want to produce given a formula that is not necessarily in cnn if we want to produce a

formula cnf that is equally satisfiable that is it preserves satisfiability in other words the

original formula is satisfiable if and only the output formula is satisfiable and the output is

going to be linear in this house with the original formula so we assume now that the input operators

are only not or or n yeah and we assume that this is already in n f okay so

because we saw before that the transformation to n f is pretty simple and this is uh also also linear

so also recall that we've defined the notion of subformulas yeah so this is uh [Music]

so this is also written here just for convenience

so i've mentioned the notion that a formula um that we that sighting transformation

replaces minimal non literal sub formulas each time yeah so here is the definition

formal definition of um minimal non-literal sub formula so as a formula is minimal non-literal

so minimal sub formula is said to be minimal non-literal if it's of the following form here

l dot l prime where l and l prime are literals

and dot here is n or or okay so as i mentioned to you this always has to be

basically it means that you have a conjunction or a disjunction of two of two literals yeah um

so this is also this also explains why we had this um if you remember we had three different

um we have we have three different minimal non-literal sub formulas before in our

in our example on the slides so uh saturn's transformation as i mentioned so this works

recursively you replace a minimal non-literal sub formula by a new variable and then you're

gonna assert that this new variable is equivalent to the um is equivalent to the um the formula that

you replace it with so equivalent here simply means if and only if yeah so i use the so be

be careful here by uh when i when i wrote the uh when i when i say equivalent here okay so

this simply just says x if only if psi okay so this is an axiomatization of psi so to speak

okay so um basically if you want to formalize this thing so what you do here is that initially so you

you you have this set of formulas that you carry around initially you set this to be

an empty set and what you're gonna do is you're gonna while you recursively replace an unliteral

sub formula l dot l prime by phi okay uh of by a new variable x you always add this axiomatization

that is uh the um the formula that asserts this is uh that this actually defines this l dot l prime

yeah x defines l dot l prime you add this formula to c okay so there are two cases of course uh so

i'm gonna let's go through this one by one so this is actually the case that we you

um we went through already so in the case of uh that the for the the operator is n

this contains precisely the following clauses yeah here the following three clauses here now this

simply of course uh if you take a look at these three clauses here this simply just says that

x if and only if l dot l prime and if you expand this thing this is says this is equivalent to

this first formula and the second formula and the third formula okay so you just remove the ethan

leaf and the same goes here with the second case yeah so this is basically just an expansion of

the formula x if and only if l or l prime okay so you get these three clauses here yeah so that's um

that basically you here you do this isn't it really just an equivalent formula

okay so so this is what i explained here as well

and as i mentioned to you this procedure terminates at some point because yeah because

you because the formula fi you keeps reducing it each time you remove at least one binary

operator so at some point so if you keep doing this thing the original formula will get reduced

further and further and at some point you will have no binary operator anymore and in that case

you stop yeah so the formula stops when you have only um when you end up with the single literal

so let's go through a little example which is this one

so if you have a look at this formula here let's take let's try to first identify what the

minimal literal not sub formulas minimal non-literal sub formulas are in this case you

only have a single non-literal a minimal a single minimal non-literal sub formula which is this

y n set yeah so uh what you do here is um firstly you start with phi and c0 is empty set

what we do here is we initially replace y and z yeah by a new variable so this is uh the only

possibility here so um in this case we obtain we follow the recipe here so you have y and z yeah so

you if you just look at this c1 that is you have to add this three guys with this l and l prime uh

appropriately you cover this appropriately yeah using this what you get here is the following

um not x1 so you use x x1 instead of x yeah so you have not x1 or y not x1 or that uh

not y or not z or x1 yeah so this is basically using this recipe here now oops

right so we add this three clauses into c c0 and you get c1 yeah um

and the formula here phi f um phi one so i wrote it in uh as x implies x one but

actually that just simply uh means not x or um x one of course yeah it's the same thing

so now we're going to replace this not x or x1 by any variable x2

and we in to do this we're going add we're gonna do the same thing but then we have this

um we have this three clauses here that we add so let's take a look again here so what what do we

have so we have not x or x1 yeah so we follow the recipe here so you have x2 uh let's have a look

so you have not x2 or l l in this case is not x1 or l prime l prime in this case is x1 yeah

and then you have not l or x not l is uh so l here is not x of course so not l here will be x yeah

and the same thing goes with the last one right so you add this thing to c therefore you obtain

phi 2 equals x 2 and c 2 here is uh not x 1 or y so basically you just skip you add everything here

to the um to c1 so you get this bigger uh bigger set of constraints yeah so the output formula here

in this case is simply just um um the conjunction of this clause in c2 yeah and of course

you have the formula you conjunct that with the formula of i2 yeah so you have this formula

here yeah so remember phi 2 here is already a single formula yeah so you only get x2 yeah

so that's uh basically uh the end of saturn's transformation here so uh one question that you

should think about um right now is the following do you really need to end up do you really need to

keep doing this thing until the very end when you apply certain transformation that is do you really

need to get rid of all the boolean binary uh binary boolean operators from the original formula

well the answer is well this really depends on what you try to do yeah so

this works of course for um set solving okay that this will transform something to cnf and

yeah i mean you but the the thing is that this is something transformation that works in general

so if you want to tailor this thing for set solving for our purposes

it is um one thing to notice of course is that you don't you you can actually you don't really

need to go until the end you can stop as soon as the original formula that is this physe yeah

become that that is already in cnf yeah so for example if you take a look at this this

formula this little formula here this is of course not in cnf this is in dnf yeah

but the second one here the phi one oh sorry not if i one here yeah so this phi one here this is

already a formula in cnf right because this is a single clause so you could actually have stopped

here but i just showed you that we can actually continue um just for the purpose of illustration

yeah but if you want to use this if you're asked for example to transform this to cnf

you could have stopped here and of course there are um again one thing the other thing that is

important is that there are at any given moment there could be multiple options for this minimal

non-literal sub formulas and you can pick different ones yeah but um in general you

yeah this is uh you know this is a non this is not deterministic engine so you can pick any one of

them but if you want to for you're asked to do this and if you want to do this really well of

course you there are certain choices that could lead you to smaller formulas of course yeah so

smaller in the sense yeah i mean you know they are still like only linearly bigger but they are

actually in fact um i mean if you just look at the number of variables for example this can minimal

you can actually minimize the number of variables and of course in the exam you don't really need to

carry it out until the end you just need to stop as soon as it becomes a formula in cnf

so you you need to experiment a little bit yeah and to see what kind of uh

what kind of choices will lead you to a more optimal formula a smaller formula okay so that's

titan's transformation that's the description of the recursive procedure so we're going to

prove this little theorem now that titan's transformation is satisfiability preserving

and in order to prove this this is something

this theorem follows from the more general the falling more general lemma

and this is what the lemma says so let me try to give you a little illustration here what's oops

so what does it say here so suppose you have a formula phi so let me just draw this formula

and so suppose you have this formula phi and you have this sub formula psi

and you pick a variable x that does not appear in phi okay

so the lemma here says that you can replace psi by x and assert that

x is equivalent or x if only psi yeah so this this new formula is uh phi prime

so i'm just gonna put this one like this basically this is the

phi yeah

so this is phi x is used to replace your replaces by x

yeah and

x if and only if psi that's formula um prime so this is equivalent so this is um

this formula phi prime so for any interpretation i that satisfies x if only if psi

that that satisfies this maximization we have that this interpretation cannot be distinguished by

the formula phi and phi prime so the formula phi and phi prime agree on the interpretation i okay

and in particular phi satisfiable if only if i prime is satisfiable

okay so let's try to take a uh proof uh a look at the proof of that and one thing here that i wrote

down for the proof it is important to firstly recall the substitutions theorem so this is

actually an application of substitution theorem but you in fact you need to first kind of look at

a general version of the substitution theorem and this is i'm just going to state it here

basically this two lines here the last two lines of the first paragraph it says that suppose you

take a formula f yeah and um and you have so let me just draw it here so you take a formula f

okay and then you have um maybe i just take different this different

this h here so in different places okay so you have uh f and then you have the sub formulas h

here suppose i take some uh some formula g yeah uh so i just take another formula g yeah and

i plug this g into f here so i replace h by g so i get something like this f

okay so maybe i'll just draw it like this now okay so this is g now

so this is g and this is g yeah so here we make an assumption that uh so take any interpretation

i yeah that's um that agrees on g and h yeah so um that is i satisfies g infinitely if i satisfies h

then this formula this interpretation i cannot really distinguish f uh cannot distinguish this uh

this second formula here that is obtained by replacing every current of h by g and the original

formula f here yeah so this is the original formula f so they cannot really distinguish

these two formulas so they uh they will agree on this uh on on this interpretation okay so into

intuitively it is quite clear yeah because you know so you take an interpretation i so

this uh the definition of satisfaction of course in defined in terms of um is defined recursively

right and when you hit when you look at this uh this definition of interpretation this eventually

goes to um this eventually goes to the subformula h right and in this case h and g they're really

they really really agree on each other um on this interpretation i so they cannot be distinguished

by i so they have to um the bigger the bigger guy that is f and f g h they have to agree on i that's

that's intuitively uh what happens here okay so um so we're going to make an assumption uh we're

going to make this uh [Music] um we can assume this general statement of the substitution theorem

so how do we prove the lemma here um from the uh from the uh from this generalization

of substitution theorem so let's try to prove that so here is the proof

let me try to just erase this thing for us right okay so let's try to prove this

so in order to prove this we consider an interpretation i that

satisfies x if it only if psi so we use the assumption here

and we need to prove that i cannot distinguish phi and phi prime yeah

so let's try to prove this so the assumption here yeah so this is this the assumption so i

satisfies x if and only psi so this is the same as saying i satisfies x if only if i

satisfies psi yeah so this is an assumption of the interpretation that we meant that we take and

so do we have here so let's make use of the substitutions uh this generalization of the

substitution theorem that is here so we have um this is this one right okay so

basically this says that if you look at this part here this simply says that i satisfies

um i satisfy the formula phi where psi is replaced by x yeah if and only if i satisfies phi

okay so this is the just the corollary of this of this generalization of the substitution theorem so

so if we so now we gonna prove it uh from left to right and from and then afterwards

from right to left there so we take uh from right to left here which is basically the spot

yeah so from right to uh sorry left to right so you have i implies 5

basically you now go through this you take a look at this this just says that then you will have to

have i satisfies this will i will just put a star here yeah so this means i satisfies phi x

phi x i but this thing is nothing but um this is a sub formula of phi prime and if you remember if

you want to prove i satisfies phi prime you need to prove that i satisfies this and i satisfies

x if and only if psi yeah so this is uh the thing that you need to prove but actually

that is actually already one of the that's already um that you already assume here yeah

in the assumption here

so therefore we have that i this is by assumption

f i satisfies phi prime okay so this is from left to right and from right to left now

this is written here and this act this part actually is easier i satisfies

phi prime and you want to prove now that i satisfies phi

so how do you show that well i satisfies phi prime so if you look at phi prime again here so

this consists of it consists of two parts and so the first part is uh phi so i satisfies phi prime

well this one here is just uh phi x psi and x

psi right psi so this is basically uh this would imply that i satisfies phi x i yeah and we can now

make use of the generalization of the substitution theorem again here yeah that [Music]

this would imply that uh i would just put um what's a symbol here to use

yeah so i will just put a star again

yeah so this would imply that i satisfy spy alrighty so this is a corollary of the um

this star of course as you saw this is a crawlery of the generalization of the substitutions theorem

so that's pretty much it for this uh first part of the oops i will put this double star so for uh

for the first part of lemma one so in order to prove that phi satisfiable if and only five prime

is satisfiable you just need to define the uh the interpretation i yeah basically by looking at the

um by setting the um the variable the new variable to be one if and only this satisfies the the the

the given interpretation i satisfies satisfies as a formula in the original formula so this is i

x equals one if finally if i satisfy psi here yeah so that's that's pretty much it okay so um yeah

so that's pretty much the proof of this lemma one and of course this would imply that um the

uh theorem one that satins transformation is satisfiability preserving because what

you're doing here really is that your this is a single step of the

of satins transformation and then you each so this is in some sense you would call this

an invariant yeah so each time you perform this transfer replacement each step of tyson

transformation preserves this environment and at the end this basically you will get

the final one will be satisfiable if not the original one is satisfiable

because each of the steps is satisfiably preserving okay