Logical Connective

Logical connectives are operations over propositions that create a compound statement. They are used to chain propositions to create more complex logic. While the word connective generally implies a binary operations (i.e. two inputs), the negation operator is an exception.

There are 5 main logical connectives.

• Negation (NOT)
• Conjunction (AND)
• Disjunction (OR)
• Implication (IMPLIES)
• Bi-implication (IFF)

Connectives can be constructed!

With just negation and conjunction, it is possible to construct every other connective! For example, the disjunction connective can be constructed by:

$$P\vee Q\equiv \neg (\neg P\wedge \neg Q)$$

Negation §

The negation operator is $\neg$ and inverts the truth table of the original proposition, i.e. every false is true and every true is false. It is a unary operator, and only requires one input:

Truth Table §

$P$	$\neg P$
T	F
F	T
^truth-table-not

It is equivalent to the NOT Logic Gate.

Conjunction §

Equivalent to the AND logic gate.

The conjunction operation is $\wedge$ and is a binary operator. As the name implies, is true if both it’s operands are true, and false otherwise:

Truth Table §

$P$	$Q$	$P\wedge Q$
T	T	T
T	F	F
F	T	F
F	F	F
^truth-table-and

Disjunction §

Equivalent to the OR logic gate.

The disjunction operation is $\vee$ and is a binary operator. As the name implies, is true if either of it’s operands are true, and false only if both operands are false:

Truth Table §

$P$	$Q$	$P\vee Q$
T	T	T
T	F	T
F	T	T
F	F	F
^truth-table-or

Material Implication §

Also called conditional

The implication operation is $\to$ and is heavily used in proofs. $p\to q$ is false only when $P$ is true and $Q$ is false. This makes sense because if we define a condition $P$ and the consequence $Q$, we want it to hold that whenever our condition is true, so should our consequence. If this does not happen, there is no conditional link between $P$ and $Q$.

Note that the implication $p\to q$ is logically equivalent to $\neg p\vee q$

Implication Properties §

Unlike disjunction and conjunction, implication has some extra properties:

• Non-symmetric: $p\to q\not\equiv q\to p$
• Right-associative: When having multiple implications, we evaluate them right-to-left: $P\to Q\to R$ should be evaluated as $(P\to (Q\to R))$ (so we start evaluating from the righ first)

Truth Table §

$P$	$Q$	$p\to q$	$q\to p$
T	T	T	T
T	F	F	T
F	T	T	F
F	F	T	T
^truth-table-implies

Contrapositive §

The logical statements $p\to q$ and it’s contrapositive $\neg q\to \neg p$ are logically equivalent

$P$	$Q$	$\neg q$	$\neg p$	$p\to q$	$\neg q\to \neg p$
T	T	F	F	T	T
T	F	T	F	F	F
F	T	F	T	T	T
F	F	T	T	T	T

A proof by contrapositive uses this fact.

Vacuous Truth §

If we have the implication $p\to q$ and $P$ is known to be always false, i.e. $\perp \to q$ always holds true, (see truth table above). This is known as a vacuous truth. Examples include:

• The empty set satisfies most properties due to this.

Material Equivalence §

The equivalence operator is $\leftrightarrow$ and it means the exact same thing as iff (if and only if), also used heavily in proofs. $p\leftrightarrow q$ is symmetric and is true whenever $P$ and $Q$ have the same value, whether true or false.

It is logically equivalent to the conjunction of an implication and it’s symmetrical equivalent:

$$p\leftrightarrow q\equiv (p\to q)\wedge (q\to p)$$

Truth Table §

$P$	$Q$	$p\leftrightarrow q$
T	T	T
T	F	F
F	T	F
F	F	T

• The operation is equivalent to the logic gate XNOR (Exclusive NOR)
• We can show the

Chaining §

If multiple logical equivalences are being chained together, we can ‘simplify’ them:

$$\begin{array}{rl}& a\leftrightarrow b\leftrightarrow c\\ & \equiv ((a\to b)\wedge (b\to a))\leftrightarrow c\\ & \equiv [((a\to b)\wedge (b\to a))\to c]\wedge [c\to ((a\to b)\wedge (b\to a))]\\ & \equiv \end{array}$$

#todo

$$a\leftrightarrow b\leftrightarrow c\equiv a\to b\to c\to a$$