فهرست قواعد استنتاج

این فهرستی از قواعد استنتاج منطقی است. این قوانین مربوط به فرمول‌های ریاضی هستند.

مقدمه

قواعد استنتاج یا قوانین استنتاج، نحوهٔ تبدیل قوانین هستند که می‌توان برای پی بردن به یک نتیجه از یک فرض برای ایجاد یک استدلال استفاده کرد.

این مجموعه از قواعد یا قوانین را می‌توان برای به دست آوردن نتایج معتبر استفاده کرد. برای اثبات نیاز به استفاده از همهٔ قواعدِ فهرست نیست.

در نماد زیر، از درستی عبارت اول به درستی عبارت دوم پی می‌بریم

${\displaystyle \varphi \vdash \psi \,\!}$

قواعد کلاسیک جمله‌های حساب دیفرانسیل و انتگرال

جمله‌های حساب دیفرانسیل و انتگرال همچنین به‌عنوان حساب گزاره‌ای (منطق گزاره‌ای) شناخته شده‌است.

قوانین برای نفی

برهان آگهی خلف (یا نفی مقدمه)

${\displaystyle \varphi \vdash \psi \,\!}$

${\displaystyle {\underline {\varphi \vdash \lnot \psi }}\,\!}$

${\displaystyle \lnot \varphi \,\!}$

برهان آگهی خلف (مربوط به قانون مستثنی میانه)

${\displaystyle \lnot \varphi \vdash \psi \,\!}$

${\displaystyle {\underline {\lnot \varphi \vdash \lnot \psi }}\,\!}$

${\displaystyle \varphi \,\!}$

Non contradiction (یا نفی حذف)

${\displaystyle \varphi \,\!}$

${\displaystyle {\underline {\lnot \varphi }}\,\!}$

${\displaystyle \psi \,\!}$

دو نفی و حذف

${\displaystyle {\underline {\lnot \lnot \varphi }}\,\!}$

${\displaystyle \varphi \,\!}$

دو نفی مقدمه

${\displaystyle {\underline {\varphi \quad \quad }}\,\!}$

${\displaystyle \lnot \lnot \varphi \,\!}$

قوانین به صورت شرطی

قضیه کسر (و یا مشروط مقدمه)

${\displaystyle {\underline {\varphi \vdash \psi }}\,\!}$

${\displaystyle \varphi \rightarrow \psi \,\!}$

وضع مقدم (یا مشروط حذف)

${\displaystyle \varphi \rightarrow \psi \,\!}$

${\displaystyle {\underline {\varphi \quad \quad \quad }}\,\!}$

${\displaystyle \psi \,\!}$

نقیض انتزاع

${\displaystyle \varphi \rightarrow \psi \,\!}$

${\displaystyle {\underline {\lnot \psi \quad \quad \quad }}\,\!}$

${\displaystyle \lnot \varphi \,\!}$

قوانین برای حروف ربط

ضمیمه (یا رابطه مقدمه)

${\displaystyle \varphi \,\!}$

${\displaystyle {\underline {\psi \quad \quad \ \ }}\,\!}$

${\displaystyle \varphi \land \psi \,\!}$

ساده‌سازی (یا حذف پیوستگی)

${\displaystyle {\underline {\varphi \land \psi }}\,\!}$

${\displaystyle \varphi \,\!}$

${\displaystyle {\underline {\varphi \land \psi }}\,\!}$

${\displaystyle \psi \,\!}$

قوانین برای disjunctions

علاوه بر این (و یا جدایی مقدمه)

${\displaystyle {\underline {\varphi \quad \quad \ \ }}\,\!}$

${\displaystyle \varphi \lor \psi \,\!}$

${\displaystyle {\underline {\psi \quad \quad \ \ }}\,\!}$

${\displaystyle \varphi \lor \psi \,\!}$

مورد تجزیه و تحلیل (یا اثبات از طریق موارد یا استدلال با موارد)

${\displaystyle \varphi \rightarrow \chi \,\!}$

${\displaystyle \psi \rightarrow \chi \,\!}$

${\displaystyle {\underline {\varphi \lor \psi }}\,\!}$

${\displaystyle \chi \,\!}$

قیاس فصلی

${\displaystyle \varphi \lor \psi \,\!}$

${\displaystyle {\underline {\lnot \varphi \quad \quad }}\,\!}$

${\displaystyle \psi \,\!}$

${\displaystyle \varphi \lor \psi \,\!}$

${\displaystyle {\underline {\lnot \psi \quad \quad }}\,\!}$

${\displaystyle \varphi \,\!}$

معضل سازنده

${\displaystyle \varphi \rightarrow \chi \,\!}$

${\displaystyle \psi \rightarrow \xi \,\!}$

${\displaystyle {\underline {\varphi \lor \psi }}\,\!}$

${\displaystyle \chi \lor \xi \,\!}$

قوانین برای دو شرطی‌ها

معرفی دو شرطی

${\displaystyle \varphi \rightarrow \psi \,\!}$

${\displaystyle {\underline {\psi \rightarrow \varphi }}\,\!}$

${\displaystyle \varphi \leftrightarrow \psi \,\!}$

حذف دو شرطی

${\displaystyle \varphi \leftrightarrow \psi \,\!}$

${\displaystyle {\underline {\varphi \quad \quad }}\,\!}$

${\displaystyle \psi \,\!}$

${\displaystyle \varphi \leftrightarrow \psi \,\!}$

${\displaystyle {\underline {\psi \quad \quad }}\,\!}$

${\displaystyle \varphi \,\!}$

${\displaystyle \varphi \leftrightarrow \psi \,\!}$

${\displaystyle {\underline {\lnot \varphi \quad \quad }}\,\!}$

${\displaystyle \lnot \psi \,\!}$

${\displaystyle \varphi \leftrightarrow \psi \,\!}$

${\displaystyle {\underline {\lnot \psi \quad \quad }}\,\!}$

${\displaystyle \lnot \varphi \,\!}$

${\displaystyle \varphi \leftrightarrow \psi \,\!}$

${\displaystyle {\underline {\psi \lor \varphi }}\,\!}$

${\displaystyle \psi \land \varphi \,\!}$

${\displaystyle \varphi \leftrightarrow \psi \,\!}$

${\displaystyle {\underline {\lnot \psi \lor \lnot \varphi }}\,\!}$

${\displaystyle \lnot \psi \land \lnot \varphi \,\!}$

قوانین کلاسیک گزاره حساب دیفرانسیل و انتگرال

در زیر قوانین ${\displaystyle \varphi (\beta /\alpha )\,\!}$ است دقیقاً مانند ${\displaystyle \varphi \,\!}$ به جز داشتن این اصطلاح ${\displaystyle \beta \,\!}$ در همه جا ${\displaystyle \varphi \,\!}$ به متغیر آزاد ${\displaystyle \alpha \,\!}$است.

تعمیم جهانی (یا مقدمه جهانی)

${\displaystyle {\underline {\varphi {(\beta /\alpha )}}}\,\!}$

${\displaystyle \forall \alpha \,\varphi \,\!}$

محدودیت 1: ${\displaystyle \beta }$ یک متغیر است که در ${\displaystyle \varphi }$ رخ می‌دهد.

محدودیت 2: ${\displaystyle \beta }$ در هر فرضیه یا فرضیات ذکر نشده‌است.

نمونه جهانی (یا حذف جهانی)

${\displaystyle \forall \alpha \,\varphi \!}$

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

تعمیم وجودی (یا مقدمه وجودی)

${\displaystyle {\underline {\varphi (\beta /\alpha )}}\,\!}$

${\displaystyle \exists \alpha \,\varphi \,\!}$

نمونه وجودی (یا حذف وجودی)

${\displaystyle \exists \alpha \,\varphi \,\!}$

${\displaystyle {\underline {\varphi (\beta /\alpha )\vdash \psi }}\,\!}$

${\displaystyle \psi \,\!}$

محدودیت 1: ${\displaystyle \beta }$ یک متغیر است که در ${\displaystyle \varphi \,\!}$ رخ می‌دهد

محدودیت ۲: هیچ اتفاق یا محدود از ${\displaystyle \beta \,\!}$ در ${\displaystyle \psi \,\!}$.

محدودیت 3: ${\displaystyle \beta }$ در هر فرضیه یا فرضیات ذکر نشده‌است.

جدول: قوانین استنتاج

قوانین فوق را می‌توان در جدول زیر خلاصه کرد.^[۱] ستون "درست نماً نشان می‌دهد که چگونه به وسیلهٔ قانون نماد تفسیر داده می‌شود.

Rules of inference	Tautology	Name
${\displaystyle {\begin{aligned}p\\p\rightarrow q\\\therefore {\overline {q\quad \quad \quad }}\\\end{aligned}}}$	${\displaystyle ((p\wedge (p\rightarrow q))\rightarrow q}$	Modus ponens
${\displaystyle {\begin{aligned}\neg q\\p\rightarrow q\\\therefore {\overline {\neg p\quad \quad \quad }}\\\end{aligned}}}$	${\displaystyle ((\neg q\wedge (p\rightarrow q))\rightarrow \neg p}$	Modus tollens
${\displaystyle {\begin{aligned}(p\vee q)\vee r\\\therefore {\overline {p\vee (q\vee r)}}\\\end{aligned}}}$	${\displaystyle ((p\vee q)\vee r)\rightarrow (p\vee (q\vee r))}$	Associative
${\displaystyle {\begin{aligned}p\wedge q\\\therefore {\overline {q\wedge p}}\\\end{aligned}}}$	${\displaystyle (p\wedge q)\rightarrow (q\wedge p)}$	Commutative
${\displaystyle {\begin{aligned}p\rightarrow q\\q\rightarrow p\\\therefore {\overline {p\leftrightarrow q}}\\\end{aligned}}}$	${\displaystyle ((p\rightarrow q)\wedge (q\rightarrow p))\rightarrow (\ p\leftrightarrow q)}$	Law of biconditional propositions
${\displaystyle {\begin{aligned}(p\wedge q)\rightarrow r\\\therefore {\overline {p\rightarrow (q\rightarrow r)}}\\\end{aligned}}}$	${\displaystyle ((p\wedge q)\rightarrow r)\rightarrow (p\rightarrow (q\rightarrow r))}$	Exportation
${\displaystyle {\begin{aligned}p\rightarrow q\\\therefore {\overline {\neg q\rightarrow \neg p}}\\\end{aligned}}}$	${\displaystyle (p\rightarrow q)\rightarrow (\neg q\rightarrow \neg p)}$	Transposition or contraposition law
${\displaystyle {\begin{aligned}p\rightarrow q\\q\rightarrow r\\\therefore {\overline {p\rightarrow r}}\\\end{aligned}}}$	${\displaystyle ((p\rightarrow q)\wedge (q\rightarrow r))\rightarrow (p\rightarrow r)}$	Hypothetical syllogism
${\displaystyle {\begin{aligned}p\rightarrow q\\\therefore {\overline {\neg p\vee q}}\\\end{aligned}}}$	${\displaystyle (p\rightarrow q)\rightarrow (\neg p\vee q)}$	Material implication
${\displaystyle {\begin{aligned}(p\vee q)\wedge r\\\therefore {\overline {(p\wedge r)\vee (q\wedge r)}}\\\end{aligned}}}$	${\displaystyle ((p\vee q)\wedge r)\rightarrow ((p\wedge r)\vee (q\wedge r))}$	Distributive
${\displaystyle {\begin{aligned}p\rightarrow q\\\therefore {\overline {p\rightarrow (p\wedge q)}}\\\end{aligned}}}$	${\displaystyle (p\rightarrow q)\rightarrow (p\rightarrow (p\wedge q))}$	Absorption
${\displaystyle {\begin{aligned}p\vee q\\\neg p\\\therefore {\overline {q\quad \quad \quad }}\\\end{aligned}}}$	${\displaystyle ((p\vee q)\wedge \neg p)\rightarrow q}$	Disjunctive syllogism
${\displaystyle {\begin{aligned}p\\\therefore {\overline {p\vee q}}\\\end{aligned}}}$	${\displaystyle p\rightarrow (p\vee q)}$	Addition
${\displaystyle {\begin{aligned}p\wedge q\\\therefore {\overline {p\quad \quad \quad }}\\\end{aligned}}}$	${\displaystyle (p\wedge q)\rightarrow p}$	Simplification
${\displaystyle {\begin{aligned}p\\q\\\therefore {\overline {p\wedge q}}\\\end{aligned}}}$	${\displaystyle ((p)\wedge (q))\rightarrow (p\wedge q)}$	Conjunction
${\displaystyle {\begin{aligned}p\\\therefore {\overline {\neg \neg p}}\\\end{aligned}}}$	${\displaystyle p\rightarrow (\neg \neg p)}$	Double negation
${\displaystyle {\begin{aligned}p\vee p\\\therefore {\overline {p\quad \quad \quad }}\\\end{aligned}}}$	${\displaystyle (p\vee p)\rightarrow p}$	Disjunctive simplification
${\displaystyle {\begin{aligned}p\vee q\\\neg p\vee r\\\therefore {\overline {q\vee r}}\\\end{aligned}}}$	${\displaystyle ((p\vee q)\wedge (\neg p\vee r))\rightarrow (q\vee r)}$	Resolution

همه قوانین از عملگرهای منطقی استفاده می‌کنند. یک جدول کامل از عملگرهای منطقی با جدول درستی نشان داده شده که تعریفی از همهٔ متغیرهای بولی(pبا q)است:

p	q	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
T	T	F	F	F	F	F	F	F	F	T	T	T	T	T	T	T	T
T	F	F	F	F	F	T	T	T	T	F	F	F	F	T	T	T	T
F	T	F	F	T	T	F	F	T	T	F	F	T	T	F	F	T	T
F	F	F	T	F	T	F	T	F	T	F	T	F	T	F	T	F	T

که در آن T = درست و F = نادرست و ستون هستند عملگرهای منطقی: 0false تناقض; ۱کار نه منطقی و نه; ۲زن صحبت nonimplication; 3با pبا نفی; ۴با مواد nonimplication; 5با qنفی؛ ۶با XORهای منحصر به فرد جدایی; 7NAND سه منطقی NAND; 8و منطقی رابطه; ۹با نقیض یای انحصاری با اگر و تنها اگربا منطقی biconditional; 10با پرسشهای طرح تابع؛ ۱۱اگر/پس منطقی مفهوم; ۱۲با pپروجکشن تابع؛ ۱۳پس از آن/اگر صحبت مفهوم; ۱۴یا منطقی جدایی; ۱۵با درست است گو.

هر منطق اپراتور را می‌توان در ادعا در مورد متغیرها و عملیات نشان از قانون اساسی استنباط است. نمونه:

• ستون-۱۴ اپراتور (یا) نشان می‌دهد علاوه بر این قانون: زمانی که p=T (فرضیه انتخاب دو خط اول جدول) ما (در ستون-۱۴) که p∨q=T.

  ما همچنین می‌توانید ببینید که با همان فرض یکی دیگر از نتایج معتبر هستند: ستون ۱۲, ۱۴ و ۱۵ در حال T.

• ستون-۸ اپراتور (و) نشان می‌دهد، ساده‌سازی قانون: زمانی که p∧q=T (خط اول جدول) ما می‌بینیم که p=T.

  با این فرض ما نیز نتیجه‌گیری کرد که q=T, p∨q=T، به عنوان نشان داد توسط ستون ۹–۱۵.

• ستون-۱۱ اپراتور (اگر/پس از آن) نشان می‌دهد Modus ponens قانون: زمانی که p→q=T و p=T فقط یک خط از حقیقت در جدول () صدق این دو شرایط. در این خط q نیز صادق است؛ بنابراین هر زمان که p → q درست است و p درست است و q نیز باید درست باشد.

ماشین خوبی آموزش دیده و با مردم با استفاده از این نگاه در جدول رویکرد به فراموش پایه استنتاج و برای بررسی اگر دیگر استنتاج (در همان محل) می‌توان به دست آمده.

مثال ۱

اجازه دهید ما در نظر گرفتن مفروضات زیر: "اگر باران امروز، پس از آن ما نمی‌خواهد در یک قایق رانی امروز. اگر ما در یک قایق رانی سفر امروز، پس از آن ما را بر روی یک قایق رانی سفر فردا؛ بنابراین (ریاضی نماد برای "بنابراین" است ${\displaystyle \therefore }$) اگر باران امروز ما در یک قایق رانی سفر فردا". به استفاده از قواعد استنتاج در جدول بالا ما اجازه ${\displaystyle p}$ بود که گزاره "اگر باران امروز" ${\displaystyle q}$ بود "ما نمی‌خواهد در یک قایق رانی امروز" و اجازه دهید ${\displaystyle r}$ "ما را در یک قایق رانی سفر فردا". سپس این استدلال این است که از فرم:

مثال ۲

اجازه دهید ما در نظر پیچیده‌تر مجموعه‌ای از مفروضات: "آن است نه آفتابی امروز و آن را سردتر از دیروز". "ما را به شنا کردن تنها در صورتی از آن آفتابی است" "اگر ما فراموش نمی شنا و سپس ما یک کباب پز" و "اگر ما یک کباب پز، پس از آن ما خواهد بود با غروب آفتاب" منجر به نتیجه‌گیری "ما خواهد بود با غروب آفتاب است." اثبات توسط قوانین استنتاج: اجازه بدهید ${\displaystyle p}$ بود که گزاره "آن است که رو به آفتاب امروز" ${\displaystyle q}$ گزاره "آن است که سردتر از دیروز" با ${\displaystyle r}$ گزاره "ما شناً با ${\displaystyle s}$ گزاره "ما یک کباب پز" و ${\displaystyle t}$ گزاره "ما خواهد بود با غروب آفتاب". سپس فرضیه تبدیل شده ${\displaystyle \neg p\wedge q,r\rightarrow p,\neg r\rightarrow s}$ و ${\displaystyle s\rightarrow t}$. با استفاده از شهود ما ما حدس می‌زنیم که این نتیجه ممکن است ${\displaystyle t}$. با استفاده از قواعد استنتاج جدول ما می‌توانیم اثبات این حدس به راحتی:

گام	دلیل
1.${\displaystyle \neg p\wedge q}$	فرضیه
2. ${\displaystyle \neg p}$	ساده‌سازی با استفاده از گام ۱
3. ${\displaystyle r\rightarrow p}$	فرضیه
4. ${\displaystyle \neg r}$	Modus tollens با استفاده از مرحله ۲ و ۳
5. ${\displaystyle \neg r\rightarrow s}$	فرضیه
6. ${\displaystyle s}$	Modus ponens با استفاده از مرحله ۴ و ۵
7. ${\displaystyle s\rightarrow t}$	فرضیه
8. ${\displaystyle t}$	Modus ponens با استفاده از گام ۶ و ۷

منابع

1. Kenneth H. Rosen: Discrete Mathematics and its Applications, Fifth Edition, p. 58.