CS202 Study Guide

Unit 3: Mathematical Logic

3a. Describe declarative statements in math that have 100% "true" or 100% "false" values

  • What is the difference between stating a proposition in propositional logic and in human language?
  • What is the difference between "implication" and "consequence"?
  • What is the worth of a truth table?

As it says in the readings, "Logic is the study of consequence". Mathematics is meant to be objective symbology and methods for determining facts and truth, given various circumstances. This topic, however, deals with facts that are either 100% true or 100% false.

Facts, when considered together, have consequences. Sometimes this is because of physics. Other times it is due to civil or criminal law. Other times, it is something all agreed upon. For instance, in color science, colors are named according to their mixture of pure Red, Green, and Blue, the color's RGB representation. To call anything other than RGB = (255,0,0) "RED" is incorrect, according to the tight definitions of color science. International tables of RGB triplets and their associated color names exist so that there is some agreement. Here is where a truth table comes in handy. A color-name truth table might appear such as shown here:

Red (R)

Green (G)

Blue (B)

Color Name

255

0

0

RED

. . .

     

 

In a table of this type, a color name can only appear once in the far-right column and a triplet of RGB values can only appear once. We might say, "If R =255, and is G = 0, and is B =0; then the color's name is 'RED'". Another way to view this is more akin to the truth tables we are studying::

RED = 255

Green = 0

Blue = 0

R & -G & -B

1 (true)

0 (false)

0

1

1

0

1

0

1

1

0

0

1

1

1

0

0

0

0

0

0

0

1

0

0

1

0

0

0

1

1

0

 

Using the second form of the table is much harder to represent and understand all the facts (the RGB values and associated color names). But, it underlies the first table. Clearly, in either case, a measurement of RGB values is needed if we are to determine the consequence, the name of the color. The facts must be known exactly. While that is not always possible in human situations, we must know what needs to be known, what facts affect a situation. Then we need to investigate so we can discover what the values of those facts are, what the complete truth is. 

Notice that a consequence results from the facts. We determine consequences only from what is known and assume that everything that needs to be known is indeed known and that associated data is accurately determined. For instance: in the notation of our subject, the triplet (R, G, B) is measured data. We know that (R,G,B) implies some color name, (R,G,B) → (color name) or "Measurements of R, G, B imply a specific color name. According to the truth table, we know that this implication is a fact, (255,0,0) → (RED). Here we write it in a formal argument to show how data and facts lead to a conclusion (consequence).

Contrary to what this implies, we absolutely do care that the data is accurate. We care what is contained in every implication. If the data is not correct, the implication is not correct. We cannot assume that an implication, however boldly stated, is true. Further, we cannot accept implications drawn from conclusions or facts without verifying the implications are true. This is fundamental to propositional logic. As explained in our readings, we might find that certain implications and facts are known and correct. But, if other implications and facts are not part of the investigation, then the assumption cannot be taken as valid

Review Propositional Logic.

 

3b. Classify sequences of logical statements as yielding true or false conclusions, given the sequence of statements and the values of individual statement parameters (arguments)

  • Explain the truth table for the conditional proposition, "if p then q". How can the truth of that statement be true if p is false and q is true?
  • If we propose that x → y, do we necessarily propose, by implication, that y → x? How so?
  • How does the clarity of a definition affect the truth of a proposition?

Propositional logic offers a means of considering statements and determining if they are true or false. Our readings make this appear to be an easy thing because the examples have clear definitions for the terms in the proposition. But, clarity is not always easy to achieve. For example, we might say true or false is easy to determine for the statement, "The number 5 is an odd number". But, as we apply propositional logic to practical applications, what does "odd" mean? If we limit the discussion to pure mathematics, we know the definition of "odd" and can say the statement is true. But, if we make the statement in the domain of temperature control and are expecting a reading of 5, then that number would not be odd at all, in the sense of the domain and expectations for readings. Basically, the domain of discussion matters a great deal.

We also have to think clearly about what is said and what is not said as we determine whether or not a statement is true. Consider the situation described in the readings regarding the statement, "if p then q". Its truth table is repeated here:

If p and q are both false, then the statement is true since p is supposed to directly lead to q. If p is true and q is false, for the same reason, we know the statement to be false. And so it is also true when p and q are both true. But, how is it that if p is false and q is true that the statement is true? There is nothing that says q cannot be true if p is false. Put another way, just because product p has not been delivered does not mean product q cannot be produced. In this situation, product p may already be on hand in sufficient quantity. As discussed in the readings, other factors may come into play when making a decision. As a lawyer once said to this writer, any reasonably intelligent person can understand what is said. It takes a lawyer to understand what is not said. The same is true in computer programming and other fields of work. Definition, clarity, situation, and logic matter.

Another area of confusion is that many people, colloquially, assume that if x implies y then y also implies x. This is false and causes much confusion because correlation does not mean causation. Another way of looking at it is to say that, because a blue bottle is a good bottle, all good bottles are blue. An assembly line may be set up to produce bottles that filter out certain wavelengths of light. Blue might be the best filter, and so bottles are accepted in that color. But, lesser shades of blue might also be sufficient filtering, and the difference may not be visible to the human eye. Thus, not all good bottles are necessarily blue, in the strict sense of the definition of "blue". 

Review Propositions and Logical Operators.

 

3c. Write a logic equation based on the natural-language statement of a problem

  • As statements become more complex, is there a way to summarize them so that the summary is logically equivalent to the original statement?
  • Why do we use specialized notation instead of just writing out what we want to say?
  • In what way do logic operations compare to arithmetic operations?

Like arithmetic operations, logic operations have strict definitions. Each symbol (notation) has a certain meaning that is exactly specified. The specification is exact so that there is no confusion with colloquial languages. And, arithmetic and logic symbols tie their meaning to certain other symbols. For example, in both systems, arithmetic and logic, we can write, "A + B". Without knowing which system we are speaking of, we cannot determine the meaning of the variables A, B, nor the operator +. In arithmetic, we know that A, B refer to numbers and that the operator means we are to determine the new value when A, B are added. Numeric addition is exactly specified and we know how to carry out that operation. In logic, "A + B" means we are to take the OR of A,B. Since we are in the logic system, not the arithmetic system, we know that A, B are binary values, {0, 1}, {false, true). We know how to carry out the OR operation since OR has a precise definition. (Of course, there are other systems of logic that are not binary but discrete multivalued systems. Still, in our sense of the word, "logic" refers to binary).

Because of the exact specification of logic operations and variables, we can often translate colloquial languages into equations, if we can overcome the vagueness of colloquial words. This is important because it allows understanding to be achieved where there is only confusion. At times too, simplification can be achieved that enables more effective and efficient achievement in practical situations. Consider this situation: 

Reviewing our complex project plan, our goal will be achieved if we reach milestones X and Y; or if we reach milestones Y and Z, while at the same time milestones Y or Z are reached.

Since complexity can lead to confusion, let's try to simplify things. Using the syntax (notation) of logic equations, the colloquial statement could be written as G = (X and Y) or ((Y and Z) and (Y or Z)). 

Sometimes it is the case that complex logical statements can be summarized into an equivalent form. This leads to better understanding and easier transition to practical application. Here is an example:

Reviewing our project plan, our goal will be achieved if we reach milestones X and Y; or if we reach milestones Y and Z, while at the same time milestones Y or Z are reached.

Complexity can lead to confusion. Let's try to simplify things. Using the syntax of logic equations (logic notation), this could be written as G = (X and Y) or ((Y and Z) and (Y or Z)). Using a simplified version of the equation, we get G = XY + (YZ(Y + Z)). By the rules of manipulating logic equations, we can then write: XY + YYZ + YZZ, which becomes XY + YZ + YZ, which we easily reduce to XY + YZ, which reduces further to Y(X + Z). Looking back at the original colloquial statement, we see that if we accomplish milestone Y and either milestone X or Z, then the goal is accomplished. This reduces the complexity of the original project plan and improves our understanding of what must be accomplished. Such an approach can also reduce cost in various categories. 

Objective logical thought can help transition plans to accomplishment. The same is true of transitioning theory to reality.

Review:

 

3d. Calculate logical expressions of multiple variables assigned values according to a given circumstance

  • Why is it important for logical laws to be proposed and proven?
  • What is the role of truth tables in the context of logical laws?
  • Describe the importance of investigation.

We bring our study from pieces to a whole in this learning outcome. Laws of logic are proposed and proven so that it is not necessary to start from scratch when examining a complex statement or proving a more involved basic law. Truth tables can be a guide to this effort since they allow us to chart basic facts and show how they combine to ultimately yield true or false for the final statement. This is possible because facts, in binary logic (what we are studying), can only be true or false. Ultimately, complicated laws of logic are constructed from basic building blocks, less complex laws, and those from statements that are completely true or completely false.

Investigation is essential to the application of the laws of logic. Every law of logic depends on certain facts being true or false. But, is the proposed fact actually true, or is it actually false? Does a shade of colloquial meaning matter? For example, if we say that the color RED is composed of 255 units of RED visual frequency and 0 of any other frequency, (R,G,B) = (255,0,0), Is it still RED if (R,G,B) = (254,0,1)? Technically, the answer is no. But, is it RED enough to be called RED for the purpose at hand? That has to be determined via investigation and is not a matter of personal opinion. 

Review:

 

Unit 3 Vocabulary

This vocabulary list includes terms you will need to know to successfully complete the final exam.

  • assumption
  • binary logic
  • causation
  • conclusion
  • consequence
  • correlation
  • equations 
  • equivalent form
  • formal argument 
  • implication
  • logic operations
  • proposition
  • propositional logic 
  • simplification
  • syntax
  • truth table
  • valid