تعاريف

**تعريف 1**

& لتكن لدينا دارة منطقية α ولها n دخلاً و   mخرجاً هي بيان حلقي ومعنون وموجه α=(V,E) عناصر مجموعة العقد V مرقمة من l إلى |V|  ومقسمة إلى أربع مجموعات منفصلة:

1 - عقد الدخل nodes   input

2- عقد ثابتة nodes  constant

3- عقد عمليات nodes  operation

4- عقد الخرج nodes  output

-ال n عقدة دخل لا تملك أقواساً داخلة إليها. كل واحدة منها معنونة برمز متغير مختلف. فيما يلي سنفترض أن هذه العقد مرقمة من l إلى n وأن عنون العقدة I هو xi حيث: (n...1=i).

العقد الثابتة لا تملك أقواساً داخلة إليها ,و كل منها معنون ب O أو 1. و يمكن أن تكون مجموعة العقد الثابتة خالية (فارغة)، وإن وجدت هذه العقد فإنها ترقم من n+l إلى n+c حيث c>l.

 ال m  عقدة خرج لا تملك أقواساً خارجة منها و تملك تحديداً قوس دخل واحد. كل منها معنون بواسطة رمز متغير مختلف. سنفترض أن هذه العقد مرقمة من 1+ m  -|v| إلى +|v| و إن عنوان العقدة I  هو Yi حيث:

I=|v|-m+1……|v|

عقد العمليات تملك الأقواس الداخلة والخارجة. كل منها معنون برمز لدالة منطقية مع واحد أو أكثر من الوسطاء، ويعطى عدد الوسطاء الموجودة بواسطة عدد الأقواس الداخلة إلى العقدة.

 سنفترض فيما يلي أن عنوان العقدة  I مع ji قوس دخل هو  f1(i)حيث:

F1(i) : {0,1} ^ji   {0,1} , i=n+c+1……..|v|-m

المجموعات F={f1……fr} من جميع الدالات التي تعنون عقد العمليات في a تدعى قاعدة الدارة. وفي حالة خاصة يمكن أن تكون مجموعة عقد العمليات فارغة.

عدد الأقواس الداخلة (الخارجة) لعقدة معطاة يدعى fan-in (fan-out) لتلك العقدة . ويعتبر أعظم    fan-in (maximum) لجميع العقد هو fan-in للدارة، ويحدد عن طريق الدوال القاعدية.

سنبين ذلك على قاعدة تدعى القاعدة القانونية ,و هي مكونة من عمليات الجمع المنطقي والضرب المنطقي والإتمام المنطقي والتي نرمز لها بالرموز التالية على التوالي: (  ᷆, ᴧ,v  )

من المعروف أن القاعدة القانونية هي قاعدة تامة ، على سبيل المثال إن أي دالة منطقية يمكن أن نعبر عنها بواسطة عمليات الجمع المنطقي والضرب المنطقي والإتمام المنطقي فقط.

 ال in  fan للدارات المعرفة على القاعدة القانونية هو بوضوح (2).    &

**تعريف 2**

&  لتكن (V.E)α دارة منطقية ب n دخلاً و m خرجاً ، يرمز لحجم الدارة a ب  z(a)هو عدد  العقد في الدارة أي إن:

Z(a)>=n+m ان z(a)=|v|

يرمز ب (a)D لعمق الدارة وهو الطول الأعظمي للمسالك في الدارة (أي بين جميع المسالك الواصلة بين عقد الدخل وعقد الخرج).إن الحجم والعمق هما أهم مقياسين للتعقيد في الدارات المنطقية.

يظهر الشكل  التالي دارة منطقية بسيطة فيها أربعة مداخل ومخرج واحد. حجمها وعمقها على التوالي هما 15 و 6.

الشكل السابق يبين دارة منطقية بسيطة تعتمد على القاعدة القانونية فيها D(a)=6 , z(a)=15

سنفترض فيما يلي أن كل عقدة دخل تتصل بعقدة خرج من خلال مسلك ، إذ إن كل دخل يستعمل في تحديد قيمة الخرج إلى حد ما مما يوضح أهمية العمق لدارة.

إن الدارة  a  بـ n مدخلاً  و  m  خرجاً حيث n>m تملك عمقاً لا يقل عن  [log.(n\m)]+1حيث هو fan-in الدارة.