یک متغیر منطقی مانند $a$ متغیری است که تنها مقادیر ۰ و ۱ را می‌پذیرد. دستگاهی داریم که $n+1$ متغیر منطقی $x_i$ ($0 \le i \le n$) و $n + 1$ متغیر منطقی $y_i$ ($0 \le i \le n$) به آن وارد می‌شوند و یک متغیر منطقی $r$ از آن خارج می‌شود. به ازای هر $1 \le i \le n$ داریم $y_i = 1 - x_i$. در ضمن همیشه $x_0 = 0$ و $y_0 = 1$ است. اگر دست‌کم دو تا از متغیرهای $x_i$ مقدار ۱ داشته باشند٬ $r=1$ و در غیر این صورت $r=0$ خواهد بود.

دو نوع قطعه‌ی منطقی داریم که در ساخت این دستگاه از آن استفاده شده است. هر کدام از این قطعات دو ورودی و یک خروجی دارند. خروجی قطعه‌ی از نوع $A$ تنها وقتی ۱ است که هر دو ورودی ۱ باشد. حال آن که خروجی قطعه‌ی از نوع $B$ تنها وقتی ۰ است که هر دو ورودی ۰ باشد.

در ساخت این دستگاه از $K$ قطعه استفاده کرده‌ایم که با شماره‌های ۱ تا $K$ نشان داده می‌شوند. هر یک از ورودی‌های یک قطعه می‌تواند از ورودی‌های دستگاه (یعنی $x_i$ها و $y_i$ها) یا خروجی قطعات قبلی (با شماره کوچک‌تر) باشد. در ضمن خروجی دستگاه(همان $r$) خروجی آخرین قطعه است.

به عنوان مثال٬ ورودی‌های قطعه شماره ۱ ممکن است $x_1$ و $y_2$ باشند. قطعه‌ی شماره ۲ ممکن است ورودی‌هایش $x_1$ و خروجی قطعه‌ی شماره ۱ باشند. قطعه‌ی شماره ۳ نیز ممکن است ورودی‌هایش را از خروجی قطعات ۱ و ۲ بگیرد.

الف) ثابت کنید که عدد $1 \le i \le n$ و دو قطعه‌ی $P$ و $Q$ وجود دارند به طوری که هر یک از دو قطعه‌ی $P$ و $Q$ حداقل یکی از ورودی‌هایشان را از مجموعه‌ی {$x_i,y_i$} می‌گیرند.

ب) نشان دهید که $2n-4 \le K$.

• سوال بعد
• سوال قبل