Chapter 7 Mathematical Reasoning (Concepts)

Propositions

Mathematical reasoning is the process of forming conclusions based on logical steps and principles. It is the foundation upon which mathematical proofs and theorems are built. The fundamental building blocks of mathematical reasoning are statements that can be evaluated for their truthfulness. These statements are called Propositions.

Definition of a Proposition (or Statement)

In logic, a Proposition, also referred to as a Statement, is formally defined as a declarative sentence that is unequivocally either true or false, but not both simultaneously.

The key requirement for a sentence to be a proposition is that it must have a definite and objective truth value. It must be possible, in principle, to determine whether the statement is true or false, even if we do not currently know its truth value.

The truth or falsity of a proposition is called its truth value.

• If a proposition is true, its truth value is designated as True (T).
• If a proposition is false, its truth value is designated as False (F).

Propositions are the atomic units in logical arguments. We can combine them using logical connectives to form more complex statements, but the basic propositions must have this property of having a single, definite truth value.

Examples of Sentences that ARE Propositions:

• "The sun rises in the East." This is a declarative sentence asserting a fact about a natural phenomenon. Its truth value is objectively True.

• "Chennai is the capital of Tamil Nadu." This is a declarative sentence stating a geographical and political fact about India. Its truth value is objectively True.

• "$2 + 2 = 4$." This is a declarative sentence asserting a mathematical equality. Its truth value is objectively True.

• "Every prime number is odd." This is a declarative sentence making a claim about prime numbers. Its truth value is objectively False, as the number 2 is a prime number but is not odd.

• "Mount Everest is the tallest mountain in the world." This is a declarative sentence about geography. Its truth value is objectively True.

Examples of Sentences that are NOT Propositions:

Sentences that do not have a definite truth value are not considered propositions. These include:

• Questions (Interrogative Sentences): These ask for information and do not assert anything that can be true or false.

  Example: "What is your name?"

  Example: "Is it raining?"

• Commands or Requests (Imperative Sentences): These express directives or pleas.

  Example: "Shut the door."

  Example: "Please pass the salt."

• Exclamations (Exclamatory Sentences): These express strong feelings or surprise.

  Example: "May God bless you!"

  Example: "What a beautiful day!"

• Open Sentences or Predicates: These contain variables, and their truth value depends on the values assigned to the variables. They are not definitively true or false on their own.

  Example: "$x + 5 = 10$." This is true if $x=5$ but false if $x=3$. It is not a proposition unless $x$ is assigned a specific value or quantified (e.g., "For all real numbers $x$, $x+5=10$" - this IS a proposition, a false one).

  Example: "He is a cricketer." This is not a proposition unless "He" refers to a specific person whose identity is known.

• Paradoxical Sentences: These are self-referential sentences that cannot be assigned a single truth value without leading to a contradiction.

  Example: "This statement is false." If we assume it's true, then according to its content, it must be false. If we assume it's false, then it must be true. This violates the principle that a proposition must be either true or false, but not both.

• Subjective Statements: Statements whose truth value depends on opinion or interpretation.

  Example: "Chocolate is the best flavour." This is a matter of taste, not objective fact.

In mathematical logic, we often use lowercase letters such as $p, q, r, s$, etc., to represent propositions. This allows us to work with the logical structure of arguments abstractly, without needing to know the specific content of the propositions.

For example, instead of writing "The sun rises in the East AND 2 + 2 = 4", we can represent "The sun rises in the East" as $p$ and "2 + 2 = 4" as $q$, and then represent the combined statement as $p \land q$ (using the logical connective for "and").

Negation of a Statement

In logic, a fundamental operation we can perform on a proposition is Negation. The negation of a statement is a new statement that asserts the opposite truth value of the original statement. If the original statement is true, its negation is false, and if the original statement is false, its negation is true.

Definition and Notation for Negation

The Negation of a proposition $p$ is the statement that is false when $p$ is true, and true when $p$ is false. It essentially denies the assertion made by the original statement.

The negation of a statement $p$ is denoted by the symbol $\neg p$ or $\sim p$.

It is typically read as:

• "not $p$"
• "It is not the case that $p$"
• "It is false that $p$"

Truth Table for Negation

A truth table is a way to show the truth value of a compound statement for all possible truth values of its simple components. For negation, the truth table is straightforward, showing the relationship between the truth value of $p$ and the truth value of $\neg p$.

This table formally defines the negation operation: if $p$ is True, $\neg p$ is False; if $p$ is False, $\neg p$ is True.

Forming the Negation of a Statement

To form the negation of a statement in English, we often introduce the word "not" at an appropriate place or use a phrase like "It is not the case that...". However, careful attention is needed, especially when dealing with statements involving quantifiers like "all", "some", "every", "there exists".

Let $p$ be a statement. The negation $\neg p$ can often be formed by saying "It is not the case that $p$". Then simplify the resulting sentence.

Answer:

Answer:

Answer:

Double Negation

Applying negation twice to a statement returns the original statement. The negation of the negation of a statement $p$ is logically equivalent to $p$.

Explanation: If $p$ is True, $\neg p$ is False, and $\neg(\neg p)$ is True. If $p$ is False, $\neg p$ is True, and $\neg(\neg p)$ is False. In both cases, $\neg(\neg p)$ has the same truth value as $p$.

Example: Let $p$ be "It is raining". $\neg p$ is "It is not raining". $\neg(\neg p)$ is "It is not the case that it is not raining", which simplifies to "It is raining", the original statement $p$.

Compound Statements

While simple propositions (statements that are definitively true or false) form the basic units of logic, real-world arguments and mathematical proofs often involve more complex statements. These complex statements are formed by combining two or more simple propositions using logical connectors. Such combined statements are known as Compound Statements.

Definition of a Compound Statement

A Compound Statement is a statement that is formed by combining two or more simple propositions using one or more logical connectives.

Simple propositions are the independent statements that make up the compound statement. The truth value of a compound statement depends entirely on the truth values of its constituent simple propositions and the specific logical connective(s) used to combine them.

We can represent simple propositions using letters like $p, q, r, s$, etc.

Logical Connectives

Logical connectives are the words or symbols used to join simple statements to form compound statements. The most common logical connectives are:

• AND: Used for conjunction (joining two statements where both must be true for the compound statement to be true).
• OR: Used for disjunction (joining two statements where the compound statement is true if at least one of the simple statements is true).
• IF...THEN: Used for conditional statements or implications (expressing a relationship where one statement follows from another).
• IF AND ONLY IF (IFF): Used for biconditional statements or double implications (expressing equivalence between two statements).

In addition to these, negation ("NOT") is also often considered a logical operator, although it modifies a single statement rather than connecting two.

Components of Compound Statements

The simple propositions that are combined to create a compound statement are referred to as its component statements or simple components.

Answer:

Answer:

Answer:

In the following sections, we will delve deeper into the specific logical connectives, define their meaning precisely using truth tables, and learn how they affect the truth value of the compound statements they form.

Logical Connectives and Quantifiers

In mathematical reasoning, we often need to build complex statements from simpler ones or make assertions about collections of objects. Logical Connectives and Quantifiers are the tools that allow us to do this precisely. Logical connectives combine propositions, while quantifiers make statements about the extent to which a property holds for elements in a set.

Logical Connectives (Detailed)

Logical connectives are operators that combine two or more simple propositions (or simple statements) to form a compound statement. The truth value of the resulting compound statement is determined by the truth values of the component propositions and the specific connective used. Let $p$ and $q$ be two simple propositions.

1. Conjunction (AND)

The conjunction of two propositions $p$ and $q$ is the compound statement "$p$ and $q$". It is true only when both $p$ and $q$ are true. If either $p$ is false, or $q$ is false, or both are false, then the conjunction is false.

The conjunction of $p$ and $q$ is denoted by $p \land q$. The symbol $\land$ resembles an 'A' (for AND) without the crossbar.

It is read as "$p$ and $q$".

Truth Table for Conjunction ($p \land q$):

Example: Let $p$: "It is raining" and $q$: "The ground is wet". The conjunction $p \land q$: "It is raining and the ground is wet". This statement is true only if it is actually raining AND the ground is actually wet.

2. Disjunction (OR)

The disjunction of two propositions $p$ and $q$ is the compound statement "$p$ or $q$". In mathematical logic, "or" is almost always used in the inclusive sense. This means the disjunction is true if $p$ is true, or if $q$ is true, or if both $p$ and $q$ are true. The disjunction is false only when both $p$ and $q$ are false.

The disjunction of $p$ and $q$ is denoted by $p \lor q$. The symbol $\lor$ resembles a 'V'.

It is read as "$p$ or $q$".

Truth Table for Disjunction ($p \lor q$):

Example: Let $p$: "I will eat pizza" and $q$: "I will eat pasta". The disjunction $p \lor q$: "I will eat pizza or I will eat pasta". This statement is true if I eat only pizza, only pasta, or both pizza and pasta. It is false only if I eat neither.

Note: The exclusive OR (XOR), denoted $p \oplus q$ or $p \text{ XOR } q$, is true if exactly one of $p$ or $q$ is true. Its truth table is: T $\oplus$ T = F, T $\oplus$ F = T, F $\oplus$ T = T, F $\oplus$ F = F. Unless specified otherwise, "OR" in mathematical reasoning refers to the inclusive OR.

Quantifiers

In predicate logic, quantifiers are symbols used to specify the number or quantity of objects in a given domain that satisfy a certain property or predicate. They are used to convert open sentences (sentences with variables whose truth value depends on the variable) into propositions (statements with a definite truth value).

Let $P(x)$ be a predicate (an open sentence involving the variable $x$).

1. Universal Quantifier ($\forall$)

The Universal Quantifier is denoted by the symbol $\forall$. It is used to express that a predicate is true for every element in a specified domain or set.

The statement $\forall x, P(x)$ is read as "For all $x$, $P(x)$ is true", "For every $x$, $P(x)$ is true", or "For each $x$, $P(x)$ is true".

Truth Value of $\forall x, P(x)$:

• $\forall x, P(x)$ is True if $P(x)$ is true for every single value of $x$ in the specified domain.
• $\forall x, P(x)$ is False if there exists at least one value of $x$ in the domain for which $P(x)$ is false. (Finding just one such value is sufficient to prove the universal statement false; this is called a counterexample).

Answer:

2. Existential Quantifier ($\exists$)

The Existential Quantifier is denoted by the symbol $\exists$. It is used to express that a predicate is true for at least one element in a specified domain or set.

The statement $\exists x, P(x)$ is read as "There exists an $x$ such that $P(x)$ is true", "There is at least one $x$ such that $P(x)$ is true", or "For some $x$, $P(x)$ is true".

Truth Value of $\exists x, P(x)$:

• $\exists x, P(x)$ is True if there is at least one value of $x$ in the specified domain for which $P(x)$ is true. (Finding just one such value is sufficient to prove the existential statement true).
• $\exists x, P(x)$ is False if $P(x)$ is false for every single value of $x$ in the domain.

Answer:

Negation of Quantified Statements

The negation of statements involving quantifiers follows specific rules:

• The negation of a universal statement is an existential statement with a negated predicate.

  $$\neg (\forall x, P(x)) \iff \exists x, \neg P(x)$$

  ... (62)

  Read as: "It is not true that for all $x$, $P(x)$ is true" is equivalent to "There exists an $x$ such that $P(x)$ is false".

• The negation of an existential statement is a universal statement with a negated predicate.

  $$\neg (\exists x, P(x)) \iff \forall x, \neg P(x)$$

  ... (63)

  Read as: "It is not true that there exists an $x$ such that $P(x)$ is true" is equivalent to "For all $x$, $P(x)$ is false".

Answer:

Answer:

Implications

In mathematical reasoning and everyday language, we frequently encounter statements that express a cause-and-effect relationship or a condition and its consequence. These types of compound statements are known as Implications or Conditional Statements. They are typically structured in the form "If [statement $p$], then [statement $q$]".

Definition of Implication (Conditional Statement)

An Implication (or Conditional Statement) is a compound statement connecting two propositions, $p$ and $q$, using the structure "If $p$, then $q$".

The implication "If $p$, then $q$" is denoted symbolically by $p \implies q$ or $p \to q$. The symbol $\implies$ (or $\to$) is the logical connective for implication.

In the conditional statement $p \implies q$:

• The proposition $p$ is called the antecedent, the hypothesis, or the premise. It is the "if" part of the statement.
• The proposition $q$ is called the consequent or the conclusion. It is the "then" part of the statement.

The statement $p \implies q$ asserts that $q$ is true whenever $p$ is true. It does NOT necessarily mean that $p$ causes $q$. It defines a logical relationship between their truth values.

The statement $p \implies q$ can be expressed in English in various equivalent ways, which are important to recognize:

• If $p$, then $q$. (The standard form)
• $p$ implies $q$.
• $p$ is a sufficient condition for $q$. (Meaning, if $p$ is true, that is enough to guarantee $q$ is true).
• $q$ is a necessary condition for $p$. (Meaning, if $q$ is not true, then $p$ cannot be true. For $p$ to be true, $q$ *must* be true).
• $p$ only if $q$. (Similar to necessary condition: if $p$ happens, the only way it could happen is if $q$ is true).
• $q$ whenever $p$. (Equivalent to "If $p$, then $q$").
• $q$ provided $p$. (Equivalent to "If $p$, then $q$").
• $q$ follows from $p$.

Answer:

Answer:

Related Conditional Statements

Given an implication $p \implies q$, we can form three related conditional statements by interchanging or negating the antecedent and consequent:

• Converse: The converse of $p \implies q$ is formed by interchanging the antecedent and the consequent.
  Converse: $q \implies p$ (If $q$, then $p$)

  Example: Original statement: "If it rains ($p$), then the ground is wet ($q$)" ($p \implies q$). Converse: "If the ground is wet ($q$), then it rains ($p$)" ($q \implies p$).

• Inverse: The inverse of $p \implies q$ is formed by negating both the antecedent and the consequent, but keeping the original order.
  Inverse: $\neg p \implies \neg q$ (If not $p$, then not $q$)

  Example: Original statement: "If it rains ($p$), then the ground is wet ($q$)" ($p \implies q$). Inverse: "If it does not rain ($\neg p$), then the ground is not wet ($\neg q$)" ($\neg p \implies \neg q$).

• Contrapositive: The contrapositive of $p \implies q$ is formed by interchanging the antecedent and the consequent AND negating both. It is the inverse of the converse, or the converse of the inverse.
  Contrapositive: $\neg q \implies \neg p$ (If not $q$, then not $p$)

  Example: Original statement: "If it rains ($p$), then the ground is wet ($q$)" ($p \implies q$). Contrapositive: "If the ground is not wet ($\neg q$), then it does not rain ($\neg p$)" ($\neg q \implies \neg p$).

Answer:

Understanding the logical relationship and truth values of these related conditional statements is crucial for constructing proofs and evaluating logical arguments. The truth value of a conditional statement itself is explored in detail in the next section.

Truth Values of Conditional Statement

A Conditional Statement, or Implication, of the form "If $p$, then $q$" ($p \implies q$) is a compound statement whose truth value is determined by the truth values of its antecedent ($p$) and its consequent ($q$). Understanding the truth conditions for implications is crucial for logical reasoning.

Truth Table for Implication ($p \implies q$)

The truth value of the implication $p \implies q$ is defined according to the following table. The definition in mathematical logic might initially seem counter-intuitive in cases where the antecedent is false, but it is essential for consistency within the logical system.

The implication $p \implies q$ is considered false only in one specific scenario: when the antecedent ($p$) is true and the consequent ($q$) is false. In all other possible combinations of truth values for $p$ and $q$, the implication $p \implies q$ is true.

Let's examine each case with a common example, where $p$: "It is raining" and $q$: "The ground is wet". The implication is $p \implies q$: "If it is raining, then the ground is wet."

Explanation of Truth Values:

• Case 1: $p$ is True, $q$ is True. ("It is raining" is T, "The ground is wet" is T).

  Scenario: It is raining, and the ground is wet. The statement "If it is raining, then the ground is wet" seems correct in this situation. The implication $p \implies q$ is True.

• Case 2: $p$ is True, $q$ is False. ("It is raining" is T, "The ground is wet" is F).

  Scenario: It is raining, but the ground is not wet. This situation contradicts the assertion made by the statement "If it is raining, then the ground is wet". If rain is happening, we expect the ground to get wet. Since the expected consequence ($q$) did not occur despite the condition ($p$) being met, the implication is considered False. This is the only case where $p \implies q$ is false.

• Case 3: $p$ is False, $q$ is True. ("It is raining" is F, "The ground is wet" is T).

  Scenario: It is not raining, but the ground is wet. The statement "If it is raining, then the ground is wet" does not claim that rain is the *only* way the ground can get wet (it could be from sprinklers, a water pipe burst, etc.). The statement only says what happens IF it rains. Since it's not raining (p is False), the condition of the 'if' part is not met, so the implication's claim ("q must follow if p happens") is not tested or contradicted. In logic, such an implication is considered True by convention. This is sometimes called vacuously true or true by default.

• Case 4: $p$ is False, $q$ is False. ("It is raining" is F, "The ground is wet" is F).

  Scenario: It is not raining, and the ground is not wet. This situation does not contradict the statement "If it is raining, then the ground is wet". The condition ($p$) is false, and the expected consequence ($q$) is also false, which is consistent. The implication is considered True.

The definition reflects the idea that the implication $p \implies q$ is false only when it is possible for $p$ to be true and $q$ to be false simultaneously. If this scenario (T $\implies$ F) never occurs, the implication is always true.

Truth Values of Related Conditional Statements

As discussed in the previous section, given a conditional statement $p \implies q$, we have related statements: the converse ($q \implies p$), the inverse ($\neg p \implies \neg q$), and the contrapositive ($\neg q \implies \neg p$). Let's construct their truth tables and compare them.

We apply the definition of implication to the columns for the related statements. For example, for the converse $q \implies p$, we look at the truth values of $q$ and $p$ and apply the implication rule (T $\implies$ F is False, otherwise True). We see $q=T, p=F$ in the 3rd row, making $q \implies p$ False. All other rows for $q \implies p$ are True.

Observations from the Truth Tables:

• Logical Equivalence: Two statements are logically equivalent if they have the same truth value in every possible scenario (i.e., their columns in the truth table are identical). From the table:
  • The original statement ($p \implies q$) and its contrapositive ($\neg q \implies \neg p$) are logically equivalent. Their truth value columns are identical (T, F, T, T). This is a very important equivalence used in proofs (proof by contrapositive).
  • The converse ($q \implies p$) and the inverse ($\neg p \implies \neg q$) are also logically equivalent to each other. Their truth value columns are identical (T, T, F, T).
• The converse ($q \implies p$) is NOT logically equivalent to the original statement ($p \implies q$). Knowing that "If $p$, then $q$" is true does not mean "If $q$, then $p$" is also true. (Example: "If a number is divisible by 10, then it is divisible by 5" is true. The converse "If a number is divisible by 5, then it is divisible by 10" is false, e.g., 15 is divisible by 5 but not by 10).

Biconditional Statement (If and Only If)

The Biconditional statement, or Double Implication, of two propositions $p$ and $q$ is denoted by $p \iff q$ or $p \leftrightarrow q$. It is essentially a combination of two implications: "$p$ implies $q$" AND "$q$ implies $p$".

The statement $p \iff q$ is logically true if and only if $p$ and $q$ have the same truth value (i.e., both are true or both are false).

It is read as:

• "$p$ if and only if $q$" (often abbreviated as "$p$ iff $q$").
• "$p$ is a necessary and sufficient condition for $q$." (This means $p$ implies $q$ (sufficient) AND $q$ implies $p$ (necessary)).
• "$p$ is logically equivalent to $q$".

The statement $p \iff q$ is logically equivalent to the conjunction of the original implication and its converse: $(p \implies q) \land (q \implies p)$.

Truth Table for Biconditional ($p \iff q$):

From the table, we can see that $p \iff q$ is True only when the truth values of $p$ and $q$ match (both T or both F). This table is consistent with the definition $p \iff q \equiv (p \implies q) \land (q \implies p)$. Let's verify one row, say $p=T, q=F$: $p \implies q$ is F, $q \implies p$ is T. $(p \implies q) \land (q \implies p)$ is F $\land$ T = F. This matches the biconditional truth value for $p=T, q=F$.

Validating Statements

In mathematical reasoning, once we have defined simple propositions and learned how to combine them using logical connectives and quantifiers, the next crucial step is to analyze and validate statements and arguments. Validating statements involves determining the overall truth value of a compound statement based on the truth values of its components. Validating arguments involves checking if a conclusion logically follows from a set of premises.

Truth Tables for Compound Statements

For any compound statement, we can determine its truth value for every possible combination of truth values of its simple component propositions. This is systematically done by constructing a Truth Table. A truth table lists all possible truth assignments for the component simple statements and then shows the resulting truth value of the compound statement step by step, following the definitions of the logical connectives involved.

If a compound statement involves $n$ simple propositions, there will be $2^n$ rows in the truth table, representing every possible combination of True and False values for these $n$ propositions.

Answer:

Types of Statements Based on Truth Values

Based on the truth values in the final column of its truth table, a compound statement can be classified into one of three types:

• Tautology: A compound statement is a tautology if it is always true, regardless of the truth values of its simple component statements. In its truth table, the final column contains only True (T) values.

  Example: $p \lor (\neg p)$ ("$p$ or not $p$"). This statement is always true (a proposition is either true or false, there is no other option in classical logic). Its truth table (shown in Example 2 below) has T in all rows of the final column.

• Contradiction: A compound statement is a contradiction if it is always false, regardless of the truth values of its simple component statements. In its truth table, the final column contains only False (F) values.

  Example: $p \land (\neg p)$ ("$p$ and not $p$"). A statement cannot be both true and false simultaneously. Its truth table (shown in Example 3 below) has F in all rows of the final column.

• Contingency: A compound statement is a contingency if it is neither a tautology nor a contradiction. Its truth value depends on the specific truth values of its component simple statements. In its truth table, the final column contains at least one True (T) value and at least one False (F) value.

  Example: $p \land q$ ("$p$ and $q$"). This is true only when both are true, and false otherwise. The statement $(p \land q) \lor (\neg p)$ from Example 1 is also a contingency.

Answer:

Answer:

Validating Logical Arguments

In mathematics and logic, an Argument is a set of statements called premises, followed by a statement called the conclusion. The argument form is:

Premise 1

Premise 2

...

Premise $n$

Conclusion

An argument is considered valid if the conclusion logically follows from the premises. This means that whenever all the premises are true, the conclusion must also be true. If it is possible for all premises to be true while the conclusion is false, the argument is invalid.

Formally, an argument with premises $P_1, P_2, ..., P_n$ and conclusion $C$ is valid if and only if the conditional statement $(P_1 \land P_2 \land ... \land P_n) \implies C$ is a tautology.

Methods for Validating Arguments

Several methods can be used to check the validity of an argument:

1. Truth Table Method: Construct a truth table that includes columns for all premises and the conclusion. Examine the rows where all premises are simultaneously true. If in all such rows, the conclusion is also true, the argument is valid. If there is even one row where all premises are true but the conclusion is false, the argument is invalid. Alternatively, construct the truth table for the implication (Premises) $\implies$ Conclusion and check if it is a tautology.

2. Using Logical Equivalences and Inference Rules: Apply known rules of logical inference (like Modus Ponens, Modus Tollens, etc.) and logical equivalences (like De Morgan's Laws, double negation, etc.) to deduce the conclusion from the premises step by step. This method is more like building a proof.

3. Counterexample Method (for proving invalidity): To demonstrate that an argument is invalid, find a specific assignment of truth values to the simple component statements such that all the premises become true, but the conclusion becomes false. If such a scenario is possible, the argument is invalid.

Answer:

Answer: