Comprehensive Study Guide for Logic and Discrete Structures

Learning Objectives in Logic and Computer Science

Upon completion of this module, students will demonstrate the ability to solve logical truth tables for elaborate statements involving the logical operators AND, OR, NOT, and implication. The curriculum covers obtaining logical statements through logical equivalence rules and the construction of logical statements derived from real-world problems. Students learn to determine the validity of logical arguments using inference, equivalence rules, and relations within logical equivalences. Further objectives include the proper identification of predicates and quantifiers, alongside understanding the critical distinctions between propositional logic and predicate logic. The module also covers the Lewis Carrol argument and relates the field of logic to practical computer science problems, specifically in the design of automobile safety devices utilizing digital logic and algorithms.

Logic is a crucial field that aids computer engineers and scientists in ordering and structuring their thinking in a logical manner. This logical structure is essential for implementing efficient algorithms and tasks in high-level programming languages such as $C++$ or $Java$.

Logical Statements and Basic Operators

Logical statements are phrases that possess a truth value, meaning they can be either true or false. These can be simple sentences, such as "I feel cold," "I am hungry," or "the seat belt is connected." They can also be elaborate or composed sentences consisting of simple statements joined by logic operators. Common symbols for representing these statements include letters such as $A, B, p$, or $q$.

The NOT operator, also known as negation, complement, or the opposed operator, is symbolized by $-, ',$ or $\neg$. The result of a statement using the NOT operator is false if the original statement $p$ is true, and conversely, it is true if the original statement is false. An example of this is the statement $p$, "I feel warm," which becomes $\neg p$, "I do not feel warm (I feel cold)" upon negation.

The AND operator is referred to as intersection, conjunction, or the logic product of two statements $p$ and $q$. It is symbolized by $*$ or \bwedge. The truth table for conjunction indicates that the result is true if and only if both statements $p$ and $q$ are true. For example, if statement $A$ is "I feel warm," $B$ is "I have eaten," and $C$ is "I am happy," then $C$ is composed of A \bwedge B, meaning "I am happy if I feel warm and I have eaten."

The OR operator is also known as union, disjunction, or the logic sum of two statements. It is symbolized by $+$ or \bvee. The result of an OR operation is false only if both statements are false. For example, if statement $D$ is "the sun is warming me," $E$ is "I have a heater stove," and $A$ is "I feel warm," then $A$ is composed of D \bvee E, or "I feel warm if the sun warms me or if I have a heater stove."

Advanced Logical Operators: Implication, XOR, and Equivalence

The Implication operator is symbolized by \rightarrow, \bRightarrow, or $\rightarrow$. If $p$ and $q$ are statements, the implication $p \rightarrow q$ is true in all cases except when $p$ is true and $q$ is false. In this relationship, $p$ is known as the antecedent and $q$ is the consequent. A practical example is the "honest politician" scenario: "If I win the election ($p$), then I will lower your taxes ($q$)." If the politician wins ($p = T$) and lowers taxes ($q = T$), they are honest. If they win ($p = T$) and do not lower taxes ($q = F$), they are dishonest. If they lose ($p = F$), they are considered honest regardless of whether taxes are lowered, as they did not have the power to write the law.

Another implication example involves academic grades: "If you earn $90\%$ of the possible points in $CS\,313K$, then you will get an $A$." Here, $P$ is earning the points and $Q$ is getting the $A$. The statement $P \rightarrow Q$ is true as long as the commitment is honored. If $P$ is false, the instructor has not broken a promise regardless of whether the student gets an $A$ or not, so the implication remains true.

XOR, or the Exclusive-OR operator, is symbolized by \boplus. The result of an XOR operation is true only if the propositions $p$ and $q$ have different logic states. For instance, a heterosexual couple ($C$) is only formed of a man ($p$) and a woman ($q$), or vice versa, expressed as C = p \boplus q.

The Equivalence operator is symbolized by \bequiv, \bleftrightarrow, \bleftrightarrow, or \bLeftrightarrow. Two statements are equivalent if they share the same logic state. This can also be interpreted as a double implication between two statements.

Truth Table Construction and Simplification Rules

Constructing truth tables for complex statements requires a step-by-step approach. For the statement (A \bvee B') \rightarrow (A \bvee B)', one must first determine the truth values for $A$ and $B$. Next, determine $B'$, then (A \bvee B'), followed by (A \bvee B), and then the negation (A \bvee B)'. Finally, the implication of the two components yields the final result. Other examples include validating [A \bvee (A \bwedge B)] \rightarrow (A \bvee B) and (p \bwedge q') \rightarrow (p \bwedge q).

Simplification of logical statements uses specific equivalence rules. The rules include Commutative, Associative, Idempotent, Implication, DeMorgan’s, Absorption, Identity, Distributive, and Domination rules. To simplify (A' \bvee (B' \bvee A')) \rightarrow B:

1. Commutative rule: (A' \bvee (A' \bvee B')) \rightarrow B

2. Associative rule: ((A' \bvee A') \bvee B') \rightarrow B

3. Idempotent rule: (A' \bvee B') \rightarrow B

4. Implication rule: (A' \bvee B')' \bvee B

5. DeMorgan rule: (A \bwedge B) \bvee B

6. Absorption rule: $B$ is the final simplified solution.

Alternatively, if the absorption rule is not used, the Identity, Distributive, and Domination rules can lead to the same result. For instance, (A \bwedge B) \bvee B can be treated as (A \bwedge B) \bvee (T \bwedge B), then simplified via the Distributive rule to (A \bvee T) \bwedge B, then to (T) \bwedge B via Domination, and finally to $B$.

Logical Arguments and Predicate Logic

An argument is defined as a sequence of propositions ($p$) joined by AND operators, known collectively as the premise. This premise acts as the antecedent of an implication, while the consequent is a final proposition ($q$) called the conclusion. A valid argument is a tautology, written as (p_1 \bwedge p_2 \bwedge p_3 \bwedge \bdots \bwedge p_n) \rightarrow q. Formal logic uses derivation rules to solve these arguments without necessarily computing a full truth table.

To determine if an argument is valid, one must analyze the logical flow. Consider the exercise: "If I am wealthy ($R$), then I am happy ($H$). I am happy. Therefore, I am wealthy." Represented logically: [(R \rightarrow H) \bwedge H] \rightarrow R.

1. Apply implication: [(R' \bvee H) \bwedge H] \rightarrow R

2. Apply implication again: [(R' \bvee H) \bwedge H]' \bvee R

3. DeMorgan: [(R' \bvee H)' \bvee H'] \bvee R

4. DeMorgan and double negation: [(R \bwedge H') \bvee H'] \bvee R

5. Associative: (R \bwedge H') \bvee [H' \bvee R]

6. Distributive/Commutative: (R \bvee (R \bvee H')) \bwedge (H' \bvee (R \bvee H'))

7. Idempotent: (R \bvee H') \bwedge (R \bvee H')

8. Final result: R \bvee H'

Because the final result is not a tautology, the argument is invalid. This can be verified with a truth table, which would show that the statement is not true for all possible logic states.