Processing math: 100%

المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:مرحله ی دوم:دوره ی ۱۵:سوال ۷

مدار منطقی

یک متغیر منطقی مانند a متغیری است که تنها مقادیر ۰ و ۱ را می‌پذیرد. دستگاهی داریم که n+1 متغیر منطقی xi (0in) و n+1 متغیر منطقی yi (0in) به آن وارد می‌شوند و یک متغیر منطقی r از آن خارج می‌شود. به ازای هر 1in داریم yi=1xi. در ضمن همیشه x0=0 و y0=1 است. اگر دست‌کم دو تا از متغیرهای xi مقدار ۱ داشته باشند٬ r=1 و در غیر این صورت r=0 خواهد بود.

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

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

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

الف) ثابت کنید که عدد 1in و دو قطعه‌ی P و Q وجود دارند به طوری که هر یک از دو قطعه‌ی P و Q حداقل یکی از ورودی‌هایشان را از مجموعه‌ی {xi,yi} می‌گیرند.

ب) نشان دهید که 2n4K.


ابزار صفحه