Overview

Use Boolean logic to program a Web site function that requires users to confirm their identities to gain access to their online accounts. Then, solve three proof problems related to networking and security.

Context

The Assessment 3 Context document contains information about mathematical logic, specifically set theory and proofs.

Resources

Suggested Resources

The following optional resources are provided to support you in completing the assessment or to provide a helpful context. For additional resources, refer to the Research Resources and Supplemental Resources in the left navigation menu of your courseroom.

Resources

Click the links provided to view the following resources:

Capella Multimedia

Click the links provided below to view the following multimedia pieces:

• Discrete Math Logic | Transcript.
  • This presentation includes the following topics:
    • Definitions.
    • Truth table of compound statements.
    • Conditional propositions.
    • Logical equivalence.
    • Tautology.
    • De Morgan’s law.
• Proofs | Transcript.
  • This presentation includes the following topics:
    • Definitions.
    • Types of proofs.
    • Rules of influence.
    • Rules of inference for quantified statements.
    • Resolution proofs.
    • Mathematical induction.

• Koshy, T. (2004).Discrete mathematics with applications. Burlington, MA: Elsevier Academic Press.
  • Chapters 1, 4, and 12.

• Johnsonbaugh, R. (2018). Discrete mathematics (8th ed.). New York, NY: Pearson.
  • The following chapters and sections are particularly useful for your work in this assessment.
    • Chapter 1, “Sets and Logic,” sections 1.1 through 1.4. These sections address sets, propositions, conditional propositions, logical equivalence, arguments, and rules of inference.
    • Chapter 2, “Proofs,” sections 2.1 through 2.4. These sections cover mathematical systems, counterexamples, direct proofs, resolution proofs, and various methods of proofs.
    • Chapter 11, “Boolean Algebras and Combinatorial Circuits,” sections 11.1 and 11.2. These sections focus on combinational circuits and their properties.

Assessment Instructions

Part 1: Logic and Boolean Algebra

Imagine that you are programming a Web site where users must confirm their identities to attain access to their online accounts. The users are able to confirm their identities by supplying the following information: UserID, SS#, MothersName, and Password. Specifically, a user will be able to gain access by correctly answering at least 3 of the 4 above queries. For example, a user who supplies the correct UserID, SS#, and Password, but supplies an incorrect MothersName, will gain access.Note that these 4 input variables/conditions are Boolean variables: the information is supplied either correctly (true) or incorrectly (false). We will also use a 5th Boolean variable (output variable) named Access, which is true if the user supplies the necessary information correctly and is false otherwise.

1. Restate/define the 5 Boolean variables used in this scenario and describe when each variable is true or false.
2. Create a truth table that shows the values of the output variable for all possible combinations of values of the input variables.
3. Create a Boolean equation using Boolean operators (AND, OR) that characterizes the relationship between the output and input variables.
4. Create a logical circuit diagram that describes your variables using the correct symbols for each logic gate. You may draw the diagram by hand or use one of the free, online schematic drawing tools to create it.

Part 2: Logic and Proofs

Answer each of the 3 following problems that require the synthesis of logical proofs. Be sure to answer all the parts of each problem.

Proof 1: Logical Reasoning and Proofs: Application Server Load

Assume you have been tasked with assessing the “load” or “user traffic” that users might impose on your company’s servers. Specifically, you wish to bound the total number of threads opened up on the servers given the number of users active. Given initial analysis, the number of threads, t, can be estimated in terms of the number of users, n, within a reasonable error using the following equation:Σⁿ_x= 1^x = (1 + 2 + 3 + … + n) = tYou believe n² is a reasonable bound for (1 + 2 + 3 +…+ n). To justify this, you must first prove the following inequality holds for all integers n ≥ 1.

(1 + 2 + 3+ …+ n) = ≤ n²

1. State your proof idea. What type of proof will you use to prove/disprove this inequality and why?
2. Prove or disprove the inequality.

Proof 2: Logical Reasoning and Proofs: Functions and Discrete Structures

Security and encryption is also a concern of IT personnel. Many simple encryption schemes rely on the use of the modulus function. The modulus function is also popularly used as a hash function, which is used in the construction of hash tables. The modulus function returns the remainder value resulting from a division operation. For example, 6 mod 5 = 1 and 13 mod 7 = 6.

1. In order to build an appropriate hash function, one must have a good understanding of the properties of the hash function used. To this end, prove or disprove the following statement for all positive integers n and m.

   2 ⁿ mod 2 m = 4 ⁿ mod 2( m+ 1)

Proof 3: Logical Reasoning and Proofs: Encryption and SecurityNetwork security and encryption is also a concern of IT personnel. Many encryption schemes are based on number theory and prime numbers; for example, RSA encryption. These methods rely on the difficulty of computing and testing large prime numbers. (A prime number is a number that has no divisor except for itself and 1.)For example, in RSA, one must choose two prime numbers, p and q; these numbers are private but their product, z = pq is public. For this scheme to work, it is important that one cannot easily find p or q given z, which is why p and q are generally large numbers. Seemingly this strategy would work best if there are many large prime numbers, so that one could not easily guess the prime divisor of z.

1. State your proof idea. What type of proof will you use to prove or disprove this inequality and why?
2. Prove or disprove the statement.
   

   Logic Scoring Guide

   CRITERIA				DISTINGUISHED
   Define Boolean variables.				Defines Boolean variables, explains their use in the IT/computing scenario, and relates Boolean variables to propositional logic.
   Construct truth table using Boolean algebra and logic.				Constructs truth table using Boolean algebra and logic. Designs truth table in an orderly manner and has columns for intermediate results.
   Compose Boolean equation using Boolean operators.				Composes Boolean equation using Boolean operators, arranges equation in a standardized form, and reduces the size of the expression.
   Design a logical circuit diagram using correct symbols for gates.				Designs a logical circuit diagram using correct symbols for gates, and the number of logic gates used is minimal.
   Select an appropriate proof type for proof problems.				Selects an appropriate proof type for proof problems. Investigates or rejects other proof types for each problem.
   Construct a proof using mathematical reasoning, deductive logic, or inductive logic to assess truth of mathematical or logical statements.				Constructs a proof using mathematical reasoning, deductive logic, or inductive logic to assess truth of mathematical or logical statements. Proofs are formal: orderly, organized, and flawless.