ಪ್ರೆಡಿಕೇಟ್ ಲಾಜಿಕ್ (Predicate Logic), ಕ್ವಾಂಟಿಫೈಯರ್‌ಗಳು (Quantifiers) ಮತ್ತು ನೆಸ್ಟೆಡ್ ಕ್ವಾಂಟಿಫೈಯರ್‌ಗಳು (Nested Quantifiers) | Predicate Logic, Quantifiers and Nested Quantifiers
In the syllabus of UGC NET CS
Saved in this browser only. Sign in to keep your ticks on every device. See all revisions due
Key points
- ∀ ಜೊತೆ →, ∃ ಜೊತೆ ∧. | ∀ pairs with →, ∃ pairs with ∧.
- ನೆಗೇಶನ್ ಕ್ವಾಂಟಿಫೈಯರ್ ದಾಟಿದಾಗ ∀ ಎಂಬುದು ∃ ಆಗುತ್ತದೆ ಮತ್ತು ವಿರುದ್ಧ. | Negation passing a quantifier turns ∀ into ∃ and the reverse.
- ∀ ಎಂಬುದು ∧ ಮೇಲೆ ವಿತರಿಸುತ್ತದೆ, ∃ ಎಂಬುದು ∨ ಮೇಲೆ; ವಿರುದ್ಧ ಜೋಡಿಗಳು ಇಲ್ಲ. | ∀ distributes over ∧ and ∃ over ∨; the crossed pairs do not.
- ∃y∀x ಇಂದ ∀x∃y ಬರುತ್ತದೆ; ವಿರುದ್ಧ ದಿಕ್ಕು ಬರುವುದಿಲ್ಲ. | ∃y∀x implies ∀x∃y; the reverse does not follow.
- ಫಸ್ಟ್-ಆರ್ಡರ್ ವ್ಯಾಲಿಡಿಟಿ ಅನ್‌ಡಿಸಿಡಬಲ್ ಆದರೆ ಸೆಮಿ-ಡಿಸಿಡಬಲ್. | First-order validity is undecidable but semi-decidable.
On this page
- ಪ್ರೆಡಿಕೇಟ್ (Predicate) ಮತ್ತು ಡೊಮೈನ್ (Domain) | Predicates and the domain
- ಅನುವಾದದ ಸುವರ್ಣ ನಿಯಮ | The golden rule of translation
- ಕ್ವಾಂಟಿಫೈಯರ್ ನೆಗೇಶನ್ (Quantifier Negation) | Negating quantifiers
- ವಿತರಣೆ: ಯಾವುದು ಸರಿ, ಯಾವುದು ಅಲ್ಲ | Distribution: what holds and what does not
- ನೆಸ್ಟೆಡ್ ಕ್ವಾಂಟಿಫೈಯರ್‌ಗಳು (Nested Quantifiers) | Nested quantifiers
- ಪ್ರೆಡಿಕೇಟ್ ಲಾಜಿಕ್‌ನ ಇನ್‌ಫರೆನ್ಸ್ ನಿಯಮಗಳು | Inference rules for quantifiers
- ವ್ಯಾಲಿಡಿಟಿ (Validity) ಮತ್ತು ಡಿಸಿಡಬಿಲಿಟಿ (Decidability) | Validity and decidability
ಪ್ರೆಡಿಕೇಟ್ (Predicate) ಮತ್ತು ಡೊಮೈನ್ (Domain) | Predicates and the domain
ಪ್ರೆಡಿಕೇಟ್ (Predicate) P(x) ಎಂಬುದು ವೇರಿಯೇಬಲ್ ಹೊಂದಿರುವ ವಾಕ್ಯ; x ಗೆ ಡೊಮೈನ್ (Domain) ನಿಂದ ಮೌಲ್ಯ ಕೊಟ್ಟಾಗ ಅಥವಾ ಕ್ವಾಂಟಿಫೈಯರ್ (Quantifier) ಸೇರಿಸಿದಾಗ ಮಾತ್ರ ಅದು ಪ್ರೊಪೊಸಿಷನ್ ಆಗುತ್ತದೆ. | A predicate P(x) is a sentence with a variable; it becomes a proposition only when x is given a value from the domain or is bound by a quantifier.
- ∀x P(x): ಡೊಮೈನ್‌ನ ಪ್ರತಿ x ಗೆ P(x) ಸತ್ಯ. ಸೀಮಿತ ಡೊಮೈನ್‌ನಲ್ಲಿ ಇದು ದೊಡ್ಡ ∧. | ∀x P(x): P(x) holds for every x in the domain. On a finite domain it is a big ∧.
- ∃x P(x): ಕನಿಷ್ಠ ಒಂದು x ಗೆ P(x) ಸತ್ಯ. ಸೀಮಿತ ಡೊಮೈನ್‌ನಲ್ಲಿ ಇದು ದೊಡ್ಡ ∨. | ∃x P(x): P(x) holds for at least one x. On a finite domain it is a big ∨.
- ಬೌಂಡ್ ವೇರಿಯೇಬಲ್ (Bound Variable): ಕ್ವಾಂಟಿಫೈಯರ್ ವ್ಯಾಪ್ತಿಯೊಳಗಿರುವುದು. ಫ್ರೀ ವೇರಿಯೇಬಲ್ (Free Variable): ಯಾವ ಕ್ವಾಂಟಿಫೈಯರ್‌ಗೂ ಒಳಪಡದ್ದು. | Bound variable: inside the scope of a quantifier. Free variable: bound by none.
ಅನುವಾದದ ಸುವರ್ಣ ನಿಯಮ | The golden rule of translation
| ವಾಕ್ಯ | Sentence | ಸರಿ | Correct | ಸಾಮಾನ್ಯ ತಪ್ಪು | Common error |
|---|---|---|
| ಎಲ್ಲಾ ವಿದ್ಯಾರ್ಥಿಗಳು ಬುದ್ಧಿವಂತರು | All students are clever | ∀x (S(x) → C(x)) | ∀x (S(x) → C(x)) | ∀x (S(x) ∧ C(x)): ಪ್ರತಿಯೊಂದೂ ವಿದ್ಯಾರ್ಥಿ ಎಂದು ಹೇಳುತ್ತದೆ | ∀x (S(x) ∧ C(x)): says everything is a student |
| ಕೆಲವು ವಿದ್ಯಾರ್ಥಿಗಳು ಬುದ್ಧಿವಂತರು | Some students are clever | ∃x (S(x) ∧ C(x)) | ∃x (S(x) ∧ C(x)) | ∃x (S(x) → C(x)): ವಿದ್ಯಾರ್ಥಿಯಲ್ಲದ ಒಂದು ವಸ್ತು ಇದ್ದರೂ ಸತ್ಯ | ∃x (S(x) → C(x)): true as soon as one non-student exists |
| ಯಾವ ವಿದ್ಯಾರ್ಥಿಯೂ ಬುದ್ಧಿವಂತನಲ್ಲ | No student is clever | ∀x (S(x) → ¬C(x)) | ∀x (S(x) → ¬C(x)) | ∀x (¬S(x) → ¬C(x)) | ∀x (¬S(x) → ¬C(x)) |
| ಎಲ್ಲಾ ವಿದ್ಯಾರ್ಥಿಗಳು ಬುದ್ಧಿವಂತರಲ್ಲ (Not all) | Not all students are clever | ∃x (S(x) ∧ ¬C(x)) | ∃x (S(x) ∧ ¬C(x)) | ∀x (S(x) → ¬C(x)) | ∀x (S(x) → ¬C(x)) |
∀ ಜೊತೆ → , ∃ ಜೊತೆ ∧. ಇದನ್ನು ಮುರಿದ ಆಯ್ಕೆ ಬಹುತೇಕ ಯಾವಾಗಲೂ ತಪ್ಪು ಉತ್ತರ. | ∀ goes with →, ∃ goes with ∧. An option that breaks this pairing is almost always the wrong one.
ಕ್ವಾಂಟಿಫೈಯರ್ ನೆಗೇಶನ್ (Quantifier Negation) | Negating quantifiers
- ¬∀x P(x) ≡ ∃x ¬P(x) | ¬∀x P(x) ≡ ∃x ¬P(x)
- ¬∃x P(x) ≡ ∀x ¬P(x) | ¬∃x P(x) ≡ ∀x ¬P(x)
- ¬∀x (P(x) → Q(x)) ≡ ∃x (P(x) ∧ ¬Q(x)) | ¬∀x (P(x) → Q(x)) ≡ ∃x (P(x) ∧ ¬Q(x))
- ¬∃x (P(x) ∧ Q(x)) ≡ ∀x (P(x) → ¬Q(x)) | ¬∃x (P(x) ∧ Q(x)) ≡ ∀x (P(x) → ¬Q(x))
ವಿತರಣೆ: ಯಾವುದು ಸರಿ, ಯಾವುದು ಅಲ್ಲ | Distribution: what holds and what does not
| ಸೂತ್ರ | Formula | ಸ್ಥಿತಿ | Status |
|---|---|
| ∀x (P ∧ Q) ≡ ∀x P ∧ ∀x Q | ∀x (P ∧ Q) ≡ ∀x P ∧ ∀x Q | ಸಮಾನ | Equivalent |
| ∃x (P ∨ Q) ≡ ∃x P ∨ ∃x Q | ∃x (P ∨ Q) ≡ ∃x P ∨ ∃x Q | ಸಮಾನ | Equivalent |
| ∀x P ∨ ∀x Q → ∀x (P ∨ Q) | ∀x P ∨ ∀x Q → ∀x (P ∨ Q) | ಒಂದು ದಿಕ್ಕಿನಲ್ಲಿ ಮಾತ್ರ | One direction only |
| ∃x (P ∧ Q) → ∃x P ∧ ∃x Q | ∃x (P ∧ Q) → ∃x P ∧ ∃x Q | ಒಂದು ದಿಕ್ಕಿನಲ್ಲಿ ಮಾತ್ರ | One direction only |
ಪೂರ್ಣಾಂಕಗಳಲ್ಲಿ: ಪ್ರತಿ ಸಂಖ್ಯೆ ಸಮ ಅಥವಾ ಬೆಸ ಎಂಬುದು ಸತ್ಯ, ಆದರೆ ಎಲ್ಲವೂ ಸಮ ಅಥವಾ ಎಲ್ಲವೂ ಬೆಸ ಎಂಬುದು ಅಸತ್ಯ. ಆದ್ದರಿಂದ ∀ ಎಂಬುದು ∨ ಮೇಲೆ ವಿತರಿಸುವುದಿಲ್ಲ. | Over the integers: every number is even or odd is true, but every number is even, or every number is odd, is false. So ∀ does not distribute over ∨.
ನೆಸ್ಟೆಡ್ ಕ್ವಾಂಟಿಫೈಯರ್‌ಗಳು (Nested Quantifiers) | Nested quantifiers
- ಒಂದೇ ಪ್ರಕಾರದ ಕ್ವಾಂಟಿಫೈಯರ್‌ಗಳ ಕ್ರಮ ಬದಲಿಸಬಹುದು: ∀x∀y ≡ ∀y∀x, ∃x∃y ≡ ∃y∃x. | Quantifiers of the same kind commute: ∀x∀y ≡ ∀y∀x and ∃x∃y ≡ ∃y∃x.
- ಮಿಶ್ರ ಕ್ವಾಂಟಿಫೈಯರ್‌ಗಳ ಕ್ರಮ ಬದಲಿಸಬಾರದು: ∃y∀x P(x, y) → ∀x∃y P(x, y) ಸದಾ ಸತ್ಯ, ವಿರುದ್ಧ ದಿಕ್ಕು ಅಲ್ಲ. | Mixed quantifiers do not commute: ∃y∀x P(x, y) → ∀x∃y P(x, y) is valid, the reverse is not.
- ಉದಾ: ಪೂರ್ಣಾಂಕಗಳಲ್ಲಿ ∀x∃y (x + y = 0) ಸತ್ಯ (y = ಋಣ x), ಆದರೆ ∃y∀x (x + y = 0) ಅಸತ್ಯ. | Example: over the integers ∀x∃y (x + y = 0) is true (y = minus x), but ∃y∀x (x + y = 0) is false.
ಪ್ರೆಡಿಕೇಟ್ ಲಾಜಿಕ್‌ನ ಇನ್‌ಫರೆನ್ಸ್ ನಿಯಮಗಳು | Inference rules for quantifiers
- ಯೂನಿವರ್ಸಲ್ ಇನ್‌ಸ್ಟಾಂಶಿಯೇಶನ್ (Universal Instantiation): ∀x P(x) ಇಂದ ಯಾವುದೇ c ಗೆ P(c). | Universal instantiation: from ∀x P(x) infer P(c) for any c.
- ಯೂನಿವರ್ಸಲ್ ಜನರಲೈಸೇಶನ್ (Universal Generalization): ಯಾದೃಚ್ಛಿಕ (arbitrary) c ಗೆ P(c) ಸಾಬೀತಾದರೆ ∀x P(x). | Universal generalization: from P(c) for an arbitrary c infer ∀x P(x).
- ಎಕ್ಸಿಸ್ಟೆನ್ಶಿಯಲ್ ಇನ್‌ಸ್ಟಾಂಶಿಯೇಶನ್ (Existential Instantiation): ∃x P(x) ಇಂದ ಹೊಸ ಕಾನ್ಸ್ಟಂಟ್ c ಗೆ P(c); ಈಗಾಗಲೇ ಬಳಸಿದ ಹೆಸರು ಬಳಸಬಾರದು. | Existential instantiation: from ∃x P(x) infer P(c) for a new constant c; never reuse a name already in the proof.
- ಎಕ್ಸಿಸ್ಟೆನ್ಶಿಯಲ್ ಜನರಲೈಸೇಶನ್ (Existential Generalization): P(c) ಇಂದ ∃x P(x). | Existential generalization: from P(c) infer ∃x P(x).
ವ್ಯಾಲಿಡಿಟಿ (Validity) ಮತ್ತು ಡಿಸಿಡಬಿಲಿಟಿ (Decidability) | Validity and decidability
- ಸೂತ್ರ ವ್ಯಾಲಿಡ್ (Valid) ಆಗುವುದು ಅದರ ನೆಗೇಶನ್ ಅನ್‌ಸ್ಯಾಟಿಸ್ಫಯಬಲ್ (Unsatisfiable) ಆದಾಗ ಮಾತ್ರ. | A formula is valid exactly when its negation is unsatisfiable.
- ಪ್ರೊಪೊಸಿಷನಲ್ ಸ್ಯಾಟಿಸ್ಫಯಬಿಲಿಟಿ (SAT) ಡಿಸಿಡಬಲ್ (Decidable) ಮತ್ತು ಎನ್‌ಪಿ-ಕಂಪ್ಲೀಟ್ (NP-complete). | Propositional satisfiability (SAT) is decidable and NP-complete.
- ಫಸ್ಟ್-ಆರ್ಡರ್ ಲಾಜಿಕ್ (First-Order Logic) ವ್ಯಾಲಿಡಿಟಿ ಅನ್‌ಡಿಸಿಡಬಲ್ (Undecidable), ಆದರೆ ಸೆಮಿ-ಡಿಸಿಡಬಲ್ (Semi-decidable): ವ್ಯಾಲಿಡ್ ಸೂತ್ರಗಳನ್ನು ಸಾಬೀತುಪಡಿಸುವ ಪ್ರಕ್ರಿಯೆ ನಿಲ್ಲುತ್ತದೆ, ಇತರವುಗಳಿಗೆ ನಿಲ್ಲದಿರಬಹುದು. | First-order validity is undecidable but semi-decidable: a procedure halts on valid formulas but may run forever on the rest.
Practice questions
Answer all, then check. Explanations appear after checking.
Finished this topic? Tick it off.
Saved in this browser only. Sign in to keep your ticks on every device. See all revisions due