All language subtitles for resolution

hello everybody welcome to week three of
logic and semantic approach languages so

this week we're going to talk about several
topics related to solving satisfiability

proving that something is unsatisfiable
or proving that something is valid

we're going to see a number of different
techniques in particular we're going to look at

the resolution proof system we're going to build
on top of this to come up with the so-called dpl

algorithm for performing for checking whether or
not a formula is satisfiable this is also as i

mentioned in the first week the building block of
of modern set solvers let's move on with this uh

with the first topic we're going to first
look at the resolution proof system now

and the goal of the resolution proof system
is we want to suppose we want to prove that

a formula is unsatisfiable or that a formula is
valid how do we go about it there are a couple

of things that we've seen now the in fact
the only automatic techniques for doing that

that we've seen is just the truth tables
yeah we've also seen last week a method of

equational reasoning that is using boolean algebra
axioms for performing syntactic manipulations

from your original formula and to further simplify
that formula to eventually get that to either

top or bottom yeah so that's one way
to prove also that a formula is valid

but this is not automatic and unfortunately at
the moment it's not easily automatable as well um

so so far the only automatic method
that we've seen is just semantic based

we've got we're going to look at another
method now it's called resolution so this is uh

it's a pretty simple and widely used proof system
and this can be used for proving that a formula is

well but the setting the basic framework
of resolution is to prove that a formula is

unsatisfiable and we assume that it is in cnf
yeah so and firstly observe that validity and

unsatisfiability are of course dual notions you
remember that a formula is valid if and only if

it's negation is unsatisfiable so you can reduce
validity to unsatisfiability and vice versa so

what about the restriction that the formula here
yeah we assume that a formula is in cnf so we will

see later on that this is not a restriction
so there's a way to convert general formula

into one in cnf so we've seen we've seen a
way to do that before of course last week yeah

but the method is not um yeah i mean in general
it gives a formula that can be quite large

now yeah so we're gonna see another method for
doing that that is more efficient it's called

the sightings transformation and this week later
on this week we also got to look at the um the dpl

algorithm so this is which is the basic building
block for modern set solvers fast modes or solvers

like for example z3 yeah and this dpl itself
is actually also based on resolution per system

so let's take a look at
the um before we go through

the formal definition of resolution and more
technical details like proofs etc we first just

going to look at the intuition of resolution
so the concept of resolution is pretty simple

and i will explain to you by example firstly i
will tell you what it uh uh what is a a single

resolution step after that i'll tell you what it
means by um the yeah what this entire proof system

consists of so let's say you're given already
a formula in cnf yeah so this formula here

um as you can see it's in cnf it has two
clauses okay so a single resolution step

consists of the following firstly you pick um you
identify two literals from the from two clauses

in the formula yeah that are opposite to each
other in this case you can see for example q

and q prime of course these are two opposite
literals yeah so we want opposite literals in two

different clauses they seem really important yeah
so two opposite literals in two different clauses

so from here what you can do is you can derive
a new clause by eliminating these two opposite

literals so you simply eliminate them and then
you union you take the union of the remaining

literals yeah so this p r and t so this is what
you get and then you get you derive a new clause

this new clause here and

uh what you do next is you add this thing
this new clause into the formula yeah

and you get this bigger formula here okay so
you get this one here the first one second

one and this is this is the third one yeah so um
just to make this more a little bit more precise

this new class is actually semantically
entailed from the original formula

and therefore the new formula here is actually
in fact equivalent to the initial formula so um

yeah you can for example try to prove
that in this case for example here

by a little uh semantic argument so why is this
new clause entailed by this initial formula

well so so for example you take a you take
an interpretation that satisfies this formula

then we know that either q or not q that that
is q is assigned to one or assigned to zero yeah

in the case where it's assigned to one where
where q is assigned to one then this p this

either p or r has to be true because i in order
to make this um clause true because uh we assume

that this it satisfies this formula here yeah
so this has to be this thing has to be true so

then it's what either one either one of p or
r has to be true therefore this new clause is

true that is the interpretation of this uh
in uh over this new clause is true and also

yeah when q is assigned to 0 then t has to be
true in order for this initial in order for

this initial formula to be satisfied by the
model and therefore this the model also the

interpretation of satisfies t here yeah
so that's a little semantic argument that

you can apply in order to check that this
actually is entailed by the initial formula

now a resolution proof system is extremely
simple so you it goes as follows you

are given your initial formula in cnf
and you just have to keep applying this

resolution steps of course
different resolution steps

um until no new clauses could be added
yeah so that's that's pretty much it and

yeah and the theorem here is that the initial
formula is unsatisfiable if and only if the

empty clause um the empty clause that is uh
uh this guy here that we write like this yeah

bottom because it's actually unsatisfiable
empty clause is generated by resolution

so we're going to take a look at a little bit
more details now on the resolution proof system

um in order to talk about the resolution

um system it is convenient to assume the
so-called set representation of cnn formulas

so the key idea here is as follows so claus
remember it just a disjunction of literals yeah

and disjunctions of course satisfy commissivity
sensitivity and adam potence we saw last week

so we can then because of this
we can then represent a clause

as this as a set for example if you look at the
example here so the clause here on the left can

be represented as the um as the set on the right
here yeah and of course um the idea here is that

take every literal and just put that in that set
take delete every literal in the class put it in

that set now if you have duplicate literals of
course this will be removed but then that's fine

it doesn't really make any difference just
because of the adam potent properties of um

so likewise a conjunction of formulas can also
be represented using a set i mean just because

of the connectivity and associativity as well of
and this of course also other importance of con

of conjunctions um now uh the idea here
is that every clause will then just be put

in the in the biggest set as opposed to a
literal so you can for example um represent

this formula here okay so you can see a formula
in cnf yeah so this so this has a bunch of clauses

so each clause here will be represented as a set
and after your percentage clause is set to just

put the um you just put the um just make a bigger
set that consists of all these classes yeah so

for example you uh for this example you simply
create this bigger set and each of this guy here

will just be put as the um inside this bigger set
yeah um if you have for example duplicate clauses

then the duplicates of course will be
removed but it doesn't make any difference

it's fine yeah so that's the representation
of cnn formulas using sets of sets of literals

i have a couple of um questions for you
little questions just to check whether

or not you understand uh the um how to do this
conversion and what it really means when you see

a sienna formula in this representation yeah so

which ones of the following formulas are
unsatisfiable so i have five questions

here i encourage you to think about this for
about two minutes before you continue the video

okay so let's go through the
solutions to this uh to this quiz

let's take let's take a look at the formulas one
by one so let's take a look at the first formula

well this is just the same as a formula consisting
of a single clause so this is basically you know

you have this formula here a and of course that's
that's the single clause consisting of a and

so this is of course satisfiable you can assign

one to a then that's going to be a
satisfiable satisfying assignment

take a look at the second one here so
the second one here is you have a and

not a well that's of course not satisfiable
yeah so a and not a as we saw before

this unsatisfiable what about the third
one is it satisfiable or not satisfiable

so let's see what it means so just be a bit
careful here yeah so you see like so the the

braces yeah so you have the the top most uh
so basically you have a set consisting of a

comma not a so the innermost the innermost set
yeah so this is basically just a or not a so you

have um we have a single class consisting of
these two literals a comma not a now of course

if you see this thing then um then you can see
now that this is of course this has to be um

this is equivalent to the equivalent to top this
is basically just the valid it's just a tautology

so it is of course satisfiable now we have these
two little uh i would say like corner cases here

so what are these corner cases well firstly
what do they really mean so this is just you

have basically um empty sets at some level here
for four and five so let's take a look at um four

four here is you have a single clause consisting
of well you have a single empty clause

in the uh you have a single empty clause in
the um in the formula so what does it mean

by an empty clause remember if you have
an empty conjunctions yeah so let's say

one up to um it's a zero you have um that's
a literal so do you remember what this

conventionally uh what this convention means
if you have um if you have an empty disjunction

so this is interpreted as by convention
this is interpreted as bottom okay so

this would mean that the formula here
actually is just equivalent to bottom

okay so of course that would
just be the unsatisfiable formula

so what about this one here so
here you have an empty clause

story not empty clause empty
conjunction so empty conjunction

by definition or by a
convention uh sorry this is uh

so empty conjunction of clauses so if it's empty
it's always interpreted as top yeah and therefore

this is simply just the yeah this is just
the um the tautology so therefore this

this uh this is a satisfiable formula okay yeah
well that's pretty much it for the in-class quiz

um let's try to go through the resolution proof

um the resolution step in more detail in order
to define this resolution step in more detail

we need to we need the notion of a resolvent
so the resolvent here intuitively speaking

is the clause that you generate after you find
this uh two clauses with conflicting literals yeah

so let's um formalize this so you're given two
clauses c and c prime such that you have literal l

in c and you have the opposite literal not l
in c prime okay so this is for some literal l

then the resolvent of cnc prime is defined to be
the following clause it's the clause this is the

clause r and obtained by you take the union
of c minus l yeah so you remove the l from c

and you remove the and then here you all and then
you a union c prime where the where not l here is

removed from c prime okay so that's the uh that's
the notion of resolvent this the new velocity

generate after you apply a single resolution
step here that we you saw um let's do so before

so here's an example so this here this p t and
r is a resolvent for the the two clauses here

so this is the example that you saw um the second
slide and what's going on here so you as you saw

before the what is the l here the l here is simply
this yeah the l here is just oh here's q yeah okay

right so that's uh the notion of resolvent how do
we formalize this uh resolution uh proof system

so this can be formalized in two
different ways so this is the

so the first way is to think of it as some kind of
uh some kind of um fixed point computation so we

the idea here is um given your original set of um
clauses um you want to keep generating resolvence

from your original from your um from your set of
formulas from your set of clauses and then you

keep adding it to your you keep adding it to your
set of clauses yeah and then you keep you keep

applying it until you can't really get any more
resolvence out of it so here can be formalized as

follows you you you derive here uh you define here
the following function press yeah and this takes a

set of clauses and this will return a set of plots
the set of clauses that you return always subsumes

the original set of clauses as you can see here
f is contained in the um in the output of rest of

f okay so um so what is here well if r is a
resolvent of f yeah then you just add that to

your um to you you add that to f okay so this
is a single resolution single resolution step

and then you can define it um and then you can
define res rest n of f yeah so this means applying

this operator n times to f and this can
be formally defined using using induction

as follows here yeah so initially the rest of rest
0 of f it means you don't apply anything so it's

basically just f so rest n plus 1 of f is obtained
by applying res applying res to this rest n of f

yeah so which is we assume already uh is already
defined so this is uh um the formal definition of

uh rus and uh rest n of f and we define the limit
yeah this is star yeah of uh res restart of f

to be yeah simply you just take the union of all
this rest n of f yeah so um so it just means that

so this is uh this this basically the set of
all clauses that we can obtain by applying

zero or more resolution steps to f
right so the second way to define this

is to use the notion of uh to define
the notion of a proof right so

um here's the definition so given a set of
clauses f a sequence of clauses of course

it's just c one of the c n yeah now a proof would
just be a sequence of clauses such that either

the following is true for h clause c i so c i is
either in f that is one of the um pluses that you

started with or that c is a resolvent of two
clauses that appear in this sequence okay so

meaning that they were either already in f or they
were already previously derived using these rules

here so this is what it means by proof also known
as the derivation yeah so and this is a derivation

of the last um the last clause here the derivation
of c n from f in this case we just simply write f

and here you can note you can see here there's
a new symbol a single single turn style yeah

f single turn cell cn so this is another way
to write or to say that f can be used to prove

cn or f proves cn or says cn can be
derived from f using resolution so

okay so here's an example
of a proof using resolution

so and here i of course you saw the notion of a
proof is a sequence of clauses but there's also a

visual representation of this yeah so the visual
representation this is more like a tree-like

representation it's more sometimes more convenient
when you want to write it down when you want to

present the proof to other people so let's
see how do you apply resolution steps here

this there are several ways here that you can
approach this so for example you notice that

there are already a number of places number of uh
there are already several clauses here that have

conflicting literals for example here i have this
q and q uh q and q prime yeah sorry q and not q

and you also have r here i'll just take a
different color r and not r and then also here you

also have p and not p right so you have several
ways to proceed um and you can proceed in any way

you like so let's take a look [Music] so firstly
of course we are going to represent this using

the set representation so this is what you have
so you can for example proceed by by taking the

resolvent of the second and the third
clause yeah so if this is the resolvent here

that yeah would be this q you eliminate the r
and not r and then for example you can then pick

the this one here so you have this q and not
q so you can then eliminate this q a not q

and then you get p right this is the resolvent
of these two clauses and then you can then uh

for example look at this p and then not p
here yeah um so p and not p here so these

are uh two clauses with conflicting literals so
you remove the p and not p and take the union

you just get the empty empty claw okay so so
this is as i mentioned just now this is this

three representation of proofs is also called the
proof tree so it's uh more descriptive sometimes

than the cumbersome proof sequence so you could
for example instead of this you could just write

it down like this yeah so this is like the first
formula so the first clause second clause third

clause and then just keep writing this down
and at the end you just get the bar okay so

so here are some exercises for you so apply
resolutions on the following formulas and

determine satisfiability of these formulas so i
will give you guys about um let's say about 10

minutes to do this examples and afterwards we'll
talk about the uh we'll go through some of them

okay so let's take a look at the solutions to
the exercises let's try the first example first

um in this case what we're gonna do

remember we're gonna have to first translate
it to the set representation so we have

oops let me change color x y not x comma z

not x comma not that and the other
one is x comma not y right so what

what are we gonna do now what are we um
which two clauses are we gonna pick so first

when we see these four classes the best thing just
a little trick here we want to we want to try to

generate so the rule here or rule of thumb yeah
is to try to keep it simple we try to generate a

clause that is as simple as possible yeah so this
is uh um this is always good if we can do that

and in this case we can take a look at these two
clauses here the first one and the fourth one and

these two clauses you see that the only difference
here is just the you have y and not y right

so let's try to take the compute the resolvent
for that so this is a little bit far and if you

want to try to draw it nicely you might need to
kind of shuffle things around a little bit but

that's not a problem because we are doing
it the first uh the first time around yeah

so um you would get if you take the
result of this you would get x right right

and now once we've done that we
can for example consider the second

okay so let me just write five
so we can look at the fifth

clause and the second clause so
from here and here you would get

you would get that

yeah and now we can take for example
the fifth one and the third one

yeah so notice that we might need to use a clause
multiple times and this is you closely use the

clause fifth clause multiple times yeah so let's
take fifth and third in this case you would get

not that okay and then

we can just do the six um computer resolving

of six and seven you would get the empty clause
and yeah that's that's pretty much it here

so by by the soundness theorem that you will
see in a bit this would mean that you would

get a formula that is unsatisfiable so uh the this
formula the original formula is unsatisfiable all

right all right let's take a look at solution to
the second question and in this case we don't yet

have a formula in cnf so firstly the first thing
you need to do is to convert it to cnf and in this

case it's actually not that difficult because it
is almost in cnf so you would get you just have to

simplify this so an application it means that
it's just not p or q or r yeah so that would be

not p q or r yeah so this is pretty much
already cnf actually so it's not q s and not r

s and p not s so we can then write
it down in the set representation

set representation we have
not p q r we have not q s

we have not r s and then we have p

s right so let's take a look what we can do now to

apply the resolution proof system

so the rule of thumb remember we always
try we always prefer the smaller clauses

yeah whenever possible or prefer to use smaller
clauses and prefer to generate smaller clauses

um of course this is not always
possible yeah but this is what we

you know what we're gonna try to do because
it's just simpler as human so let's to do

that let's try to do that the let's take this one
and this one for now yeah you would get q comma r

right so let's uh is there something
else we can do here let's try

um this is s okay let's let's do this one now

yeah third and fifth you get

not r yep so now if you do that here
this one and that you would get q

right so it looks like we have to bring um
into play the second clause how do we do that

so this is s remember yeah so this is not
q comma s so what do we have here okay so

looks like we can do the following here so we can
do the second and the fifth class you would get

not q here okay and therefore
this and that should give you

the empty class right so that's
pretty much the solution to the second

the second exercise and therefore it's
also unsatisfiable formula all right

okay so let me conclude with the following
question so what are the differences between

these two symbols we've seen a bunch of symbols
that look pretty similar and this is one of them

one possible source of one possible source
of confusion yeah so on the one hand here

so we've seen this thing used for for
example for entailment also to mean like um

an interpretation is a satisfying interpretation
for some formula or it's a model for some formula

and this one here so we've
used this to mean um that

a set of form a set of clauses in our case of our
set of clauses can be used to derive a clause yeah

so what are the differences between these two
symbols so i will give you a general guideline

here this is a general answer so in general
this so if you have a single turn style a single

stripe like this here so this is typically used to
indicate some kind of a probability in some proof

system so this typically means it's syntactic
and it's it can be uh this can be implemented uh

in uh as computer program and this doesn't have
direct connection with semantics yet at this point

and this notion of this notation is typically used
to yeah i mean this is typically used to mean um

that it has something to do with
semantics yeah as opposed to the syntax

and uh one thing here that is really important
is that we typically uh so for the for example

for this uh for any of this notion in fact any
of this notation sometimes we take um we put

some kind of a prefix like this for example like
rasia so for example we can have this probability

and then with rest we just specifically to
mean that this is probability in um using

resolution proof system yeah but yeah we don't
need to do that whenever the meaning is clear

okay so we now gonna talk about three
important properties of the resolution

proof system soundness completeness and
termination so the first two statements

relate the syntax and semantics typically yeah so
syntax means the proof system so it is something

that is syntactic something that you can just
carry out algorithmically and semantics is

yeah i mean this is not something that is
immediately automatable now the soundness

theorem or soundness property says that for as
far as the resolution proof system is concerned

if the empty clause can be derived then the
formula is unsatisfiable now the completeness

theorem it says that if a formula is unsatisfiable
then there is the resolution proof system

then you can find a proof in
the resolution proof system yeah

namely that you can derive the empty clause from
the set of given clauses so um yeah both of these

properties soundness and completeness are really
important for proof system we will see this theme

several times in this course now the next question
is that is really important is can we make the

proof system a terminating algorithm so what we've
seen so far is that as far as the resolution proof

system is concerned some of the steps you might
have to guess a little bit i mean it is possible

to automate this in the sense that okay so we just
generate all the possible resolvence but it is not

immediate not uh not directly immediate
that this will actually terminate so this

in fact we can actually make turn
this into a terminating algorithm

and it will not be really difficult later on
because in some sense the set of all possible

resolvence is bounded so we will see all of
this we will cover all these three properties

one by one first we're going to talk about
soundness so as we as we just mentioned

if the empty clause can be derived by
resolutions then the formula isn't satisfiable

so we're going to look at a proof of this in
order to prove dishonest theorem we need the

following lemma resolution lemma which says
that if r is a resolvent of c and c prime

then we can add r into the formula without
while preserving the equivalence yeah so

that is c and c prime is equivalent
to c and c prime and r yeah so this r

doesn't really change the semantics of
the formula so let's try to prove that

so in order to prove this it is sufficient
to just prove that c and c prime

semantically entails r yeah so

why is that the case if c and c prime
semantically entails r then so firstly

this the right hand side entails the
left-hand side obviously and you just

need to show that the left-hand side entails
the right-hand side and in order to show that

the left-hand side in tells the right-hand side
of course you can break it down into two parts

this c and c-prime of course intel c and c-prime
so that's not a problem so you just then need

to show that c-s-prime entails are which
is basically what this statement is about

so um so how do we show this firstly recall that r
here is defined as follows so it's um basically c

union c prime but then you remove l this you
remember that we have two con opposite literals

yeah so l and l prime so ln not l so remove
l from c and then not l from c prime yeah so

so let's say we are so in order to
prove this we assume we are given

an interpretation that satisfies c and c prime
yeah so in order to prove that this i satisfies r

we break it down to two cases the first
case is when the um when l is set to

1 by i yeah so this is the first case here in this
case l prime in this case l prime for some l prime

in um l prime in this c c prime um c prime minus
not l of course yeah because um so this is um this

is gonna be set one by i the reason of course is
that the literal not l is not satisfied by i so it

but this is because if because it's conjunction
you have to satisfy at least one of the literals

in c prime so therefore you have this statement
here so the second condition here of course is um

so this is when um this literal
here that is not l is satisfied by i

so that is you set l to be zero so in this
case this case is just completely symmetric

so um one of the uh literals l
prime in c in this in c minus l here

going to be set to true it's for the same reason
as well so in either case we have i satisfies

the the resolvent yeah because one of this l prime
so the l prime here will be in the resolvent so

okay so that's the resolution
lemma that's the end of the proof

so we're now gonna use the resolution
lemma to prove the sauna's theorem

so the proof goes as follows
so we're going to prove that

we're going to prove something more general that
is if c can be derived from f then c is entailed

by alpha so um of course if we just set c to
be the empty clause then um this would be the

statement of the theorem here that we want to
prove here so let's try to prove this this more

general statement and we're gonna do this by
induction on the length and of the proofs of

oops let me just yeah um of the proofs of
this so we're gonna start with n equals zero

um and in this case the length of the proof um
yeah so if the length of the proof is zero this is

basically the very last clause yeah so this means
that this actually has to be in f itself yeah

this has to be in this has to be one of the um one
of the clauses one of the clauses in f we have not

actually applied any resolution steps at all this
would immediately imply that f intel c because

this is enough so this is very this is really a
vacuum statement so now let's take a look at the

um inductive step so we can assume that n is
greater than zero and we have an induction

hypothesis that if c can be derived from f in in
this case n minus one steps yeah then uh f entails

f intel c so this is basically what is written
here so um say we have the proof c1 up to cn

and in this case the cn here
would be would actually be c now

so induction hypothesis gives us that
f semantically entails ci for each

ion between one up to n minus one yeah so um so
this because the length is shorter now so there

are two cases here the first case is that cn
actually is already in is actually already in

in f yeah but the in in that case is um it's
really the same as this the base case it's vacuous

here so let's assume the more difficult case
where c n is actually a resolvent of c i comma c j

yeah in this case where i s i and j are less than
n so in this case we by resolution theorem we

have this c i comma c j semantically until c n
okay so this resolution theorem and we simply

then have to combine this statement here double
star with a single star here yeah to obtain that

f semantically entails c n this is because of
transitivity of course yeah so we know that f

semantically until c i am semantically
intel's cj now this would imply that

f would also semantically intel and then
because ci and cj in semantically intel cn

then you uh f would semantically entail cn
so this is because of transitivity of of

this um of the semantic end element okay so that's
basically the proof of soundness the sonos theorem

okay so we're gonna now move on to the
proof of completeness theorem for resolution

that is we want to prove that if
the given formula is unsatisfiable

the empty clause can then be derived by resolution

and our proof proceeds by induction on the
total number of variables in the formula f

so what is the base case here it is it is
the case when the formula the given formula

has no variable at all can there be such
a is there such a formula the answer is

yes there are two types of we have two types of
formula with no variables the first one is the

the formula top and the other one is
the formula bottom yeah so both of these

can be represented using conjunction of
clauses the first one of course but the

only one that is unsatisfiable of course is
bottom which is this one as you saw before

and in this case you have
precisely one clause and the

the proof of the empty clause
of course is just consists of uh

of a single of single clause here so it's
a proof of length of like one so this one

is uh the base case is easy so we're now
going to move on to the inductive case

so we want to prove that given a formula
with n variables let's say x one of x n

yeah if the formula is unsatisfiable then the
empty clause can be derived by resolution so

we of course have an assumption the inductive
case yeah basically this statement but for

formulas with up to x sorry up to n minus
one variables so how do we create a formula

with small number of variables from this given
formula with n variables the is that we're going

to do some kind of a substitution particular
we're going to create these two formulas here

from the given formula f yeah so let's
say the formula the given formula is f

so this is obtained as follows we're going
to substitute for the first one we're going

to substitute the value 0 into f sorry
into into the variable x yeah and you do e

of course after that you simplify yeah so this
basically going to be interpreted as bottom

you just apply the standard simplification from
boolean algebras to get rid of the bottom yeah

and after that um you also construct the
formula the second formula here and this

is done by simply substituting one to x and
in the order in the original formula f yeah

so the same thing you after that you also
have to simplify removing the top from the

resulting formula now since the formula
f is assumed to be unsatisfiable

both of these new formulas here must also
be unsatisfiable and this is easy to see

um so what do we what can we then say the
first one is that the first formula because is

unsatisfiable it will have uh it will have uh by
inductive hypothesis by the induction hypothesis

then you have a proof of the empty clause by
resolution let's say the proof is this c1 up

c1 up to ck okay so the ck here is going to be
the empty clause so what we can do now is we can

put the xn back to these clauses and we're gonna
then get uh we get a derivation ending in either

bottom or x n yeah now the same thing we're gonna
do the same thing for the second formula here

so we're gonna get the same a
different possibly different

resolution proof of the empty clause

and we're going to do the same thing we're going
to put x and back to these clauses and then the

derivation that we're going to get after that
will end in either an empty clause or not x n okay

so let's finish off the proof so if any of
these derivations after we substitute xn back

contains the empty class then we are done
because we have a proof of the empty class

otherwise we simply have to combine the these two
derivations that will which will then contain both

xn and not xn so after that we can then just
simply apply one resolution step to this

clauses and derive the empty class so that's
pretty much the proof of the completeness theorem

so here's a little exercise
for you so we know that

we can apply resolution to prove unsatisfiably
but what happens in this case here so we have

these two clauses

we can apply resolution once we let's say
we get that but after that there's nothing

more that you can apply yeah we are we're kind of
stuck so what kind of what kind of things can you

say now by component and completeness and think
about it a little bit before you see the answer

yeah so the answer here is that this means that
the formula is satisfiable so if this satisfiable

you should be able to give a satisfying assignment
and what would be a satisfying assignment for this

so you can think about it the answer is not that
difficult so simply have to set p to zero yeah

and q to zero this will give you a
satisfying assignment for the formula

here

right so

we conclude now with the last property
of resolution which is that it can be

turned into a terminating algorithm how
do we do that well in order to do that

the most important question here is the following
remember the notation here this means that

f together with any resolvence of f that can
be applied that can be obtained by applying

any number of resolution sets so what's the
maximum size of this is this infinite set

the answer is that this is not an infinite set
this is uh always a finite set and in fact you

can come up with an estimate for this yeah since
each variable in f so let's say you have x1 up to

xn yeah so n variables can either
appear positively negatively or not

appear at all in a class then the size
of this set is simply you can obtain by

simple counting but this has to be less than
or equal to 3 to the power of the number of

variables in f yeah so this is finite but
it's exponential it's a large enough number

but in any case this would imply immediately
that the resolution procedure is guaranteed to

terminate that is as soon as you um stop producing
new resolvence you just stop so um we're gonna

know um i'm just gonna leave you now with a couple
of general questions regarding proof systems

that we're gonna revisit in uh uh in two weeks
first question actually in a week or two yeah

so the first question what is a proof system
so we've looked at resolution proof system but

what is the proof system in general what's it
really mean so the second question is what does

using a proof system require one to understand the
semantics of a given formula or this is something

that is easily automatable third question is the
method of checking validity via a truth table

so this is a proof system so yeah so this
is these are the three general questions i

want to leave i want to leave you with the admit
multiple correct answers to these questions but

i want you to think about this a little bit and
to come up with your own answers and of course

also to just to have a justification of your
answer as well right so um that's all i have for

the topic of resolution per system we're going
to next move to the topic of the pll algorithm