Basic Logical Operators: Negation and Conjunction

TL;DR

Logical operators like negation and conjunction are fundamental tools for building complex statements in discrete mathematics. Negation flips the truth value of a statement, while conjunction combines two statements, being true only if both are true. Understanding these helps you analyze and construct precise logical arguments and expressions.

1. The Mental Model

Think of logical operators as switches you use to control the truth of a statement. Negation is like an "OFF/ON" flip, reversing the switch's current position. Conjunction is like two "ON" switches linked together: both must be on for the light to turn on.

2. The Core Material

In discrete math, we often work with propositions, which are declarative sentences that are either true or false, but not both. For example, "The sky is blue" is a proposition. "Is the sky blue?" is not.

We use logical operators to combine or modify these propositions, creating more complex statements. Let's dive into two basic ones: negation and conjunction.

Negation (NOT)

Negation is the simplest operator. It takes a single proposition and reverses its truth value. If a statement P is true, its negation not P is false. If P is false, not P is true.

We often represent "not P" symbolically as ¬P or ~P.

Example:
* Let P be the proposition "It is raining."
* If P is true (it is indeed raining), then ¬P ("It is not raining") is false.
* If P is false (it is not raining), then ¬P ("It is not raining") is true.

A truth table summarizes this:

Conjunction (AND)

Conjunction combines two propositions, let's say P and Q, into a new proposition "P and Q". This new proposition is only true if both P and Q are true. If either P or Q (or both) are false, then "P and Q" is false.

We represent "P and Q" symbolically as P ∧ Q.

Example:
* Let P be "It is sunny."
* Let Q be "It is warm."
* P ∧ Q means "It is sunny and it is warm."

When is "It is sunny and it is warm" true?
* Only when it's sunny AND it's warm.
* If it's sunny but not warm, the statement is false.
* If it's warm but not sunny, the statement is false.
* If it's neither sunny nor warm, the statement is false.

Here's its truth table:

Combining Operators

You can combine these operators to form more complex statements. The order of operations generally dictates that negation is applied before conjunction (unless parentheses specify otherwise).

Let's visualize how truth values propagate through these operations:

graph TD
    A["Statement P"] --> B{{"Is P True?"}}
    B -- "Yes" --> C["¬P is False"]
    B -- "No" --> D["¬P is True"]

    E["Statement Q"] --> F{{"Is Q True?"}}

    G["P ∧ Q is True"]
    H["P ∧ Q is False"]

    B -- "Yes" --> I{{"Is Q True?"}}
    I -- "Yes" --> G
    I -- "No" --> H

    B -- "No" --> H

3. Worked Example

Let's work with actual statements and assign truth values.

Consider these propositions:
* P: "The number 5 is even." (This is False)
* Q: "The number 7 is prime." (This is True)
* R: "The sky is green." (This is False)

Now let's evaluate some combined statements:

1. ¬P

   • Since P is "The number 5 is even" (False), then ¬P is "The number 5 is not even" or "The number 5 is odd".
   • This statement is True.

2. P ∧ Q

   • P is False, Q is True.
   • "The number 5 is even AND the number 7 is prime."
   • According to the conjunction rule, for P ∧ Q to be true, both P and Q must be true. Since P is false, P ∧ Q is False.

3. ¬Q ∧ R

   • First, let's find ¬Q. Since Q is "The number 7 is prime" (True), ¬Q is "The number 7 is not prime" (False).
   • Now we have ¬Q (False) and R (False).
   • So, we're evaluating "The number 7 is not prime AND the sky is green."
   • Since both parts are false, their conjunction ¬Q ∧ R is False.

4. Key Takeaways

• A proposition is a statement that is definitively either true or false.
• Negation (¬ or ~) reverses the truth value of a single proposition.
• Conjunction (∧) combines two propositions; it's true only if both propositions are true.
• Truth tables are essential tools for visualizing and determining the truth values of logical expressions.
• Understanding these basics is crucial for building more complex logical arguments and proofs.
• You can combine operators; negation usually takes precedence over conjunction.

Common Mistakes to Avoid:
- Confusing "and" with "or" (another operator we'll cover later) – "and" is much stricter.
- Incorrectly negating a statement, especially one with multiple parts. Remember it flips the truth of the entire statement.
- Assuming a complex statement is true just because one of its parts is true when using conjunction.
- Forgetting to assign a clear truth value (True/False) to initial propositions before combining them.

5. Now Try It

Take the following propositions and determine the truth value of the combined statements:

• A: "All cats have wings." (False)
• B: "2 + 2 = 4." (True)
• C: "Paris is the capital of France." (True)

1. Evaluate ¬A.
2. Evaluate A ∧ B.
3. Evaluate ¬B ∧ C.
4. Evaluate ¬(A ∧ B) (Negate the entire result of A AND B).

What success looks like: You should be able to confidently state whether each of the four resulting propositions is True or False, and explain why using the definitions of negation and conjunction.