Properties of Conjunction

Properties

Just like arithmetic operations satisfy specific properties, logical operations like conjunction also satisfy certain properties. Here, we will discuss the most fundamental properties of conjunction.

Associativity

$$(p\land q)\land r \equiv (T\land F)\land T \equiv F\land T \equiv F$$

$$p\land (q\land r) \equiv T\land (F\land T )\equiv T\land F \equiv F$$

We can see that $(p\land q)\land r \equiv p\land (q\land r)$ holds for the case when $p$ is true, $q$ is false, and $r$ is true. All the possible cases are covered in the following truth table in an exhaustive manner:

$p$	$q$	$r$	$p \land q$	$q \land r$	$(p\land q) \land r$	$p \land (q \land r)$
T	T	T	T	T	T	T
T	T	F	T	F	F	F
T	F	T	F	F	F	F
T	F	F	F	F	F	F
F	T	T	F	T	F	F
F	T	F	F	F	F	F
F	F	T	F	F	F	F
F	F	F	F	F	F	F

Notice that in this truth table, the truth values in the last two columns are exactly the same. This shows that:

$$(p \land q) \land r \equiv p \land (q \land r).$$

Although the above truth table formally proves the associativity of conjunction, it is more intuitive to observe that both $(p \land q) \land r$ and $p \land (q \land r)$ are true if and only if the three propositions $p, q,$ and $r$ are all simultaneously true.

We can also obtain the same result if we use the $0/1$-notation. In that case, conjunction corresponds to the product of two variables. Consequently, $(pq)r = p(qr)$ simply follows from the associative law for multiplication.

Given three propositions $p, q$, and $r$, the statements $(p \land q) \land r$ and $p \land (q \land r)$ are compound propositions. We can think of each $p,q$, and $r$ as atomic propositions. The associative law asserts that these two compound statements are equivalent. More precisely, it claims that the associative law holds regardless of what truth values $p, q$, and $r$ take. Therefore, here logical equivalence is a very meaningful terminology: it claims the validity of eight different possibilities.

Let’s understand this by taking an analogy with real numbers. Consider the equation:

$$\begin{equation} (a+b)^2 = a^2 + 2ab + b^2.\end{equation}$$

This equation is true for all real numbers $a, b$, and $c$. In this case, $a, b,$, and $c$ are called variables: they are the atoms. In particular, the equation says that,

$$( \pi + e )^2 = \pi^2 + 2 \pi e + e^2 .$$

Although the exact values of $\pi$ and $e$ are impossible to write, this is not a requirement. It is enough to know that they are real numbers.

We call $p,q$, and $r$ boolean variables. Boolean variables can take only one of two possible values: true and false. The associative law holds regardless of the individual values of the boolean variables, just like Equation (1) holds irrespective of the values taken by real variables.

It is customary to write equations using the equal ($=$) sign, and we write logical equivalences with the logical equivalence ($\equiv$) sign.

In Equation (1), we do not bother about where the real numbers came from. The variables $a$ and $b$ may have been complicated measurements made by an astronomical observation costing large amounts of resources, yet the equation will hold.

Similarly, in the logical laws, we do not bother to find the truth value of the individual propositions or boolean variables. What matters is that they are either true or false but not both; that is, they are indeed propositions.

---

Consider the three propositions:

• $D$: The dinosaurs’ extinction was due to a large meteor impact.
• $P$: I have a pet dog.
• $B$: Broccoli is good for health.

---

Individually, their truth values are hard to establish. Yet, the associative law tells us that to make all three claims, there are two equivalent alternatives to expressing this:

$$(D \land P) \land B,$$

and

$$D \land (P \land B).$$

Since we can switch parenthesis, we can simply write this as,

$$D \land P \land B.$$

Logical equivalence is a far more fundamental concept than algebraic equations. Yet, we are more comfortable with mathematical equations because we are not taught logic formally at an early age.

Commutativity

$p$	$q$	$p \land q$	$q \land p$
T	T	T	T
T	F	F	F
F	T	F	F
F	F	F	F

We can observe that the last two columns of this truth table are identical. Once again, we can argue that $p \land q$ and $q \land p$ are both true only when both $p$ and $q$ are simultaneously true.

Given $n$ propositions,

$$p_{1},p_{2},...,p_{n},$$

we can take their conjunction; that is, we can construct a new proposition

$$p \equiv p_{1}\land p_{2}\land \cdots \land p_{n} .$$

A convenient way to represent a conjunction of many variables is the iterative notation. In this notation, the above conjunction is written as:

$$p \equiv \bigwedge_{i=1}^n p_i.$$

With commutativity and associativity in hand, we can arrange these $n$ propositions on the right-hand side of the equivalence above in any of the $n!$ possible ways. Furthermore, we can parenthesize the conjunction in many possible ways, and the resulting compound proposition will remain equivalent to $p$. The proposition $p$ will only be true when all the $n$ propositions, $p_{1}$, $p_{2}$, …, $p_{n}$, are true. It will be false if at least one of the $n$ propositions is false.

Quiz