Introduction to Logical Connectives

What is a Proposition?

In mathematics, we build arguments out of declarative sentences. A proposition is a statement that can be definitively said to be either true or false, but not both. This principle is known as the Law of the Excluded Middle.

For example:

• "The integer 7 is odd." (This is a true proposition).
• "1 + 1 = 3." (This is a false proposition).
• "x > 5." (This is a proposition, but its truth value depends on the value of x).

Statements that are not propositions include questions ("What time is it?"), commands ("Solve for x."), or subjective opinions ("Mathematics is beautiful.").

To learn more about what qualifies as a proposition, please watch the following short video clip.

The Five Logical Connectives

Simple propositions can be combined into more complex compound propositions using logical connectives. There are five fundamental connectives that we will use throughout this course.

To begin, let's establish the formal names and symbols for these connectives. The following reading provides a concise summary.

Let's summarize these connectives. Let $p$ and $q$ be two propositions.

1. Negation (NOT)

   • Symbol: $\neg$
   • Usage: $\neg p$ ("not p")
   • Meaning: $\neg p$ is true if and only if $p$ is false.

2. Conjunction (AND)

   • Symbol: $\wedge$
   • Usage: $p\wedge q$ ("p and q")
   • Meaning: $p\wedge q$ is true if and only if both $p$ and $q$ are true.

3. Disjunction (OR)

   • Symbol: $\vee$
   • Usage: $p\vee q$ ("p or q")
   • Meaning: $p\vee q$ is true if at least one of $p$ or $q$ is true. This is an inclusive "or".

4. Conditional (IMPLIES)

   • Symbol: $\to$
   • Usage: $p\to q$ ("if p, then q" or "p implies q")
   • Meaning: $p\to q$ is false only when $p$ is true and $q$ is false. In all other cases, it is true. The proposition $p$ is called the antecedent and $q$ is the consequent.

5. Biconditional (IF AND ONLY IF)

   • Symbol: $\leftrightarrow$
   • Usage: $p\leftrightarrow q$ ("p if and only if q", often abbreviated "p iff q")
   • Meaning: $p\leftrightarrow q$ is true if and only if $p$ and $q$ have the same truth value (both true or both false). It is equivalent to $(p\to q)\wedge (q\to p)$.

The image below summarizes the behavior of these connectives. We will delve into the construction and use of such "truth tables" in the next lesson, but for now, you can use it as a reference for how each connective operates.

Understanding the Conditional Statement

The conditional connective, $\to$, is often the most counter-intuitive, particularly the cases where the antecedent ($p$) is false. Why is "if false, then true" and "if false, then false" both considered true implications? The key is to think of it as a promise. The statement $p\to q$ only makes a promise about what happens if $p$ is true. If $p$ is false, the promise is not broken, regardless of the status of $q$.

The following video provides an excellent, multi-faceted explanation to build a solid intuition for the conditional.

Forming Compound Statements

Now that we have the building blocks, we can construct more complex statements. Just as in programming, logic has syntactic rules. We use parentheses to group statements and ensure there is no ambiguity in the order of operations. The main connective is the one that connects the largest components of the formula.

For example, in the statement $\neg (p\vee q)\to r$, the main connective is $\to$. It connects the compound proposition $\neg (p\vee q)$ to the simple proposition $r$.

The following video segment discusses these rules for creating "well-formed formulas."

Practice: Translating from English to Logic

Let's practice translating a few sentences into the language of propositional logic. Define your own proposition letters (e.g., let $R$ be "It is raining").

1. If the program is running and there are no errors, then the task will complete.
2. The system is not in a secure state, or the alarm is not active.
3. You can pay with a credit card or with cash, but not both.

Solutions

1. Let $P$ be "The program is running," $E$ be "There are errors," and $T$ be "The task will complete."
   The statement translates to: $(P\wedge \neg E)\to T$.

2. Let $S$ be "The system is in a secure state," and $A$ be "The alarm is active."
   The statement translates to: $\neg S\vee \neg A$.

3. Let $C$ be "You can pay with a credit card," and $H$ be "You can pay with cash."
   The "or" part is $C\vee H$. The "but not both" part means "and not (C and H)", which is $\wedge \neg (C\wedge H)$.
   Putting it all together: $(C\vee H)\wedge \neg (C\wedge H)$. This is the logical structure of an exclusive or.

Conclusion

In this introductory lesson, we have established the fundamental components of propositional logic. You have learned to:

• Identify a proposition as a statement that is either true or false.
• Recognize the five logical connectives: negation ($\neg$), conjunction ($\wedge$), disjunction ($\vee$), conditional ($\to$), and biconditional ($\leftrightarrow$).
• Translate simple English sentences into compound propositions using these connectives and parentheses to ensure clarity.

This is the essential vocabulary and grammar of mathematical language. In our next lesson, we will build upon this foundation by exploring truth tables. This powerful tool will allow us to systematically determine the truth value of any compound statement, no matter how complex, and to establish logical equivalences—a critical skill for constructing rigorous proofs.