Logic

True and False

True and false denoted by \( T, F \) respectively are distinct symbols ( \( T \neq F \) ).

Predicate

A predicate is a function \( f : X \to \left\{ T, F \right\} \) for some set \( X \)

Logical And

We define the function \( \lor : \left\{ T, F \right\} \times \left\{ T, F \right\} \to \left\{ T, F \right\} \) by the following table: \[ \begin{array}{|c c|c|} \hline T & T & T\\ T & F & F\\ F & T & F\\ F & F & F\\ \end{array} \] note that we use infix notation for this function.

Logical Negation

We define the function \( \neg : \left\{ T, F \right\} \to \left\{ T, F \right\} \) by the following table: \[ \begin{array}{|c|c|} p & \neg p\\ % Use & to separate the columns \hline % Put a horizontal line between the table header and the rest. T & F \\ F & T \\ \end{array} \]

When working with the negation, we almost never include the parenthesis unless it is really necessary, so you'll see \( \neg T = F \) rather than the standard function notation: \( \neg \left( T \right) = F \)

Logical Or

We define \( \lor : \left\{ T, F \right\} \times \left\{ T, F \right\} \to \left\{ T, F \right\} \) as \[ p \lor q := \neg \left( \neg p \land \neg q \right) \]

Rightward Logical Implication

We define \( \implies : \left\{ T, F \right\} \times \left\{ T, F \right\} \to \left\{ T, F \right\} \) as \[ p \implies q := \neg p \lor q \]

Note that even though the above doesn't seem intuitive, it exactly matches your intuition, we know that the only time an implication can be false is when we have the antecdent to be true, but the result false, which is exactly the case for the above definition.

Usually \( p \) is called the "antecedent" and \( q \) the "consequent".

Leftward Logical Implication

We define \( \impliedby : \left\{ T, F \right\} \times \left\{ T, F \right\} \to \left\{ T, F \right\} \) as \[ p \impliedby q := q \implies p \]

Logical Bi-Implication

We define \( \iff : \left\{ T, F \right\} \times \left\{ T, F \right\} \to \left\{ T, F \right\} \) as \[ p \iff q := \left( p \implies q \right) \land \left( p \impliedby q \right) \]

Note that in writing mathematicians will use the word "iff" as short-hand for if and only if, which represents the bi-implication.

Logical And True iff both Arguments are True

\[ p \land q = T \iff p = T \land q = T \]

TODO

The above proof might feel a bit meta, indeed, we are using the definition of "iff" that we just defined on this page. The "metaness" is coming from the fact that the "iff" we use in english language is actually the bi-implication which we formally define a bit later in the page (which in-turn is then defined in terms of logical and eventually).

Logical Exclusive Or

We define \( \oplus : \left\{ T, F \right\} \times \left\{ T, F \right\} \to \left\{ T, F \right\} \) as \[ p \oplus q := \left( \neg p \land q \right) \lor \left( p \land \neg q \right) \]

"XOR" is sometimes used in place of it's regular name.

Addition Mod 2 is Associative

Suppose that we have the function \( p : \left\{ 0, 1 \right\} \to \left\{ 0, 1 \right\} \) defined such that

\( p \left( 0, 0 \right) = p \left( 1, 1 \right) = 0 \)
\( p \left( 0, 1 \right) = p \left( 1, 0 \right) = 1 \)

then it is associative

Let \( a, b, c \in \left\{ 0, 1 \right\} \), and consider the equation \[ p \left( p \left( a, b \right), c \right) = p \left( a, p \left( b, c \right) \right) \] when all of \( a, b, c = 0 \) we have \( \left( p \left( 0, 0 \right) = p \left( 0, 0 \right) \right) \), when exactly one of them is zero, then without loss of generality we get the equation \( p \left( 1, 0 \right) = p \left( 0, 1 \right) \), if exactly two of them are ones then we either get an equation of the form \( p \left( 0, 0 \right) = p \left( 1, 1 \right) \) which holds, or one of the form \( p \left( 1, 1 \right) = p \left( 1, 1 \right) = 0 \), finally if all are 1 then we get \( p \left( 0, 1 \right) = p \left( 1, 0 \right) \), since all equations hold true from the definition then \( p \) is associative.

Exclusive Or is Associative

For any \( x _ 1, x _ 2, x _ 3 \in \left\{ T, F \right\} \) we have that \[ \left( x _ 1 \oplus x _ 2 \right) \oplus x _ 3 = x _ 1 \oplus \left( x _ 2 \oplus x _ 3 \right) \]

Consider the bijective mapping \( f \left( T \right) = 1 \) and \( f \left( F \right) = 0 \) we can see that \( f \left( a \oplus b \right) = p \left( f \left( a \right), f \left( b \right) \right) \), the it follows that \( f \left( \cdot \oplus \cdot \right) \) is associative, therefore so is \( \oplus \)

Sum of Ones Mod 2 becomes 0 iff Even

Since \( p \) is associative let's use it as a binary operation and temporarily label it as \( + \) then consider a sequence \( \left( a _ n \right): \mathbb{ N } _ 0 \to \left\{ 0, 1 \right\} \) \[ \sum _ { i = 0 } ^ k a _ n = 0 \] if and only if \( \lvert \left\{ a _ j: a _ j = 1 \right\} \rvert \) is even.

Induction I believe on even numbers + 2 each time.

Exclusive Or Evaluates to True iff an odd number of arguments are True

\[ x _ 1 \oplus x _ 2 \oplus \cdots \oplus x _ k = T \] if and only if \[ \sum _ { i = 1 } ^ k x _ i \] is odd.

Tautology

We say that a predicate \( P : X \to \left\{ T, F \right\} \) is a tautology iff for every \( x \in A, P \left( x \right) = T\).

In mathematics, when we prove a statement, we are actually showing that it is a tautology.

Contrapositive

The following is a tautology \[ \left( p \implies q \right) \iff \left( \neg q \implies \neg p \right) \]

Forced Consequence

The following is a tautology \[ \left( T \implies p \right) \iff p = T \]

Arbitrary And

For any \( n \in \mathbb{ N } _ 0 \) we define arbitrary and as the predicate \( \bigwedge: \left\{ T, F \right\} ^ n \to \left\{ T, F \right\} \) such that for any \( X = \left( x _ 1, \ldots , x _ n \right) \in \left\{ T, F \right\} ^ n \). \[ \bigwedge X = T \] if and only if the following statement holds true \[ \forall i \in \left\{ 1, \ldots , n \right\}, x _ i = T \]

Empty And is True

Suppose that \( X = \left( \right) \) (the empty tuple), then \[ \bigwedge X = T \] where we've used the the arbitrary and

It holds vacuously true.

Arbitrary And Indexed Notation

Suppose that, \( a, b \in \mathbb{ Z } \) and \( p _ a, \ldots p _ b \in \left\{ T, F \right\} \) then we define \[ \bigwedge _ { i = a } ^ b p _ i := \bigwedge \left( p _ a, \ldots , p _ b \right) \] where we've used the the arbitrary and

Arbitrary And Indexed Notation with Reversed Integers is True

Suppose \( a > b \in \mathbb{ Z } \) and \[ \bigwedge _ { i = a } ^ b p _ i = T \]

Recall that \[ \bigwedge _ { i = a } ^ b p _ i = \bigwedge \left( p _ a, \ldots , p _ b \right) \] But at the same time \( \left( p _ a, \ldots, p _ b \right) = \left( \right) \) because \( a \gt b \) therefore \( \bigwedge \left( p _ a, \ldots , p _ b \right) = \bigwedge \left( \right) \) and therefore evaluates to true.

Arbitrary And Expanded Notation

Suppose that \( p _ 1, \ldots p _ n \in \left\{ T, F \right\} \) then we define \[ p _ 1 \land \cdots \land p _ n := \bigwedge _ { i = 1 } ^ n p _ i \] where we've used the previous definition

Arbitrary Or

Uniqueness

Suppose that \( P : X \to \left\{ T, F \right\} \) is a predicate, then we say that there is a unique element which satisfies \( P \) over the set \( S \subseteq X \) when \[ \exists s \in S, P \left( s \right) \land \forall t \in S, P \left( t \right) \implies t = s \]

For Every, There Exists is a Function

The statement \[ \forall x \in X, \exists y \in Y, P \left( x, y \right) \] is equivalent to \[ \exists f: X \to Y, \forall x \in X, P \left( x, f \left( x \right) \right) \]