Understanding Discrete Math and Logic

Introduction to Logic

Logic forms the foundation of mathematical reasoning and clear thinking. When you understand logic, you can distinguish valid arguments from invalid ones and build stronger mathematical proofs.

The rules of logic help us understand statements like "There exists an integer that is not the sum of two squares" or mathematical formulas like "For every positive integer n, the sum of positive integers not exceeding n is n$n+1$/2".

In computer science, logic isn't just theoretical—it's practical. Whether you're designing circuits, programming algorithms, or debugging code, logical thinking is essential to your success.

Remember: Logic isn't just about being "logical" in everyday speech—it's a precise mathematical system with specific rules and applications.

The Circuit

When analyzing electrical circuits, we often make logical conjectures about how they function. Let's examine some statements about a circuit with lamps L1-L6:

1. If lamp L4 shines, then lamp L1 shines too.
2. If L2 shines then L5 shines too.
3. If L5 doesn't shine, then L2 doesn't shine either.
4. If L5 shines, then L2 shines.
5. If L2 doesn't shine, then L5 doesn't shine.
6. If L1 or L6 shines then L3 or L4 shines.
7. If L1 and L3 then L2 and not L5.

These statements demonstrate how logic helps us understand relationships between components in a system. Some statements may seem similar but have different logical meanings.

Try this: Pick any two statements from above and determine if they're logically equivalent by writing out what happens in all possible scenarios.

Proposition

A proposition is a declarative sentence that is either true or false, but not both. This definition is crucial because it forms the foundation of logical reasoning.

Examples of propositions include:

• "Washington, D.C., is the capital of the United States of America." (True)
• "Toronto is the capital of Canada." (False)
• "1 + 1 = 2." (True)
• "2 + 2 = 3." (False)

Not everything is a proposition. Questions like "What time is it?" or commands like "Read this carefully" are not propositions because they don't declare facts that can be judged true or false.

Mathematical expressions with variables (like "x + 1 = 2" or "x + y = z") are not propositions by themselves because their truth value depends on the values assigned to the variables.

We use letters (typically p, q, r, s) to represent propositions, similar to how we use letters for variables in algebra. The truth value is denoted by T (or 1) for true propositions and F (or 0) for false ones.

Propositional Calculus

We have 4 basic logic operators used in the propositional calculus.

Based on them we can validate other propositions called Compound propositions by using the Truth Tables.

1. The negation: (no $P$), which reverses the truth value of a proposition
2. The disjunction: ($P$ or $Q$), which combines propositions with "or"
3. The conjunction: ($Q$ and $R$), which combines propositions with "and"
4. The implication: ($P \Rightarrow Q$ or $R$), which shows logical consequence

These operators allow us to build complex logical expressions and analyze their truth values systematically. In computer science, these operators translate directly to operations in Boolean logic, which forms the basis of digital circuit design and programming.

Pro tip: When working with truth tables, remember that with n propositions, you'll need to examine 2^n possible combinations of truth values.

The Negation

The negation of a proposition A is "no A," denoted $\bar{A}$ or $\neg A$.

It is False when A is True and True when A is False. This logic operator can be summarized in the following Truth table:

The negation is a fundamental operation that simply flips the truth value of a proposition. It's similar to the NOT gate in digital electronics.

An interesting property worth noting is that the proposition $\neg(\neg A)$ has the same truth table as A. In other words, negating a negation brings you back to the original proposition.

This operation is critical because it allows us to express the opposite of any logical statement, which is essential for constructing complex logical arguments and proofs.

The Conjunction

The proposition "A and B" is True when A and B are simultaneously True. It is False elsewhere.

The conjunction has important properties:

• Commutativity: The assertions "A and B" and "B and A" have the same truth table.
• Associativity: The assertions "A and (B and C)" and "(A and B) and C" have the same truth table.

These properties allow us to rearrange conjunctions without changing their meaning, which is useful when simplifying complex logical expressions or constructing proofs.

In computing: Conjunction is equivalent to the AND gate in digital circuits, and the && operator in many programming languages.

The Disjunction

The proposition "A or B" is False when A and B are simultaneously False.

It is True if one of them or both of them are True.

The disjunction has key properties similar to conjunction:

• It's commutative: "A or B" equals "B or A"
• It's associative: "A or (B or C)" equals "(A or B) or C"

Two important logical equivalences worth remembering:

1. The assertion "no(A or B)" has the same truth table as "(no A) and (no B)"
2. The assertion "no(A and B)" has the same truth table as "(no A) or (no B)"

These are known as De Morgan's laws, which are extremely useful in simplifying logical expressions.

The Implication

"$A \implies B$", is read "if $A$, then $B$" "$A$ implies $B$" "for $B$, it is sufficient $A$" "for $A$, it needs $B$" "$A$ is a sufficient condition for $B$" "$B$ is a necessarily condition for $A$".

Its Truth Table is:

Attention: By definition, "A ⇒ B" is True when A is False! This often confuses students, but it's crucial to understanding implication.

An important equivalence: "A ⇒ B" has the same truth table as "(not A) or B".

Critical insight: The logical implication is not the same as causality in the real world. A statement like "If 1+1=2, then x^n + y^n = z^n has no integer solutions for n≥3" is logically true, even though there's no causal relationship.

Converse, Contrapositive, and Inverse

When working with an implication $(P): A \implies B$, we can derive related implications:

The converse of $(P)$ is: $(P_r): B \implies A$

• The truth of $(P)$ and $(P_r)$ are independent.

The contrapositive of $(P)$ is: $(P_c): (\neg B) \implies (\neg A)$

• The propositions $(P)$ and $(P_c)$ have the same truth table.

The negation of $(P)$ is: $(\neg P): A \text{ and } (\neg B)$

The contrapositive is particularly useful in mathematics. When proving "if A then B," we can instead prove "if not B then not A," which is often easier.

This relationship between an implication and its contrapositive provides a powerful alternative approach to mathematical proofs.

The Equivalence

"$A \iff B$" can be read as "$A$ is equivalent to $B$" "$A$ if and only if $B$" "$A$ is a necessarily and sufficient condition to $B$"

Its truth table is the same as "$(A \implies B)$ and $(B \implies A)$". This means:

Conclusion: "$A \iff B$" is True means that A and B have the same truth value.

Unlike implication, equivalence represents a stronger relationship between propositions - they must both be true together or both be false together.

Equivalence is not generally associative. That is, "$(A \iff B) \iff C$" doesn't have the same truth table as "$(A \iff B)$ and $(B \iff C)$".

In mathematical proofs, a sequence of equivalences is often used when solving systems of equations because each step maintains the same solution set as the original.