---
# System prepended metadata

title: CSC-208 Practice Problem 1 Solution

---

---
title: CSC-208 Practice Problem 1 Solution
fontsize: 12pt
---
# CSC-208 Practice Problem 1 Solution
### Problem 1:
``` racket
(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.

