WEBVTT

1
00:00:00.000 --> 00:00:08.567
This overview explains the difference between written
syntax, a truth table, and the Boolean function they describe.

2
00:00:08.567 --> 00:00:16.419
Different expressions can mean the same thing, while
agreement on a few cases can conceal a real difference.

3
00:00:16.419 --> 00:00:16.433
Different expressions can mean the same thing, while
agreement on a few cases can conceal a real difference.

4
00:00:16.733 --> 00:00:24.400
For the input A zero and B one, the direct and expression returns zero because A is false.

5
00:00:24.400 --> 00:00:30.000
Now keep that same input fixed while evaluating a differently written expression.

6
00:00:30.000 --> 00:00:35.367
Changing expressions must not accidentally change the test input.

7
00:00:35.367 --> 00:00:38.100
Negating A gives one.

8
00:00:38.100 --> 00:00:40.867
Negating B gives zero.

9
00:00:40.867 --> 00:00:45.667
The inner or combines one and zero and returns one.

10
00:00:45.667 --> 00:00:50.933
This intermediate one is not the final answer, because the complete expression contains

11
00:00:50.933 --> 00:00:55.400
one more negation outside the parentheses.

12
00:00:55.400 --> 00:00:59.200
The outer negation changes that one to zero.

13
00:00:59.200 --> 00:01:02.600
The two expressions agree for zero one.

14
00:01:02.600 --> 00:01:08.300
We have compared the same complete input through two different instruction structures.

15
00:01:08.300 --> 00:01:15.500
This single match is useful, but it does not yet prove agreement for every input.

16
00:01:15.500 --> 00:01:15.509
An expression records syntax.

17
00:01:15.509 --> 00:01:18.467
An expression records syntax.

18
00:01:18.467 --> 00:01:23.500
Its Boolean function specifies the output for every complete assignment.

19
00:01:23.500 --> 00:01:28.000
A truth table lists that mapping in a declared variable order.

20
00:01:28.000 --> 00:01:33.967
Here the order is 00, 01, 10, 11.

21
00:01:33.967 --> 00:01:37.567
Compare A AND B with NOT of NOT A OR NOT B.

22
00:01:37.567 --> 00:01:40.600
Both output 0, 0, 0, 1.

23
00:01:40.600 --> 00:01:44.400
Different written syntax describes the same function.

24
00:01:44.400 --> 00:01:49.567
A OR B agrees at 00 and 11, but differs at both middle cases.

25
00:01:49.567 --> 00:01:54.233
At 01, AND returns zero while OR returns one.

26
00:01:54.233 --> 00:01:58.300
That single counterexample disproves their equivalence.

27
00:01:58.300 --> 00:02:02.300
all 4 cases are exhaustive for these two-input rules.

28
00:02:02.300 --> 00:02:06.133
Larger universes need an appropriate exact method.

29
00:02:06.467 --> 00:02:11.100
Work a second complete case with A 1, B 0.

30
00:02:11.100 --> 00:02:14.900
Keep this assignment fixed throughout the calculation.

31
00:02:14.900 --> 00:02:19.400
Each symbol retains the meaning already introduced; a new value does not

32
00:02:19.400 --> 00:02:22.667
create a new logical rule.

33
00:02:22.667 --> 00:02:26.933
Not A is zero and not B is one.

34
00:02:26.933 --> 00:02:29.733
Their inclusive or is one.

35
00:02:29.733 --> 00:02:36.133
Apply the outer not only after that inner result is known: not one is zero.

36
00:02:36.133 --> 00:02:40.733
Direct and of one and zero is also zero.

37
00:02:40.733 --> 00:02:46.367
Each intermediate negation has a different role from the final negation.

38
00:02:46.367 --> 00:02:50.333
This case establishes a specific contrast.

39
00:02:50.333 --> 00:02:53.333
The two expressions agree at 10.

40
00:02:53.333 --> 00:02:56.200
Do not omit the outer negation.

41
00:02:56.200 --> 00:03:01.433
Keep the input, intermediate values, and conclusion together when comparing

42
00:03:01.433 --> 00:03:03.800
it with the previous case.

43
00:03:03.800 --> 00:03:11.033
The calculated answer belongs to this complete assignment under the stated rule.

44
00:03:11.333 --> 00:03:15.767
For input one one, both inner negations are zero.

45
00:03:15.767 --> 00:03:20.367
Their or is zero, and the outer negation makes one.

46
00:03:20.367 --> 00:03:23.200
Direct and also returns one.

47
00:03:23.200 --> 00:03:27.367
The same sequence of operations works; we have not changed the meaning

48
00:03:27.367 --> 00:03:30.833
of negation between examples.

49
00:03:30.833 --> 00:03:38.667
The remaining inputs zero zero and one zero both give zero under each expression.

50
00:03:38.667 --> 00:03:40.900
All four rows agree.

51
00:03:40.900 --> 00:03:45.700
Because two Boolean inputs have exactly four assignments, this is an exhaustive

52
00:03:45.700 --> 00:03:52.367
equivalence check for this example, not a sample of a larger unstated universe.

53
00:03:52.367 --> 00:03:55.333
Compare and with or instead.

54
00:03:55.333 --> 00:04:01.600
They agree at zero zero and one one, so those two tests alone look reassuring.

55
00:04:01.600 --> 00:04:04.267
At zero one they disagree.

56
00:04:04.267 --> 00:04:08.700
One counterexample is sufficient to disprove equivalence.

57
00:04:08.700 --> 00:04:16.260
Establishing equivalence requires every relevant case or a sound proof covering them.

58
00:04:16.260 --> 00:04:16.267
Establishing equivalence requires every relevant case or a sound proof covering them.

59
00:04:16.267 --> 00:04:19.933
One counterexample disproves equivalence.

60
00:04:19.933 --> 00:04:25.200
Complete agreement needs an exact check over the declared universe.