Math for CS: Logic and Propositions

I'm doing sort of a brain dump of units as I learn them. I don't want these posts getting too long though. Just want to keep it simple. Starting with unit 1.4 because I haven't created the blog yet while going through previous lessons. I might go back and make posts about them.

Unit 1.4: Logic and Propositions

A proposition is a statement that is True or False.

A large fraction of all math statements are of the if-then form.

Learning about propositions, and propositions from propositions. The propositions from propositions can be combinations, modifications, or relations.

For example, and, or, not. A implies B. A if and only if B.

Truth tables are used to illustrate.

You can have propositional expressions that can be simplified into a logically equivalent form. This has applications in computer science where it can make a program easier to read and understand. Simplified programs may also run faster, since they require fewer operations.

In hardware, simplifying expressions can decrease the number of logic gates on a chip because digital circuits can be described by logical formulas.

Minimizing the logical formulas corresponds to reducing the number of gates in the circuit. The payoff of gate minimization is potentially enormous: a chip with fewer gates is smaller, consumes less power, has a lower defect rate, and is cheaper to manufacture

Discusses equivalence and validity. Implications and contrapositives are equivalent. For example, Do these two sentences say the same thing? If I am hungry, then I am grumpy. If I am not grumpy, then I am not hungry.

The answer is yes, a truth table is used to demonstrate.

In contrast, the implication is not equivalent to its converse. That is, P implies Q does not equal Q implies P. However, the implication and the converse can be used for the statement if and only if. That is. P iff Q = P implies Q AND Q implies P.

We go on to discuss the algebra of propositions. For proving equivalences, we can use truth tables or sometimes use algebra with axioms.

Overall, this unit was good. Some things I had already learned when I took discrete math in college. The in-class problems weren't too bad.