CS50 Session 4 - (2.2) De Morgan’s Laws PDF

Preview

Summary

Lecture notes on Session 4...

Description

CS50 Session 4 - (2.2) De Morgan’s Laws #algorithms Apply algorithmic thinking strategies to solve problems and effectively implement working code. (C) FA An algorithm defines a set of steps that lead a given input to produce the desired output. The steps of a proper algorithm are well-ordered, clear, unambiguous, and effective (doable). Additionally, the algorithm should be robust enough to handle a range of inputs, rather than a small set of specific cases. It should also be as simple and efficient as possible, avoiding unnecessary redundancies. Lastly, a proper algorithm should terminate in a finite number of steps. These properties can be achieved by systematically incorporating conditional steps (in which a decision must be made) and iteration (repeated steps), usually requiring careful testing and troubleshooting (“debugging”). Familiarity with various algorithmic strategies, such as brute-force methods, greedy algorithms, and divide-and-conquer approaches, can certainly broaden one’s problem-solving repertoire. These algorithmic strategies can be used to efficiently solve many real-world  problems, from connecting individuals on social media, to controlling self-driving  cars, to sequencing DNA. Algorithms are the most powerful when they can be interpreted and run by computers. Thus, writing and explaining computer code helps to boost one’s algorithmic thinking and problem-solving capabilities. Having identified a problem that benefits from an algorithmic solution, an appropriate process is developed and explained to assign students to rooms. The details of the algorithm are identified, explained, and justified: input, internal logic, output, and error message. De Morgan's laws

1) P ^ Q is equivalent to ~(~P v ~Q) 2) P v Q is equivalent to ~(~P ^ ~Q) In propositional logic and Boolean algebra, De Morgan's laws are a pair of transformation rules that are both valid rules of inference. The rules can be expressed in English as: the negation of a disjunction is the conjunction of the negations; and the negation of a conjunction is the disjunction of the negations; or not (A or B) = not A and not B; and not (A and B) = not A or not B

Negating a conditional statement Negate a statement means to put a negating sign before it. T  he negation of the

conditional statement is not a conditional statement! It’s an AND statement. If P then Q. Negation: P and Not Q

Why is this true? Given “p implies q”, there are two possibilities. We could have “p”, and therefore “q” (so q is possibility 1). Or, we could have “not p”, and therefore, we would not have q (so we could use possibility 2 as not p). Thus, “p implies q” is equivalent to “q or not p”, which is typically written as “not p or q”. This is one of those things you might have to think about a bit for it to make sense, but even with that, the truth table shows that the two statements are equivalent.

When trying to understand logical statements and how to negate them, it can be helpful to consider equivalent statements and to utilize truth tables to check your work at every stage. Finally, the negation of a statement may not always be what you expect – for example here we saw that the negation of the conditional is actually an “and” statement. As you develop your mathematical intuition for ideas like these, you will feel more and more comfortable with the sometimes surprising results. The negation of the conditional statement is not a conditional statement! It’s an AND statement.

Algorithm An algorithm is a well-ordered collection of unambiguous and effectively computable operations that when executed produces a result and halts in a finite amount of time. With this definition, we can identify five important characteristics of algorithms. 1. Algorithms are well-ordered. 2. Algorithms have unambiguous operations. 3. Algorithms have effectively computable operations. 4. Algorithms produce a result. 5. Algorithms halt in a finite amount of time. When we write in plain English, we must include many words that contribute to correct grammar or style but do nothing to help communicate the algorithm. Second, plain English is too ambiguous. Often an English sentence can be interpreted in many different ways. Remember that our definition of an algorithm requires that each operation be unambiguous.

Pre-class Work Conditional statement: If I’m writing a good algorithm, I’ll receive a 5 grade in class. Algorithm: 1) Delete an IF at the beginning of the conditional statement. 2) Look for the conditional word THEN between the two parts of the sentence. 3) If THEN was founded, then delete it. 4) Put and AND between two parts of the conditional sentence. 5) Change the verb in the concluding sentence to the opposite one. 6) Congratulations, the statement is negated. def conditional(a,b): #inputs two Boolean variables representing atomic sentences a, b #outputs the truth value of the conditional a->b  return not a or b print(conditional(True,True)) -- True print(conditional(True,False)) -- False print(conditional(False,True)) -- True print(conditional(False,False)) -- True

Explanation: So, the code basically returns a (Not a or b) statement given the initials values (True or False) of a and b. Knowing the De Morgan’s rules, we know that (Not a or b) is equivalent to the

conditional statement a-->b. So, the code is telling us whether or nor the conditional statement is true given all possible values of two atomic sentences a and b....