Basic Logic

Logic is the foundation of mathematical reasoning and critical thinking, especially in computer science. It provides a formal system for reasoning about propositions, their validity, and relationships. Understanding logic is essential for algorithm design, programming, and problem-solving in computer science.

This lecture will cover the fundamental principles of propositional logic and predicate logic, progressing from basic to advanced topics:

1. Propositions
2. Logical Connectives
3. Truth Tables
4. Logical Equivalences
5. Conditional Statements
6. Predicates and Quantifiers
7. Negation of Quantified Statements
8. Nested Quantifiers
9. Free and Bound Variables
10. Translating English to Logical Expressions
11. Expressing Mathematical Statements in Logic
12. Law of Excluded Middle and Proof Techniques

A proposition is a declarative sentence that is either true or false, but not both.

• Pronunciation: prop-uh-ZI-shun
• Alternative terms: Statement, Assertion

• “The sky is blue.”
• “2 + 2 = 4.”
• “Beijing is the capital of China.”

• “The moon is made of cheese.”
• “5 is greater than 10.”
• “All birds can fly.”

• Questions: “What time is it?”
• Commands: “Close the door.”
• Opinions: “Chocolate is the best ice cream flavor.”

• Denoted by letters such as \( p \), \( q \), \( r \).
• Represent arbitrary propositions.
• Example: Let \( p \) represent “It is raining.”

Logical connectives (also called logical operators) are used to form new propositions from existing ones.

• Symbol: \( \lnot \) (LaTeX: \lnot)
• Pronunciation: not, negation
• Definition: The negation of proposition \( p \) is \( \lnot p \), which is true when \( p \) is false, and false when \( p \) is true.

• If \( p \) is “It is raining,” then \( \lnot p \) is “It is not raining.”

• Symbol: \( \land \) (LaTeX: \land)
• Pronunciation: and, conjunction
• Definition: The conjunction of \( p \) and \( q \) is \( p \land q \), which is true only when both \( p \) and \( q \) are true.

• \( p \): “It is raining.”
• \( q \): “I have an umbrella.”
• \( p \land q \): “It is raining, and I have an umbrella.”

• Symbol: \( \lor \) (LaTeX: \lor)
• Pronunciation: or, disjunction
• Definition: The disjunction of \( p \) and \( q \) is \( p \lor q \), which is true when at least one of \( p \) or \( q \) is true.

• \( p \): “I will study.”
• \( q \): “I will watch a movie.”
• \( p \lor q \): “I will study, or I will watch a movie.”

• Symbol: \( \oplus \) (LaTeX: \oplus)
• Pronunciation: exclusive or, xor
• Definition: \( p \oplus q \) is true when exactly one of \( p \) or \( q \) is true, but not both.

• \( p \): “I will eat noodles.”
• \( q \): “I will eat rice.”
• \( p \oplus q \): “I will eat noodles or rice (but not both).”

• Symbol: \( \rightarrow \) (LaTeX: \rightarrow)
• Pronunciation: implies, if…then
• Definition: \( p \rightarrow q \) is false only when \( p \) is true and \( q \) is false; otherwise, it is true.

• \( p \): “It rains.”
• \( q \): “The ground gets wet.”
• \( p \rightarrow q \): “If it rains, then the ground gets wet.”

• Symbol: \( \leftrightarrow \) (LaTeX: \leftrightarrow)
• Pronunciation: if and only if, iff
• Definition: \( p \leftrightarrow q \) is true when \( p \) and \( q \) have the same truth value.

• \( p \): “You are a citizen.”
• \( q \): “You can vote.”
• \( p \leftrightarrow q \): “You are a citizen if and only if you can vote.”

A truth table is a mathematical table used to determine the truth value of a compound proposition for all possible truth values of its components.

1. List all possible truth value combinations of the propositional variables.
2. Compute the truth value of the compound proposition for each combination.

Two propositions are logically equivalent if they have the same truth value in all possible scenarios.

• Notation: \( p \equiv q \)
• Pronunciation: p is equivalent to q

• First Law:

  \[ \lnot (p \land q) \equiv (\lnot p) \lor (\lnot q) \]

• Second Law:

  \[ \lnot (p \lor q) \equiv (\lnot p) \land (\lnot q) \]

• Pronunciation: Dee Morgan’s Laws

• Original Statement: “It is not true that I will study and exercise.”
• Logical Form: \( \lnot (p \land q) \)
• Equivalent Statement: “I will not study or I will not exercise.”
• Logical Form: \( (\lnot p) \lor (\lnot q) \)

• \[ \lnot (\lnot p) \equiv p \]

• \[ p \rightarrow q \equiv \lnot q \rightarrow \lnot p \]

• Definition: A compound proposition where \( p \) is the hypothesis (antecedent) and \( q \) is the conclusion (consequent).
• Pronunciation: p implies q, if p then q

1. “If \( p \), then \( q \).”
2. “\( p \) implies \( q \).”
3. “Whenever \( p \), \( q \).”
4. " \( p \) is sufficient for \( q \)."
5. " \( q \) is necessary for \( p \)."
6. " \( q \) if \( p \)."
7. " \( p \) only if \( q \)."

• Contrapositive: \( \lnot q \rightarrow \lnot p \)
  • Equivalent to: \( p \rightarrow q \)
• Converse: \( q \rightarrow p \)
• Inverse: \( \lnot p \rightarrow \lnot q \)

• Original Statement: “If it is raining, then I will get wet.”
• Contrapositive: “If I do not get wet, then it is not raining.”

• Converse: “If I get wet, then it is raining.”
• Note: The converse is not logically equivalent to the original implication.

• Definition: A predicate is a statement containing variables that becomes a proposition when the variables are specified.
• Pronunciation: pred-uh-kit
• Example: \( P(x) \): " \( x \) is greater than 5."

Quantifiers specify the extent to which a predicate’s statement is true over a range of elements.

• Symbol: \( \forall \) (LaTeX: \forall)
• Pronunciation: for all, for every
• Definition: \( \forall x , P(x) \) means “For all \( x \), \( P(x) \) is true.”

• \( P(x) \): " \( x \) is greater than 0."
• \( \forall x \in \mathbb{N}, P(x) \): “All natural numbers are greater than 0.”

• Symbol: \( \exists \) (LaTeX: \exists)
• Pronunciation: there exists, there is at least one
• Definition: \( \exists x , P(x) \) means “There exists an \( x \) such that \( P(x) \) is true.”

• \( P(x) \): " \( x \) is an even prime number."

• \( \exists x \in \mathbb{N}, P(x) \): “There exists a natural number that is an even prime.”

• Note: The only even prime number is 2.

• Negation of Universal Quantifier:

  \[ \lnot (\forall x , P(x)) \equiv \exists x , \lnot P(x) \]

• Negation of Existential Quantifier:

  \[ \lnot (\exists x , P(x)) \equiv \forall x , \lnot P(x) \]

• Original: “All birds can fly.”
• Logical Form: \( \forall x , B(x) \)
• Negation: \( \exists x , \lnot B(x) \)
• English Translation: “There exists a bird that cannot fly.”

• Original: “There exists a student who has never cheated.”
• Logical Form: \( \exists x , S(x) \)
• Negation: \( \forall x , \lnot S(x) \)
• English Translation: “All students have cheated.”

The order of quantifiers matters, especially when they are of different types.

• Statement A: \( \forall x \exists y , P(x, y) \)

  • “For every \( x \), there exists a \( y \) such that \( P(x, y) \).”

• Statement B: \( \exists y \forall x , P(x, y) \)

  • “There exists a \( y \) such that for every \( x \), \( P(x, y) \).”

• These statements are not equivalent.

• \( \forall x \in \mathbb{R}, \exists y \in \mathbb{R}, y = x + 1 \)
• Translation: “For every real number \( x \), there exists a real number \( y \) such that \( y = x + 1 \).”

• \( \exists y \in \mathbb{R}, \forall x \in \mathbb{R}, y = x + 1 \)
• Translation: “There exists a real number \( y \) such that for all real numbers \( x \), \( y = x + 1 \).”
• This is false, since no single \( y \) can satisfy \( y = x + 1 \) for all \( x \).

• Free Variable: A variable not bound by a quantifier. The statement’s truth depends on its value.
• Bound Variable: A variable that is quantified; its value is fixed within the quantifier’s scope.

• \( P(x): x > 0 \)
• \( x \) is a free variable.

• \( \forall x , P(x) \)
• \( x \) is bound by the universal quantifier.

1. Identify the domain of discourse.
2. Define predicates.
3. Determine the quantifiers.
4. Translate into logical expressions.

• Domain: All people.

• Predicate: \( S(x) \): " \( x \) is a student in the class."

• Predicate: \( C(x) \): " \( x \) has a calculator."

• Logical Expression:

  \[ \forall x , (S(x) \rightarrow C(x)) \]

• Domain: All people.

• Predicate: \( K(x, y) \): " \( x \) knows \( y \)."

• Logical Expression:

  \[ \exists x , \forall y , K(x, y) \]

• Statement: For any integer \( a \) and positive integer \( b \), there exist integers \( q \) and \( r \) such that \( a = bq + r \) and \( 0 \leq r < b \).

• Logical Expression:

  \[ \forall a \in \mathbb{Z}, \forall b \in \mathbb{N}^+, \exists q \in \mathbb{Z}, \exists r \in \mathbb{Z}, (a = bq + r) \land (0 \leq r < b) \]

• Statement: There exists a unique solution to the equation \( x + 2 = 5 \).

• Logical Expression:

  \[ \exists! x \in \mathbb{R}, x + 2 = 5 \]

• Explanation: The symbol \( \exists! \) denotes “there exists exactly one.”

• Definition: The Law of Excluded Middle (LEM) states that for any proposition \( P \), either \( P \) is true or its negation \( \lnot P \) is true. There is no third option or middle ground.

• Symbolically:

  \[ P \lor \lnot P \]

• Pronunciation: Law of Excluded Middle, Either P or not P

• Alternative expressions: “A proposition is either true or false,” “No middle truth value exists between true and false.”

• The Law of Excluded Middle is a fundamental principle in classical logic.
• It allows for certain proof techniques, such as proof by contradiction, to be valid and effective.
• In computer science, especially in areas like algorithm design and formal verification, LEM underpins logical reasoning and decision-making processes.

• Proposition \( P \): “The program has no bugs.”
• According to LEM: “Either the program has no bugs, or the program has bugs.”
• There is no third possibility regarding the program’s bug status.

• Proposition \( P \): “Number \( n \) is divisible by 3.”
• According to LEM: “Either \( n \) is divisible by 3, or \( n \) is not divisible by 3.”
• For any integer \( n \), one of these statements must be true.

• Predicate \( P(x) \): “\( x \) is a prime number.”
• For a specific \( x = 11 \):
  • LEM asserts: “Either 11 is a prime number, or 11 is not a prime number.”
  • Since 11 is prime, \( P(11) \) is true.

• Proposition \( P \): “The new software update will be released tomorrow.”
• LEM states: “Either the update will be released tomorrow, or it will not be released tomorrow.”
• Despite uncertainty, one of these outcomes must occur.

• Proposition \( P \): “This statement is false.”
• While this creates a paradox known as the liar paradox, in classical logic, LEM insists that the statement is either true or false.
• Note: Such paradoxes highlight limitations and areas of interest in logical theory but do not invalidate LEM in classical logic.

• Definition: A proof method where we assume the negation of the statement we want to prove and show that this assumption leads to a contradiction.
• Connection to LEM: Relies on the principle that either a proposition or its negation is true; there is no third option.

1. Assume the Opposite: Assume that the proposition \( P \) we want to prove is false, i.e., assume \( \lnot P \).
2. Logical Deduction: Use logical reasoning and known facts to derive consequences from \( \lnot P \).
3. Reach a Contradiction: Show that these consequences lead to a contradiction, such as a statement that is always false (e.g., \( Q \land \lnot Q \)).
4. Conclude Original Proposition: Since \( \lnot P \) leads to a contradiction, \( P \) must be true.

• Proposition: “The number \( \sqrt{2} \) is irrational.”
• Proof Outline:
  1. Assume the Opposite: Suppose \( \sqrt{2} \) is rational.
  2. Express as Fraction: Then \( \sqrt{2} = \frac{a}{b} \), where \( a \) and \( b \) are integers with no common factors.
  3. Manipulate Equation: \( 2 = \frac{a^2}{b^2} \) leads to \( a^2 = 2b^2 \).
  4. Deduce Parity: \( a^2 \) is even, so \( a \) must be even.
  5. Represent \( a \): Let \( a = 2k \), where \( k \) is an integer.
  6. Substitute Back: \( (2k)^2 = 2b^2 \) simplifies to \( b^2 = 2k^2 \).
  7. Conclude \( b \) is Even: \( b^2 \) is even, so \( b \) is even.
  8. Contradiction: Both \( a \) and \( b \) are even, contradicting that they have no common factors.
  9. Conclusion: Therefore, \( \sqrt{2} \) is irrational.

• Proposition: “There is no smallest positive rational number.”
• Proof Outline:
  1. Assume the Opposite: Suppose there is a smallest positive rational number \( r \).
  2. Consider \( r/2 \): \( r/2 \) is also a positive rational number and smaller than \( r \).
  3. Contradiction: This contradicts the assumption that \( r \) is the smallest.
  4. Conclusion: Therefore, there is no smallest positive rational number.

• Proposition: “There are infinitely many prime numbers.”
• Proof Outline:
  1. Assume the Opposite: Suppose there are finitely many primes \( p_1, p_2, …, p_n \).
  2. Construct a Number: Let \( N = p_1 p_2 \cdots p_n + 1 \).
  3. Analyze Divisibility: \( N \) is not divisible by any \( p_i \), as it leaves a remainder of 1.
  4. Contradiction: \( N \) must be prime or have prime factors not in the list.
  5. Conclusion: There must be more primes than those listed.

• Classical Logic:
  • Accepts the Law of Excluded Middle.
  • Permits proof techniques like proof by contradiction.
  • Widely used in mathematics and computer science.
• Intuitionistic Logic:
  • Does not accept the Law of Excluded Middle universally.
  • Requires constructive proofs; a proposition is only true if there is a constructive proof.
  • Proof by contradiction is limited or not used.

• Algorithm Correctness: Ensures that algorithms behave predictably by adhering to binary true/false evaluations.
• Formal Verification: Utilizes LEM to verify that software meets specifications.
• Programming Languages: Some languages and paradigms (like functional programming) explore concepts from intuitionistic logic, affecting how LEM is applied.

• The Law of Excluded Middle is essential for understanding and applying proof techniques in logic.
• Recognizing the validity of LEM in classical logic allows for effective reasoning and problem-solving.
• Awareness of different logical systems broadens understanding but classical logic remains the standard in most of mathematics and computer science.

• Propositions: Basic statements with a truth value.
• Logical Connectives: Form compound propositions.
• Truth Tables: Evaluate the truth of propositions.
• Logical Equivalences: Simplify logical expressions.
• Implications: Conditional statements with hypotheses and conclusions.
• Predicates: Statements with variables.
• Quantifiers: Express the extent of predicates over domains.
• Negation Rules: Invert the truth of statements.
• Nested Quantifiers: Order matters in multiple quantifiers.
• Free vs. Bound Variables: Variables’ scope in statements.
• Translation: Converting English to logical expressions.

1. Logical Equivalence:

   • Problem: Show that \( \lnot (p \lor q) \) is logically equivalent to \( \lnot p \land \lnot q \).
   • Solution: Apply De Morgan’s Law.

2. Translating Statements:

   • Problem: Translate “Some cats are black” into a logical expression.

   • Solution:

     \[ \exists x , (C(x) \land B(x)) \]

     Where \( C(x) \): " \( x \) is a cat," \( B(x) \): " \( x \) is black."

3. Negating Quantifiers:

   • Problem: Negate the statement \( \forall x , (P(x) \rightarrow Q(x)) \).

   • Solution:

     \[ \lnot \forall x , (P(x) \rightarrow Q(x)) \equiv \exists x , (P(x) \land \lnot Q(x)) \]

4. Nested Quantifiers:

   • Problem: Determine whether the following statement is true or false: \( \forall x \in \mathbb{R}, \exists y \in \mathbb{R}, y = x^2 \).
   • Solution: True, since for every real number \( x \), \( y = x^2 \) is also a real number.

5. Conditional Statements:

   • Problem: Write the converse and contrapositive of “If a number is even, then it is divisible by 2.”
   • Solution:
     • Converse: “If a number is divisible by 2, then it is even.”
     • Contrapositive: “If a number is not divisible by 2, then it is not even.”

• \( \lnot \): not, negation
• \( \land \): and, conjunction
• \( \lor \): or, disjunction
• \( \oplus \): exclusive or, xor
• \( \rightarrow \): implies, if…then
• \( \leftrightarrow \): if and only if, iff
• \( \forall \): for all, for every
• \( \exists \): there exists
• \( \exists! \): there exists exactly one

• “Only if”: \( p \text{ only if } q \) means \( p \rightarrow q \).
• “Necessary and Sufficient”:
  • \( p \) is necessary for \( q \): \( q \rightarrow p \).
  • \( p \) is sufficient for \( q \): \( p \rightarrow q \).