Return to Video

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
    Yeah, finally, what about this one here?
  • 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
Amara Bot added a translation

English subtitles

Revisions