GAC024 Matematika Diskrit
GAC Matematika Topik 4 16:39 Narasi bahasa Inggris · Subtitle bahasa Inggris + 中文 disematkan langsung
Bab-bab
Transkrip
A repeated set member is counted once, a binary carry may exceed a fixed width, and the fewest-edge route may not have the smallest weight. Discrete mathematics makes those rules explicit. GAC zero two four covers sets, counting systems, binary logic, algorithms and networks, and this lesson works one example in each area. Your centre's current brief determines the actual assessment tasks, tools, weights and deadlines; these original practice sheets do not establish official marking rules or a university credit decision.
Before solving, state the conventions the problem lives in: the universe for a set question, the width for a binary representation, the allowed inputs for an algorithm, the graph assumptions for a network. Show enough working for another reader to reproduce the result, because a bare answer cannot be checked against the conventions it assumed. And keep the boundary between a mathematical model and its real implementation: a truth table proves logical equivalence, not circuit timing; a shortest path is computed on stated weights, not on live traffic. The conventions are part of the mathematics.
A set is a collection of distinct objects, and distinct is the word doing the work: order does not matter, and a repeated member is counted once. The union of A and B is everything in either; the intersection is what is in both; the complement is everything in the stated universe but outside the set, which is why a complement without a universe is meaningless. A subset has all its elements inside another set. A Venn diagram turns the problem into a picture, showing the disjoint regions and their counts; check that those regions add to the supplied universe total, because that sum is the diagram's own error check.
A relation pairs elements of two sets, with no further promise. A function is a relation where each input in its stated domain has exactly one output; that is the whole definition, and each word in it is testable. Different inputs may share an output, which is allowed, and which is exactly why an inverse relation is a function only when outputs uniquely identify their inputs. Squaring is a function; its inverse relation is not a function on the reals, because both two and minus two map to four. The domain statement is not decoration; it decides the verdict.
The inclusion-exclusion principle subtracts the twice-counted overlap once. The size of A union B is the size of A, plus the size of B, minus the size of A intersect B. Learners in both subjects appear in both totals, so the plain sum counts them twice; subtracting the intersection once leaves them counted once, like everybody else. The failure mode is subtracting twice, or not at all, and either error shows up immediately when the four disjoint regions fail to add to the universe, which is the check the Venn diagram gives you for free.
A class universe of thirty is divided into French-only eleven, both seven, German-only eight, and neither four. Known: thirty learners, eighteen study French, fifteen German, and seven study both. The union is eighteen plus fifteen minus seven, which is twenty-six. Neither is thirty minus twenty-six, four. French-only is eighteen minus seven, eleven, and German-only is fifteen minus seven, eight. The four disjoint regions, eleven, seven, eight and four, sum to thirty, which is the check that the subtraction happened exactly once. Practice sheet four point one includes progressively harder problems and independently checked solutions.
Pause and choose. The union is fourteen plus twelve minus five, which is twenty-one, so neither is twenty-five minus twenty-one, four. The distractor six subtracts the raw sum from the universe, forgetting that the five both-players are inside that sum twice. Five is the overlap itself, not a region total. And the last option invents a correction that appears nowhere in the principle. Add, subtract the overlap once, then take the complement of the union.
A positional number base b uses digits from zero to b minus one, and each position carries the weight b to the i. Decimal uses ten, binary uses two, and hexadecimal uses sixteen. Every digit's value is its place value: in binary, the places from right to left are one, two, four, eight, sixteen, and so on, each double the last. Hexadecimal is shorthand for binary, because one hex digit is exactly four bits, so a conversion groups a stated-width binary pattern into four-bit blocks. Leading zeros preserve the width while leaving the unsigned value unchanged, which is how an intended width is recorded.
For n unsigned bits, the representable values run from zero to two to the n, minus one. The boundary that matters: an unrestricted sum is an arithmetic fact, while a stored fixed-width result is what a stated width can hold, and a binary carry may exceed the fixed width. A wraparound rule, if the problem explicitly gives one, keeps the low n bits and discards the rest; without that stated rule, you have an overflow to report, not a value to quote. The width is a convention, and the convention is part of the answer.
The binary digits one one zero one are aligned with place weights eight, four, two and one. Reading the numeral with its weights: one eight, one four, zero twos, and one one, which totals thirteen. The same value is D in hexadecimal, because the four bits group into one hex digit. Leading zeros would not change this nonnegative value, but they can record an intended width, such as oh oh one one zero one for an eight-bit pattern. The method is the weights, right to left, every time. Practice sheet four point two includes progressively harder problems and independently checked solutions.
Pause and choose. Reading one zero one one with weights from the right: one eight, zero fours, one two, one one, which is eleven. Thirteen belongs to one one zero one, the worked example's numeral; reading the digits in the order written, instead of by weight, produces that swap. Nine drops the middle one. And B is the hexadecimal name for eleven, which answers a different question, in a different base.
Binary arithmetic adds exactly like decimal, carrying at two instead of at ten, so one plus one is zero, carry one. A bit is one binary digit, and a byte is eight. Boolean algebra works on true and false with three core operations: AND, OR and NOT. Use inclusive OR, the one that is true when either or both inputs are true, and write explicit brackets rather than trusting an assumed precedence. De Morgan's law trades the operations under a negation: not, open A and B, close, equals, not A, or, not B. Bitwise NOT inverts only the stated width, not an unspecified infinite representation, so the width convention from the previous section still applies.
A truth table lists every Boolean input combination and the output for each, which is possible because the inputs are finite: two variables give four rows, three give eight. Matching every row proves equivalence of two expressions for the same finite Boolean inputs, which is a complete proof for that question. It does not prove physical circuit timing, propagation delays, or real-system security, which live in the implementation, not the algebra. Logic gates implement stated operations, and a logic circuit connects them; trace the abstract logic according to its connections and input conventions, and leave the electronics to the electronics.
Inputs A and B enter an OR-labelled block, whose output enters a NOT-labelled block to give Y, so Y equals not, open A or B. Inclusive OR is false only when both inputs are false. Not reverses that result. In row order zero zero, zero one, one zero, one one, the OR column reads zero one one one, and the output column reads one zero zero zero. De Morgan gives the equivalent expression, not A and not B, and a truth table with matching rows would prove the equivalence for these Boolean inputs. Practice sheet four point three includes progressively harder problems and independently checked solutions.
Pause and choose. The OR is evaluated first: one or zero, inclusive, is one. The NOT then gives zero. The distractors each break the circuit in a different place: treating the OR as exclusive, applying NOT only to A, or reading the zero input as controlling the output. Trace gates in order, evaluate inside-out, and the table writes itself.
An algorithm describes unambiguous steps for a task, and a procedure solving the stated finite task must terminate and give the required result for its allowed inputs. A flowchart draws it, with a diamond for a decision and a rectangle for a process. Pseudocode represents the steps without requiring a particular implementation language, which makes its conventions your responsibility: state the assignment direction, the loop bounds and the index conventions before tracing, because the same pseudocode can mean different things under different conventions. The representation is a language, and languages need their grammar stated.
Tracing an algorithm means a table with one column per variable and one row per step, recording the actual updates in order. A trace checks the chosen input, and only that input; a claim for all allowed inputs also needs a correctness argument, because a thousand clean traces still do not cover the one input that breaks the loop bound. Efficiency matters too. A linear search can stop early at a match but may inspect all n items when the target is absent or last. Binary search repeatedly discards half of an ordered range, and its logarithmic comparison count requires the sorted-data and bound conventions; on unsorted data it is not slow, it is wrong.
The flowchart tests whether b equals zero; otherwise it computes a remainder and updates the pair before returning to the test. Start with a equal to ten and b equal to six. First iteration: ten mod six is four, so the pair becomes six and four. Second: six mod four is two, giving four and two. Third: four mod two is zero, giving two and zero. Now b is zero, and the output is two, the greatest common divisor. The temporary r preserves the remainder before a and b change, which is why the assignments work in that order. Termination is supported because each nonzero remainder is smaller than the previous positive b, so the second number strictly falls toward zero. Practice sheet four point four includes progressively harder problems and independently checked solutions.
Pause and choose. From eight and six: eight mod six is two, so the pair becomes six and two. Then six mod two is zero, giving two and zero, and the output is two. Four is the first remainder of a different start; six is the initial b, not a result; and termination is exactly what the shrinking-second-number argument supports. Trace the rows, and the algorithm's calm repetitiveness becomes visible.
A graph is a set of vertices joined by edges, and it models anything with connections: roads, friendships, dependencies. For a simple undirected graph with no loops or repeated edges, the degree of a vertex counts its incident edges, and every edge contributes two to the total degree sum, one at each end, which is why that sum is always even. A tree is a connected graph with no cycles, and a finite tree with n vertices has exactly n minus one edges. Some hierarchical models use trees, but actual systems can also contain cross-links or cycles, so check the assumption before applying the edge count.
A shortest path problem asks for the cheapest route between two vertices, by total weight under the stated constraints, rather than by the number of edges alone. A minimum spanning tree instead connects every vertex without cycles and minimises the total weight of the included edges. The two tasks can agree on an answer for a small network, but that agreement does not make them the same task: one optimises a route between two points, the other a connected subgraph over all points. Keeping the task straight is the examination point, because applying the wrong optimisation silently produces a defensible-looking wrong answer.
The undirected network joins A to B with weight two, B to C with three, A to C with eight, and C to D with one. The path A to C to D has weight eight plus one, nine. The path A to B to C to D has weight two plus three plus one, six. Therefore the three-edge path is shorter by weight despite having more edges, and the fewest-edge route from A, the direct hop to C, is the worst start. The minimum spanning tree for this small network uses A B, B C and C D with total six; the agreement of totals here does not make the tasks identical. Practice sheet four point five includes progressively harder problems and independently checked solutions.
Pause and choose. Adding the edges along each route: A B C D weighs two plus three plus one, six, and A C D weighs eight plus one, nine. So A B C D is the shortest path, at weight six. The wrong totals come from dropping an edge or misreading a weight, and choosing A C D is the fewest-edges instinct, which the weights overrule. Sum the weights, do not count the hops.
Pause for four checks. First, the union is eighteen plus fifteen minus seven, twenty-six, and neither is thirty minus twenty-six, four. Second, one zero one one base two is eleven in decimal, and its hex digit is B. Third, for Y equals not of A or B, only the row where both inputs are false gives Y true. Fourth, A B C D wins with weight six against nine, because shortest means smallest total weight under the stated constraints, not fewest edges. Take one of these five topics, sets, bases, logic, algorithms or networks, and trace a full practice sheet with its conventions stated first.