-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathequiv.tex
50 lines (45 loc) · 3.09 KB
/
equiv.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
\chapter{Useful Equivalences}
\label{equivs}
\[ \begin{array}{>{\raggedleft\it}p{4cm} r c l}
commutation & \phi\wedge \psi & \dashv\vdash & \psi\wedge \phi \\
commutation & \phi\vee\psi & \dashv\vdash & \psi\vee\phi \\
association & \phi\wedge (\psi\wedge\chi ) & \dashv\vdash & (\phi\wedge \psi)\wedge \chi \\
association & \phi\vee (\psi\vee \chi) & \dashv\vdash & (\phi \vee \psi )\vee \chi \\
material conditional & \phi\to\psi & \dashv\vdash & \neg \phi\vee \psi \\
material conditional & \neg (\phi\to \psi ) & \dashv\vdash & \phi\wedge\neg \psi \\
contraposition & \phi\to\psi & \dashv\vdash & \neg \psi\to \neg \phi \\
DeMorgan & \neg (\phi\vee \psi) & \dashv\vdash & \neg \phi\wedge\neg \psi \\
DeMorgan & \neg (\phi\wedge \psi) & \dashv\vdash & \neg \phi\vee \neg \psi \\
distribution & \phi\wedge (\psi\vee \chi) &\dashv\vdash & (\phi\wedge \psi)\vee (\phi\wedge \chi) \\
distribution & \phi\vee (\psi\wedge \chi) &\dashv\vdash & (\phi\vee \psi)\wedge (\phi\vee \chi) \\
exportation & \phi\to (\psi\to \chi) & \dashv\vdash & (\phi\wedge \psi)\to \chi \\
duplication & \phi & \dashv\vdash & \phi\wedge \phi \\
duplication & \phi & \dashv\vdash & \phi\vee \phi \\
top & \top & \dashv\vdash & \phi\vee\top \\
top & \phi & \dashv\vdash & \phi\wedge\top \\
bottom & \phi & \dashv\vdash & \phi\vee \bot \\
bottom & \bot & \dashv\vdash & \phi\wedge\bot \\
self undermining & \phi\to \neg \phi & \dashv\vdash & \neg \phi \\
biconditional & \neg (\phi\lra \psi) & \dashv\vdash & \neg \phi\lra \psi \\
biconditional & \phi\lra \psi & \dashv\vdash & (\phi\wedge \psi)\vee (\neg \phi\wedge \neg \psi) \\
biconditional & \phi\lra \psi & \dashv\vdash & (\phi\to \psi)\wedge (\psi\to \phi ) \\
bicontraposition & \phi\lra \psi & \dashv\vdash & \neg \phi\lra\neg \psi \end{array} \]
\section{Predicate Logic}
\[ \begin{array}{>{\raggedleft\it}p{4cm} r c l p{6cm}}
quantifier negation & \neg\forall x\phi & \dashv\vdash & \exists x\neg \phi & \\
quantifier negation & \neg\exists x\phi & \dashv\vdash & \forall x\neg \phi & \\
alpha & \forall x\phi & \dashv\vdash & \forall y\phi [y/x] & substitute $y$ for $x$ \\
alpha & \exists x\phi & \dashv\vdash & \exists y\phi [y/x] & substitute $y$ for $x$ \\
swoosh & \forall x(\phi\wedge \psi ) & \dashv\vdash & \forall x\phi\wedge \forall x\psi & \\
swoosh & \exists x(\phi\vee\psi ) & \dashv\vdash & \exists x\phi\vee\exists x\psi & \\
& \forall x(\chi \to \phi) & \dashv\vdash & \chi\to\forall x\phi & $x$ not free in $\chi$ \\
& \exists x(\chi\to \phi ) & \dashv\vdash & \chi \to\exists x\phi & $x$ not free in $\chi$ \\
& \forall x(\phi\to \chi ) & \dashv\vdash & \exists x\phi\to \chi & $x$ not free in $\chi$ \\
& \exists x(\phi\to \chi ) & \dashv\vdash & \forall x\phi\to \chi & $x$ not free in $\chi$ \\
& \forall x\forall y\phi & \dashv\vdash & \forall y\forall x\phi \\
& \exists x\exists y\phi & \dashv\vdash & \exists y\exists x\phi
\end{array} \]
%%% Local Variables:
%%% mode: latex
%%% TeX-master: "main"
%%% End: