All language subtitles for tseitin

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