Formula collection logic

This is a collection of formulas for the mathematical branch of logic .

Propositional logic

Logical values:

• true 1
• false (false) 0

Extended logic:

• indefinite ( don't care ) X

Statements can be linked by logical operators , also called joiners . The usual junctions are:

Surname	symbol	linguistic description	surgery	definition
Negator	${\displaystyle \neg }$	Not	negation	The negation of a logical value is true if and only if the value is false.
Conjunctor	${\displaystyle \land }$	and	conjunction	The conjunction of two values ​​is true if and only if both values ​​are true.
Disjunctor	${\displaystyle \lor }$	or	Disjunction	The disjunction of two values ​​is true if and only if at least one value is true.

In order to be able to easily distinguish the symbols of the conjunctur and the disjunctor, there is the Eselsbrücke with the three O: "Or is Oben Offen." Alternatively, you can remember " A nd" (English) for and, as well as " v el" (Latin ) for or.

Linking two statements

Surname		linguistic description	presentation		Truth table				Logic gate
			by negator, conjunctor and disjunctor	through other junctions	A = 1		A = 0
					B = 1	B = 0	B = 1	B = 0
conjunction		A and B	${\displaystyle A\land B}$	${\displaystyle \neg (B\implies \neg A)}$	1	0	0	0	AND
Exclusion, contrary contrast		not A and B at the same time	${\displaystyle \neg (A\land B)\iff \neg A\lor \neg B}$	${\displaystyle A\mid B\iff (A\implies \neg B)\iff (B\implies \neg A)}$	0	1	1	1	NAND
Disjunction		A or B (or both)	${\displaystyle A\lor B}$	${\displaystyle (\neg A\implies B)\iff (\neg B\implies A)}$	1	1	1	0	OR
Nihilition, Rejection		neither a nor B	${\displaystyle \neg (A\lor B)\iff \neg A\land \neg B}$		0	0	0	1	NOR
Contravalence , contradictory contrast		either A or B	${\displaystyle (A\land \neg B)\lor (\neg A\land B)\iff (A\lor B)\land (\neg A\lor \neg B)}$	${\displaystyle A\veebar B\iff \neg (A\iff B)}$	0	1	1	0	XOR
Biconditional , Bisubjunktion, substantive equivalence		only if A then B, then B if A	${\displaystyle (A\land B)\lor (\neg A\land \neg B)\iff (A\lor \neg B)\land (\neg A\lor B)}$	${\displaystyle (A\iff B)\iff (A\implies B)\land (B\implies A)}$	1	0	0	1	XNOR
Conditional, subjunction , material implication	implication	if A then B	${\displaystyle \neg A\lor B}$	${\displaystyle (A\implies B)\iff (\neg B\implies \neg A)}$	1	0	1	1
	Replication	if B then A	${\displaystyle \neg B\lor A}$	${\displaystyle (B\implies A)\iff (\neg A\implies \neg B)}$	1	1	0	1
Inhibition	Mail section	A and not B	${\displaystyle A\land \neg B}$	${\displaystyle \neg (A\implies B)}$	0	1	0	0
	Presection	B and not A	${\displaystyle B\land \neg A}$	${\displaystyle \neg (B\implies A)}$	0	0	1	0

Basic logical laws

Law of double negation	${\displaystyle x=\neg (\neg x)}$
Commutative laws	${\displaystyle x\land y=y\land x}$	${\displaystyle x\lor y=y\lor x}$
Associative Laws	${\displaystyle x\land (y\land z)=(x\land y)\land z}$	${\displaystyle (x\lor y)\lor z=x\lor (y\lor z)}$
Distributive laws	${\displaystyle x\land (y\lor z)=(x\land y)\lor (x\land z)}$	${\displaystyle x\lor (y\land z)=(x\lor y)\land (x\lor z)}$
Idempotence	${\displaystyle x\land x=x}$	${\displaystyle x\lor x=x}$
Laws of negation (tautology / contradiction)	${\displaystyle x\lor \neg x=1}$	${\displaystyle x\land \neg x=0}$
Absorption laws	${\displaystyle x\land (x\lor y)=x}$	${\displaystyle x\lor (x\land y)=x}$
neutrality	${\displaystyle x\lor 0=x}$	${\displaystyle x\land 1=x}$
De Morgan's Laws	${\displaystyle \neg (x\land y)=\neg x\lor \neg y}$	${\displaystyle \neg (x\lor y)=\neg x\land \neg y}$

Final rules

Modus ponens	${\displaystyle ((a\rightarrow b)\land a)\rightarrow b}$
Mode maddening	${\displaystyle ((a\rightarrow b)\land \neg b)\rightarrow \neg a}$
Hypothetical syllogism	${\displaystyle (a\rightarrow b)\land (b\rightarrow c)\rightarrow (a\rightarrow c)}$
Disjunctive syllogism	${\displaystyle ((a\lor b)\land \neg a)\rightarrow b}$

Predicate logic

Quantifiers

p is a placeholder for a predicate logic proposition.

${\displaystyle \forall _{x}p=\neg (\exists _{x}\neg p)}$	${\displaystyle \exists _{x}p=\neg (\forall _{x}\neg p)}$
${\displaystyle \neg \forall _{x}p=(\exists _{x}\neg p)}$	${\displaystyle \neg \exists _{x}p=(\forall _{x}\neg p)}$

Prenex form

${\displaystyle \phi }$and are in the following placeholders for predicate logic statements. The transformations in lines 1, 2, 4 and 5 of the table only apply if x occurs within not free, i.e. H. when moving the quantifier does not create (or dissolve) a variable link that was not there (or was there) before. The last transformation only applies if x occurs within not free, i.e. H. when moving the quantifier does not create (or dissolve) a variable link that was not there (or was there) before. ${\displaystyle \psi }$ ${\displaystyle \psi }$ ${\displaystyle \phi }$

This is not a problem if the variables are named differently in the statement forms and in each case. ${\displaystyle \phi }$ ${\displaystyle \psi }$

${\displaystyle (\forall x\phi )\land \psi }$= , ${\displaystyle \forall x(\phi \land \psi )}$	${\displaystyle (\forall x\phi )\lor \psi }$= ; ${\displaystyle \forall x(\phi \lor \psi )}$
${\displaystyle (\exists x\phi )\land \psi }$= , ${\displaystyle \exists x(\phi \land \psi )}$	${\displaystyle (\exists x\phi )\lor \psi }$= . ${\displaystyle \exists x(\phi \lor \psi )}$
${\displaystyle \lnot \exists x\phi }$ = ${\displaystyle \forall x\lnot \phi }$	${\displaystyle \lnot \forall x\phi }$= . ${\displaystyle \exists x\lnot \phi }$
${\displaystyle (\forall x\phi )\rightarrow \psi }$= , ${\displaystyle \exists x(\phi \rightarrow \psi )}$	${\displaystyle (\exists x\phi )\rightarrow \psi }$= . ${\displaystyle \forall x(\phi \rightarrow \psi )}$
${\displaystyle \phi \rightarrow (\exists x\psi )}$= , ${\displaystyle \exists x(\phi \rightarrow \psi )}$	${\displaystyle \phi \rightarrow (\forall x\psi )}$= . ${\displaystyle \forall x(\phi \rightarrow \psi )}$

Minimum final rules

Quasi order

${\displaystyle \vdash }$ is in the following a quasi-order between statements.

${\displaystyle {\begin{array}{c}{~}\\\hline A\vdash A\end{array}}\qquad {\begin{array}{c}A\vdash B\qquad B\vdash C\\\hline A\vdash C\end{array}}}$

conjunction

${\displaystyle \top }$and are defined by the following rules. ${\displaystyle \land }$

${\displaystyle {\begin{array}{c}{~}\\\hline A\vdash \top \end{array}}\qquad {\begin{array}{c}A\vdash B\qquad A\vdash C\\\hline A\vdash B\land C\end{array}}{\uparrow }{\downarrow }}$

Disjunction

${\displaystyle \bot }$and are defined by the following rules. ${\displaystyle \lor }$

${\displaystyle {\begin{array}{c}{~}\\\hline \bot \vdash A\end{array}}\qquad {\begin{array}{c}A\vdash C\qquad B\vdash C\\\hline A\lor B\vdash C\end{array}}{\uparrow }{\downarrow }}$

Heyting implication and negation

${\displaystyle \to }$ is by the rule

${\displaystyle {\begin{array}{lcr}A\land B&\vdash &C\\\hline A&\vdash &B\to C\end{array}}{\uparrow }{\downarrow }}$

defined, and per . ${\displaystyle \lnot }$ ${\displaystyle \lnot A:=A\to \bot }$

It apply

• ${\displaystyle A\land \lnot A\vdash \bot }$,
• ${\displaystyle \lnot \top \vdash \bot }$ and
• ${\displaystyle \top \vdash \lnot \bot }$.

Co-Heyting implication and negation

Dual to and are and . ${\displaystyle \to }$ ${\displaystyle \lnot }$ ${\displaystyle \setminus }$ ${\displaystyle \sim }$

${\displaystyle {\begin{array}{lcr}A\setminus B&\vdash &C\\\hline A&\vdash &B\lor C\end{array}}{\uparrow }{\downarrow }}$,

${\displaystyle {\sim }A:=\top \setminus A}$.

It apply

• ${\displaystyle \top \vdash A\lor {\sim }A}$
• ${\displaystyle {\sim }\top \vdash \bot }$ and
• ${\displaystyle \top \vdash {\sim }\bot }$.

Relationship between the negations

It always applies . This also applies if you get classic logic. ${\displaystyle \lnot A\vdash {\sim }A}$ ${\displaystyle {\sim }A\vdash \lnot A}$

Quantifiers

Let it be a picture. Any statement about elements of can be transformed into a statement about elements using. Notation: . is a functor. Its right and left adjoint are, respectively, universal and existential quantifiers. Ie ${\displaystyle f\colon X\to Y}$ ${\displaystyle A}$ ${\displaystyle Y}$ ${\displaystyle f}$ ${\displaystyle X}$ ${\displaystyle A\circ f}$ ${\displaystyle (-\circ f)}$

${\displaystyle {\begin{array}{lcr}A\circ f&\vdash _{X}&B\\\hline A&\vdash _{Y}&\forall _{f}B\end{array}}{\uparrow }{\downarrow }\qquad {\begin{array}{rcl}C&\vdash _{X}&A\circ f\\\hline \exists _{f}C&\vdash _{Y}&A\end{array}}{\uparrow }{\downarrow }}$.