Seznam pravidel odvození - List of rules of inference

Toto je seznam pravidla odvození, logické zákony, které se vztahují k matematickým vzorcům.

Úvod

Pravidla odvození jsou syntaktické přeměnit pravidla, která lze použít k odvození závěru z premisy k vytvoření argumentu. Sada pravidel lze použít k odvození jakéhokoli platného závěru, pokud je úplný, a nikdy k odvození neplatného závěru, pokud je správný. Řádná a úplná sada pravidel nemusí zahrnovat všechna pravidla v následujícím seznamu, protože mnoho pravidel je nadbytečných a lze je prokázat jinými pravidly.

Pravidla udělování absolutoria povolit odvození z subderivace na základě dočasného předpokladu. Níže je notace

${ displaystyle varphi vdash psi}$

označuje takovou subderivaci z dočasného předpokladu ${ displaystyle varphi}$ na ${ displaystyle psi}$.

Pravidla pro klasický sentenciální počet

Sentenciální počet je také známý jako výrokový kalkul.

Pravidla pro negace

Reductio ad absurdum (nebo Negativní úvod)

${ displaystyle varphi vdash psi}$

${ displaystyle { podtržení { varphi vdash lnot psi}}}$

${ displaystyle lnot varphi}$

Reductio ad absurdum (související s zákon vyloučeného prostředku )

${ displaystyle lnot varphi vdash psi}$

${ displaystyle { podtržení { lnot varphi vdash lnot psi}}}$

${ displaystyle varphi}$

Ex contradictione quodlibet

${ displaystyle varphi}$

${ displaystyle { podtržení { lnot varphi}}}$

${ displaystyle psi}$

Odstranění dvojí negace

${ displaystyle { podtržení { lnot lnot varphi}}}$

${ displaystyle varphi}$

Úvod do dvojí negace

${ displaystyle { podtržení { varphi quad quad}}}$

${ displaystyle lnot lnot varphi}$

Pravidla pro podmínku

Věta o dedukci (nebo Podmíněný úvod )

${ displaystyle { podtržení { varphi vdash psi}}}$

${ displaystyle varphi rightarrow psi}$

Modus ponens (nebo Podmíněné vyloučení)

${ displaystyle varphi rightarrow psi}$

${ displaystyle { podtržení { varphi quad quad quad}}}$

${ displaystyle psi}$

Modus tollens

${ displaystyle varphi rightarrow psi}$

${ displaystyle { podtržení { lnot psi quad quad quad}}}$

${ displaystyle lnot varphi}$

Pravidla pro spojky

Adjunkce (nebo Úvod do spojení)

${ displaystyle varphi}$

${ displaystyle { podtržení { psi quad quad }}}$

${ Displaystyle varphi land psi}$

Zjednodušení (nebo Vyloučení spojky)

${ displaystyle { podtržení { varphi land psi}}}$

${ displaystyle varphi}$

${ displaystyle { podtržení { varphi land psi}}}$

${ displaystyle psi}$

Pravidla pro rozhodování

Přidání (nebo Úvod do disjunkce)

${ displaystyle { podtržení { varphi quad quad }}}$

${ displaystyle varphi lor psi}$

${ displaystyle { podtržení { psi quad quad }}}$

${ displaystyle varphi lor psi}$

Analýza případů (nebo Důkaz podle případů nebo Argument případy nebo Odstranění disjunkce)

${ displaystyle varphi rightarrow chi}$

${ displaystyle psi rightarrow chi}$

${ displaystyle { podtržení { varphi lor psi}}}$

${ displaystyle chi}$

Disjunktivní úsudek

${ displaystyle varphi lor psi}$

${ displaystyle { podtržení { lnot varphi quad quad}}}$

${ displaystyle psi}$

${ displaystyle varphi lor psi}$

${ displaystyle { podtržení { lnot psi quad quad}}}$

${ displaystyle varphi}$

Konstruktivní dilema

${ displaystyle varphi rightarrow chi}$

${ displaystyle psi rightarrow xi}$

${ displaystyle { podtržení { varphi lor psi}}}$

${ displaystyle chi lor xi}$

Pravidla pro dvojí podmínky

Dvojpodmínečný úvod

${ displaystyle varphi rightarrow psi}$

${ displaystyle { podtržení { psi rightarrow varphi}}}$

${ displaystyle varphi leftrightarrow psi}$

Dvoupodmínečná eliminace

${ displaystyle varphi leftrightarrow psi}$

${ displaystyle { podtržení { varphi quad quad}}}$

${ displaystyle psi}$

${ displaystyle varphi leftrightarrow psi}$

${ displaystyle { podtržení { psi quad quad}}}$

${ displaystyle varphi}$

${ displaystyle varphi leftrightarrow psi}$

${ displaystyle { podtržení { lnot varphi quad quad}}}$

${ Displaystyle lnot psi}$

${ displaystyle varphi leftrightarrow psi}$

${ displaystyle { podtržení { lnot psi quad quad}}}$

${ displaystyle lnot varphi}$

${ displaystyle varphi leftrightarrow psi}$

${ displaystyle { podtržení { psi lor varphi}}}$

${ displaystyle psi země varphi}$

${ displaystyle varphi leftrightarrow psi}$

${ displaystyle { podtržení { lnot psi lor lnot varphi}}}$

${ Displaystyle lnot psi land lnot varphi}$

Pravidla klasiky predikátový počet

V následujících pravidlech ${ displaystyle varphi ( beta / alfa)}$ je přesně jako ${ displaystyle varphi}$ kromě toho, že máte termín ${ displaystyle beta}$ kdekoli ${ displaystyle varphi}$ má volnou proměnnou ${ displaystyle alpha}$.

Univerzální generalizace (nebo Univerzální úvod )

${ displaystyle { underline { varphi {( beta / alpha)}}}}$

${ displaystyle forall alpha , varphi}$

Omezení 1: ${ displaystyle beta}$ je proměnná, která se nevyskytuje v ${ displaystyle varphi}$.
Omezení 2: ${ displaystyle beta}$ není zmíněn v žádné hypotéze nebo nevyčerpaných předpokladech.

Univerzální instance (nebo Univerzální eliminace )

${ displaystyle forall alpha , varphi}$

${ displaystyle { overline { varphi {( beta / alpha)}}}}$

Omezení: Bez volného výskytu ${ displaystyle alpha}$ v ${ displaystyle varphi}$ spadá do rozsahu kvantifikátoru kvantifikujícího proměnnou vyskytující se v ${ displaystyle beta}$.

Existenciální generalizace (nebo Existenciální úvod )

${ displaystyle { underline { varphi ( beta / alpha)}}}$

${ displaystyle existuje alpha , varphi}$

Omezení: Žádný volný výskyt ${ displaystyle alpha}$ v ${ displaystyle varphi}$ spadá do rozsahu kvantifikátoru kvantifikujícího proměnnou vyskytující se v ${ displaystyle beta}$.

Existenční instance (nebo Existenciální eliminace )

${ displaystyle existuje alpha , varphi}$

${ displaystyle { podtržení { varphi ( beta / alfa) vdash psi}}}$

${ displaystyle psi}$

Omezení 1: ${ displaystyle beta}$ je proměnná, která se nevyskytuje v ${ displaystyle varphi}$.
Omezení 2: Neexistuje žádný výskyt, volný ani vázaný ${ displaystyle beta}$ v ${ displaystyle psi}$.
Omezení 3: ${ displaystyle beta}$ není zmíněn v žádné hypotéze ani nevypuštěných předpokladech.

Pravidla substrukturální logika

Následují speciální případy univerzální generalizace a existenční eliminace; tyto se vyskytují v substrukturálních logikách, jako např lineární logika.

Pravidlo oslabení (nebo monotónnost zavinění ) (aka věta o klonování )

${ displaystyle alpha vdash beta}$

${ displaystyle { overline { alpha, alpha vdash beta}}}$

Pravidlo kontrakce (nebo idempotence zavinění ) (aka věta bez odstranění )

${ displaystyle { podtržení { alfa, alfa, gama vdash beta}}}$

${ displaystyle alpha, gamma vdash beta}$

Tabulka: Pravidla odvození

Výše uvedená pravidla lze shrnout v následující tabulce.^[1] „Tautologie "sloupec ukazuje, jak interpretovat notaci daného pravidla.

Pravidla odvození	Tautologie	název
${ displaystyle { begin {zarovnáno} p p rightarrow q tedy { overline {q quad quad quad}} end {zarovnáno}}}$	${ displaystyle (p klín (p rightarrow q)) rightarrow q}$	Modus ponens
${ displaystyle { begin {zarovnáno} neg q p rightarrow q tedy { overline { neg p quad quad quad}} end {zarovnáno}}}$	${ displaystyle ( neg q klín (p rightarrow q)) rightarrow neg p}$	Modus tollens
${ displaystyle { begin {zarovnáno} (p vee q) vee r tedy { overline {p vee (q vee r)}} end {zarovnáno}}}$	${ Displaystyle ((p vee q) vee r) rightarrow (p vee (q vee r))}$	Asociativní
${ displaystyle { begin {zarovnáno} p klín q tedy { overline {q klín p}} konec {zarovnáno}}}$	${ displaystyle (p klín q) pravá šipka (q klín p)}$	Komutativní
${ displaystyle { begin {zarovnáno} p rightarrow q q rightarrow p tedy { overline {p leftrightarrow q}} konec {zarovnáno}}}$	${ displaystyle ((p rightarrow q) klín (q rightarrow p)) rightarrow ( p leftrightarrow q)}$	Zákon dvou podmínek
${ displaystyle { begin {aligned} (p wedge q) rightarrow r proto { overline {p rightarrow (q rightarrow r)}} end {aligned}}}$	${ displaystyle ((p klín q) rightarrow r) rightarrow (p rightarrow (q rightarrow r))}$	Vývoz
${ displaystyle { begin {zarovnáno} p rightarrow q tedy { overline { neg q rightarrow neg p}} konec {zarovnáno}}}$	${ displaystyle (p rightarrow q) rightarrow ( neg q rightarrow neg p)}$	Transpoziční nebo kontrapoziční právo
${ displaystyle { begin {zarovnáno} p rightarrow q q rightarrow r tedy { overline {p rightarrow r}} konec {zarovnáno}}}$	${ displaystyle ((p rightarrow q) klín (q rightarrow r)) rightarrow (p rightarrow r)}$	Hypotetický úsudek
${ displaystyle { begin {zarovnáno} p rightarrow q tedy { overline { neg p vee q}} konec {zarovnáno}}}$	${ displaystyle (p rightarrow q) rightarrow ( neg p vee q)}$	Materiální implikace
${ displaystyle { begin {aligned} (p vee q) wedge r proto { overline {(p wedge r) vee (q wedge r)}} end {aligned}} }$	${ Displaystyle ((p vee q) klín r) rightarrow ((p klín r) vee (q klín r))}$	Distribuční
${ displaystyle { begin {zarovnáno} p rightarrow q tedy { overline {p rightarrow (p wedge q)}} end {zarovnáno}}}$	${ displaystyle (p rightarrow q) rightarrow (p rightarrow (p klín q))}$	Vstřebávání
${ displaystyle { begin {zarovnáno} p vee q neg p tedy { overline {q quad quad quad}} end {zarovnáno}}}$	${ Displaystyle ((p vee q) klín neg p) rightarrow q}$	Disjunktivní úsudek
${ displaystyle { begin {zarovnáno} p proto { overline {p vee q}} konec {zarovnáno}}}$	${ Displaystyle p rightarrow (p vee q)}$	Přidání
${ displaystyle { begin {zarovnáno} p klín q tedy { overline {p quad quad quad}} konec {zarovnáno}}}$	${ displaystyle (p klín q) pravá šipka p}$	Zjednodušení
${ displaystyle { begin {zarovnáno} p q tedy { overline {p wedge q}} konec {zarovnáno}}}$	${ displaystyle ((p) klín (q)) pravá šipka (p klín q)}$	Spojení
${ displaystyle { begin {zarovnáno} p proto { overline { neg neg p}} konec {zarovnáno}}}$	${ Displaystyle p rightarrow ( neg neg p)}$	Dvojitá negace
${ displaystyle { begin {zarovnáno} p vee p proto { overline {p quad quad quad}} end {zarovnáno}}}$	${ displaystyle (p vee p) rightarrow p}$	Disjunktivní zjednodušení
${ displaystyle { begin {zarovnáno} p vee q neg p vee r proto { overline {q vee r}} konec {zarovnáno}}}$	${ Displaystyle ((p vee q) klín ( neg p vee r)) rightarrow (q vee r)}$	Rozlišení
${ displaystyle { begin {zarovnáno} p rightarrow q r rightarrow q p vee r proto { overline {q quad quad quad}} end {zarovnáno}} }$	${ Displaystyle ((p rightarrow q) klín (r rightarrow q) klín (p vee r)) rightarrow q}$	Odstranění disjunkce

Všechna pravidla používají základní logické operátory. Kompletní tabulku „logických operátorů“ zobrazuje a pravdivostní tabulka, poskytující definice všech možných (16) pravdivostních funkcí 2 booleovské proměnné (p, q):

kde T = true a F = false, a sloupce jsou logické operátory: 0, Nepravdivé, Rozpor; 1, NOR, Logické NOR (Peirceův šíp); 2, Konverzní neimplikace; 3, ¬p, Negace; 4, Zjednodušení materiálu; 5, ¬q, Negace; 6, XOR, Exkluzivní disjunkce; 7, NAND, Logické NAND (Shefferův tah); 8, A, Logická spojka; 9, XNOR, Kdyby jen, Logická biconditional; 10, q, Projekční funkce; 11, pokud / pak, Logické důsledky; 12, p, Projekční funkce; 13, pak / pokud, Konverzní implikace; 14, NEBO, Logická disjunkce; 15, skutečný, Tautologie.

Každý logický operátor lze použít v tvrzení o proměnných a operacích, které ukazuje základní pravidlo odvození. Příklady:

• Zobrazí se operátor sloupce 14 (OR) Pravidlo sčítání: když p= T (hypotéza vybírá první dva řádky tabulky), vidíme to (ve sloupci 14) p∨q= T.

  Vidíme také, že se stejnou premisou platí další závěry: sloupce 12, 14 a 15 jsou T.

• Zobrazí se operátor sloupce 8 (AND) Pravidlo zjednodušení: když p∧q= T (první řádek tabulky), to vidíme p= T.

  S touto premisou to také uzavíráme q= T, p∨q= T atd., Jak ukazují sloupce 9-15.

• Zobrazí se operátor sloupce 11 (IF / THEN) Pravidlo Modus ponens: když p→q= T a p= T pouze jeden řádek pravdivostní tabulky (první) splňuje tyto dvě podmínky. Na tomto řádku q je také pravda. Proto vždy, když p → q je pravda a p je pravda, q musí být také pravda.

Používají to stroje a dobře vyškolení lidé podívejte se na tabulkový přístup udělat základní závěry a zkontrolovat, zda lze získat další závěry (pro stejné prostory).

Příklad 1

Uvažujme o následujících předpokladech: "Pokud dnes prší, dnes nepůjdeme na kánoi. Pokud dnes nepůjdeme na výlet na kánoi, zítra půjdeme na kánoi. Proto (matematický symbol pro" proto " je ${ displaystyle proto}$), pokud dnes prší, zítra se vydáme na výlet na kánoi. “Abychom využili pravidla odvození ve výše uvedené tabulce, necháme ${ displaystyle p}$ být tvrzení „Pokud dnes prší“, ${ displaystyle q}$ buďte „Dnes nepůjdeme na kánoi“ a nechte ${ displaystyle r}$ být „Půjdeme zítra na výlet na kánoi“. Pak má tento argument tvar:

${ displaystyle { begin {zarovnáno} p rightarrow q q rightarrow r tedy { overline {p rightarrow r}} konec {zarovnáno}}}$

Příklad 2

Zvažte komplexnější soubor předpokladů: „Dnes není slunečno a je chladněji než včera“. „Půjdeme se plavat jen za slunečného počasí“, „Pokud se nebudeme plavat, budeme grilovat“ a „Pokud budeme grilovat, budeme doma při západu slunce“ vést k závěru “ Budeme doma do západu slunce. “Důkaz podle pravidel odvození: Let ${ displaystyle p}$ být návrhem „Dnes je slunečno“, ${ displaystyle q}$ návrh „Je chladnější než včera“, ${ displaystyle r}$ návrh „Půjdeme si zaplavat“, ${ displaystyle s}$ návrh „Budeme grilovat“ a ${ displaystyle t}$ tvrzení „Budeme doma do západu slunce“. Pak se stanou hypotézy ${ Displaystyle neg p klín q, r rightarrow p, neg r rightarrow s}$ a ${ displaystyle s rightarrow t}$. Pomocí naší intuice předpokládáme, že by to mohl být závěr ${ displaystyle t}$. Pomocí tabulky pravidel odvození můžeme snadno dokázat domněnku:

Krok	Důvod
1.${ displaystyle neg p klín q}$	Hypotéza
2. ${ displaystyle neg p}$	Zjednodušení pomocí kroku 1
3. ${ displaystyle r rightarrow p}$	Hypotéza
4. ${ displaystyle neg r}$	Modus mýtného pomocí kroků 2 a 3
5. ${ displaystyle neg r rightarrow s}$	Hypotéza
6. ${ displaystyle s}$	Modus ponens pomocí kroků 4 a 5
7. ${ displaystyle s rightarrow t}$	Hypotéza
8. ${ displaystyle t}$	Modus ponens pomocí kroků 6 a 7

Reference

Viz také

Seznam logických systémů