Gain insights into formal logic, propositional logic, and first-order logic. Learn about inference rules and master constructing rigorous proofs, enhancing critical thinking and problem-solving skills.

Formal logic provides a systematic and rigorous framework for expressing and analyzing arguments, which enables learners to evaluate the validity of reasoning, fostering critical thinking skills. Proficiency in constructing and understanding proofs enhances problem-solving abilities, encourages precision in thought, and promotes clarity in communication.

In this course, you’ll explore propositions and logical connectives in propositional logic. Next, you’ll cover first-order logic, which extends the scope to include variables, quantifiers, and predicates. Next, the rules of inference are discussed which provide the logical steps required to establish the validity of mathematical statements. 

After taking this course, you’ll develop the skills to navigate and manipulate logical systems effectively. You’ll also acquire the essential toolkit for constructing rigorous and convincing mathematical proofs—a skill that is pivotal in advanced mathematics, computer science, and other analytical disciplines.

Introduction to Logic: Basics of Mathematical Reasoning

# Common mistakes

As humans, we all make mistakes. To avoid typographic errors, we must proofread the script we write. We must carefully verify each algebraic manipulation in proof to ensure correctness. Overall, the proof must be a valid argument type, and every deduction must be according to inference rules. Sometimes, errors in algebraic manipulation are straightforward to catch, but sometimes they are very subtle. Let’s look at the following example of a wrong derivation with a subtle mistake:

$\begin{aligned}{}
&1.& x &= y\\
&2.& x^2 &= xy &\text{Multiplying both sides with }x\text{.}\\
&3.& x^2-y^2 &= xy -y^2 &\text{Subtracting }y^2\text{ from both sides.}\\
&4.& (x+y)(x-y) &= y(x-y) &\text{Factorizing.}\\
&5.& x+y &= y &\text{Cancelling }(x-y)\text{ from both sides.}\\
&6.& 2y &= y &\text{Substituting from line 1.}\\
&7.& 2 &= 1 &\text{Cancelling }y\text{ from both sides.}
\end{aligned}$

We notice that every step is fine except the fifth step if we look closely. As $x=y$, we can not cancel out $(x-y)$ from both sides because it equals zero. Such mistakes can lead to inconsistent results, as in line number seven.

Now let’s look at some common mistakes of argument.

## The fallacy of affirming the conclusion
Let’s assume we have $\forall x (P(x)\Rightarrow Q(x))$ is true for some propositions $P$ and $Q$ for a given domain. Instead of assuming $P(a)$ true, we assume that $Q(a)$ is true for some element $a$ of the domain. The fallacy of affirming the conclusion is a wrong argument type as follows:

$$\begin{aligned}{}
&\forall x (P(x) \Rightarrow Q(x))\\
&Q(a)\\
&\rule[0 pt]{80 pt}{0 pt}\\
&\therefore P(a)
\end{aligned}$$

Let’s look at a few examples to clarify this error.

### Example
Assume the domain set contains all the mammals. 

---
Consider the following propositions:

* $C(x)$: $x$ is a cow.
* $M(y)$: $y$ is a mammal.
---
Assume the following statement as a fact:

$$\forall x C(x) \Rightarrow M(x).$$

The above statement is saying that every cow is a mammal. Now, let's look at the wrong argument.

As Frankie is a mammal, therefore, Frankie is a cow.


## The fallacy of denying the hypothesis
Let's assume we have $\forall x (P(x)\Rightarrow Q(x))$ is true for some propositions $P$ and $Q$ for a given domain. Instead of assuming $P(a)$ true, we assume that $\neg P(a)$ is true for some element $a$ of the domain. The fallacy of denying the hypothesis is a wrong argument type as follows:

$$\begin{aligned}{}
&\forall x (P(x) \Rightarrow Q(x))\\
&\neg P(a)\\
&\rule[0 pt]{80 pt}{0.5 pt}\\
&\therefore \neg Q(a)
\end{aligned}$$

Let's look at a few examples to clarify this error.

### Example

Look at an example. 

---
Let's take the following propositions:

* $L(x)$: $x$ is a lawyer.
* $I(y)$: $y$ is intelligent.
---

Assume we are given the following statement as fact:

$$\forall x \left(L(x) \Rightarrow I(x)\right).$$

The above statement is saying that all lawyers are intelligent. As shown below, the fallacy of denying the hypothesis is a wrong argument.

Because Zack is not a lawyer, therefore, Zack is not intelligent.

## The fallacy of begging the question
The fallacy of begging the question happens while proving a statement when the same statement or its logical equivalent is used to build the argument of proof. Let's look at the following wrong proof as an example of the fallacy of begging the question.

### Example

Let's prove that $\sqrt2$ is a rational number. The faulty argument is as follows: 

Let's assume that $\sqrt2$ is a rational number; therefore, we can write it in the form of $\frac{p}{q}$, where $p$ and $q$ are integers and $q\ne0$. We can write $\sqrt2$ in the form of $\frac{p}{q}$; therefore, it is a rational number. 

## The fallacy of the inability to find a counterexample
This fallacy occurs when we observe that a property is present in the domain elements abundantly, but we are unable to come up with proof to show that this property is present in all the domain elements. In such a situation, we try to find a counterexample to prove that the property is not present in all the domain elements, and we fail in it. In such a scenario, there can be a tendency to believe that all the domain elements have the property under consideration. Simply put, this fallacy is to get convinced that all the domain elements have a particular property because we are unable to find a counterexample.

Let's look at an example of a wrong claim residing on the fallacy of being unable to find a counterexample. 

### Example

Let's deal with the claim that the following formula always generates a prime number for positive integer values.

$$y=x^2+x+41.$$

Let’s put some values for $x$ to see the output of this formula:

|$x$|$y$|Is $y$ Prime?|$x$|$y$|Is $y$ Prime?|
|-|-|-|-|-|-|
|1|43|Yes|11|173|Yes|
|2|47|Yes|12|197|Yes|
|3|53|Yes|13|223|Yes|
|4|61|Yes|14|251|Yes|
|5|71|Yes|15|281|Yes|
|6|83|Yes|16|313|Yes|
|7|97|Yes|17|347|Yes|
|8|113|Yes|18|383|Yes|
|9|131|Yes|19|421|Yes|
|10|151|Yes|20|461|Yes|



It seems to be a valid claim, and if we try to find a counterexample, it’s not obvious. It will be a fallacy if we say that the given formula always generates a prime number. 

If we examine closely, we can observe that, for $x=41$, it outputs a composite number.
$$\left(41\right)^2+41+41=41\left(43\right).$$
It seems like this formula always generates prime numbers, but we should not consider it true without proof or should not reject it without a counter-example.
 
## The fallacy of missing a case

Sometimes, proof of a statement consists of multiple cases. A common mistake is to ignore or forget one of the cases, leaving the proof incomplete. Look at the following example to understand further:

### Example
Prove that $x^2 > 0$, for any real number $x$.

There are two cases where $x$ is positive or negative. If $x$ is positive, its square is also positive, hence greater than zero. If $x$ is negative, its square is positive. Therefore, it is greater than zero.

The argument presented above is faulty because it is missing a case of $x=0$. This is when $x$ is neither positive nor negative. In that case, $\left(0\right)^2 \not > 0$. Therefore, the statement that we wanted to prove is false. The argument works if the statement is modified as follows:

$x^2 > 0$, for any real number $x\ne0$.

## The fallacy of using the “apparently obvious”

In certain situations, it is tempting to assert a statement that seems apparently obvious. Such simplistic assertions are sometimes shown to be either non-trivial or simply false. Using an assertion without proof makes an argument incomplete and sometimes wrong. 

We can take the example of Dehn’s lemma, which asserts that every simple polygon on at least four vertices has a diagonal. Its proof may start with the assertion that every polygon contains a convex vertex, namely, a vertex whose interior angle is less than $180$ degrees.
Considering this assertion as “obvious” keeps the argument incomplete. A complete proof of Dehn’s lemma must include proof of such statements or must not rely on them. In this case, this “obvious” statement does have a simple proof. We can pick the lowest vertex of the polygon and argue that it must be convex.


Another example is the proof of the use of the axiom of choice. The axiom states that given any collection of nonempty sets, it is possible to choose one element from every set. This innocent-looking statement has deep consequences in mathematics and can be used to prove some spectacular theorems. A common question in mathematics is often to ask if the proof requires the axiom of choice. 

Another example is the celebrated Jordan curve theorem, which says that any one-to-one map from the circle to the plane (a simple loop) divides the plane into two connected regions, exactly one of which is bounded (the inside). This theorem, though intuitively obvious, is not easy to prove. It is considered a cornerstone in topology. 

Introduction

Propositional Logic

Basic Operations

Assessment-I

Propositional Toolkit

Assessment-II

Logical Reasoning

Assessment-III

Quantifiers and First Order Logic

Assessment-IV

Quantified Logical Reasoning

Assessment-V

Proving Theorems

Assessment-VI

Conclusion

Errors and Mistakes in Developing Proofs