Mathematical Preliminaries

الفصل الأول: الأساسيات الرياضية (مجموعات، علاقات، ورسوم بيانية)

الهدف: بناء الأساس المنطقي لفهم لغات الآلة والأوتوماتا لاحقاً.
1

Sets (المجموعات)

الخصائص الأساسية

  • بدون ترتيب (Unordered): الترتيب لا يهم $\{1, 2\} = \{2, 1\}$.
  • بدون تكرار (Unique): العناصر لا تتكرر $\{1, 1, 2\} = \{1, 2\}$.
  • المجموعة الخالية (Empty Set): يرمز لها بـ $\emptyset$ أو $\{\}$.
  • Universal Set (U): المجموعة الشاملة لكل العناصر المحتملة.

Power Set (مجموعة القوى)

هي مجموعة كل المجموعات الجزئية (Subsets) الممكنة.

إذا كانت $|S| = n$، فإن عدد عناصر $P(S) = 2^n$.
مثال: $S=\{0, 1\}$
$P(S) = \{ \emptyset, \{0\}, \{1\}, \{0, 1\} \}$ (4 عناصر).

العمليات على المجموعات (Set Operations)

Union ($\cup$) $A \cup B$
العناصر في A أو B.
Intersection ($\cap$) $A \cap B$
العناصر المشتركة فقط.
Difference ($-$) $A - B$
في A وليست في B.
Cartesian ($\times$) $A \times B$
أزواج مرتبة $\{(a,b)\}$.
2

Relations & Functions

Equivalence Relation (علاقة التكافؤ)

يجب أن تحقق 3 شروط:

  1. Reflexive (انعكاسية): $xRx$.
  2. Symmetric (تناظرية): $xRy \iff yRx$.
  3. Transitive (متعدية): $xRy \land yRz \implies xRz$.

Function (الدالة)

هي علاقة خاصة حيث كل مدخل (Input) له مخرج (Output) واحد فقط.

Vertical Line Test: إذا قطع الخط الرأسي الرسم البياني في أكثر من نقطة، فهي ليست دالة.
3

Graphs & Trees

Graph Terminology

  • Node (Vertex): العنصر (الدائرة).
  • Edge: الرابط بين عنصرين.
  • Path: تسلسل من العقد المتصلة.
  • Cycle: مسار يبدأ وينتهي بنفس العقدة.
  • Connected: يوجد مسار بين أي زوج من العقد.

Trees (الأشجار)

هي Graph متصل (Connected) ولا يحتوي على دوائر (Acyclic).

Binary Tree Height:
عدد العقد الأقصى لشجرة ارتفاعها $h$:
$$ Nodes = 2^{h+1} - 1 $$
(ملاحظة: أحياناً يحسب الارتفاع بعدد الحواف أو عدد المستويات، تأكد من تعريف كتابك).
4

Strings & Languages

المصطلح الرمز الشرح
Alphabet $\Sigma$ مجموعة محدودة من الرموز (مثل $\{0, 1\}$).
String $w$ سلسلة من الرموز (مثل $101$).
Empty String $\epsilon$ السلسلة الفارغة (طولها 0).
Kleene Star $\Sigma^*$ كل السلاسل الممكنة (بما فيها الفارغة).
Positive Closure $\Sigma^+$ كل السلاسل الممكنة (بدون الفارغة).
5

Proof Techniques (البراهين)

1. Proof by Induction (الاستقراء الرياضي)

تستخدم لإثبات صحة عبارة لجميع الأعداد الطبيعية.

  • Basis Step: أثبت صحة العبارة عند $n=0$ أو $n=1$.
  • Inductive Hypothesis: افترض أن العبارة صحيحة عند $n=k$.
  • Inductive Step: أثبت صحة العبارة عند $n=k+1$.

2. Proof by Contradiction (التناقض)

لإثبات $P$:
1. افترض أن $P$ خاطئة (النقيض).
2. حاول الوصول إلى نتيجة منطقية مستحيلة (تناقض).
3. إذاً الفرضية خاطئة، و $P$ صحيحة.
(مثال: إثبات أن $\sqrt{2}$ عدد غير نسبي).

🛡️ EXAM VAULT (خزنة الاختبار)
TRAP / فخ

Empty Set vs Set Containing Empty Set

انتبه للفرق!
$\emptyset$ : مجموعة فارغة، عدد عناصرها 0.
$\{\emptyset\}$ : مجموعة تحتوي على عنصر واحد (وهو المجموعة الفارغة)، عدد عناصرها 1.

CALCULATION / حساب

Number of Subsets

كم عدد المجموعات الجزئية لمجموعة تحتوي على 5 عناصر؟
القاعدة: $|P(S)| = 2^{|S|}$
الجواب: $2^5 = 32$.
تذكر: المجموعة الفارغة ونفس المجموعة دائماً من ضمنهم.

الرئيسية الفصل التالي (Ch 2) ←