Original subtitles

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