Logic - Review

Definition

For two valued logic (2VL), a proposition is a statement that can be either true (T) or false (F) but not both. Consider the following:

• Major is HCI
• Age less than 25

These statements are examples of propositions. If John is an HCI major who is 30 years of age then the truth value of these propositions may be determined for John.

Logical Operators

Given two (or more) propositions, we may combine them by using the following logical operators. Let P and Q represent two propositions then:

1. Conjunction (AND):

   P AND Q is true when, and only when, both P, Q are true. We may construct a truth table thus:

                 P   |  Q  |  P AND Q
               ------------------------
                 T   |  T  |     T  
                 T   |  F  |     F  
                 F   |  T  |     F  
                 F   |  F  |     F  
                 
   

   Thus, for the "John" example above, the compound proposition:

   Major is HCI AND Age less than 25

   is F since John is 30 years of age and so the proposition "Age less than 25" is F.

2. Disjunction (OR):

   P OR Q is true when at least one of P, Q is true. It is false only when both P, Q are false. We may construct a truth table thus:

                 P   |  Q  |  P OR Q
               -----------------------
                 T   |  T  |     T  
                 T   |  F  |     T  
                 F   |  T  |     T  
                 F   |  F  |     F  
                 
   

   Thus, for the "John" example above, the compound proposition:

   Major is HCI OR Age less than 25

   is T since John is an HCI major.

3. Negation (NOT):

   NOT P has the opposite truth value than P. If P is true then NOT P is false and if P is false then NOT P is true. We may construct a truth table thus:

                 P   | NOT P 
               --------------
                 T   |   F  
                 F   |   T 
                 
   

   Thus, for the "John" example above, the proposition:

   NOT (Major is HCI)

   is F since John is an HCI major.

Precedence

To evaluate the truth value of a compound proposition consisting of several propositions connected by logical operators we must consider the "precedence" rules for logical operators.

1. NOT, then AND, then OR
2. From left to right when multiple operators at the same precedence level.
3. Parentheses may be used to override the rules 1 and 2 above.

Example:

Consider the following compound proposition involving propositions P, Q, R.

1. P AND NOTQ AND R

   ...is equivalent to:

   (P AND (NOTQ)) AND R

2. P OR NOTQ AND R

   ...is equivalent to:

   P OR ((NOTQ) AND R)

3. NOT P AND NOT Q

   ...is equivalent to:

   (NOT P) AND (NOT Q)

DeMorgans Laws

DeMorgans Laws address the truth value of a compound proposition which involves the negation of a conjunction or the negation of a disjunction. Consider the negation of the following compound proposition involving propositions P, Q.

1. NOT (P AND Q)

   ...is equivalent to:

   (NOT P) OR (NOT Q)

2. NOT (P OR Q)

   ...is equivalent to:

   (NOT P) AND (NOT Q)

We may easily verify this by constructing truth tables.