Discrete Mathematics: Principles of Logic and Propositional Logic

Foundations of Mathematical and Automated Reasoning

• Logic serves as the fundamental basis for all mathematical reasoning as well as all automated reasoning.
• Standard mathematical logic is essential for providing precisely formulated statements that would otherwise be expressed in natural language.
• The application of logical principles allows for the development of sets of laws that remain internally consistent.
• Within the field of computer science, mathematical logic is utilized to:
  • Construct specific computer programs.
  • Provide verification that programs perform exactly what they were designed to do.

Propositional Logic

• A proposition is defined as a statement or sentence that declares a specific fact.
• A proposition must evaluate to exactly one of two truth values: TRUE or FALSE, but it cannot be both.
• Truth values are typically denoted by letters:
  • If a proposition is true, it is denoted by $T$.
  • If a proposition is false, it is denoted by $F$.

Examples of Quantitative and Factual Propositions

• True Propositions:
  • There are seven days in a week.
  • Accra is the capital of Ghana.
  • $2 + 4 = 6$
• False Propositions:
  • The angles of a triangle add up to $360^\circ$.
  • London is the capital of France.
  • $2 - 4 = 7$

Sentences That Are Not Propositions

• Sentences that do not declare a fact are not considered propositions.
• Questions: "Who are you?"
• Commands or Exclamations: "Read this chapter before the next class."
• Sentences with Unassigned Variables: "$x + 1 = 2$" is not a proposition because its truth value depends on the value of $x$. However, if values are assigned to variables, such sentences can become propositions.

Mathematical Notation for Propositions

• Letters are used to denote specific propositional statements. Common examples include:
  • $P$ : Jane drives a Ford
  • $Q$ : Bob has grey hair
  • $R$ : Joe likes computer science

Logical Connectives and Truth Tables

• Logical connectives are operators used to combine propositions into compound statements.
• These connectives provide precise semantic meanings to words used in natural language such as "AND" and "OR."
• Semantic meaning for these connectives is defined using truth tables, which list the resulting truth value for every possible combination of values of the individual component statements.

Negation (The NOT Operator)

• If $P$ is a proposition, "not $P$" is the negation, represented by the symbols $\neg P$ or $\sim P$.
• The negation yields a value opposite to that of the original proposition.
• Example: If $P$ represents "I like dogs," then $\sim P$ represents "I do not like dogs."
• Truth Table for Negation:

Conjunction (The AND Operator)

• The conjunction of propositions $P$ and $Q$ is represented by the symbol $\wedge$.
• The compound statement is written as $P \wedge Q$.
• Example: If $P$ is "I like shopping" and $Q$ is "The sun is shining," then $P \wedge Q$ is "I like shopping and the sun is shining."
• Truth Table for Conjunction:

Disjunction (The OR Operator)

• The disjunction of propositions $P$ and $Q$ is represented by the symbol $\vee$.
• The compound statement is written as $P \vee Q$.
• This is an inclusive OR, meaning it is true if either or both propositions are true.
• Example: If $P$ is "I do the gardening" and $Q$ is "Today is Wednesday," then $P \vee Q$ can represent "I do gardening every Wednesday" (or "I do gardening or it is Wednesday").
• Truth Table for Disjunction:

Exclusive OR (The XOR Operator)

• The exclusive or connects propositions $P$ and $Q$ to result in "$P$ or $Q$ (but not both)."
• The symbol for exclusive or is $\oplus$.
• The statement is true only when one proposition is true and the other is false.
• Example: $P =$ "I will earn an A in this course," $Q =$ "I will drop this course." $P \oplus Q =$ "I will either earn an A in this course, or I will drop it (but not both!)."
• Truth Table for Exclusive OR:

Conditional Statements and Implications

The Implication Operator

• The implication operator gives meaning to the expression "$P$ implies $Q$," represented by the symbol $\Rightarrow$.
• This is also known as a conditional statement, often expressed as "if $P$ then $Q$."
• Components:
  • $P$ is the hypothesis, antecedent, or premise.
  • $Q$ is the conclusion, consequence, or result.
• Alternative phrasings for $P \Rightarrow Q$:
  • If $P$, then $Q$
  • $P$ is sufficient for $Q$
  • A necessary condition for $P$ is $Q$
  • $P$ only if $Q$
  • $Q$ unless $\neg P$
  • $Q$ follows from $P$
• Example: "If you get an A ($P$), then I'll give you a dollar ($Q$)."
  • If both are true, the promise is kept ($T$).
  • If $P$ is true but $Q$ is false, the promise is broken ($F$).
  • If $P$ is false, the promise hasn't been broken regardless of $Q$. Thus, in two-valued logic, it is considered true ($T$).
• Truth Table for Implication:

Converse, Contrapositive, and Inverse

From an original conditional statement $P \Rightarrow Q$, we can derive three related statements:

1. Converse: $Q \Rightarrow P$
2. Contrapositive: $\neg Q \Rightarrow \neg P$
3. Inverse: $\neg P \Rightarrow \neg Q$

Example Application:

• Original Statement: "The home team wins whenever it is raining" (If it is raining, then the home team wins).
• Converse: "If the home team wins, then it is raining."
• Contrapositive: "If the home team does not win, then it is not raining."
• Inverse: "If it is not raining, then the home team does not win."

Biconditional (The Equivalence Operator)

• The biconditional combines two propositions to express that they share the same truth value.
• Represented by the symbol $\Leftrightarrow$, often read as "$P$ if and only if (iff) $Q$."
• It is true if $P$ and $Q$ are both true, or if $P$ and $Q$ are both false.
• Example: $P$: "David is son of Ricky (male)." $Q$: "Ricky is father of David." This can be written as $P \Leftrightarrow Q$.
• Truth Table for Biconditional:

Three-Valued Logic

In both computing and mathematics, expressions sometimes cannot be evaluated precisely (e.g., the square root of a negative integer). In these cases, a three-valued logic is defined using truth values: TRUE ($T$), FALSE ($F$), and UNDEFINED.

Three-Valued Conjunction ($\wedge$)

Three-Valued Disjunction ($\vee$)

Three-Valued Implication ($\Rightarrow$)

Three-Valued Exclusive OR ($\oplus$) and Biconditional ($\Leftrightarrow$)

Truth Table for $P \oplus Q$:

Truth Table for $P \Leftrightarrow Q$:

Working with Compound Statements

• Compound statements involve two or more logical operations.
• Order of Operations (Precedence):
  1. Parenthetical Expressions: $()$ (evaluated innermost to outermost).
  2. Negation (NOT): $\sim$
  3. Conjunction (AND): $\wedge$
  4. Disjunction (OR): $\vee$
  5. Conditional (Implication): $\Rightarrow$
• Operations with equal precedence are evaluated from left to right.

Creating a Truth Table

1. Row Count: Determined by $2^n$, where $n$ is the number of propositional variables. (e.g., $3$ variables $= 2^3 = 8$ rows).
2. Column Count: Number of variables plus one column for each logical operation.
3. General Steps:
   • Assign variables to basic statements.
   • Symbolize the compound statement.
   • Identify the order of operations based on precedence.
   • Fill the table left to right.

Walkthrough Example

Statement: "If the tire is flat then I will have to remove it and take it to the gas station."

• Step 1 (Variables):
  • $P$: The tire is flat.
  • $Q$: I have to remove the tire.
  • $R$: I have to take the tire to the gas station.
• Step 2 (Symbolism): $P \Rightarrow (Q \wedge R)$. (Parentheses are used for clarity, though conjunction naturally has higher precedence than implication).
• Step 3 (Precedence Checking):
  1. AND ($Q \wedge R$)
  2. Conditional ($P \Rightarrow (Q \wedge R)$)
• Final Truth Table Construction:

Logical Equivalence, Tautology, and Contradiction

Logical Equivalence

• Two compound propositions are logically equivalent ($\equiv$) if they produce identical results in their truth tables.
• Example 1: $\sim\sim P \equiv P$ (Double negation).
• Example 2 (De Morgan's Laws derivation): $\sim(P \wedge Q) \equiv \sim P \vee \sim Q$.

Tautology

• A tautology is a statement that is always TRUE regardless of the truth values of its components. All rows of the truth table evaluate to $T$.
• Example 1: $P \vee \sim P$
• Example 2: $(P \Rightarrow Q) \vee (Q \Rightarrow P)$

Contradiction

• A contradiction is a statement that is always FALSE. All rows of the truth table evaluate to $F$.
• Example: $P \wedge \sim P$