تابع ارزش

در منطق، **تابع صدق** تابعی است که ارزش‌های صدق را به عنوان ورودی می‌پذیرد و یک ارزش صدق منحصربه‌فرد را به عنوان خروجی تولید می‌کند. به عبارت دیگر: ورودی و خروجی یک تابع صدق همه ارزش‌های صدق هستند؛ یک تابع صدق همیشه دقیقاً یک ارزش صدق را خروجی می‌دهد و ورودی دادن همان ارزش(های) صدق همیشه همان ارزش صدق را خروجی می‌دهد. مثال بارز آن در منطق گزاره‌ای است، که در آن یک گزاره مرکب با استفاده از گزاره‌های منفردی ساخته می‌شود که توسط پیوندهای منطقی به هم متصل شده‌اند؛ اگر ارزش صدق گزاره مرکب کاملاً توسط ارزش(های) صدق گزاره(های) سازنده تعیین شود، گزاره مرکب یک تابع صدق نامیده می‌شود و هر پیوند منطقی استفاده‌شده **تابع صدق** گفته می‌شود.

منطق گزاره‌ای کلاسیک یک منطق تابع‌صدق است، از این جهت که هر گزاره دقیقاً یک ارزش صدق دارد که یا صادق است یا کاذب، و هر پیوند منطقی تابع صدق است (با یک جدول درستی متناظر)، بنابراین هر گزاره مرکب یک تابع صدق است. از سوی دیگر، منطق موجهات غیرتابع-صدق است.

## مرور کلی
یک پیوند منطقی تابع صدق است اگر ارزش-صدق یک جمله مرکب تابعی از ارزش-صدق جملات زیر-جمله آن باشد. یک رده از پیوندها تابع صدق است اگر هر یک از اعضای آن چنین باشد. برای مثال، پیوند "*و*" تابع صدق است، زیرا جمله‌ای مانند "*سیب میوه است و هویج سبزی است*" صادق است *[[اگر و فقط اگر]]*، هر یک از جملات زیر-جمله آن "*سیب میوه است*" و "*هویج سبزی است*" صادق باشد، و در غیر این صورت کاذب است. برخی از پیوندهای یک زبان طبیعی، مانند انگلیسی، تابع صدق نیستند.

پیوندهایی به شکل "x *باور دارد که* ..." نمونه‌های بارز پیوندهایی هستند که تابع صدق نیستند. اگر مثلاً ماری به اشتباه باور داشته باشد که ال گور در ۲۰ آوریل ۲۰۰۰ رئیس‌جمهور ایالات متحده بوده است، اما او باور نداشته باشد که ماه از پنیر سبز درست شده است، آن‌گاه جمله

:"*ماری باور دارد که ال گور در ۲۰ آوریل ۲۰۰۰ رئیس‌جمهور ایالات متحده بود*"

صادق است در حالی که

:"*ماری باور دارد که ماه از پنیر سبز درست شده است*"

کاذب است. در هر دو مورد، هر جمله مؤلفه (یعنی "*ال گور در ۲۰ آوریل ۲۰۰۰ رئیس‌جمهور ایالات متحده بود*" و "*ماه از پنیر سبز درست شده است*") کاذب است، اما هر جمله مرکب که با پیشوند قرار دادن عبارت "*ماری باور دارد که*" ساخته شده است از نظر ارزش-صدق متفاوت است. یعنی، ارزش-صدق یک جمله به شکل "*ماری باور دارد که...*" صرفاً با ارزش-صدق جمله مؤلفه آن تعیین نمی‌شود، و از این رو، (تک‌تایی) پیوند منطقی (یا صرفاً *عملگر* زیرا تکی است) غیرتابع-صدق است.

رده پیوندهای منطق کلاسیک (مانند &، →) که در ساخت فرمول‌ها استفاده می‌شوند، تابع صدق هستند. مقادیر آن‌ها برای ارزش‌های-صدق مختلف به عنوان آرگومان معمولاً توسط جدول‌های درستی داده می‌شود. حساب گزاره‌ای تابع-صدق یک سامانه صوری است که فرمول‌های آن ممکن است به عنوان صادق یا کاذب تفسیر شوند.

## جدول توابع صدق دوتایی

در منطق دو-ارزشی، شانزده تابع صدق ممکن وجود دارد که توابع بولی نیز نامیده می‌شوند، با دو ورودی *P* و *Q*. هر یک از این توابع با یک جدول درستی از یک پیوند منطقی خاص در منطق کلاسیک مطابقت دارد، از جمله چندین حالت منحط مانند تابعی که به یک یا هر دو آرگومان خود وابسته نیست. صدق و کاذب به ترتیب به عنوان ۱ و ۰ در جدول‌های درستی زیر برای اختصار نشان داده شده‌اند.

## تمامیت تابعی

از آنجا که یک تابع ممکن است به صورت یک ترکیب بیان شود، یک حساب منطقی تابع-صدق نیازی به داشتن نمادهای اختصاصی برای تمام توابع فوق‌الذکر ندارد تا از نظر تابعی کامل باشد. این در یک حساب گزاره‌ای به صورت هم‌ارزی منطقی گزاره‌های مرکب خاصی بیان می‌شود. برای مثال، منطق کلاسیک دارای  است که با  هم‌ارز است. بنابراین عملگر شرطی "→" برای یک سامانه منطقی مبتنی بر کلاسیک ضروری نیست اگر "¬" (نقیض) و "∨" (فصل) از قبل استفاده شده باشند.

یک مجموعه از عملگرها که می‌توانند هر گزاره قابل بیانی در حساب گزاره‌ای را بیان کنند، یک *مجموعه تماماً تابعی مینیمال* نامیده می‌شود. یک مجموعه مینیمال کامل از عملگرها با NAND به تنهایی {↑} و NOR به تنهایی {↓} به دست می‌آید.

موارد زیر مجموعه‌های تماماً تابعی مینیمال از عملگرهایی هستند که تعداد آرگومان‌های آن‌ها از ۲ تجاوز نمی‌کند:
;یک عنصر: {↑}, {↓}.
;دو عنصر: \{\vee, \neg\}, \{\wedge, \neg\}, \{\to, \neg\}, \{\gets, \neg\}, \{\to, \bot\}, \{\gets, \bot\}, \{\to, \nleftrightarrow\}, \{\gets, \nleftrightarrow\}, \{\to, \nrightarrow\}, \{\to, \nleftarrow\}, \{\gets, \nrightarrow\}, \{\gets, \nleftarrow\}, \{\nrightarrow, \neg\}, \{\nleftarrow, \neg\}, \{\nrightarrow, \top\}, \{\nleftarrow, \top\}, \{\nrightarrow, \leftrightarrow\}, \{\nleftarrow, \leftrightarrow\}.
;سه عنصر: \{\lor, \leftrightarrow, \bot\}, \{\lor, \leftrightarrow, \nleftrightarrow\}, \{\lor, \nleftrightarrow, \top\}, \{\land, \leftrightarrow, \bot\}, \{\land, \leftrightarrow, \nleftrightarrow\}, \{\land, \nleftrightarrow, \top\}.

## ویژگی‌های جبری
برخی توابع صدق دارای ویژگی‌هایی هستند که ممکن است در قضایای حاوی پیوند مربوطه بیان شوند. برخی از آن ویژگی‌هایی که یک تابع صدق دوتایی (یا یک پیوند منطقی متناظر) ممکن است داشته باشد عبارتند از:

**[[شرکت‌پذیری]]*: در یک عبارت شامل دو یا چند تا از پیوندهای شرکت‌پذیر مشابه به صورت متوالی، ترتیب عملیات تا زمانی که توالی عملوندها تغییر نکند، اهمیتی ندارد.
**[[جابجایی‌پذیری]]*: عملوندهای پیوند ممکن است بدون تأثیر بر ارزش-صدق عبارت جابجا شوند.
**[[توزیع‌پذیری]]*: یک پیوند که با · نشان داده می‌شود بر روی پیوند دیگری که با + نشان داده می‌شود توزیع می‌شود، اگر برای همه عملوندهای *a*، *b*، *c* داشته باشیم *a* · (*b* + *c*) = (*a* · *b*) + (*a* · *c*).
**[[خودتوانی]]*: هرگاه عملوندهای عملیات یکسان باشند، پیوند عملوند را به عنوان نتیجه می‌دهد. به عبارت دیگر، عملیات هم صدق-نگهدار و هم کذب-نگهدار است (به زیر مراجعه کنید).
**[[قانون جذب|جذب]]*: یک جفت از پیوندها \land, \lor قانون جذب را برآورده می‌کند اگر برای همه عملوندهای *a*، *b* داشته باشیم a\land(a\lor b)=a\lor(a\land b)=a.

یک مجموعه از توابع صدق از نظر تابعی کامل است اگر و فقط اگر برای هر یک از پنج ویژگی زیر حداقل یک عضو داشته باشد که فاقد آن ویژگی باشد:
**[[یکنوا]]*: اگر برای همه *a*1, ..., *a**n*, *b*1, ..., *b**n* ∈ {0,1} به طوری که *a*1 ≤ *b*1, *a*2 ≤ *b*2, ..., *a**n* ≤ *b**n*، آن‌گاه *f*(*a*1, ..., *a**n*) ≤ *f*(*b*1, ..., *b**n*). برای مثال، \vee, \wedge, \top, \bot.
**[[نگاشت آفین|آفین]]*: برای هر متغیر، تغییر مقدار آن یا همیشه ارزش-صدق عملیات را تغییر می‌دهد یا هرگز آن را تغییر نمی‌دهد، برای همه مقادیر ثابت سایر متغیرها. برای مثال، \neg, \leftrightarrow، \not\leftrightarrow, \top, \bot.
**خود دوگان*: خواندن تخصیص‌های ارزش-صدق برای عملیات از بالا به پایین در جدول درستی آن، همانند گرفتن متمم خواندن آن از پایین به بالا است؛ به عبارت دیگر، *f*(¬*a*1, ..., ¬*a**n*) = ¬*f*(*a*1, ..., *a**n*). برای مثال، \neg.
**صدق-نگهدار*: تفسیری که تحت آن به همه متغیرها یک ارزش صدق *صادق* نسبت داده می‌شود، یک ارزش صدق *صادق* را در نتیجه این عملیات تولید می‌کند. برای مثال، \vee, \wedge, \top, \rightarrow, \leftrightarrow, \subset. (نگاه کنید به اعتبار)
**کذب-نگهدار*: تفسیری که تحت آن به همه متغیرها یک ارزش صدق *کاذب* نسبت داده می‌شود، یک ارزش صدق *کاذب* را در نتیجه این عملیات تولید می‌کند. برای مثال، \vee, \wedge, \nleftrightarrow, \bot, \not\subset, \not\supset. (نگاه کنید به اعتبار)

### تعداد آرگومان‌ها

یک تابع عینی ممکن است به عنوان یک *عملگر* نیز نامیده شود. در منطق دو-ارزشی، ۲ عملگر صفرتایی (ثابت‌ها)، ۴ عملگر یکتایی، ۱۶ عملگر دوتایی، ۲۵۶ عملگر سه‌تایی، و 2^{2^n} عملگر *n*-تایی وجود دارد. در منطق سه-ارزشی، ۳ عملگر صفرتایی (ثابت‌ها)، ۲۷ عملگر یکتایی، ۱۹۶۸۳ عملگر دوتایی، ۷۶۲۵۵۹۷۴۸۴۹۸۷ عملگر سه‌تایی، و 3^{3^n} عملگر *n*-تایی وجود دارد. در منطق *k*-ارزشی، *k* عملگر صفرتایی، k^k عملگر یکتایی، k^{k^2} عملگر دوتایی، k^{k^3} عملگر سه‌تایی، و k^{k^n} عملگر *n*-تایی وجود دارد. یک عملگر *n*-تایی در منطق *k*-ارزشی تابعی است از \mathbb{Z}_k^n \to \mathbb{Z}_k. بنابراین، تعداد چنین عملگرهایی |\mathbb{Z}_k|^ = k^{k^n} است، که نحوه به‌دست‌آوردن اعداد فوق است.

با این حال، برخی از عملگرهای یک تعداد آرگومان خاص در واقع اشکال منحطی هستند که یک عملیات با تعداد آرگومان کمتر را روی برخی از ورودی‌ها انجام می‌دهند و بقیه ورودی‌ها را نادیده می‌گیرند. از میان ۲۵۶ عملگر سه‌تایی بولی ذکر شده در بالا، \binom{3}{2}\cdot 16 - \binom{3}{1}\cdot 4 + \binom{3}{0}\cdot 2 از آن‌ها چنین اشکال منحطی از عملگرهای دوتایی یا با تعداد آرگومان کمتر هستند، با استفاده از اصل شمول و عدم شمول. عملگر سه‌تایی f(x,y,z)=\lnot x یکی از این عملگرها است که در واقع یک عملگر یکتایی است که به یک ورودی اعمال می‌شود و دو ورودی دیگر را نادیده می‌گیرد.

"نقیض" یک عملگر یکتایی است، یک عبارت واحد را می‌گیرد (¬*P*). بقیه عملگرهای دوتایی هستند که دو عبارت را می‌گیرند تا یک گزاره مرکب بسازند ().

مجموعه عملگرهای منطقی  ممکن است به زیرمجموعه‌های مجزا به صورت زیر تجزیه شود:

::: \Omega = \Omega_0 \cup \Omega_1 \cup \ldots \cup \Omega_j \cup \ldots \cup \Omega_m \,.

در این تجزیه، \Omega_j مجموعه نمادهای عملگر با *[[تعداد آرگومان‌ها|تعداد آرگومان‌]]*  است.

در حساب‌های گزاره‌ای آشناتر، \Omega معمولاً به صورت زیر تجزیه می‌شود:

:::عملگرهای صفرتایی: \Omega_0 = \{\bot, \top \} 

:::عملگرهای یکتایی: \Omega_1 = \{ \lnot \} 

:::عملگرهای دوتایی: \Omega_2 \supset \{ \land, \lor, \rightarrow, \leftrightarrow \} 

## اصل ترکیب‌پذیری

به جای استفاده از جدول‌های درستی، نمادهای پیوند منطقی را می‌توان به وسیله یک تابع تفسیر و یک مجموعه تماماً تابعی از توابع-صدق تفسیر کرد (گاموت ۱۹۹۱)، همانطور که توسط اصل ترکیب‌پذیری معنا شرح داده شده است.
فرض کنید  یک تابع تفسیر باشد، فرض کنید  هر دو جمله دلخواه باشند و تابع صدق *f*nand به صورت زیر تعریف شود:
* *f*nand(T,T) = F; *f*nand(T,F) = *f*nand(F,T) = *f*nand(F,F) = T

سپس، برای راحتی، *f*not، *f*or، *f*and و غیره به وسیله *f*nand تعریف می‌شوند:

* *f*not(*x*) = *f*nand(*x*,*x*)
* *f*or(*x*,*y*) = *f*nand(*f*not(*x*), *f*not(*y*))
* *f*and(*x*,*y*) = *f*not(*f*nand(*x*,*y*))

یا به طور جایگزین، *f*not، *f*or، *f*and و غیره به طور مستقیم تعریف می‌شوند:

* *f*not(T) = F; *f*not(F) = T;
* *f*or(T,T) = *f*or(T,F) = *f*or(F,T) = T; *f*or(F,F) = F
* *f*and(T,T) = T; *f*and(T,F) = *f*and(F,T) = *f*and(F,F) = F

سپس

و غیره.

بنابراین اگر *S* جمله‌ای باشد که رشته‌ای از نمادها متشکل از نمادهای منطقی *v*1...*v**n* نمایانگر پیوندهای منطقی، و نمادهای غیرمنطقی *c*1...*c**n* است، آن‌گاه اگر و فقط اگر  برای تفسیر *v*1 تا *v**n* به وسیله *f*nand (یا هر مجموعه دیگری از توابع-صدق کامل) ارائه شده باشد، آن‌گاه ارزش-صدق  کاملاً توسط ارزش‌های-صدق *c*1...*c**n*، یعنی  تعیین می‌شود. به عبارت دیگر، همانطور که انتظار می‌رود و لازم است، *S* فقط تحت تفسیر همه نمادهای غیرمنطقی خود صادق یا کاذب است.

## تعریف

با استفاده از توابع تعریف‌شده در بالا، می‌توانیم یک تعریف صوری از تابع صدق یک گزاره ارائه دهیم.

فرض کنید *PROP* مجموعه همه متغیرهای گزاره‌ای باشد،

:  PROP = \{p_1,p_2,\dots\}

ما یک **تخصیص صدق** را به عنوان هر تابع \phi:PROP\to \{T,F\} تعریف می‌کنیم. یک تخصیص صدق بنابراین یک ارتباط از هر متغیر گزاره‌ای با یک ارزش صدق خاص است. این در واقع معادل یک ردیف خاص از جدول درستی یک گزاره است.

برای یک تخصیص صدق، \phi، ما **تخصیص صدق توسعه‌یافته** آن را، \overline\phi، به صورت زیر تعریف می‌کنیم. این \phi را به یک تابع جدید \overline \phi گسترش می‌دهد که دامنه آن برابر با مجموعه همه فرمول‌های گزاره‌ای است. برد \overline\phi همچنان \{T,F\} است.

# اگر A \in PROP آن‌گاه \overline\phi(A) = \phi(A).
# اگر *A* و *B* هر فرمول گزاره‌ای باشند، آن‌گاه 
## \overline\phi(\neg A) = f_{\text{not}} (\overline\phi(A)).
## \overline\phi(A\land B) = f_{\text{and}} (\overline\phi(A),\overline\phi(B)).
## \overline\phi(A\lor B) = f_{\text{or}} (\overline\phi(A),\overline\phi(B)).
## \overline\phi(A\to B) = \overline\phi(\neg A\lor B).
## \overline\phi(A\leftrightarrow B) = \overline\phi((A\to B)\land (B\to A)).

سرانجام، اکنون که تخصیص صدق توسعه‌یافته را تعریف کردیم، می‌توانیم از آن برای تعریف تابع-صدق یک گزاره استفاده کنیم. برای یک گزاره، *A*، **تابع صدق** آن، f_A، دارای دامنه‌ای برابر با مجموعه همه تخصیص‌های صدق و برد برابر با \{T,F\} است.  

این تابع، برای هر تخصیص صدق \phi، توسط f_A(\phi) = \overline\phi(A) تعریف می‌شود. مقدار داده‌شده توسط \overline\phi(A) همان مقداری است که در ستون آخر جدول درستی *A*، در ردیف شناسایی‌شده با \phi نمایش داده می‌شود.

## علوم کامپیوتر
عملگرهای منطقی به عنوان گیت‌های منطقی در مدارهای دیجیتال پیاده‌سازی می‌شوند. عملاً تمام مدارهای دیجیتال (استثنای عمده DRAM است) از گیت‌های NAND، NOR، NOT و گیت‌های انتقال ساخته می‌شوند. گیت‌های NAND و NOR با ۳ یا بیشتر ورودی به جای ۲ ورودی معمول، نسبتاً رایج هستند، اگرچه از نظر منطقی معادل یک آبشار از گیت‌های ۲ ورودی هستند. همه عملگرهای دیگر با تجزیه آن‌ها به یک ترکیب منطقی معادل از ۲ یا بیشتر از گیت‌های منطقی فوق پیاده‌سازی می‌شوند.

"هم‌ارزی منطقی" "NAND به تنهایی"، "NOR به تنهایی"، و "NOT و AND" مشابه هم‌ارزی تورینگ است.

این واقعیت که همه توابع صدق را می‌توان با NOR به تنهایی بیان کرد، توسط رایانه راهنمای آپولو نشان داده شده است.

## جستارهای وابسته

* برتراند راسل و آلفرد نورث وایتهد،*[[پرینکیپیا ریاضی]]*، ویرایش دوم
* لودویگ ویتگنشتاین،*[[رساله منطقی-فلسفی]]*، گزاره ۵.۱۰۱
* عملیات بیتی
* تابع دوتایی
* دامنه بولی
* منطق بولی
* تابع بولی
* فهرست موضوعات جبر بولی
* ثابت منطقی
* عملگر وجهی
* حساب گزاره‌ای
* منطق گزاره‌ای تابع-صدق

## یادداشت‌ها

## منابع
*

## مطالعه بیشتر
* یوزف ماریا بوخنسکی (۱۹۵۹)، *خلاصه منطق ریاضی*، ترجمه از نسخه‌های فرانسوی و آلمانی توسط اوتو برد، دوردرخت، هلند جنوبی: انتشارات دی رایدل.
* آلونزو چرچ (۱۹۴۴)، *مقدمه‌ای بر منطق ریاضی*، پرینستون، نیوجرسی: انتشارات دانشگاه پرینستون. برای تاریخچه مفهوم تابع صدق به مقدمه مراجعه کنید.

رده:منطق ریاضی
رده:درست منطقی