13
|
9833 Views
|
60 Replies
|
51 Total Likes
View groups...
Share

# [WSG23] Daily Study Group: Introduction to Discrete Mathematics

Posted 10 months ago
 A Wolfram U Daily Study Group on Introduction to Discrete Mathematics begins on October 16th 2023. Join me and a group of fellow learners to learn about the mathematics behind the innovations of computer science using the Wolfram Language. Our topics cover the most well-known branches of discrete mathematics, including logic, sets, discrete functions, sequences, combinatorics, algorithms, proofs, recursion and graphs. This study group aims to develop a broad understanding of discrete mathematics, with a focus on concepts useful in computer science, software engineering and programming, and make this rich and useful domain accessible for any college student, professional or interested hobbyist. A basic working knowledge of the Wolfram Language is recommended but not necessary. We are happy to help beginners get up to speed with Wolfram Language using resources already available on Wolfram U. Please feel free to use this thread to collaborate and share ideas, materials and links to other resources with fellow learners. REGISTER HERE
60 Replies
Sort By:
Posted 10 months ago
 Marc Vicuna has done a great job in developing this thoroughly up-to-date introduction to Discrete Mathematics.I strongly recommend the Study Group to everyone!
Posted 10 months ago
 Registered! The best Group Theory thing I ever figured out on my own: the late Skwish Toy inventor Tom Flemons pointed out to me that his manufacturing operation made the toy with a single elastic line that was segmented when the balls were glued to the end of the rods. That makes the lines of Skwish an Eulerian Cycle. In my University class, all of the groups used as examples for cycles, etc., were flat (and boring!) drawings on a page; I suggested to my prof to use the Skwish geometry on a problem set to mix things up a bit. The Manhattan Toy product is the best-selling tensegrity model on the planet, but most of the customers seem to just chew on it. :)
Posted 9 months ago
 Hello Wolfram community! This course will start in 15 minutes! If you're interested, join us now with the link above!Happy learning to all!
Posted 9 months ago
 Hi Marc,Thanks for creating this great (refresher) course. Below I share a few minor issues I found:Issues with lesson notebooks The notebooks are created with a higher version of Mathematica and it hangs the Kernel start-up on my machine. Workaround: start Mathematica first, then open the notebook. With the Mathematica Welcome Screen open, double-clicking a notebook may not open it. Workaround: use Open from the Welcome Screen menu; locate the file and open it. Scrolling a notebook, may hang the Kernel after pressing the Enable Dynamics button. Workaround: do not Enable Dynamics until you're done scrolling. BigMarker recording at timecode 25:56In the recoding of Monday's Lesson 2 Slide 5 Example (timecode 25:56) Should this be: "I did not pass the exam?"Given the logic, should this be "I did not study for the exam, nor did I pass it"?
Posted 9 months ago
 Anticipating today's lesson on Sets: Can we use abstract symbolic calculations on sets and what is the best way to do it? For example, can we use Union and Intersection, or should we use the AND and OR operators to make it work? For example ResourceFunction["VennDiagram] uses AND and OR operators.The context of my question is: Set theory and Logic are used in axiomatic probability i.e. for two events A and B, P(A union B) = P(A) + P(B) - P(A inter B). The same probability becomes cumbersome to manually calculate when there are more than two events i.e. P(A union B union C). I started with multiple replacement rules (distributive, associative, commutative, idempotency etc) , but then I derived a general equation for which I created code for any number of events > 2, but I had to fudge the notation. I'm sure there is a better way; for instance if we can use Set theory and any symbolic calculation on them. Clear[P] P[l_List] := Total@Table[ Function[a, (-1)^(i + 1) Total[Apply[P, #] & /@ a]]@ Union[Sort /@ Permutations[l, {i}]], {i, 1, Length@l}] P /: P[a__, b__] := Quiet@P[a \[Intersection] b] The result for three events is:
Posted 9 months ago

Hello Marc!

I'm here to learn and to offer feedback.

Most of the lessons seemed fine in yesterday's recording. However, there was an issue with the photo of the woman chosen to portray "disorientation" and "confusion" at the 31:41 time stamp. The photo is misogynistic and inappropriate. Instead, try using a more generic image, such as a stick figure or a confused puppy with question marks all over it. This would be more appropriate and add a touch of humor to the presentation.

See you at 11AM.

## Lori

Posted 9 months ago
 Hi Davendra!I've enjoyed three of your courses. Nice to 'see' you again :-D
Posted 9 months ago
 Hello.
Posted 9 months ago
 Hello Lori,Thank you very much for your active participation and support for these online courses!
Posted 9 months ago
 Think I heard somebody was looking for references. Here is a general document about Discrete Mathematics found at Yale and distributed under Creative Commons Attribution-ShareAlike 4.0 International license. The link: Notes on Discrete Mathematics
Posted 9 months ago
 Hello Dave, For the versioning, we're working on changing it to the correct Mathematica version. For dynamics, there is not much we can do about it, unfortunately.For the mistakes in the slides, that is correct, thank you, it will be corrected.Best, Marc
Posted 9 months ago
 Hi Marc,I am struggling with a statement in “Lesson 4 - Predicate Logic.nb”, Slide 6: This is a special case of existence. -> I agreeIt is unique and is denoted by ... -> Is it correct to say that Mathematica cannot print the right symbolic? Otherwise, the output of "Exists[x, x == -x]" is wrong.Please clarify.
Posted 9 months ago
 Hi Marc,The following request is related to Week1_Polls.nb -> Lesson 5 -> Question 2.Life is difficult but* fun.*Yesterday, I have learned that the English word but means AND in the logical language. Do other keywords, like but, exist to translate English sentences into logical statements? Do you have a list of such keywords? Can you please give me a reference?English is not my first language. Therefore, support is highly appreciated.
Posted 9 months ago
 Hello Dave,The Wolfram Language does not have symbolic set computations available. In fact, the Wolfram language intentionally does not have a proper theoretical set implementation, since it would require many implementation choices on definitions that may not fit the user. However, you can implement set manually easily with Sort and DeleteDuplicates. In a sense, this is one major use of boolean expressions: you may simplify and analyze set expressions in logical form, then, when comes to computing actually sets, you may transfer your logical expression to a set expression. The equivalences between set theory and logic guarantee this. See this post for example.Best, Marc
Posted 9 months ago
 Thank you, Lori.This is noted. The poll questions are only used for the study group, so this will not appear on the course framework. However, my courses do tend to use a lot of images. It will be corrected. If you notice any similar problems in the lessons, exercises, or quizzes, feel free to tell us when we don't catch those mistakes ourselves.Best, Marc
Posted 9 months ago
 Hello Jürgen,I'd argue this is the right output. In mathematics, usually, we usually indeed write: However, in code, the Wolfram Language uses a different but equivalent notation, where the variable is written as a subscript. This will still evaluate as you would expect. For example, Reduce[Exists[x, x == -x]] return True.
Posted 9 months ago
 Hello! Marc
Posted 9 months ago
 Hi Jürgen,Thank you for the great question, this is likely useful for many. Let's start with or. Usually, this operator is the simplest to recognize, you'll find it when using "or" and it is sometimes implied when a choice is given. However, in day-to-day language, it is often confused with xor, the exclusive or. In our course, every time either is used, it is xor, anywhere else, or means or. In real situation, you may have to require your client to specify what is meant.For the case of "and", while "and" is often used, it is also often implied. For example, in the line "this excellent white shredded French cheese", this cheese is excellent AND white AND shredded AND French. When searching for "and", it's best to think about what is said to be simultaneously true, and put in a conjunction all those statements. When and is not used, synonyms include but, however, along with, plus, also, as a consequence, as well as, furthermore, including, moreover, together with. Note two notable ways to get a negative "and", in the form "not p and not q": "nor" and "neither" are usually used to denote a negative and.By far, the most difficult operator to recognize is the "implies" operator. There is p is a sufficient condition for q, p only if q, p implies q, q whenever p, q is a necessary condition for p (i.e., if not q, then not p), or ¬ q→¬ p, q is a consequence of p, q follows from p, q if p, if not q, then not p. See this post. Generally, if you see "if", "implies", you are in a conditional statement. When analyzing conditional, be also careful to determine which is the condition, and which is the implication.Logic is everywhere, so people have all kinds of ways of expressing their reasoning. Sometimes, it just takes patience.
Posted 9 months ago
 Thank you Marc,I will explore the route to simplify and analyze set expressions in logical form and transfer them to sets later.
Posted 9 months ago
Posted 9 months ago
 WRT resources in the course, one excellent resource I have found is Wolfram Mathworld: the web's most extensive mathematics resource. For definitions of terms, it's quite a winner. It's far superior to the Wikipedia: a small number of curators help insure high quality. I've stumbled across a fair number of wrong entries in the Wikipedia -- even in science articles -- but I've never seen anything but top-shelf data in Wolfram Mathworld. Note: all of the entries are Wolfram Language notebooks (!!!) available for download and manipulation.Like many things associated with Stephen Wolfram or Wolfram Research, there's no good reason for Mathworld to exist. An individual created it in the 1990s, and Wolfram bought it in 1999. Entries continue to be added and enhanced. I first stumbled across the encyclopedia earlier this year when I as looking for a particular 3D Curve and found Viviani's Curve in the entries.
Posted 9 months ago
 Download of zipped lesson files is missing Lesson 1. First file with no name is another copy of Lesson 16.
Posted 9 months ago
 I'm curious why the community page for this study group has WSG23 in the name rather than WSG46.
Posted 9 months ago
 To answer a Q/A that appeared at the end of class today,You can change the printing of any notebook using File->Print Settings->Print Setup or File->Print Settings->Print Setup->Printing Environment.Personally, for my slides, I usually use a landscape print setup and an Elegant Printout printing environment, and then select the slide I want to print since there will be empty pages.Feel free to experiment with the settings, and checking your result with File->Print PreviewBest, Marc
Posted 9 months ago
 Hello,Indeed, the study group does not follow exactly the order of the lessons in the course, due to the restriction of 3 lessons per days. Instead, we will cover lesson 11 Monday, along with 2 other lessons about different types of proofs in discrete mathematics.Best, Marc
Posted 9 months ago
 Indeed! All the concepts of this course with a few exceptions can be found on Math World, demonstrating to the many resources links to Math World throughout all exercise notebooks.However, Math World's definition can be daunting to beginners, as the strict mathematical notation used can make simple concepts seem counter-intuitive. This is why we use a combination of sources for our definitions and adapt the material for the intended audience.Overall, I confirm the material on Math World is of high quality, but it is not always appropriate for beginners.Best, Marc
Posted 9 months ago
 Hello Ray,It seems strange you don't have access to Lesson 1, I see it on the shared folder for the study group. In the mean time, here is lesson 1 is here in cloud and attached too.Best, Marc Attachments:
Posted 9 months ago
 Hello Ray, Indeed, it should be 46. Thank you for bringing attention to that.Best, Marc
Posted 9 months ago
 Sorry, I was able to download the individual Lesson 1 file so I had access. I just thought you might want to correct the zip file before you go production.
Posted 9 months ago
 Well, Mathematica is addictive nerd candy and you Wolfram folk are pretty nice, online and in person. It's hard to stay away!
Posted 9 months ago
 Ray are you using Windows? Maybe the issue with the Lesson 1 notebook is happening because the filename has a question mark at the end. Most archivers have a problem with it as Windows does not allow filenames with a question mark. 7-Zip can handle files with invalid Windows filename characters and replace them with a "_" instead. I assume Wolfram Research uses Macs where questions marks can be used in filenames.
Posted 9 months ago
 Dave, yes using Windows. When I open the zipfile using OS, the first file appears as ".nb" and presents Lesson 16 when I open it.The new zip file today now has the Lesson 1 file but still contains the ".nb" file which is a second copy of Lesson 16.
Posted 9 months ago
 Hello Ray,Yes I see that file also, I'll remove it. It will be corrected.Thank you, Marc
Posted 9 months ago
 Thanks.
Posted 9 months ago
Posted 9 months ago
 I'm not seeing that, Ray. Today's (Monday, 10/23) link worked just fine for me.
Posted 9 months ago
 Cassidy reported the link has been fixed.
Posted 9 months ago
 At the beginning of the session @Marc Vicuna says that "the simplification of [propositional] expressions is not intuitive to a computer" -- implying that it is essentially impossible for the Wolfram Language (or any other computational language) to provide a natural intuitive way to simplify/process/visualize those propositions.Mark, can you prove your claim? Can you prove that it's impossible to provide any sort of way to simplify/process propositions beyond what's available now? If not, what's the point of making such a claim?The reason for my skepticism: I have seen the wondrous ways that the WL can provide simplifications in many domains. Those things were "impossible" -- until they were done in the Latest & Greatest version of the Wolfram Language. If there's some hard and fast reason why it can't be done here, it'd be educational to understand that reason why Discrete Mathematics is somehow different. TY.
Posted 9 months ago
 I am watching video recording of first day: set & logic Anyone knows, for De-Morgan's Law of quantifiers:Is this Axioms since it's so obvious. If not, how it can be deduced?
Posted 9 months ago
 I'm a bit confused by what LinearRecurrence[] is doing. The one slide in Lesson 19 was a bit fast; I experimented with it a bit this morning and read the help file, and it now mostly makes sense.One thing that still doesn't make sense is what LinearRecurrence does with the list of initial values. If I do LinearRecurrence[{2}, {5, 4, Q, 2, 1, 6}, 10] the response is {5, 4, Q, 2, 1, 6, 12, 24, 48, 96} I see in the documentation that only the last Length[ker] elements are used in the calculation -- the other elements are simply copied to the output. What is the physical (i.e., mathematical) significance of doing that copying operation on that subset of the input list? In other words, is there an example where someone would actually have a list of initial values that didn't matter? I have a hard time wrapping my brain around a list of inputs that are simply ignored.
Posted 9 months ago
 Hi Tianyi,This rule has many different proofs, which may depend on the equivalences you have access to in this context. I would generally use a proof by contradiction for both sides, as seen in this proof, where the perpendicular lines represent a contradiction: This proof and other proofs are available here.Best, Marc
Posted 9 months ago
 Hello Phil,Let's go through the basics of the LinearRecurrence function.Let's first consider the second input, which corresponds to the first terms of the sequences, a.k.a. base cases of the recurrence. Why specify that? Because all recurrences are based on n base cases, where n is the order of the recurrence. Let's now consider the first input, the coefficients of the linear recurrence. This list is the coefficients of the terms in the recursive call, a.k.a. the recursive function (in f[n]= a f[n-1] + b f[n-2] + c f[n-3], the coefficients are {a, b, c}). Thus, the length of the list of coefficient specifies the order of the linear recurrence.I'll now answer your question directly. Many basic sequences, such as when dealing with n-faced polyhedra, hypercubes, or many aggregation phenomena in data science may require special first terms, since the 0 or 1 case of applied phenomena often follow altogether different rules than the recurrent cases. If I have in a stack data structure the elements {5, 4, Q, 2, 1, 6}, and every time the stack is used, it read the head of the stack, and pushes double of the value into the stack, then after four operations I will have a stack of the sequence you made.Another interesting case would be with multiagent system with limited knowledge, where the variable length of the list coefficients over the same list of base cases (environment, or prior knowledge) may express their degree of limited understanding of a given sequence.Since the world is complicated and messy, especially in the initial cases, this feature is useful as it does not force your entire sequence to be dictated by the recurrence formula, exactly as an actual functional implementation would allow: f[0]:=5; f[1]:=4; f[2]:=Q; f[3]:=2; f[4]:=1; f[5]:=6; f[n]:=2 f[n-1]; This is a valid implementation, and it is possible to represent it using LinearRecurrence, making it more programmer-friendly.Best, Marc
Posted 9 months ago
 Hello Study Group,To confirm, the last question of lesson 22 lead to some confusion with reason, as the definition given for the vertex degree was wrong, or more precisely, only appliable to simple graphs. Therefore, the definition will soon be changed to "The number of incident edges to v is its degree.", since it's the number of edges that is important. This will be corrected.Thank you for noticing and sorry for the confusion,Marc
Posted 9 months ago
 Thank you, very, very much for understanding!
Posted 9 months ago
 A real "Traveling Salesman" problem!Recently, good friend Gil Hedley started his Nerve Tour, a series of presentations in 111 cities. Gil is conducting the tour over two years; he and his wife are traveling to all the North American cities with a camper. If you look on the tour page, you'll see the cities are laid out in a [rather boring] table; I thought it would be fun to map them out. I copied his data and used GeoListPlot to plot it out:The tour length was 21,447 miles! All things equal, an optimized tour was 12,520 miles. But all things are never quite equal: Gil arranged to be in northern latitudes in warm months and southern cities in cooler months. I tried to draw the optimized map; I'm still wrestling with GeoListPlot. I'll update the forum when I have that map.
Posted 9 months ago
 Hi Marc,I have a problem reproducing the hypergraph in Lesson 24 notebook, section "Final States". If I run ResourceFunction[ "WolframModel"][{{x, y}, {y, z}} -> {{x, y}, {z, y}, {y, w}, {w, x}}, {{0, 0}, {0, 0}}, 11, "FinalStatePlot"] The result is this hypergraphWhere I used the same rule as the example in the section before: rule = {{x, y}, {y, z}} -> {{x, y}, {z, y}, {y, w}, {w, x}}; I suspect another rule was used when the notebook was created; probably similar to the one in the example of the ResourceFunction["WolframModel"] documentation: https://resources.wolframcloud.com/FunctionRepository/resources/WolframModel/ ResourceFunction[ "WolframModel"][{{x, y}, {x, z}} -> {{x, z}, {x, w}, {y, w}, {z, w}}, {{0, 0}, {0, 0}}, 11, "FinalStatePlot"] Which gives the plot shown in the lesson notebook:
Posted 9 months ago
 Hi Phil Earnhardt,I just wanted to answer your question from the feedback. In a few words, the goal is usually to have the course framework available at the launch of the study group, and have the course officially released at the end of the study group. However, having the framework beta coincide with the planned start of the study group a month or two in advance can be difficult. The course in my view is ready at beta, but the study group is given a privileged view into the course material given. That said, we always aim to improve our courses, and this methodology is subject to change from course to course. Your comments have reached the Wolfram U team and will be considered. At the very least, I believe future courses will try to better communicate course framework status.Thank you for your feedback and happy learning, Marc
Posted 9 months ago
 Hello Dave, The explanation actually even simpler! You're using the rule from slide 10, but the rule is actually found on slide 9. In other words, you could evaluate slide 10, then 9, then 11, and it would work. The rule is rule = {{x, y}, {x, z}} -> {{x, z}, {x, w}, {y, w}, {z, w}}; (slide 9)and not rule = {{x, y}, {y, z}} -> {{x, y}, {z, y}, {y, w}, {w, x}}; (slide 10)But this is fair, this order doesn't make much sense. I guess I'll just change the variable name of slide 10 to "rule2" or such. This will be corrected.Thank you for noticing, Marc
Posted 9 months ago
 Hello Phil, Sorry for not answering your question sooner, I did not see it.Let me clarify my claim. While any boolean expression can be simplified to an outstanding degree, especially in the WL, there's a point to be made about the overreliance on computational methods. If I give my computer a huge amount of data, but I actually only need the properties of a small subsection of that data, looking at the entire dataset all at once may not help me. The point here is that even if your boolean expression is fully simplified, it may be still difficult to search for the property you want. Rules of inference are there to reduce the scope of the proposition, to be able to simplify the conclusion you take out from your computation. Thus, even with the best computers, you need to have ways to simplify the information for your own purposes.I don't think this is particularly contentious, but I understand why my hesitations may have led to some confusion.Best, Marc
Posted 9 months ago
 A reminder to the Discrete Math Study Group participants that the deadline to pass the six quizzes for your course completion certificate is Friday, November 10. The exam can be taken anytime from the course framework. Refer to your Study Group emails for a link to the pre-release framework and to recording links from Study Group sessions. We heard a lot of positive feedback from Friday's review session. You might want to watch that recording, in particular.
Posted 8 months ago
Posted 8 months ago
 @ray chandler Why should the tag be WSG46? I thought the tags for the WSG were always WSGYY where YY are the last 2 digits of the year when the WSG was held. This pattern has been followed for dozens of WSGs over the last 5 years.What is the significance of the tag WSG46, Mark? What does that stand for?
Posted 8 months ago
 @Phil Earnhardt, you're correct, we mixed up our tagging system for Wolfram Daily Study Groups. The community tag has usually referenced the year, but we also use WSG code numbers (mostly internally) to track our Study Groups in the order they are scheduled and organized by Wolfram U staff. The Introduction to Discrete Mathematics is our 46th Wolfram Study Group, so that's where that tag came from. Thanks for being an active participant in this initiative.
Posted 8 months ago
 I'm pleased to announce Introduction to Discrete Mathematics is now available on Wolfram U, including all course videos, exercises, quizzes and the final exam! Click Track My Progress to chart your certification progress. Go to the free course by visiting the course landing page and signing in using your Wolfram ID. Congratulations to Marc Vicuna and the Algorithms R&D team on this wonderful course, and kudos to the Wolfram U team for bringing it to fruition. Read Marc's blog post about the launch of the course: https://blog.wolfram.com/2023/11/29/dont-be-discreet-and-learn-discrete-mathematics-with-wolfram-language
Posted 7 months ago
 After 7 Inputs, I can't see the input line anymore of the Scratch Notebook while I try the exercises of the course. Any idea ? Thank you for your patience
Posted 7 months ago
 In lesson 7, it says "Intersection is a higher priority operation than union." Anyone can please explain why?
Posted 7 months ago
 "Intersection is a higher priority operation than union."Operator precedence in the Wolfram Language is comprehensively listed on this help page. It shows intersection has a higher precedence than union. That's a good catch: perhaps the text should be using "precedence" rather than "priority".If you're asking why intersection should have a higher precedence than union, I cannot say. This answer in a Physics Forums discussion notes that "When people generalize intersections and unions to Boolean algebra, intersection is multiplication and union is addition."I asked Google Bard (an AI) why intersection had higher precedence than union. Here is what it had to say. It sounds reasonable to me; YMMV. If that's not satisfactory, you could ask Devendra Kapadia or course instructor Marc Vicuna. Hope that helps.
Posted 7 months ago
 May I ask how to understand this result in Lesson 11 Binomial Identity?
Posted 6 months ago
 Hi Tianyi, I can confirm Phil's answer. First, it's important to understand precedence is a convention, not a theorem. We need precedence so that our expressions behave as intended. PEDMAS is a convention that is followed for common operations, but it does not covers all mathematical operations. Mathematics contains many rings outside of the set of reals with addition and multiplication. It is good practice to follow a similar precedence in all rings. To help you see the similarities between intersection and multiplication, we can ask:Consider the equality {} ∩ A = {1}. What is the set A? This is indeterminate, as this is equivalent to a division by 0. Overall, precedence is a convention rooted in group theory. The precedence of set operations has to do with its definition in group theory and its relation to the PEDMAS convention.Best, Marc Vicuna
Posted 6 months ago
 Hi Tianyi,Honestly don't try to understand it, it seems to be a mistake. It took me a while to understand what was going on. I'm a mathematician in discrete mathematics, so I have limited knowledge of complex analysis. When I wrote that lesson, I was told this is the complex variant of the Vandermonde identity, related to the Chu-Vandermonde identity. After some digging, it seems this summation is wrong. I'll inform the Summation team to fix this.Best, Marc Vicuna