Mod-01 Lec-20 Lecture-20-Examples of Tableau Proofs

So, we were discussing analytic tableau, and
then we have proved some set to be inconsistence, but the definition of inconsistence and consistence
should be looked at exactly the way we have defined, that should be taken that way only
like, you say that a set of proposition is inconsistent. Now, it is tableau inconsistency
not PC inconsistency, so it is told to be inconsistence, if there is a closed tableau
for the set of propositions. So, all that you want is you construct one
such tableau which is closing. That is what you want to check and for consistency just
its negation, that you have to see whatever tableau you construct if remains open every
tableau for the set of propositions remains open. It is never closed, then you can say
it is consistency, for inconsistency it will be then easier, right? For example, let us
see one more, so this set is inconsistence. So, we will be constructing a tableau for
this is a start with all of them at the route, then go on applying the tableau rules. Now,
I see not tab not be there already literals and there are three others which are compounds
propositions on which tableau rule can be applied, and all of them are branching. So,
any one of them I can choose that proceed, so let me chose this one and this is smaller.
So, these gives two branches, one is not s, another is not is that because all that you
remember is if it is in the form a implies b, it is equivalent to not r b, because of
this symmetric trees. So, then it will have two branches, one will be not a, another will
be b. If you founded a tableau rules then you can reconstruct in that way.
Now, what happens nothing is closing really. We have only t not r, then not s another path
is t not r not p. There are of course, other propositions in the path, then one more we
can start with shall We start with this one, they will be same of course, let us try. So,
this one gives again two branches, not of not s and t, another is q, but now if you
go to the other path you wanted to expand it breadth path, then once you are using it
that again you have to add here.So, let us do that, so again this one gives
two branches, not not s and not t, same way this is that, right? Now, this path closes
because not s and not not s, so that closes this path also closes because it is t not
t, same way this we have not. Two other open branches, open paths I have q not, s not r
t and this. So, there I have used s implies not v, this one also has been used first proposition
has not been used till now, right? So, you can still expand this path right.
So, let us expand that path, I will take that path here, so on that I have p implies q implies
r. So, that will give raise to two branches, not of p implies q and r, this one it does
not close. No, there is no not s, not s is this side. This is not closing, only this
is closing not t. Yes, good. So, that also you have to expand again, let us see this
first one is q which is open, there we have this that gives raise to again not of p implies
q not implies rule. That will give two, one is p, another is not q.
So, one is p another is not q, now this not q is closing, correct? There is q, there anything
else is closing it is here, this path we are taking So, we have t not r not s qthere not q has closed, but about p that path still remains open , p and not q, right? It
is not opening branch, they will be on the same branch, right? So, both the things will
be there, you can write p this way and not q this way or sometimes we do not write this
vertical bar, you just leave it. Now, you see that, that closes with q itself, so there
is no open path there. What about the other side there is are you have not r on the same
path, right? So, that also closes. Now, what about this q?
The whole thing will be copied there because there you want to apply this, also the whole
thing will be coming here, that is up to what you see here, that is also for the other q,
right? We have to take another copy really on same page of paper, you have to do it exactly
right. So, that means this strategy inconsistent. Not not s is there, so you have another branch,
there again you have to expand. Now, suppose you expand it, what happens theresame again you
have to come to this base. So, again the same copy will be there. Now, once it is there what do we get? It will close with. P will close with not p, right? What about
the other one, that is r and that is not r, is it clear? The same copy will be here again.
Now, there you have p not q and r p not q in the same path. So, p not q with that you
have not not s, you have not p that closes and is the other one you have r and you have
not r here, that also closes, is that clear? So, now for consistency what should we do?
Let us start say I take only this much, what should I do? So, we start the tableau now,
but the tableau copy is there already, can you see there? Suppose, they do not have this,
I have only 1, 2, 3 propositions. So, for those four propositions I have already made
the tableau here, the first proposition was never used till.
Therefore, this is the tableau, in this tableau what happens I have a closed path, now there
are three other open paths, fine? From these can you say that it is consistent or not? Yes, see I can tell now because all the compound propositions has been expanded with they have
been used, right? Suppose, it is not that I have not done up to that, I just stay here
I just drawn the tree, I do not expand, I keep up to this place. Now, I say that this
tableau is also open because this is also a tableau for the same propositions, same
set of propositions. I have not used them, but as a tableau it
says it is an open tableau up to these, also it is an open tableau, but here you are telling
we will decide that it is consistence, but up to this stage if I take you will say it
is not decidable. Here I have to go for some more steps, right? The reason is we have not
used some of the premises, right? So, that amounts to telling that the tableau should
be completed, is it right? If the tableau is completed then only you can decide whether
it is consistent or inconsistent. The completed tableau if remains open then
it has to be consistent because essentially what happens for consistency you need that
every tableau should remain open, not the completed tableau or any completed tableau,
you want every tableau to remain open. Now, if you take a completed tableau then essentially
it has a copy of all the tableaus because all the premises has been used. So, whatever
there can be expanded either they will close or if they do not close then that open path
will be still present in any other tableau, fine? That is the reason you say that it is
consistent when some completed tableau remains open, you do not have to go for every. Now,
so completed tableau becomes helpful, fine? Let us see one more example how to decide
this say q r r. So, we will start with this said, we do not know whether this is consistent
or inconsistent. So, if you guess that it is inconsistent then you just go for one construction
of the tableau, if I am not able to guess you will be going for the completed tableau,
right? Where on every path a rule should have applied on the compound propositions that
has to be sealed, then it is a completed tableau, but you do not need that even before that
it closes. Then you stop there because a completed path is one which is either closed or if it
is open then. Then all the compound propositions, all the compound propositions rules have been
applied, right? That is what we are going to do so.
Let us start the tableau say you have to take all the propositions at the route, right?
Now, I go for say branch out from this one. So, I get not t u we will take the other one
after this, so that gives me not not r and s and t here also, right? Then I can proceed
say s and t, I will break down , I have not yet checked where it is closing or not, is
it closing? Yes, not t with t it is closing. So, you do not have to expand this further
these also, I do not have to expand. So, there is one more which is to be used, so let me
use it now should guess not p and q r r again here, also not p q r r. Now, not p is there
you do not have a p there from the path and here also you have q r here, again you have
q r, is it a complete tableau, completed tableau each part should be completed.
So, this path it is closed, so it is completed, this path is open, but on every proportion
occurring in that path, every composition proposition tabular rule has been applied.
Therefore, that is also completed if it is any others say this one. So, q r r is another
compound proposition, it may not be the premise it can be obtained from another premise. So,
on that also it has been applied on all this that is also applied, so that is also a completed
path, but open path, right? So, it is said that yes it is completed, but
it is open therefore the set of proportions is consistence , see you can also make it very
mechanical, the way we have done is we have just using which term is convenient for us.
These i thought this will be convenient it is giving only two literals directly so use it
and so on, but when you do it by machine it is not able to find some eristic, right? Of
course, you can give those eristic’s feed the algorithm with some eristic like that,
but let us have a crude algorithm which says you just start the tabula systematically,
take some ordering of the propositions whichever order you decide in the begging itself, do
not change it later. Now, follow that ordering go on using the
rules, but there is one thing which we have to modify that for example, we have taken
not p q r r, this comes from the phrase p implies q r r. Now, immediately we take q
and r here, those two paths we have taken. So, imagine we have not used it at the last,
but used at the beginning, right? I can start the tabula from there itself. Say, I take a copy of that here, okay? Suppose,
I use the first one so there I will have two branches, one is not p, another with q or
r. Now, what happens you can apply rule here directly instead of going further using other
premise, but in a systematic tabula we will not do that. You want to see that all the
premises have been used slowly and then we will develop it path wise, we look at a path
see whatever is the compound proposition from the top, use a ruler on that, right?
That is what is systematic tabula is because what happens here in proportionally it does
not matter, but latter suppose you will have some opportunity to reuse the rules, right?
The same compound proportion can be overused many times, it will give ways to different
conclusions like suppose you say for each x p x in natural numbers. I would have taken
taken P 1, I would have taken P 2, I would have taken P 3 and this is infinite.
So, if I proceed from p x what to conclude as a P 1, P 2, P 3 where to stop, right? So,
we will make it systematic so that it can be again extended to fast tautology letter,
that is the reason. So, what we do here, we will not apply a rule on the recently got
promises or whatever has been obtained from the rules. We will start again looking at
the path from the top of the path you go on finding the compound proposition of either
rules, follow it systematically, right? So, let us see how does it look like. There is
one more difficulty. Suppose, you set of propositions is infinite
then what will you do? There will be problem in applying the rules, I am thinking that
tabula will finish there, but it is possible that the tabula still will become finite.
If it is closing, everything is closed after that there are only redundant propositions.
I have p, I have not p after that everything is redundant, right? It will simply close,
so similar thing can also happen even if the set of premises is infinite, okay?
Let us think a beat how to give the systematic tabula for the infinite sets directly. So,
anyway it will be countable set because the set of proportion is countable. So, whatever
set you take, set of proposition subset of the set of all propositions will be countable.
So, in that you can have ordering, so let us start with a set of proposition sigma. Let us write sigma equal to X 1, X 2 and so
on. So, you are thinking as this as an ordered set, now the O it has been written that is
its ordering, right? X 1 is the first one, X 2 is the second one, X 3 is the third one
and so on. Now, what we do we will define the generation of systematic tabula in stages
because there are infinite things. So, each stage will be defined inductively after one
stage, fine? So, first stage is this in stage 1, what you do see the problem is we cannot
take everything at the route, the way we are doing earlier. So, have to start with one
that is why the stages, right? So, introduce X 1 or take it, take X 1 on the route, X 1
as the route we start with that. Then in stage n what will do in each stage
we are introducing 1, then we are expanding starting from the top. So, in stage n plus
1, we assume that x n has been introduced already or stage n has already been performed,
then we had we are going to do in the next test, that is what we are concentrated, right?
So, suppose stage n has been performed, fine? Now, in stage n plus 1 we introduce what we
want to introduce really. Suppose, you want to introduce X n plus 1, where will you introduce? On the open branches if some path is already
closed, there is no need to introduce there right is that ok?. So, that is what we are going
to do, fine? Then in stage n has been performed, first you have to check after this whether
any part closes. If closes, you do not have to do anything, wait so first check that. check
whether any path is opened. There is the first thing to do then for each open path you have to do something. So, for each open path row let us call it
row, expand the path as follows. So, how do you expand, first we have to introduce X n
plus y, right? Introduce or the start whatever you write X n plus 1 to the path as a leaf
of course, right? Your introduction will be on the leaf level always, not from the root
that is what we are following. So, introduce at the leaf itself, X n plus 1 becomes the
new leaf. Now, it is the child to the earlier leaf, whatever leaf was there on the root,
right? Then what we do, scan row from root to leaf
for a compound proposition rule say a on which rule has not been applied. Suppose, that is the first, so you are scanning from the top root to the leaf top down right on that paths,
only row not other paths, other paths we are forgetting. Now, you are trying expand only
that path and each path we will have to expand in your end, right?
So, on that path from the root when you proceed you find one a compound probation on which
rule has not been applied. Then apply the rule at the child or children whatever it
is if it just stacking rule, then there will be one child or two may be on the same path
also, right? But if it is a branching role then there will be two branches out from the
leaf. So, art those child or children ,whatever it is add suitable child or children or you
can write propositions. Once you write suitable that takes care of propositions true the leaf
of row. Now, it is really for x n x n is at the root, now leaf x n plus 1 write. So, leaf
of row this is how you expand. So, one step of expansion is over this is
what we have to performance stage n plus 1, but there is one condition. Condition is suppose
sigma has only n number of propositions, then you cannot find x n plus 1, right? So, that
is the condition if there is at least x n plus 1 then use it for infinite only we are
thinking. For finite case, there is possible that at the stage all the propositions are
over. So, in x n plus 1 all that you have to do is look for the compound proposition
and go on expanding it, see if it cannot be further expanded, stop there, yes. We are not expanding totally, suppose you come to know p implies q r r. So, at one stage
it will give not p q r r, q r r remains, you are not expanding at that stage, only one
from the top. So, it may be expanded in the next stage or may be later, I do not know
when, right? Again I have to come from the top, I get this one first then that is why
it is systematic, they are not worried about whether it is finished or not. So, we should
add something here introduce x n plus 1 to the path as a leaf provided. Sigma has more than n propositions, if it
does not have then stop there. Now, let us look at this place, so there is when this
algorithm will stop then you cannot further expand it, right? So, if no such k is found out then stop expanding
row,this now for each path we are doing that this is only inductively defined. It does not say
that at any stage it will stop, it may not stop here because sigma is infinite and it
is consistence and it will not stop, it will go on forever. It was in P 0 core, P 1 core,
P 2 core, P 3 all proportional variable, right? Now, you will introduce at each one stage
one proportion continue, no expansion is required, still it goes on infinite, right? One part
only it is all start and it is continuing infinitely, there is an infinite path, is
that clear? So, only thing is possible there. Now, let us see here question what happens
here how to develop a systematic tabular for this set . So, suppose you take these propositions
as there order, that is may sigma as they written that is may ordering. So, you start with the first proportion which
is p implies q or r, that finishes my stage 1. So, let me write here my stage number just
to keep my documentation. So, in stage 1 I have introduced this. Now, I do in stage 2,
I have to introduce second one if there is possibility. Suppose, nothing is there, so
again it will go to stage 2, I have to write stage2 apply the rule,there is nothing to introduce,fine?If there is something I have to introduce there, so introduce in stage
2, not r implies s and t, but stage 2 is not over. I have just introduced because there
is 1, then what you have to do for each open path I have to do something, this is the only
path that is open. Now, you should go back to root, from root
I have to scan which one is on the compound proposition, which rule has not been applied.
So, I find first proposition which is my a. Now, it is dynamic variable on that, so it
is my a that I apply the rule. So, I get not p q or r, both of them have been obtained
in stage 2, there end stage 2 nothing over it does not say you do it again.
It is not a loop, it is telling that is says that is all. So, suppose that stage has been
performed have to go back again, follow the procedure, the loop will be on end directly
not there itself, there is no sub loop there, So, second stage is over, now I come to third stage, in third stage. So, in third stage
what will happen there is another we have to introduce that, so everywhere it is not over. I have to again scan on each
open path on which a compound proposition on which a rule has not been applied. So,
first one I have already applied in every path, I am doing it breadth first. So, that
will be easier to look easier to see it at least, then second one I have not applied
on this path, it is done daily path wise. So, on this path this has not been done, now
I apply it that is again in the third stage, that is again in the third stage. So, it will
have not not r s and t, all these are done in third stage, here also there is another
open path same proposition is taken. There s and t they are going third stage, third
stage is over that is the only thing I have to do anything is closing that has to be checked,
all this nothing is closing till now, so you go to fourth stage. Fourth stage there is
the proposition. So, you have to introduce fourth stage, so
that gives t implies u t implies u t implies u t implies u, fourth stage starts with that
then what have to do. This is over, I have to look at each open paths. So, one open path
is here the left most, I am taking where I have to find this compound proposition rule
has used rule has been used. So, literal this is not a literal, not everything will be obvious
for us, but not for the algorithm. So, on the fourth stage I have to write r,
this is done we have not not rule, the rule can be applied. So, I have to apply it and
I forget about that for that path. In that stage I can do next path where I have to find
similar. So, here again I get s and t, so that is again fourth stage s t. So, that is
also done, so different propositions you might get in different paths, that does not matter.
So, next open path I take there q r r that is also in fourth stage, q r and this path
same thing q r r. So, that is again fourth stage as q then next I go to fifth stage,
there is nothing more to be introduced. Now, you have to first check anything is closing
out of this, nothing is closing, looking this is closing t and not t, right? That is closed,
next about this I have q not t, nothing is closing r nothing I closing, right? Next path
you can q r nothing is closed, they remain, so next have to check each path whichever
is open till then the left must you have to take algorithm, really says you start from
the left most path and then continue. So, then you have to take this open path,
find out on four I have not applied apply it, that is the fifth stage. This is the proposition
on which I have to apply a rule not t q, that is all about the fifth stage, closed path
I do not worry open path. So, these two have been applied not t not not r. So, I have to
write r that is all about the fifth stage, then here again same thing fifth stage r,
it just does blindly, no intelligence. So, next one is again s and t, so fifth stage
will be s fifth stage will be t and here also same thing s t that is about the fifth stage
over. Now, you have to again check whether something is closing or not, this one is not
closing u r not not closing, that is also not closing r, this is also not closing s
t q not t closing t not t closing, right? So, fifth stage is over sixth stage I have
started when you are finding out which paths are opened or closed.
Now, in the sixth stage I have to go for the left most path, I see everything has been
used, there is no other compound, right? Next path everything is here, next path there is
one not used yet. So, use it that is sixth stage here, also same thing sixth stage sixth stage is over. Now, seventh stage starts
so this does not close this, does not close nothing is closing nothing is expanded over
it closes. So, that is also another way of telling the stepping criteria, if you get
some open paths as the last stage you can stop because in the next stage only you can
verify the whether some path is closing or not.
Now, you can compare this systematic tabula with the one you have already constructed
earlier this one, right? Systematic tabula will be bigger that is here does not matter
that there is a copy of this tabula inside it . Somewhere may not be in the same form
same order something else might be inside because they are closed early. So, they can
expand that is fine whether the copy is there. So, systematic tabula is necessarily a completed
tabula, right? It has to be completed, but that you are guessing only finite case. Infinite
case how do you justify that a systematic tabula is necessarily a completed tabula,
but you take any systematic tabula it has to be completed. Why is it so? Well if it
is not completed then what happens, there exists at least one path which is not completed.
So, it is not a completed path means what so that compound proposition has obtained
by the tabula either that or it is originally in the sigma. If it is originally in the sigma
then it would have been introduced in some stage, right? So, it has been obtained, if
it has been obtained then from the root to that place whatever is the number say m, then
it will be used in stage m, right? So, always you are concerned with the finite place even though tabula look infinite, you can really get away with finite place, fine? Now, systematic
tabula is completed, once it is completed what you have to do for consistency, you just
go for the systematic tabula and decide if there exist an open path, then it is consistence,
only thing for infinite, what to do? if it is inconsistent then it will close, everything
will close in a finite stage which verify, otherwise it may go for infinite.If it goes for infinite, can you say it is inconsistent or it is consistent? You need not stop, it is infinite you
are telling infinite. So, there is an infinite path, let us say. In tabula there is an infinite
path in the system in a systematic tabula. Now, does it mean it has to be open or it
is closed or it can be anything, if it is anything it will close at some finite stage,
once it is closed it has to be infinite.,why is it so? There can be infinite literal also, as we told there can be a set with P 0, P 1, P 2,
P 3 and so on, right? Suppose, you say one path is closing, there is a path which is closed, is it necessarily finite? Is finite path, is finite isn’t it? Yes, path is finite
or not, if a path is closed is it necessarily finite.
Yes, then there is one infinite path, it has to be open. It is a separate matter. Is that so you are not able decide whether
it remains infinite or it remains finite, but it is true that if it is closed it has
to be finite, if it is infinite it has to be open, right? There can be finite open paths
that is, if say propositions is finite in the beginning, yes right? So, what we see
here is in the systematic tabula, we have to be concerned about the finiteness thing,
right? Finiteness, close finiteness, open there is something which we may need because
finiteness is not easy to look in the tabula itself, finiteness will give you something
more. There we will see what does it mean. Let us take any general tree what happens
there, see how this tabula are binary trees, right? You have the binary tree, here in the
binary tree you are telling whether it goes to infinite or not, I do not know, right?
It is an infinite binary tree and I do not know what happens whether one path remains
open or not. Now, if it not a binary tree you can take
any general tree and you know there it is finally generated that every node has only
finite number of children. How many do not know, can you tell? In that case something
and slightly ask you a difficult question, but it may be easier to see. See you have
the binary tree here, it means you take any node it has less than or equal to 2 children,
right? May be 1 only, less than equal to… Now, consider one finitely generated tree
which means you take any node there, it will have finite number of children, not infinite
number of children right as usual, but that finite number I am not giving what it is.
There might be any bound, it can grow like from level 1 each one will have one child,
level 2 each one will have two children, level 3 each one can have three children and so
on, but this also finitely generated, is that clear? Possible?
It is random, I will give an example that you cannot, you sit there is a maximum number
of children of any one, right? That is possible then in that case what can you say about path,
suppose the trees finite or infinite. I give something say tree is infinite, does there
exist on infinite path or not? Why is it so?

One Reply to “Mod-01 Lec-20 Lecture-20-Examples of Tableau Proofs”

Leave a Reply

Your email address will not be published. Required fields are marked *