Propositional Logic (منطق القضايا)
Logical Connectives
- Negation ($\neg p$) NOT
- Conjunction ($p \land q$) AND
- Disjunction ($p \lor q$) OR
- Implication ($p \to q$) IF..THEN
- Bi-conditional ($p \leftrightarrow q$) IF AND ONLY IF
Important Definitions
- Tautology: عبارة صحيحة دائماً (Always True).
- Contradiction: عبارة خاطئة دائماً (Always False).
- Satisfiable: يمكن أن تكون صحيحة لتعويض واحد على الأقل.
Normal Forms (الأشكال القياسية)
Conjunctive Normal Form (CNF)
Product of Sums (AND of ORs)
مهم جداً لحل مشاكل الـ SAT ولخوارزميات الإثبات الآلي.
Disjunctive Normal Form (DNF)
Sum of Products (OR of ANDs)
سهل جداً للتحقق من الـ Satisfiability (يكفي أن يكون قوس واحد صحيحاً).
Rules of Inference (قواعد الاستنتاج)
| القاعدة | الشكل المنطقي | الوصف |
|---|---|---|
| Modus Ponens | $p \to q, p \vdash q$ | إذا تحقق الشرط والسبب، تتحقق النتيجة. |
| Modus Tollens | $p \to q, \neg q \vdash \neg p$ | إذا انتفت النتيجة، ينتفي السبب. |
| Hypothetical Syllogism | $p \to q, q \to r \vdash p \to r$ | التعدي (Transitive). |
Quantifiers (المكممات)
$\forall$
Universal Quantifier
"For all" (لكل).
$\exists$
Existential Quantifier
"There exists" (يوجد).
DeMorgan's Laws for Quantifiers
عندما يدخل النفي ($\neg$) على المكمم، فإنه يقلبه:
$\neg (\forall x, P(x)) \equiv \exists x, \neg P(x)$
$\neg (\exists x, P(x)) \equiv \forall x, \neg P(x)$
لا تنسَ نفي الدالة $P(x)$ أيضاً!
Universal Instantiation
إذا كانت $\forall x, P(x)$ صحيحة، فيمكنك استنتاج $P(c)$ لأي عنصر $c$ في المجال.
هذه القاعدة هي التي تسمح لنا بتطبيق القوانين العامة على الحالات الخاصة.