یک متغیر منطقی مانند a متغیری است که تنها مقادیر ۰ و ۱ را میپذیرد. دستگاهی داریم که n+1 متغیر منطقی xi (0≤i≤n) و n+1 متغیر منطقی yi (0≤i≤n) به آن وارد میشوند و یک متغیر منطقی r از آن خارج میشود. به ازای هر 1≤i≤n داریم yi=1−xi. در ضمن همیشه x0=0 و y0=1 است. اگر دستکم دو تا از متغیرهای xi مقدار ۱ داشته باشند٬ r=1 و در غیر این صورت r=0 خواهد بود.
دو نوع قطعهی منطقی داریم که در ساخت این دستگاه از آن استفاده شده است. هر کدام از این قطعات دو ورودی و یک خروجی دارند. خروجی قطعهی از نوع A تنها وقتی ۱ است که هر دو ورودی ۱ باشد. حال آن که خروجی قطعهی از نوع B تنها وقتی ۰ است که هر دو ورودی ۰ باشد.
در ساخت این دستگاه از K قطعه استفاده کردهایم که با شمارههای ۱ تا K نشان داده میشوند. هر یک از ورودیهای یک قطعه میتواند از ورودیهای دستگاه (یعنی xiها و yiها) یا خروجی قطعات قبلی (با شماره کوچکتر) باشد. در ضمن خروجی دستگاه(همان r) خروجی آخرین قطعه است.
به عنوان مثال٬ ورودیهای قطعه شماره ۱ ممکن است x1 و y2 باشند. قطعهی شماره ۲ ممکن است ورودیهایش x1 و خروجی قطعهی شماره ۱ باشند. قطعهی شماره ۳ نیز ممکن است ورودیهایش را از خروجی قطعات ۱ و ۲ بگیرد.
الف) ثابت کنید که عدد 1≤i≤n و دو قطعهی P و Q وجود دارند به طوری که هر یک از دو قطعهی P و Q حداقل یکی از ورودیهایشان را از مجموعهی {xi,yi} میگیرند.
ب) نشان دهید که 2n−4≤K.