nyuuzyou/wikis huggingface dataset:
Function Simple iff Positive and Negative Parts Simple

== Theorem ==
Let $\left({X, \Sigma}\right)$ be a measurable space.
Let $g: X \to \overline{\R}$ be an extended real-valued function.
Then $g$ is a simple function its positive part $g^+$ and negative part $g^-$ are simple functions.
== Proof ==
=== Necessary Condition ===
Suppose $g$ is a simple function.
By Positive Part of Simple Function is Simple Function, so is $g^+$.
By Negative Part of Simple Function is Simple Function, so is $g^-$.
=== Sufficient Condition ===
Suppose $g^+$ and $g^-$ are simple functions.
From Difference of Positive and Negative Parts:
:$g = g^+ - g^-$
Hence $g$ is simple, by Pointwise Difference of Simple Functions is Simple Function.
== Sources ==
* : $\S 8$: Problem $5$
Category:Simple Functions
Category:Positive Parts
Category:Negative Parts
Function f is Big-O of g iff g is Big-Omega of f

== Theorem ==
Let $f: \N \to \R, g: \N \to \R$ be two real sequences, expressed here as real-valued functions on the set of natural numbers $\N$.
Then:
:$\map f n \in \map \OO {\map g n}$
:
:$\map g n \in \map \Omega {\map f n}$ 
where:
:$\OO$ denotes big-$\OO$ notation
:$\Omega$ denotes big-$\Omega$ notation.
== Proof ==
Recall the definitions:
:$\map \Omega f = \set {g: \N \to \R: \exists c_1 \in \R_{>0}: \exists n_1 \in \N: \forall n > n_1: 0 \le c_1 \cdot \size {\map f n} \le \size {\map g n} }$
:$\map \OO g = \set {f: \N \to \R: \exists c_2 \in \R_{>0}: \exists n_2 \in \N: \forall n > n_2: 0 \le \size {\map f n} \le c_2 \cdot \size {\map g n} }$
for some $n_1, n_2 \in \N$.
Hence:
:If $g \in \map \Omega f$, then $\forall n > n_1: \exists c_1 > 0 : \map g n \ge c_1 \cdot \map f n$
:If $f \in \map \OO g$, then $\forall n > n_2: \exists c_2 > 0 : \map f n \le c_2 \cdot \map g n$
First let us assume that $n \ge \max \set {n_1, n_2}$ in all the below work.
=== Sufficient Condition ===
Let $g \in \map \Omega f$.
Then:
Hence we have:
:$g \in \map \Omega f \implies f \in \map \OO g$
=== Necessary Condition ===
Let $f \in \map \OO g$.
Then:
Hence we have:
:$f \in \map \OO g \implies g \in \map \Omega g$
Both conditions have been proven, hence:
:$f \in \map \OO g \iff g \in \map \Omega f$
== Sources ==
* : $2$: Growth of Functions: $2.1$ Asymptotic Notation: $\Omega$-notation
Category:Big-O Notation
Category:Big-Omega Notation
Function in Differentiability Class 1 is also in Continuity Class

== Theorem ==
Let $f$ be a real function. 
Let $f$ be an element of differentiability class $C^1$.
Then $f$ is also an element of the class $C$ of continuous real functions.
== Proof ==
By definition of $C^1$, $f \in C^1$ $f$ is differentiable.
By definition of $C$, $f \in C$ $f$ is continuous.
The result follows from Differentiable Function is Continuous.
== Sources ==
* : $1$ Partial Differentiation: $\S 2$. Functions of One Variable: $2.2$ Derivatives
Category:Differentiability Classes
Function of Bounded Variation is Bounded

== Theorem ==
Let $a, b$ be real numbers with $a < b$.
Let $f : \closedint a b \to \R$ be a function of bounded variation.
Then $f$ is bounded.
== Proof ==
We use the notation from the definition of bounded variation.
Since $f$ is of bounded variation, there exists $M \ge 0$ such that:
:$\map {V_f} {P ; \closedint a b} \le M$
for all finite subdivisions $P$ of $\closedint a b$.
Let $x$ be a real number with:
:$a < x < b$
Then $\set {a, x, b}$ is a finite subdivision of $\closedint a b$.
We have: 
:$\map {V_f} {\set {a, x, b} ; \closedint a b} = \size {\map f x - \map f a} + \size {\map f b - \map f x}$
Since $x \in \openint a b$ was arbitrary, we therefore have: 
:$\size {\map f x - \map f a} + \size {\map f b - \map f x} \le M$
for all $x \in \openint a b$.
We have:
So for all $x \in \openint a b$, we have: 
:$\size {\map f x} \le \size {\map f a} + M$
Since $M \ge 0$, this inequality is also satisfied for $x = a$. 
We therefore have: 
:$\size {\map f x} \le \map \max {\size {\map f a} + M, \size {\map f b} }$
for all $x \in \closedint a b$.
So $f$ is is bounded.
== Sources ==
* : $\S 6.3$: Functions of Bounded Variation: Theorem $6.7$
Category:Bounded Variation
Function of Discrete Random Variable

== Theorem ==
Let $X$ be a discrete random variable on the probability space $\struct {\Omega, \Sigma, \Pr}$.
Let $g: \R \to \R$ be any real function.
Then $Y = g \sqbrk X$, defined as:
:$\forall \omega \in \Omega: \map Y \omega = g \sqbrk {\map X \omega}$
is also a discrete random variable.
== Proof ==
As $\Img X$ is countable, then so is $\Img {g \sqbrk X}$.
Now consider $g^{-1} \sqbrk Y$.
We have that:
:$\forall x \in \R: \map {X^{-1} } x \in \Sigma$
We also have that:
:$\ds \forall y \in \R: \map {g^{-1} } y = \bigcup_{x: \map g x = y} \set x$
But $\Sigma$ is a sigma-algebra and therefore closed for unions.
Thus:
:$\forall y \in \R: \map {X^{-1} } {\map {g^{-1} } y} \in \Sigma$
Hence the result.
== Sources ==
* : $\S 2.3$: Functions of discrete random variables
Category:Probability Theory
Function of Exponential Order of Scalar Multiple

== Theorem ==
Let $f: \R \to \F$ be a function, where $\F \in \set {\R, \C}$.
Let $\lambda$ be a real constant.
Let $\map f t$ be of exponential order $a$.
Then the function defined by $t \mapsto \map f {\lambda t}$ is of exponential order $a\lambda$.
== Proof ==
The result follows by the definition of exponential order.
Category:Exponential Order
Function of Two Discrete Random Variables

== Theorem ==
Let $\struct {\Omega, \Sigma, \Pr}$ be a probability space.
Let $X$ and $Y$ be discrete random variables on $\struct {\Omega, \Sigma, \Pr}$.
Let $g: \R^2 \to \R$ be a real-valued function.
Then $Z = \map g {X, Y}$, defined as:
:$\forall \omega \in \Omega: \map Z \omega = \map g {\map X \omega, \map Y \omega}$
is also a discrete random variable.
=== Corollary ===
Let $\struct {\Omega, \Sigma, \Pr}$ be a probability space.
Let $X_1, X_2, \ldots, X_n$ be discrete random variables on $\struct {\Omega, \Sigma, \Pr}$.
Then $Z = \map g {X_1, X_2, \ldots, X_n}$, defined as:
:$\forall \omega \in \Omega: \map Z \omega = \map g {\map {X_1} \omega, \map {X_2} \omega, \ldots, \map {X_n} \omega}$
is also a discrete random variable.
== Proof ==
As $\Img X$ and $\Img Y$ are countable, then so is $\Img {\map g {X, Y} }$.
Now consider $\map {g^{-1} } Z$.
We have that:
* $\forall x \in \R: \map {X^{-1} } x \in \Sigma$.
* $\forall y \in \R: \map {Y^{-1} } x \in \Sigma$.
We also have that:
: $\ds \forall z \in \R: \map {g^{-1} } z = \bigcup_{\tuple {x, y}: \map g {x, y} = z} \set {\tuple {x, y} }$
But $\Sigma$ is a sigma-algebra and therefore closed for unions.
Thus $\forall z \in \R: \map {g^{-1} } z \in \Sigma^2$.
Now consider $\tuple {v, w} \in \map {g^{-1} } Z$.
As $\Sigma$ is a sigma-algebra it follows directly that:
*$\forall x \in v: \map {X^{-1} } x \in \Sigma$
*$\forall y \in w: \map {Y^{-1} } y \in \Sigma$
Hence the result.
=== Proof of Corollary ===
Follows straightforwardly by induction from the main result.
Category:Probability Theory
Function that Satisfies Axioms of Uncertainty

== Theorem ==
Let $n \in \N$ be a natural number.
Let $p_1, p_2, \dotsc, p_n$ be real numbers such that:
:$\forall i \in \set {1, 2, \dotsc, n}: p_i \ge 0$
:$\ds \sum_{i \mathop = 1}^n p_i = 1$
Let $\map H {p_1, p_2, \ldots, p_n}$ be a real-valued function which satisfies the axioms of uncertainty.
Then:
:$\ds \map H {p_1, p_2, \ldots, p_n} = -\lambda \sum_{i \mathop = 1}^n p_i \log_b p_i$
where:
:$\lambda \in \R_{>0}$
:$b \in \R_{>1}$
Thus the uncertainty function satisfies these axioms.
== Proof ==
== Also see ==
* Uncertainty Function satisfies Axioms of Uncertainty
== Sources ==
* : $\S 1$: Entropy = uncertainty = information: $1.1$ Uncertainty: Theorem $1$
Category:Uncertainty
Category:Function that Satisfies Axioms of Uncertainty
Function that Satisfies Axioms of Uncertainty/Proof

== Theorem ==
== Proof ==
Let $g: \Z \to \R$ be the mapping defined as:
:$(1): \quad \map g n = \map H {\dfrac 1 n, \dfrac 1 n, \dotsc, \dfrac 1 n}$
Let $k \in \Z_{>0}$.
We have:
Let $r, s \in \R$ and $n \in \Z_{>0}$.
Let $m$ satisfy:
:$(3): \quad r^m \le s^n \le r^{m + 1}$
From $(2)$ and Axiom 5:
:$\map g {r^m} \le \map g {s^n} \le \map g {r^{m + 1} }$
and so:
:$m \map g r \le n \map g s \le \paren {m + 1} \map g r$
Taking logarithms of $(3)$:
:$m \ln r \le n \ln s \le \paren {m + 1} \ln r$
which holds because Logarithm is Strictly Increasing.
Hence:
:$\size {\dfrac {\map g s} {\map g r} - \dfrac {\map \ln s} {\map \ln r} } \le \dfrac 1 n$
We have that $n$ is an arbitrary positive integer.
Hence the of the above can be made arbitrarily small.
Hence:
:$\size {\dfrac {\map g s} {\map g r} - \dfrac {\map \ln s} {\map \ln r} } = 0$
and so:
:$(4): \quad \dfrac {\map g s} {\map \ln s} = \dfrac {\map g r} {\map \ln r} = A$
for some constant $A$.
That is:
:$(5): \quad \map g s = A \map \ln s$
for $s \in \Z$.
Let $p$ be a rational number such that $0 < p < 1$.
That is:
:$p = \dfrac t n$
for some integers $t$ and $n$.
Thus we can set:
:$q = 1 = p = \dfrac {n - t} n$
Axiom 8 gives:
:$\map g n = \map H {\dfrac 1 n, \dfrac 1 n, \dotsc, \dfrac 1 n} = \map H {\dfrac 1 n, \dfrac {n - t} n} + \dfrac t n \map g t + \dfrac {n - t} n \map g {n - t}$
Using $(5)$ and gathering up terms:
:$\map H {\dfrac 1 n, \dfrac {n - t} n} = A \paren {\dfrac t n} \ln \dfrac t n + A \paren {\dfrac {n - t} n} \ln \dfrac {n - t} n$
which gives:
:$(6): \quad \map H {p, 1 - p} = A p \ln p + A \paren {1 - p} \, \map \ln {1 - p}$
for rational $p$.
Axiom 6 gives that $H$ is continuous.
Thus $(6)$ extends to all real $p$ such that $0 < p < 1$.
It remains to be demonstrated that:
:$(7): \quad \map H {p_1, p_2, \ldots, p_N} = A \displaystyle \sum_{i \mathop = 1}^N p_i \ln p_i$
where:
:$0 < p_i < 1$ for all $p_i$
:$p_1 + p_2 + \dotsb + p_N$
for all $N \in \Z_{\ge 2}$.
We have demonstrated that $(7)$ is true for $N = 2$.
Assume the induction hypothesis that $(7)$ holds for $N = k$.
Consider:
:$\map H {p_1, p_2, \ldots, p_k, p_{k + 1} }$
Let:
:$p = p_1 + p_2 + \dotsb + p_k$
:$q = p_{k + 1}$
and apply Axiom 8:
Hence the result from the Principle of Mathematical Induction.
== Sources ==
* : Appendix $1$: Proof of the uniqueness theorem that $H = -\sum p_i \log p_i$
Category:Function that Satisfies Axioms of Uncertainty
Function which is Zero except on Countable Set of Points is Null

== Theorem ==
Let $S \subseteq \R$ be a subset of $\R$ such that $S$ is countable, either finite or countably infinite.
Let $f: \R \to \R$ be a real function such that:
:$\forall x \in \R \setminus S: \map f x = 0$
That is, except perhaps for the elements of $S$, the value of $f$ is zero.
Then $f$ is a null function.
== Proof ==
This is an instance of Measurable Function Zero A.E. iff Absolute Value has Zero Integral.
== Sources ==
* : Chapter $1$: The Laplace Transform: Some Special Functions: $\text {IX}$. Null functions
Category:Null Functions
Function with Limit at Infinity of Exponential Order Zero

== Theorem ==
Let $f: \hointr 0 \to \to \R$ be a real function.
Let $f$ be continuous everywhere on their domains, except possibly for some finite number of discontinuities of the first kind in every finite subinterval of $\hointr 0 \to$.
Let $f$ have a (finite) limit at infinity.
Then $f$ is of exponential order $0$.
== Proof ==
Denote $\ds L = \lim_{t \mathop \to +\infty} \map f t$.
Define the constant mapping:
:$\map C t = - L$
Further define:
:$\map g t = \map f t + \map C t$
From:
:Constant Function is of Exponential Order Zero,
:Sum of Functions of Exponential Order,
it is sufficient to prove that $g$ is of exponential order $0$.
Fix $\epsilon > 0$ arbitrarily small.
By definition of limit at infinity, there exists $c \in \R$ such that:
:$\forall t > c: \size {\map f t - L} < \epsilon$
Therefore:
The result follows from the definition of exponential order, with $M = c + 1$, $K = \epsilon$, and $a = 0$.
Category:Exponential Order
Functional Completeness over Finite Number of Arguments

== Theorem ==
Every truth function is definable from the set of Binary Truth Functions.
== Proof ==
Let $f : \Bbb B^k \to \Bbb B$ be an arbitrary truth function.
Suppose that $k = 0$.
Then, let:
:$b = \map f {}$
If $b = T$, then let:
:$\map g {p, q} = \map {f_\T} {p, q} = T$
otherwise, if $b = F$:
:$\map g {p, q} = \map {f_\F} {p, q} = F$
Finally, let $\map i {} = \tuple {\F, \F}$.
$i$ is clearly an injection, and:
:$\map g {\map i {}} = b$
Thus, $f = g \circ i$, and $f$ is definable for $k = 0$.
If $k = 1$, then by Unary Truth Functions, $f$ is either:
* Constant $\F$
* Constant $\T$
* Identity
* Logical Not
If $f$ is constant mapping, then the same $g$ definitions work as above.
If $f$ is identity or logical not, then we use:
:$\map g {p, q} = \map {\pr_1} {p, q} = p$
and
:$\map g {p, q} = \map {\overline {\pr_1}} {p, q} = \neg p$
respectively.
We also define:
:$\map i p = \tuple {p, \F}$
As $f = g \circ i$, every $f$ is definable for $k = 1$.
For all remaining $k$, we will proceed by mathematical induction.
=== Basis for the Induction ===
Suppose that $k = 2$.
Then $f$ is a Binary Truth Functions already, so
:$g = f$
and
:$i$ identity
satisfies the definition.
=== Induction Hypothesis ===
Suppose that, for $k \ge 2$, every truth function $f : \Bbb B^k \to \Bbb B$ is definable from the set of Binary Truth Functions.
We want to conclude that, for $k \ge 2$, every truth function $f : \Bbb B^{k + 1} \to \Bbb B$
=== Induction Step ===
Let $f : \Bbb B^{k + 1} \to \Bbb B$ be arbitrary.
Define the two truth functions:
:$\map {f_0} {x_1, \dotsc, x_k} = \map f {\F, x_1, \dotsc, x_k}$
:$\map {f_1} {x_1, \dotsc, x_k} = \map f {\T, x_1, \dotsc, x_k}$
Define:
:$\map g {b, x_1, \dotsc, x_k} = \paren {\neg \paren {b \impliedby \map {f_0} {x_1, \dotsc, x_k}}} \lor \paren {b \land \map {f_1} {x_1, \dotsc, x_k}}$
where:
:$p \land q$ represents conjunction
:$p \lor q$ represents disjunction
:$\neg \paren {p \impliedby q}$ represents negated conditional
We want to show that, for all $b, x_1, \dotsc, x_k \in \Bbb B$:
:$\map g {b, x_1, \dotsc, x_k} = \map f {b, x_1, \dotsc, x_k}$
If $b = \F$, then:
Instead, if $b = \T$, then:
Thus, regardless of the value of $b$:
:$\map g {b, x_1, \dotsc, x_k} = \map f {b, x_1, \dotsc, x_k}$
always holds.
By the induction hypothesis, $f_0$ and $f_1$ are definable from the set of Binary Truth Functions.
As $g$ was obtained by composition from $f_0$, $f_1$, and Binary Truth Functions, it is as well.
As $f = g$, the same holds for $f$.
Thus, by the Principle of Mathematical Induction:
:For every $k \ge 2$, all truth functions $\Bbb B^k \to \Bbb B$ are definable from the set of Binary Truth Functions.
Combined with the above results for $k = 0$ and $k = 1$, the result follows.
Functional Equation for Completed Riemann Zeta Function

== Theorem ==
Let $\xi : \C \to \C$ be the completed Riemann zeta function.
Let $s\in \C$ be a complex number.
Then:
:$\map \xi s = \map \xi {1 - s}$
== Proof ==
Category:Riemann Zeta Function
Category:Reflection Formulas
Functional Equation for Dirichlet L-Functions

== Theorem ==
Let $\chi$ be a primitive Dirichlet character to the modulus $q \geq 1$.
Let $\map \Lambda {s, \chi}$ be the completed $L$-function for $\chi$.
Let $\map \tau \chi$ denote the Gaussian sum.
Then for all $s \in \C$:
:$\map \Lambda {s, \chi} = i^{-\kappa} \dfrac {\map \tau \chi} {\sqrt q} \map \Lambda {1 - s, \overline \chi}$
where $\kappa = \dfrac 1 2 \paren {1 - \map \chi {-1} }$.
== Proof ==
Category:Analytic Number Theory
Functional Equation for Riemann Zeta Function

== Theorem ==
Let $\zeta$ be the Riemann zeta function.
Let $\map \zeta s$ have an analytic continuation for $\map \Re s > 0$.
Then:
:$\pi^{-s/2 } \map \Gamma {\dfrac s 2} \map \zeta s = \pi^{\paren {s/2 - 1/2 } } \map \Gamma {\dfrac {1 - s} 2} \map \zeta {1 - s}$
where $\Gamma$ is the gamma function
== Proof ==
Let $\ds \map \omega x = \sum_{n \mathop = 1}^\infty e^{-\pi n^2 x}$.
Then from Integral Representation of Riemann Zeta Function in terms of Jacobi Theta Function we have:
:$(1): \quad \ds \pi^{-s / 2} \map \Gamma {\frac s 2} \map \zeta s = -\frac 1 {s \paren {1 - s} } + \int_1^\infty \paren {x^{s / 2 - 1} + x^{- s / 2 - 1 / 2} } \map \omega x \rd x$
We observe that this integral is invariant under $s \mapsto 1 - s$.
Then:
as required.
== Also see ==
* Functional Equation for Completed Riemann Zeta Function
* Integral Representation of Riemann Zeta Function in terms of Jacobi Theta Function
== Sources ==
* : $\S 35$: Riemann Zeta Function $\map \zeta x = \dfrac 1 {1^x} + \dfrac 1 {2^x} + \dfrac 1 {3^x} + \cdots$: $35.25$
Category:Riemann Zeta Function
Category:Reflection Formulas
Functionally Complete Logical Connectives

== Theorem ==
These sets of logical connectives are functionally complete:
=== Negation, Conjunction, Disjunction and Conditional ===
=== Conjunction, Negation and Disjunction ===
=== Negation and Conjunction ===
=== Negation and Disjunction ===
=== Negation and Conditional ===
=== NAND ===
=== NOR ===
There are others, but these are the main ones.
== Also see ==
* Functionally Complete Singleton Sets, in which it is seen that the only functionally complete singletons are $\left\{{\uparrow}\right\}$ and $\left\{{\downarrow}\right\}$.
* Functionally Incomplete Logical Connectives
Category:Functional Completeness
Functionally Complete Logical Connectives/Conjunction, Negation and Disjunction

== Theorem ==
The set of logical connectives:
:$\set {\neg, \land, \lor}$: Not, And and Or
is functionally complete.
== Proof ==
From the stronger results:
:Functionally Complete Logical Connectives: Negation and Disjunction:
::the set of logical connectives: $\set {\neg, \lor}$ is functionally complete
:Functionally Complete Logical Connectives: Negation and Conjunction:
::the set of logical connectives: $\set {\neg, \land}$ is functionally complete
it follows directly that $\set {\neg, \land, \lor}$ is likewise functionally complete.
Category:Functional Completeness
Functionally Complete Logical Connectives/NAND

== Theorem ==
The singleton set containing the following logical connective: 
:$\set \uparrow$: NAND
is functionally complete.
== Proof ==
From Functionally Complete Logical Connectives: Negation and Conjunction, any boolean expression can be expressed in terms of $\land$ and $\neg$.
From NAND with Equal Arguments:
:$\neg p \dashv \vdash p \uparrow p$
From Conjunction in terms of NAND:
:$p \land q \dashv \vdash \paren {p \uparrow q} \uparrow \paren {p \uparrow q}$
demonstrating that $p \land q$ is expressed solely in terms of $\uparrow$.
Thus any boolean expression can be represented solely in terms of $\uparrow$.
That is, $\set \uparrow$ is functionally complete.
== Also see ==
* NOR is Functionally Complete
== Sources ==
* : $\S 2.5$: Further Logical Constants
* : Chapter $2$: The Propositional Calculus $2$: $3$ Truth-Tables: Exercise $2 \ \text{(ii)}$
* : $\S 1$: Some mathematical language: Connectives
* : $\S 2.4.2$
Category:Functional Completeness
Category:Logical NAND
Functionally Complete Logical Connectives/NOR

== Theorem ==
The singleton set containing the following logical connective: 
:$\set \downarrow$: NOR
is functionally complete.
== Proof ==
From Functionally Complete Logical Connectives: Negation and Disjunction, any boolean expression can be expressed in terms of $\lor$ and $\neg$.
From NOR with Equal Arguments:
:$\neg p \dashv \vdash p \downarrow p$
From Disjunction in terms of NOR:
:$p \lor q \dashv \vdash \paren {p \downarrow q} \downarrow \paren {p \downarrow q}$
demonstrating that $p \lor q$ can be represented solely in terms of $\downarrow$.
That is, $\set \downarrow$ is functionally complete.
== Also see ==
* NAND is Functionally Complete
== Sources ==
* : Chapter $2$: The Propositional Calculus $2$: $3$ Truth-Tables: Exercise $2 \ \text{(ii)}$
* : $\S 1$: Some mathematical language: Connectives
* : $\S 2.4.2$
Category:Functional Completeness
Category:Logical NOR
Functionally Complete Logical Connectives/Negation, Conjunction, Disjunction and Conditional

== Theorem ==
The set of logical connectives:
: $\set {\neg, \land, \lor, \implies}$: Not, And, Or and Implies
is functionally complete.
== Proof ==
From Functional Completeness over Finite Number of Arguments, it suffices to consider binary truth functions.
From Count of Truth Functions, there are $16$ of these.
These are enumerated in Binary Truth Functions, and are analysed in turn as follows.
=== Constant Functions ===
There are two constant functions:
From Biconditional Properties and Exclusive Or Properties:
where $\oplus$ and $\iff$ denote exclusive or and biconditional respectively.
So both of the constant functions can be expressed in terms of $\oplus$ and $\iff$.
=== Equivalence and Non-Equivalence ===
By definition of exclusive or:
: $p \oplus q \dashv \vdash \map \neg {p \iff q}$.
Thus $\oplus$ can be expressed in terms of $\neg$ and $\iff$.
By definition of biconditional:
: $p \iff q \dashv \vdash \paren {p \implies q} \land \paren {q \implies p}$
Thus $\iff$ can be expressed in terms of $\implies$ and $\land$.
=== Projections and Negated Projections ===
There are two projections:
: $\map {\pr_1} {p, q} = p$
: $\map {\pr_2} {p, q} = q$
We note that:
: $p \land p \dashv \vdash p \dashv \vdash \map {\pr_1} {p, q}$
: $p \lor p \dashv \vdash p \dashv \vdash \map {\pr_1} {p, q}$
and similarly for $\map {\pr_2} {p, q}$.
So the projections can be expressed in terms of either $\land$ or $\lor$.
There are two negated projections:
: $\map {\overline {\pr_1} } {p, q} = \neg p$
: $\map {\overline {\pr_2} } {p, q} = \neg q$
It immediately follows from the above that these can be expressed in terms of either:
: $\neg$ and $\land$
or:
: $\neg$ and $\lor$
=== NAND and NOR ===
There are the NAND and NOR operators:
: $p \uparrow q$
: $p \downarrow q$
By definition of NAND:
: $p \uparrow q \dashv \vdash \map \neg {p \land q}$
By definition of NOR:
: $p \downarrow q \dashv \vdash \map \neg {p \lor q}$
So:
: $\uparrow$ can be expressed in terms of $\neg$ and $\land$
: $\downarrow$ can be expressed in terms of $\neg$ and $\lor$
=== Conjunction, Disjunction, Conditional ===
There are the conjunction and disjunction operators:
: $p \land q$
: $p \lor q$
There are two conditionals:
: $p \implies q$
: $q \implies p$
There are two negated conditionals:
: $\map \neg {p \implies q}$
: $\map \neg {q \implies p}$
All of the above are already expressed in terms of $\neg, \land, \lor, \implies$.
Thus all sixteen of the Binary Truth Functions can be expressed in terms of:
: $\neg, \land, \lor, \implies$
That is:
: $\set {\neg, \land, \lor, \implies}$
is functionally complete.
Category:Functional Completeness
Functionally Complete Logical Connectives/Negation and Conditional

== Theorem ==
The set of logical connectives:
:$\set {\neg, \implies}$: Not and Implies
is functionally complete.
== Proof ==
From Functionally Complete Logical Connectives: Negation and Conjunction, we can represent any boolean expression in terms of $\land$ and $\neg$.
From Conjunction and Conditional, we have that:
:$p \land q \dashv \vdash \neg \paren {p \implies \neg q}$
So it follows that we can replace all occurrences of $\land$ by $\implies$ and $\neg$.
Thus $\set {\neg, \implies}$ is functionally complete.
== Sources ==
* : $\S 2.5$: Further Logical Constants
* : Chapter $2$: The Propositional Calculus $2$: $3$ Truth-Tables
* : $\S 2.4.2$: Theorem $2.36$
Category:Functional Completeness
Functionally Complete Logical Connectives/Negation and Conjunction

== Theorem ==
The set of logical connectives:
:$\set {\neg, \land}$: Not and And
is functionally complete.
== Proof ==
From Functionally Complete Logical Connectives: Negation, Conjunction, Disjunction and Conditional, all sixteen of the binary truth functions can be expressed in terms of $\neg, \land, \lor, \implies$.
From Conjunction and Conditional, we have that:
:$p \implies q \dashv \vdash \neg \paren {p \land \neg q}$
From De Morgan's laws: Disjunction, we have that:
:$p \lor q \dashv \vdash \neg \paren {\neg p \land \neg q}$
So any instance of either $\implies$ or $\lor$ can be replaced identically with one using just $\neg$ and $\land$.
It follows that $\set {\neg, \land}$ is functionally complete.
== Sources ==
* : $\S 2.5$: Further Logical Constants
* : Chapter $2$: The Propositional Calculus $2$: $3$ Truth-Tables: Exercise $2 \ \text{(i)}$
* : $\S 1$: Some mathematical language: Connectives
* 
* 
* : $\S 2.4.2$: Theorem $2.36$
Category:Functional Completeness