Discrete Mathematics: Logic Lecture 1 - Statements, Negation, Conjunction, and Disjunction

Introduction to Discrete Mathematics

• Discrete Mathematics is the study of the mathematical properties of sets, systems, and structures that possess countably many elements.

• Key areas of study include:

  • Relations

  • Enumerative combinatorics

  • Algorithms

  • Graph theory

  • And more

• It has wide-ranging applications in various fields:

  • Computer Science

  • Engineering

  • Communications

  • Transportation

  • And other areas requiring the analysis of discrete data and structures.

Statements and Truth Values

• Categories of Sentences: Sentences can be categorized into four types:

  • Declarative

  • Interrogative (questions)

  • Imperative (commands)

  • Exclamatory

• In logic, the primary focus is on declarative sentences.

• Definition 1: Statement

  • A statement is defined as a declarative sentence that is definitively either true or false, but cannot be both simultaneously.

• Truth Value:

  • Every statement possesses a truth value, which is either True ($T$) or False ($F$).

• Examples of determining truth values:

  • $1/2 + 1/3 = 5/6$ ($T$)

  • $2/3 + 1/5 = 1/2$ ($F$)

  • $\sqrt{3} \ne 1.732$ ($T$ - since $\sqrt{3}$ is irrational and $1.732$ is a rational approximation)

  • $\pi = 22/7$ ($F$ - $\pi$ is irrational, $22/7$ is a rational approximation)

  • $(x+a)^2 = x^2 + 2ax + a^2$ (This is an identity, always true for any $x, a$)

  • $\sqrt{(-2)^2} = -2$ ($F$ - $\sqrt{(-2)^2} = \sqrt{4} = 2$)

  • $2x + 1 = 10$ (This is an open sentence, not a statement by itself as its truth value depends on $x$)

Open Sentences

• Definition 2: Open Sentence

  • An open sentence is a declarative sentence that contains one or more variables.

  • Its truth or falseness is contingent upon the specific values assigned to these variables.

• Example: $P(a, b) : a + b$ is odd, where $a$ and $b$ are integers.

  • If $a=1, b=2$, then $1+2=3$ is odd ($T$).

  • If $a=2, b=4$, then $2+4=6$ is odd ($F$).

• Problem Objective: When dealing with open sentences, the objective typically is to identify all variable values for which the sentence evaluates to true (or false).

Logical Connectives and Compound Statements

• Statements can be combined to form new, more complex statements.

• The fundamental challenge is to establish rules for efficiently computing the truth value of these new, compound statements.

• Truth tables are an essential tool for this purpose.

Negation

• Definition 3: Negation ($\sim P$)

  • The negation of a statement $P$ is the statement "not $P$", denoted by $\sim P$ (other notations may also be used).

  • The negation operator acts on a single statement, $P$, to produce a new statement with the opposite truth value.

• Truth Table for Negation:

  • If $P$ is True, $\sim P$ is False.

  • If $P$ is False, $\sim P$ is True.
    \begin{array}{|c|c|}
    \hline
    P & \sim P \
    \hline
    T & F \
    \hline
    F & T \
    \hline
    \end{array}

• Application to Open Sentences: The negation operator can also be applied to open sentences.

  • If P : x + 3 > 0, then $\sim P : x + 3 \le 0$

Conjunction

• Definition 4: Conjunction ($P \land Q$)

  • For two statements $P$ and $Q$, their conjunction is the statement "$P$ and $Q$", denoted by $P \land Q$.

  • The conjunction operator acts on a pair of statements, $P$ and $Q$, and produces a single statement that is true only when both $P$ and $Q$ are true.

• Truth Table for Conjunction:
  \begin{array}{|c|c|c|}
  \hline
  P & Q & P \land Q \
  \hline
  T & T & T \
  \hline
  T & F & F \
  \hline
  F & T & F \
  \hline
  F & F & F \
  \hline
  \end{array}

• Application to Open Sentences: Conjunction can also be applied to open sentences.

Disjunction

• Definition 5: Disjunction ($P \lor Q$)

  • For two statements $P$ and $Q$, their disjunction is the statement "$P$ or $Q$", denoted by $P \lor Q$.

  • The disjunction operator acts on a pair of statements, $P$ and $Q$, and produces a single statement that is true only when at least one of $P$ or $Q$ is true (this is known as inclusive or).

• Truth Table for Disjunction:
  \begin{array}{|c|c|c|}
  \hline
  P & Q & P \lor Q \
  \hline
  T & T & T \
  \hline
  T & F & T \
  \hline
  F & T & T \
  \hline
  F & F & F \
  \hline
  \end{array}

• Application to Open Sentences: Disjunction can also be applied to open sentences.

Exclusive OR

• The phrase "$P$ or $Q$" can sometimes imply that exactly one of $P$ or $Q$ must be true. This is distinct from inclusive or.

• If it is intended that both $P$ and $Q$ cannot be true simultaneously, this is called exclusive or.

• Definition 6: Exclusive OR ($P \oplus Q$)

  • For two statements $P$ and $Q$, the exclusive or of $P$ and $Q$ is a statement that is true when exactly one of $P$ or $Q$ is true.

• Truth Table for Exclusive OR:
  \begin{array}{|c|c|c|}
  \hline
  P & Q & P \oplus Q \
  \hline
  T & T & F \
  \hline
  T & F & T \
  \hline
  F & T & T \
  \hline
  F & F & F \
  \hline
  \end{array}

• Application to Open Sentences: Exclusive or can also be applied to open sentences.

Compound Statements and Logical Equivalence

• The symbols $\sim, \land, \lor, \oplus$ are known as logical connectives.

• Definition 7: Compound Statement

  • A compound statement is a statement formed by combining one or more simple statements using one or more logical connectives.

  • Compound statements can become very intricate.

  • A key interest in logic is simplifying compound statements as much as possible.

• Definition 8: Logical Equivalence ($R \equiv S$)

  • Two compound statements, $R$ and $S$, constructed from the same component statements, are considered logically equivalent if they consistently have the same truth value for every possible combination of truth values of their component statements.

  • This is denoted as $R \equiv S$.

  • If their truth values differ for even one combination, they are not logically equivalent, written as $R \not\equiv S$.

Laws of Logic

Commutative Laws

• Theorem 1: Commutative Laws

  • For any two statements $P$ and $Q$:

    • \begin{equation}P \land Q \equiv Q \land P\end{equation}

    • \begin{equation}P \lor Q \equiv Q \lor P\end{equation}

• Proof Idea: These laws can be proven by constructing truth tables for both sides of the equivalence and demonstrating that their final truth value columns are identical.

• Application to Open Sentences: These laws also apply to open sentences.

  • Example: "$n^2 + 4n$ is even or n^2 - 9 < 0" is logically equivalent to "n^2 - 9 < 0 or $n^2 + 4n$ is even".

De Morgan's Laws

• Theorem 2: De Morgan's Laws

  • For any two statements $P$ and $Q$, the following equivalences hold:

    • (a) \begin{equation}\sim (P \lor Q) \equiv (\sim P) \land (\sim Q)\end{equation}

    • (b) \begin{equation}\sim (P \land Q) \equiv (\sim P) \lor (\sim Q)\end{equation}

• Proof of (a) using Truth Table: \begin{array}{|c|c|c|c|c|c|c|} \hline P & Q & P \lor Q & \sim (P \lor Q) & \sim P & \sim Q & (\sim P) \land (\sim Q) \ \hline T & T & T & F & F & F & F \ \hline T & F & T & F & F & T & F \ \hline F & T & T & F & T & F & F \ \hline F & F & F & T & T & T & T \ \hline \end{array}

  • The columns for $\sim (P \lor Q)$ and $( \sim P) \land (\sim Q)$ are identical, thus proving their logical equivalence.

• De Morgan's Laws for Open Sentences: These laws similarly apply to open sentences.

  • Let $P: a$ is odd, $Q: b$ is odd.

    1. $P \lor Q$: "$a$ is odd or $b$ is odd."

    2. $\sim (P \lor Q)$: "It is not the case that ( $a$ is odd or $b$ is odd )" or "Neither $a$ is odd, nor $b$ is odd."

    3. Restate $\sim (P \lor Q)$ using De Morgan's Law (a): $( \sim P) \land (\sim Q)$: "$a$ is not odd (i.e., $a$ is even) and $b$ is not odd (i.e., $b$ is even)".

• Theorem 3: Double Negation Law

  • For every statement $P$, \begin{equation}P \equiv \sim (\sim P)\end{equation}. A statement is logically equivalent to the negation of its negation.

Exercise: Proof using De Morgan's Laws

• Problem: Prove that $\sim (P \lor (\sim Q)) \equiv (\sim P) \land Q$

• Hint: Apply an appropriate De Morgan's Law by treating $\sim Q$ as a single statement (e.g., let $R = \sim Q$).

  • Then $\sim (P \lor R) \equiv (\sim P) \land (\sim R)$

  • Substituting back $R = \sim Q$, we get $( \sim P) \land (\sim (\sim Q))$

  • By the Double Negation Law ($\sim (\sim Q) \equiv Q$), this simplifies to $( \sim P) \land Q$.

  • Thus, $\sim (P \lor (\sim Q)) \equiv (\sim P) \land Q$ is proven.

Associative and Distributive Laws

• Theorem 4: Associative and Distributive Laws

  • Let $P, Q$, and $R$ be three statements.

  • (a) Associative Laws:

    • \begin{equation}P \lor (Q \lor R) \equiv (P \lor Q) \lor R\end{equation}

    • \begin{equation}P \land (Q \land R) \equiv (P \land Q) \land R\end{equation}

    • These laws indicate that the grouping of statements in a series of disjunctions or conjunctions does not affect the logical equivalence of the compound statement.

  • (b) Distributive Laws:

    • \begin{equation}P \lor (Q \land R) \equiv (P \lor Q) \land (P \lor R)\end{equation}

    • \begin{equation}P \land (Q \lor R) \equiv (P \land Q) \lor (P \land R)\end{equation}

    • These laws are analogous to distributive laws in algebra, showing how disjunction distributes over conjunction, and vice-versa.

• Proof Idea: Both sets of laws can be proven by constructing comprehensive truth tables, showing that the truth values for both sides of each equivalence are identical for all possible combinations of truth values for $P, Q$, and $R$.