CS 228 Exam 1 – October 26, 2005

 

Name ______________________

 

1.        Using prepositional logic, prove that  the following argument is valid

 

A’   Ù  (A ∨ B)  → B

  Gersting section 1.2  #15

 

1.  A'           hypothesis

2.  (A v B)    hypothesis

3.  B            1,2, Disjunctive syllogism 

        OR

1.  A’   Ù  (A ∨ B)            hypothesis

2. (A’   Ù  A)  v (A'  Ù B)  1 Distributive property

3.    0  v  (A'  Ù B)           2. negation laws

4.  A' Ù  B                       3. identity law

5.   B                               4. simplification

 

2.      Using predicate logic,  prove that the following argument is valid.

 

("x) P(x)→("x) [P(x) ∨ Q(x)]

 

Gersting section 1.4  #10

 

1.   ("x) P(x)                    hypothesis

2.   P(a)                           universal instantiation

3.   P(a) v Q(a)                 addition

4.  ("x) [P(x) ∨ Q(x)]      universal generalization

 

3.      Prove that for every integer n,  the number   3(n2 + 2n + 3) – 2n2   is a perfect square (note:  this is not an induction proof)

 

3(n2 + 2n + 3) – 2n2  = 3n2 + 6n + 9 - 2n2  =  n2 + 6n + 9 =  (n + 3)2

 

Gersting  Section 2.1  # 16

 

4.       Use mathematical induction to prove that the following statement is true for every positive integer n.

 

1  + 5  + 9 + ... + (4n -3) = n(2n -1)

 

gersting section 2.2 # 3

 

Prove for n = 1   (base case)    

4n-3

n(2n –1)

4*1-3

1(2*1-1)

1

1

4n-3 = 4-1 = 1     and  n(2n-1) =  1(2-1) = 1

 

Assumer true for n = k

 

Prove for n = k + 1

1  + 5  + 9 + ... + (4k -3) +[ 4(k+1) –3]

(k+1)[2(k+1) –1]

k(2k-1) + [ 4(k+1) –3]

(k+1)[ (2k +2) – 1]

2k2- k +  [ (4k + 4) –3]

(k+1)[ 2k + 1]

2k2- k +  4k + 4 –3

2k2 + k + 2k + 1

2k2+ 3k + 1

2k2+ 3k + 1

 

 

5.      Find the canonical sum-of-products form for the truth function in the table below.  ( Do not simplify it).

 

x

y

z

f(x,y,z)

0

0

0

1

0

0

1

0

0

1

0

1

0

1

1

0

1

0

0

1

1

0

1

1

1

1

0

0

1

1

1

0

 

x'y'z'+ x'yz' + xy'z' + xy'z

6.      Write the following base 10 numbers in  ones complement, twos complement and sign magnitude notation using  8 bits.

 

base 10

sign magnitude

ones complement

twos complement

+67

01000011

01000011

01000011

-68

11000100

1011011

10111100

 

7.      Write the following base 10 numbers as unsigned numbers in base 2, base 8 and base 16

 

base 10

base 2

base 8

base 16

1896

111011010012

35508

76816

18.96

10010.1111012

22.758

12.F416

1.896

1.1110012

1.718

1.E416

.1896

0.0011002

0.148

0.3016

 

 

 

 

8.      For the following grammar G,  generate enough  valid sentences in the language so that you can  tell in English what the language consists of.  (show the sentences you generate)

G = (V,  VT, S, P)  where V = {0,1,A,S}  ,  VT  =  {0,1},  and P consists of

 

         S  ->  0

         S ->  ASA

          A ->  1

 

          S                           S                           S                             S

          |                         / | \                     /  |   \                   /    |   \ gersting  Section 8.4  #4

          0                         A S A                   A   S   A                  A    S    A

                                      |  |  |                |  / | \  |                          |  /  |  \  |

                                      1  0  1                  1 A S A  1               1  A  S  A 1

                                                                     |  |  |                      | / | \  |

                                                                   1 0  1                     1 ASA  1

                                                                                                       10 1

 Sentences:    

     0                         101                       11011                        1110111

 

  The language consists of a 0 preceded and followed by an identical number of 1's (including no 1's)

    

9.      The Karnaugh map below represents a combinational circuit.  Determine the  the minimal sum-of-products form for the Karnaugh map of the figure below and draw the simplified circuit.   on board

 

 

x y

xy'

x'y'

x'y

zw

 

 

 

1

zw'

1

1

 

 

z'w'

 

1

1

 

z'w

 

 

1

 

 

w’xz + x’y’z’ + wx’yz + w’xy’  OR   w’xz + x’y’z’ + wx’yz + w’z’y’

 

gersting   Section 7.3  # 5

 

 

10.   The Wiggle Captain FeatherSword designed the sequential  machine which has two flip-flops (A and B) and one input (x), and behaves in the following way.  .  When x = 1, the state of the flop-flops does not change.  When x = 0,  the state sequence is  00, 11, 01, 10, 00, and so on.

 

    1. Show the state diagram   on board
    2. Show the state table with the current state, the input and the next state
    3. add the flip-flop excitations for JK flip flops
    4. use Karnaugh maps to determine the flip-flop input functions  JA, KA, JB, KB
    5. BONUS:  draw the circuit on board

 

 

 

 

 

 

 

 

 

 

 

 

current

state

 

next

state

flip

flop

flip

flop

A

B

input

A

B

JA

KA

JB

KB

0

0

0

1

1

1

X

1

X

0

0

1

0

0

0

X

0

X

0

1

0

1

0

1

X

X

1

0

1

1

0

1

0

X

X

0

1

0

0

0

0

X

1

0

X

1

0

1

1

0

X

0

0

X

1

1

0

0

1

X

1

X

0

1

1

1

1

1

X

0

X

0

 

JA

1

 

 

1

X

X

X

X

 

 

KA

X

X

X

X

1

 

 

1

 

 

JB

1

 

X

X

 

 

X

X

 

 

KB

X

X

 

1

X

X

 

 

 

JA = x'

 

KA = x'

 

JB = A'x'

 

KB = A'x'