---
title: CSC-208 Practice Problem 1 Solution
fontsize: 12pt
---
# CSC-208 Practice Problem 1 Solution
### Problem 1:

(define length
  (lambda (l)
    (match l
      ['() 0]
      [(cons head tail) (+ 1 (length tail))])))
      
      
(define replicate
  (lambda (v n)
    (if (zero? n)
        '()
        (cons v (replicate v (- n 1))))))

***Claim***: For all lists and any v, ```(length (replicate v (length list)))``` $\equiv$ ```(length list)```

Case 1: list is empty

LHS: (length (replicate v (length null)))
-> (length null)
-> 0

RHS: (length list) -> 0

Case 2: list is not empty

Goal: (length (replicate v (length List))) = (length list)

IH: (length (replicate v (length tail))) = (length tail)

LHS: (length (replicate v (length list)))

-> (length (cons v (replicate v (- (length list) 1))))

-> (+ 1 (length (tail (cons v (replicate v (- (length list) 1))))))

-> (+ 1 (length (replicate v (- (length list) 1))))

-> (+ 1 (length (replicate v (length tail))))

-> (+ 1 (length tail))

-> (length list)

RHS: (length list)

### Problem 2: $A \rightarrow B, B \rightarrow C \vdash A \rightarrow (B \wedge C)$

_Proof_: $A \rightarrow B, B \rightarrow C \vdash A \rightarrow (B\wedge C)$ [claim]
+ $A \rightarrow B, B \rightarrow C, A \vdash B \wedge C$ [intro-$\rightarrow$]
+ $A \rightarrow B, B \rightarrow C, A \vdash B$ [intro-$\wedge$(1)]
+ $A \rightarrow B, B \rightarrow C, A \vdash A$ [elim-$\rightarrow$(1)]
+ [assumption: A]
+ $A \rightarrow B, B \rightarrow C, A, B \vdash B$ [elim-$\rightarrow$(2)]
+ [assumption: $A \rightarrow B$]

+ $A \rightarrow B, B \rightarrow C, A \vdash C$ [intro-$\wedge$(2)]
+ $A \rightarrow B, B \rightarrow C, A \vdash A$ [elim-$\rightarrow$(1)]
+ [assumption: A]

+ $A \rightarrow B, B \rightarrow C, A, B \vdash B$ [elim-$\rightarrow$(2)]
+ [assumption: $A \rightarrow B$]
+ $A \rightarrow B, B \rightarrow C, A, B, C \vdash C$ [elim-$\rightarrow$(2)]
+ [assumption: $B \rightarrow C$]

### Problem 2:
1. $U = \{\{soc, CS\}, \{soc, bio\}, \{soc, chem\}, \{bio, cs\}, \{bio, chem\}, \{cs, chem\}\}$
2. $S = \{(m1, m2)|(m1, m2) \in S, m1 \equiv CS\}$
3. $S = \{(m1, m2)|(m1, m2) \in S, m1 \equiv CS \wedge \text{m2 is in social science}\}$

### Problem 3:
A = I'm a cs major
B = I'm a chem major
$A \rightarrow \neg B$
### Problem 4:
1. It is not the case that I'm a CS major and I'm not as cool as CS major, then I'm a CS major.
2. It is not the case that if I'm a bio major then I'm a cs major or if I'm not a sociology major and I'm not as cool as cs major.