BSc CSIT (TU) Science Discrete Structure (BSc CSIT, CSC160) Question Paper 2079 Nepal

Set

A set is a well-defined, unordered collection of distinct objects called its elements (or members). If $x$ is an element of set $A$ we write $x \in A$; otherwise $x \notin A$. Example: $A = \{1, 2, 3\}$.

Set Operations (with Venn diagrams)

Let $A$ and $B$ be subsets of a universal set $U$. In a Venn diagram, $U$ is the rectangle and $A,B$ are overlapping circles inside it; the shaded region represents the result.

• Union $A \cup B = \{x : x \in A \text{ or } x \in B\}$ — both circles shaded.
• Intersection $A \cap B = \{x : x \in A \text{ and } x \in B\}$ — only the overlap shaded.
• Difference $A - B = \{x : x \in A \text{ and } x \notin B\}$ — the part of circle $A$ outside $B$.
• Complement $A' = U - A = \{x : x \in U \text{ and } x \notin A\}$ — everything outside circle $A$.
• Symmetric difference $A \oplus B = (A-B)\cup(B-A)$ — both circles shaded except the overlap.

Principle of Inclusion–Exclusion

Two sets

Proof: When we add $|A|$ and $|B|$, every element of $A \cap B$ is counted twice (once in $|A|$, once in $|B|$), while elements in only $A$ or only $B$ are counted once. Subtracting $|A \cap B|$ removes the duplicate count, so each element of $A \cup B$ is counted exactly once. Hence the formula holds.

Three sets

Proof: Treat $A \cup B \cup C = (A\cup B)\cup C$ and apply the two-set rule:

Now $|A\cup B| = |A|+|B|-|A\cap B|$, and since $(A\cup B)\cap C = (A\cap C)\cup(B\cap C)$,

Substituting gives

Intuitively: add single sets, subtract pairwise overlaps (over-subtracted the triple region), then add the triple overlap back once.

Boolean Algebra

A Boolean algebra is an algebraic structure $(B, +, \cdot, ', 0, 1)$ on a set $B$ with two binary operations $+$ (OR) and $\cdot$ (AND), a unary operation $'$ (complement/NOT), and two distinct elements $0$ and $1$, satisfying for all $a,b,c \in B$:

• Commutative: $a+b=b+a$, $a\cdot b=b\cdot a$
• Associative: $(a+b)+c=a+(b+c)$, similarly for $\cdot$
• Distributive: $a\cdot(b+c)=a\cdot b + a\cdot c$ and $a+(b\cdot c)=(a+b)\cdot(a+c)$
• Identity: $a+0=a$, $a\cdot 1 = a$
• Complement: $a + a' = 1$, $a\cdot a' = 0$

The two-element set $B=\{0,1\}$ with these rules is the switching algebra used in digital logic.

Boolean Functions

A Boolean function of $n$ variables is a mapping $f:\{0,1\}^n \to \{0,1\}$. It can be written using AND, OR, NOT and represented as a truth table, as a sum-of-minterms (SOP), or as a product-of-maxterms (POS). For example, $F(x,y,z)=\Sigma(0,2,4,6)$ means $F=1$ exactly for the minterms numbered 0, 2, 4 and 6.

Minimizing $F(x,y,z) = \Sigma(0,2,4,6)$ with a K-map

Minterms and their values: $0=x'y'z'$, $2=x'yz'$, $4=xy'z'$, $6=xyz'$. The K-map (rows $x$, columns $yz$ in Gray order $00,01,11,10$):

All four 1s lie in the columns where $z=0$ (columns $00$ and $10$). They form one group of four cells. In this group $x$ takes both values and $y$ takes both values, so only $z'$ is common.

Verification: $F=1$ whenever $z=0$ regardless of $x,y$, i.e. minterms 0, 2, 4, 6 — matching the given function.

Permutation

A permutation is an arrangement of objects in which order matters. The number of ways to arrange $r$ objects out of $n$ distinct objects is

Combination

A combination is a selection of objects in which order does not matter. The number of ways to choose $r$ objects out of $n$ distinct objects is

Arrangements of 'COMPUTER'

The word COMPUTER has 8 letters, all distinct (C, O, M, P, U, T, E, R). Total arrangements:

Arrangements beginning with a vowel

The vowels in COMPUTER are O, U, E — that is 3 vowels.

• Fix one vowel in the first position: 3 choices.
• Arrange the remaining 7 distinct letters in the other 7 positions: $7! = 5040$ ways.

Results: Total arrangements $= 40320$; arrangements beginning with a vowel $= 15120$.

The exclusive or $p \oplus q$ is true when exactly one of $p, q$ is true (i.e. when they differ).

Equivalently, $p \oplus q \equiv (p \land \lnot q) \lor (\lnot p \land q)$.

Floor function $\lfloor x \rfloor$ gives the greatest integer less than or equal to $x$. Examples: $\lfloor 3.7 \rfloor = 3$, $\lfloor 5 \rfloor = 5$, $\lfloor -2.3 \rfloor = -3$.

Ceiling function $\lceil x \rceil$ gives the least integer greater than or equal to $x$. Examples: $\lceil 3.2 \rceil = 4$, $\lceil 5 \rceil = 5$, $\lceil -2.3 \rceil = -2$.

Both map $\mathbb{R} \to \mathbb{Z}$, and for any non-integer $x$, $\lceil x \rceil = \lfloor x \rfloor + 1$.

A multiset (or bag) is a collection of elements in which an element may appear more than once; that is, the multiplicity (number of occurrences) of each element matters, although order still does not. It generalizes an ordinary set, where every element has multiplicity 1.

Example: $M = \{a, a, b, c, c, c\}$, written compactly as $\{2\cdot a,\ 1\cdot b,\ 3\cdot c\}$. Here $a$ has multiplicity 2, $b$ multiplicity 1 and $c$ multiplicity 3, and the cardinality is $|M| = 6$.

Apply the Euclidean algorithm: $\gcd(a,b) = \gcd(b,\ a \bmod b)$ until the remainder is 0.

The last non-zero remainder is 18.

A weighted graph is a graph $G=(V,E)$ in which each edge $e \in E$ is assigned a numerical value $w(e)$ called its weight (or cost, length, capacity). It can be directed or undirected and is often stored as a weighted adjacency matrix.

Real-life application: A road/transport network where vertices are cities and edge weights are distances or travel times. Algorithms such as Dijkstra's shortest-path algorithm then compute the cheapest route between two cities (e.g. GPS navigation, or finding minimum-cost network links).

A spanning tree of a connected graph $G=(V,E)$ is a subgraph that is a tree (connected and acyclic) and includes all the vertices of $G$. For a graph with $n$ vertices, every spanning tree has exactly $n-1$ edges.

Number of spanning trees of $K_3$: By Cayley's formula, the complete graph $K_n$ has $n^{\,n-2}$ spanning trees. For $K_3$:

So $K_3$ (a triangle) has 3 spanning trees — each obtained by deleting one of its three edges.

Let $G$ be a connected graph (with all non-zero-degree vertices in one component).

• Euler circuit (closed Euler trail): $G$ has an Euler circuit iff it is connected and every vertex has even degree.
• Euler path (open Euler trail): $G$ has an Euler path but no circuit iff it is connected and has exactly two vertices of odd degree (the path starts at one and ends at the other).

The reason is that, except at the start/end, each visit to a vertex uses one edge to enter and one to leave, requiring an even degree.

A Boolean expression is a finite combination of Boolean variables (each $\in \{0,1\}$), constants $0$ and $1$, and the operators $+$ (OR), $\cdot$ (AND) and $'$ (NOT), formed according to Boolean algebra rules; it evaluates to either $0$ or $1$.

Simplify $x + x'y$:

Using the distributive law $x + x'y = (x + x')(x + y)$:

Seating $n$ people around a circular table counts arrangements that differ only by rotation as the same. Fixing one person's seat to remove rotational symmetry, the remaining $n-1$ people are arranged in $(n-1)!$ ways.

For $n = 5$:

So there are 24 distinct circular seating arrangements.