## 08-04 Special Boolean Formula Solution

• 0:00 - 0:02
And the answer here is not actually
• 0:02 - 0:05
3 of those statements, those 3 down here are correct.
• 0:05 - 0:08
I'll explain them in a minute, and this one here is not correct.
• 0:08 - 0:12
So the formula indeed does have a satisfying assignment.
• 0:12 - 0:15
Not only one; it actually has several satisfying assignments,
• 0:15 - 0:18
but each of those assignments has the property that
• 0:18 - 0:21
exactly one variable is set to true,
• 0:21 - 0:23
and I'll show you in a second how that works.
• 0:23 - 0:27
And of course--I mean, the last thing was probably quite easy to figure out;
• 0:27 - 0:30
as you see this already has kind of a square shape,
• 0:30 - 0:33
so if we continue like this and add another variable here,
• 0:33 - 0:36
then we would have to add another line down here,
• 0:36 - 0:39
and each of those formulas grows by 1 and
• 0:39 - 0:42
the whole thing grows by one of those brackets here
• 0:42 - 0:44
for each variable that we add,
• 0:44 - 0:48
so the size is O(n squared) for n variables.
• 0:48 - 0:50
So let me explain this here to you.
• 0:50 - 0:53
So there are several satisfying assignments,
• 0:53 - 0:56
but each of those satisfying assignments has the property
• 0:56 - 0:58
that exactly 1 variable is true.
• 0:58 - 1:01
So for example, let's say that we set
• 1:01 - 1:04
X1 to true,
• 1:04 - 1:06
then what will happen is the following,
• 1:06 - 1:11
so X1 is true; this means this one down here goes to 0.
• 1:11 - 1:15
This one goes to 1, this one goes to 1, this one goes to 1,
• 1:15 - 1:17
this one goes to 1, and this one is 1.
• 1:17 - 1:19
So let's have a look here
• 1:19 - 1:21
at this part of the formula.
• 1:21 - 1:24
All of the variables here are connected by an or,
• 1:24 - 1:28
so we have X1 or X3 or X4 or X5 or X6.
• 1:28 - 1:31
This means if just one of the variables here
• 1:31 - 1:32
is set to true,
• 1:32 - 1:34
which it now is,
• 1:34 - 1:37
then the whole bracket here,
• 1:37 - 1:40
so from here to here will also evaluate to true,
• 1:40 - 1:43
and then we take this very, very big not here,
• 1:43 - 1:46
which means this will evaluate to 0.
• 1:46 - 1:49
Now this very big not here evaluates to 0,
• 1:49 - 1:52
then we have to make sure that this variable here
• 1:52 - 1:54
evaluates to 1,
• 1:54 - 1:56
because all of them are connected by an and,
• 1:56 - 1:58
and we are looking for a satisfying assignment,
• 1:58 - 2:01
so to do that, we have to set X2 to 0
• 2:01 - 2:04
so that this here evaluates to 1.
• 2:04 - 2:07
Now for the next bracket, it works the same way,
• 2:07 - 2:10
because again, we have X1 set to true,
• 2:10 - 2:12
so the bracket evaluates to true,
• 2:12 - 2:14
so the not evaluates to 0,
• 2:14 - 2:16
and so again we have to set this to 1
• 2:16 - 2:18
which means X3 is 1
• 2:18 - 2:21
and we can go on through this the same way.
• 2:21 - 2:27
So the formula forces us to set every variable except for X1 to false,
• 2:27 - 2:28
and now the way that this formula is structured, of course,
• 2:28 - 2:32
we could also have chosen to set X2 to true,
• 2:32 - 2:34
but then if X2 is set to true,
• 2:34 - 2:40
we have this here, so X2 here is 1, 1, 1, 1,
• 2:40 - 2:44
which means in order to get these here to go to 1,
• 2:44 - 2:47
so we need to have these here go to 1,
• 2:47 - 2:51
because this here evaluates to 0, 0, 0, 0, 0,
• 2:51 - 2:54
so we have to set all of these variables here to false.
• 2:54 - 2:56
• 2:56 - 3:00
Well, since X2 is set to true,
• 3:00 - 3:02
not X2 is set to false,
• 3:02 - 3:06
but luckily, because we've set all of the variables to false,
• 3:06 - 3:09
so we have 0, 0, 0, 0, 0.
• 3:09 - 3:12
In this case, the large not here
• 3:12 - 3:13
evaluates to true,
• 3:13 - 3:16
so this bracket here also evaluates to true,
• 3:16 -
and we have satisfied the Boolean formula.
Title:
08-04 Special Boolean Formula Solution
Team:
Udacity
Project:
CS313 - Theoretical Computer Science
Duration:
03:21