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

# What is a conjunction?

A **conjunction** is a binary operation in the sense that it requires two operands. When two propositions are connected using a conjunction operation, it becomes a new proposition whose value depends on the truth values of the operands. Another name for the conjunction operator is the **AND** operator. 
## Example

---
Consider the following propositions:
* $D$: Joseph is taking a discrete mathematics course. 
* $C$: Joseph is taking a calculus course.

---

Let’s make a new proposition $J$ by taking the conjunction of $D$ and $C$. 

* $J$: “Joseph is taking a discrete mathematics course” _and_ “Joseph is taking a calculus course.”

We can simplify $J$ without changing the meaning.

* $J$: Joseph is taking both discrete mathematics and calculus courses. 


We use the $\land$ symbol to represent the conjunction operation. So, 

$$J \equiv D \land C.$$


The truth value of $J$ is _true_ only when $D$ and $C$ both are _true_ and  _false_ otherwise.

It is intuitive to think of conjunction as an “and” in everyday language. In fact, that is the reason conjunction is also called a logical AND.


## Truth table

Let $p$ and $q$ be arbitrary propositions.
The exact definition of conjunction is given by defining the truth value of 
$p \land q$ in all possible cases. This is 
done by specifying a 
truth table. Let's use T to represent _true_ and F to represent _false_. A **truth table** enumerates all possible cases of the truth values of $p$ and $q$ and describes what the truth value will be for $p \land q$.

The truth table defining conjunction is given below: 

|$p$|$q$| $p \land q$|
|-|-|-|
|T|T|T|
|T|F|F|
|F|T|F|
|F|F|F|

In computer science, the truth values are often represented by $0$ and $1$. Where $0$ represents false, and $1$ represents true. We call this the $0/1$-notation. In this notation,  $p \land q$ is defined by the
following table:

|$p$|$q$| $p \land q$|
|-|-|-|
|$1$|$1$|$1$|
|$1$|$0$|$0$|
|$0$|$1$|$0$|
|$0$|$0$|$0$|



A keen observer must have realized that each entry in the last column can be obtained by multiplying the corresponding entries in the first two columns. For this reason $p \land q$ is sometimes denoted by $pq$, where the symbol of multiplication is normally skipped. 

## Circuit diagram

Now, let’s illustrate the concept of conjunction through circuit diagrams. Here is the key that will help you in understanding them:


When both $p$ and $q$ are _false_, both switches are off, and no electricity reaches the bulb in the following circuit diagram. Therefore, the bulb is off, indicating that $p \wedge q$ is false. 

When $p$ is _true_ and $q$ is _false_, the circuit is not complete and the bulb is off. This indicates that $p \land q$ is _false_.

 

Similarly, when $p$ is _false_ and $q$ is _true_, the circuit is not complete and the bulb is off. This indicates that $p \land q$ is _false_.


Finally, when both  $p$ and $q$ are  _true_, both switches are on, and the circuit is complete. The bulb is on, indicating that  $p \land q$ is _true_. 

If $q_3$ is a conjunction of two propositions $q_1$ and $q_2$, then $q_3$ is true if

If <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msub><mi>q</mi><mn>3</mn></msub></mrow><annotation encoding="application/x-tex">q_3</annotation></semantics></math>q3​ is a conjunction of two propositions <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msub><mi>q</mi><mn>1</mn></msub></mrow><annotation encoding="application/x-tex">q_1</annotation></semantics></math>q1​ and <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msub><mi>q</mi><mn>2</mn></msub></mrow><annotation encoding="application/x-tex">q_2</annotation></semantics></math>q2​, then <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msub><mi>q</mi><mn>3</mn></msub></mrow><annotation encoding="application/x-tex">q_3</annotation></semantics></math>q3​ is true if

David is taking psychology and philosophy courses.

Sam is taking mathematics and history courses.

David is taking only mathematics and history courses.

Both David and Sam are taking philosophy and history courses.

Let

<center>

$\begin{cases}\:d: \:\mathrm{David}\:\mathrm{is}\:\mathrm{taking}\:\mathrm{a}\:\mathrm{ philosophy}\:\mathrm{course.} \\\
s: \:\mathrm{Sam}\:\mathrm{is}\:\mathrm{taking}\:\mathrm{a}\:\mathrm{ history}\:\mathrm{course.}\\\
t \equiv d \wedge s \end{cases}$
</center>


Which statement makes $t$ necessarily false?

Let
<center>
<math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo fence="true">{</mo><mtable rowspacing="0.36em" columnalign="left left" columnspacing="1em"><mtr><mtd><mstyle scriptlevel="0" displaystyle="false"><mrow><mtext> </mtext><mi>d</mi><mo>:</mo><mtext> </mtext><mrow><mi mathvariant="normal">D</mi><mi mathvariant="normal">a</mi><mi mathvariant="normal">v</mi><mi mathvariant="normal">i</mi><mi mathvariant="normal">d</mi></mrow><mtext> </mtext><mrow><mi mathvariant="normal">i</mi><mi mathvariant="normal">s</mi></mrow><mtext> </mtext><mrow><mi mathvariant="normal">t</mi><mi mathvariant="normal">a</mi><mi mathvariant="normal">k</mi><mi mathvariant="normal">i</mi><mi mathvariant="normal">n</mi><mi mathvariant="normal">g</mi></mrow><mtext> </mtext><mi mathvariant="normal">a</mi><mtext> </mtext><mrow><mi mathvariant="normal">p</mi><mi mathvariant="normal">h</mi><mi mathvariant="normal">i</mi><mi mathvariant="normal">l</mi><mi mathvariant="normal">o</mi><mi mathvariant="normal">s</mi><mi mathvariant="normal">o</mi><mi mathvariant="normal">p</mi><mi mathvariant="normal">h</mi><mi mathvariant="normal">y</mi></mrow><mtext> </mtext><mrow><mi mathvariant="normal">c</mi><mi mathvariant="normal">o</mi><mi mathvariant="normal">u</mi><mi mathvariant="normal">r</mi><mi mathvariant="normal">s</mi><mi mathvariant="normal">e</mi><mi mathvariant="normal">.</mi></mrow></mrow></mstyle></mtd></mtr><mtr><mtd><mstyle scriptlevel="0" displaystyle="false"><mrow><mtext> </mtext><mi>s</mi><mo>:</mo><mtext> </mtext><mrow><mi mathvariant="normal">S</mi><mi mathvariant="normal">a</mi><mi mathvariant="normal">m</mi></mrow><mtext> </mtext><mrow><mi mathvariant="normal">i</mi><mi mathvariant="normal">s</mi></mrow><mtext> </mtext><mrow><mi mathvariant="normal">t</mi><mi mathvariant="normal">a</mi><mi mathvariant="normal">k</mi><mi mathvariant="normal">i</mi><mi mathvariant="normal">n</mi><mi mathvariant="normal">g</mi></mrow><mtext> </mtext><mi mathvariant="normal">a</mi><mtext> </mtext><mrow><mi mathvariant="normal">h</mi><mi mathvariant="normal">i</mi><mi mathvariant="normal">s</mi><mi mathvariant="normal">t</mi><mi mathvariant="normal">o</mi><mi mathvariant="normal">r</mi><mi mathvariant="normal">y</mi></mrow><mtext> </mtext><mrow><mi mathvariant="normal">c</mi><mi mathvariant="normal">o</mi><mi mathvariant="normal">u</mi><mi mathvariant="normal">r</mi><mi mathvariant="normal">s</mi><mi mathvariant="normal">e</mi><mi mathvariant="normal">.</mi></mrow></mrow></mstyle></mtd></mtr><mtr><mtd><mstyle scriptlevel="0" displaystyle="false"><mrow><mtext> </mtext><mi>t</mi><mo>≡</mo><mi>d</mi><mo>∧</mo><mi>s</mi></mrow></mstyle></mtd></mtr></mtable></mrow><annotation encoding="application/x-tex">\begin{cases}\:d: \:\mathrm{David}\:\mathrm{is}\:\mathrm{taking}\:\mathrm{a}\:\mathrm{ philosophy}\:\mathrm{course.} \\\
s: \:\mathrm{Sam}\:\mathrm{is}\:\mathrm{taking}\:\mathrm{a}\:\mathrm{ history}\:\mathrm{course.}\\\
t \equiv d \wedge s \end{cases}</annotation></semantics></math>⎩<svg xmlns="http://www.w3.org/2000/svg" width='0.8889em' height='0.316em' style='width:0.8889em' viewBox='0 0 888.89 316' preserveAspectRatio='xMinYMin'><path d='M384 0 H504 V316 H384z M384 0 H504 V316 H384z'/></svg>⎨<svg xmlns="http://www.w3.org/2000/svg" width='0.8889em' height='0.316em' style='width:0.8889em' viewBox='0 0 888.89 316' preserveAspectRatio='xMinYMin'><path d='M384 0 H504 V316 H384z M384 0 H504 V316 H384z'/></svg>⎧​d:Davidistakingaphilosophycourse. s:Samistakingahistorycourse. t≡d∧s​
</center>
Which statement makes <math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>t</mi></mrow><annotation encoding="application/x-tex">t</annotation></semantics></math>t necessarily false?

Test your understanding of conjunction.

Test your understanding of conjunction.

Learn to join two or more propositions using the conjunction operation.

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

Conjunction