Multiplexer Continued

Lecture 6

Multiplexer continued

c1c0 x0x1x2x3 -> These inputs produce a truth table with 64 rows ….. therefore don’t use a truth table. However this equates to…

c0 is low order bit

c1 is high order bit

0 0 -> 0 x0

0 1 -> 1 x1

1 0 -> 2 x2

1 1 -> 3 x3

_ _

The only Minterm would be M = c1c0x0

Quantifier

"  $

“For All” “There Exists”

How often is a predicate true?

Example Predicate:

R(x) = person x is wearing red

$x R(x) is true

"x R(x) is false

[$x R(x)] / ["x R(x)] / R(x)
0 / 0 / ALOF
0 / 1
1 / 0
1 / 1
"x R(x) / R(x)
0 / At least one false = ALOF to prove "x R(x)
1 / Always true or all true = AT
$x R(x) / R(x)
0 / Always false = AF
1 / At least one true = ALOT

Modus Ponens in Predicate Calculus

1 / 2
$x P(x) / L / "x P(x) -> Q(x) / => / $x Q(x)
0 AF / 0 / 0 ALOF / 1 / 0 AF
0 AF / 0 / 1 AT / 1 / 0 AF
1 ALOT / 0 / 0 ALOF / 1 / ? ALOF / Hypothesis is false therefore
Conclusion can be true
1 ALOT / 1 / 1 AT / 1 / 1 A LOT
1 4 / 3 / 2 5 / 8 / 7 6 / Order of doing columns

Ý

This column tells how frequently P(x) is true. Do not confuse with column under $x.

2 / 1
$x P(x) / L / $x Q(x) / <= / $x P(x) L Q(x)
0 AF / 0 / 0 AF / 1 / 0 AF
0 AF / 0 / 1 ALOT / 1 / 0 AF
1 ALOT / 0 / 0 AF / 1 / 0 AF
1 ALOT / 1 / 1 ALOT / 1 / ? ?
1 4 / 3 / 2 5 / 8 / 7 6 / Order of doing columns
x / y / x Å y
0 / 0 / 0
0 / 1 / 1
1 / 0 / 1
1 / 1 / 0
"x"y / x Å y ® false = 0
"x$y / x = 0 y = 1
try to find a y value ® true = 1
x = 1 y = 0
$y"x / y = 0 x = 0 F
® false = 0
y = 1 x = 1 F
"y$x / y = 0 x = 1
® true = 0
y = 1 x = 0
$x"y / x = 0 y = 0 F
® false = 0
x = 1 y = 1 F
$x$y / x = 0 y = 1 F ® true = 1
x / y / x ® y
0 / 0 / 1
0 / 1 / 1
1 / 0 / 0
1 / 1 / 1
"x"y / x ® y ® false = 0
"x$y / x = 0 y = 1
try to find a y value ® true = 1
x = 1 y = 1
$y"x / y = 1 x = 0 T
® true = 1
x = 1 T
"y$x / y = 0 x = 0
® true = 1
y = 1 x = 0
$x"y / x = 0 y = 0
® true = 0
y = 1
$x$y / ® true = 1

Contradiction – all trues $x$y has to be a contradiction to be false

"x"y has to be a tautology?

Set Theory

Sets – A set is a group of objects

-  order does not matter

-  each item is only counted once

A = {a, b, c} notation B = {c,c,c}

½A½ = 3 This is read as “size of set A is 3” ½B½ = 1