Please help with these problems for a discrete structures (computer science + mathematics) college course. Note that eac

[answerhappygod]

Please help with these problems for a discrete structures(computer science + mathematics) college course. Note that eachproblem has multiple parts so please answer all parts.
Thank you in advance!

Please Help With These Problems For A Discrete Structures Computer Science Mathematics College Course Note That Eac 1 (175.7 KiB) Viewed 35 times

Problem 1: The World is Not/And/Or Enough (25 points) In class, we discussed logical operations like 'and', 'implies', etc - the purpose of these operations is to take propositions and combine them to produce new statements, and we worked to understand the relationship between their truth values. We can think 'and' like a function F(A, B) = (A^B), where F(A, B) is true only when A, B are both true, and false otherwise. Each logical operation can be thought of in this way, a function that takes as input two truth values (or propositions that have truth values) and gives as output a proposition with a corresponding truth value. Importantly, we could then consider operations on more variables - like F(A, B, C) = (AVBVC), where this function is true when at least one of A, B, C is true, and is false otherwise. The purpose of this problem is to understand what boolean or logical functions are possible, and how to calculate them. 1) Note that for two variables A₁, A2, there are 4 possible arrangements of truth values TT, TF, FT, FF. If you had N many variables, how many possible arrangements of truth values could these variables have? 2) A logical operation needs to give an output truth value for each possible arrangement of input truth values. How many logical operations are possible on two variables? How many possible logical operations are there on N variables? (Hint: How many possible truth tables could you make with N many variables? How many rows would it have, how many possible ways to fill the final column?) 3) For each possible logical operation on two variables, show that it can be expressed using some combination of AND (^), OR (V), and NOT (-). How do you know that you got them all? The result of the previous problem is that any two variable logical operation F(A, B) can be expressed in terms of three operations, AND/NOT/OR. These next problems mean to show that this is true for any logical operation, on any number of variables. 4) Consider a boolean operation on three variables, F(A, B, C). Show that no matter what, F actually is, the following holds: F(A, B, C) = [F(A, B, True) AC] V [F(A, B, False) ^¬C] (1) 5) Note that F(A, B, True) and F(A, B, False) are in fact two variable logical operations. Use the previous result to argue that any three variable logical operation can be expressed using only AND/OR/NOT. 6) Argue then that any four variable logical operation can be expressed using only OR/NOT/AND, and in fact, any logical operation on any finite number of variables can be expressed using only OR/AND/NOT.
Problem 2: True Facts about the Justice League (25 Points) You work for noted villain the Calculator. Based on your research, you know the following things are true: • Batman can only defeat Superman if Superman is alone and Batman has Kryptonite. • To get Kryptonite, Batman must partner with Lex Luthor. • If Batman partners with Lex Luthor, Wonder Woman will help Superman. • If Wonder Woman helps Superman, then Superman is not alone. The Calculator asks you whether Batman can defeat Superman, but as you start to explain why or why not, they interrupt you "words are a coward's math, someone who is good with words can make anything sound true! Prove your claim to me logically." 1) Introducing variables for each sub-proposition, (for instance A = Batman can defeat superman), represent the four statements above in terms of these variables in logical notation. 2) Is it possible that Batman can defeat Superman? i.e., is it possible that the statement A is true? Show, logically, why or why not. (Hint: Assume that A is true. From the facts you know (as expressed in the previous problem), what else can you work out the truth value of ?) 3) The Calculator, nodding as they listen, concurs with your calculations. And then asks the following question: If Batman fails to defeat Superman, is it because Wonder Woman helped him? Why or why not.
Problem 3: Calculating the Limits of Calculation (25 Points) Computers can do a lot! But they can't do everything. 1) Argue that there are at most countably infinite computer programs. Think about the problem of computing real numbers as the output of a program. A computer might calculate 1/3 for instance, by printing 0.3, then go into an infinite loop repeating 3, forever. More complicated programs could calculate more complex things, like the square root of 2, or for instance. T 2) Argue that there are real numbers that cannot be calculated by any computer program. (Hint: Think about pairing every program with its real number output.) 3) Does it matter if you used a different language? Multiple languages? More powerful computers? Why or why not? 4) Conclude that there are fundamental limits to what can be computed by any computer.
Problem 4: Something Something Horse (25 Points) Consider the following problem: let 0₁, 02,...,an be positive real numbers; let 3₁, 32,...,BN be positive real numbers, and let B be some positive constant. What is the largest possible value you can achieve for where #1, #2,...,EN ≥ 0 and α1x1 + a2x2+...ONEN, B₁1+ B₂₂ + + BNIN = B. (2) (3) 1) Suppose (1,2,..., N) satisfied the constraints. You want to consider decreasing ; by some amount, and increasing ; by some amount to make up for it, so the constraints are still satisfied. If you decrease , by €, how much would you have to increase x; by to make sure the constraints are still satisfied? What's the most you could decrease x; by? 2) Decreasing ; by e, and increasing r; as above, when does this action improve the value of Eq.)? What has to be true about ai, aj and B₁, B₁? 3) What possible (₁, 2,...,EN) values can't be improved on, by shifting weight around in this way? 4) What is the maximum possible value of Eq. (), over the (₁,...,N) that satisfy the constraints?