ಈಕ್ವಿವಲೆನ್ಸ್‌ಗಳು (Equivalences), ನಾರ್ಮಲ್ ಫಾರ್ಮ್‌ಗಳು (Normal Forms) ಮತ್ತು ರೂಲ್ಸ್ ಆಫ್ ಇನ್‌ಫರೆನ್ಸ್ (Rules of Inference) | Equivalences, Normal Forms and Rules of Inference
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
- p → q ≡ ¬p ∨ q ಮತ್ತು p ∨ q ≡ ¬p → q; ಹೆಚ್ಚಿನ ಸರಳೀಕರಣಗಳು ಇಲ್ಲಿಂದ ಪ್ರಾರಂಭ. | p → q ≡ ¬p ∨ q and p ∨ q ≡ ¬p → q; most simplifications start here.
- ಪಿಡಿಎನ್‌ಎಫ್ (PDNF) ಮಿಂಟರ್ಮ್‌ಗಳು T ಸಾಲುಗಳು; ಪಿಸಿಎನ್‌ಎಫ್ (PCNF) ಮ್ಯಾಕ್ಸ್‌ಟರ್ಮ್‌ಗಳು F ಸಾಲುಗಳು. | PDNF minterms are the T rows; PCNF maxterms are the F rows.
- {∧, ∨} ಫಂಕ್ಷನಲಿ ಕಂಪ್ಲೀಟ್ ಅಲ್ಲ; NAND ಮತ್ತು NOR ಒಂಟಿಯಾಗಿಯೇ ಕಂಪ್ಲೀಟ್. | {∧, ∨} is not functionally complete; NAND and NOR are each complete on their own.
- ಮೋಡಸ್ ಟೋಲೆನ್ಸ್ (Modus Tollens) ¬q ನಿಂದ ¬p; ¬p ನಿಂದ ¬q ಪಡೆಯುವುದು ತಪ್ಪು ವಾದ. | Modus tollens goes from ¬q to ¬p; going from ¬p to ¬q is a fallacy.
- → ಅಸೋಸಿಯೇಟಿವ್ ಅಲ್ಲ; ಆವರಣಗಳನ್ನು ಎಂದೂ ಊಹಿಸಬೇಡಿ. | → is not associative; never guess the brackets.
On this page
ಮುಖ್ಯ ಸಮಾನತೆಯ ನಿಯಮಗಳು (Equivalence Laws) | Key equivalence laws
| ನಿಯಮ | Law | ರೂಪ | Form |
|---|---|
| ಡಿ ಮಾರ್ಗನ್ (De Morgan) | De Morgan | ¬(p ∧ q) ≡ ¬p ∨ ¬q; ¬(p ∨ q) ≡ ¬p ∧ ¬q | ¬(p ∧ q) ≡ ¬p ∨ ¬q; ¬(p ∨ q) ≡ ¬p ∧ ¬q |
| ಅಬ್ಸಾರ್ಪ್ಷನ್ (Absorption) | Absorption | p ∨ (p ∧ q) ≡ p; p ∧ (p ∨ q) ≡ p | p ∨ (p ∧ q) ≡ p; p ∧ (p ∨ q) ≡ p |
| ಡಿಸ್ಟ್ರಿಬ್ಯೂಟಿವ್ (Distributive) | Distributive | p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) | p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) |
| ಕಂಡಿಷನಲ್ ನಿರ್ಮೂಲನೆ | Conditional elimination | p → q ≡ ¬p ∨ q | p → q ≡ ¬p ∨ q |
| ಎಕ್ಸ್‌ಪೋರ್ಟೇಶನ್ (Exportation) | Exportation | (p ∧ q) → r ≡ p → (q → r) | (p ∧ q) → r ≡ p → (q → r) |
| ಬೈಕಂಡಿಷನಲ್ ನಿರ್ಮೂಲನೆ | Biconditional elimination | p ↔ q ≡ (p → q) ∧ (q → p) | p ↔ q ≡ (p → q) ∧ (q → p) |
| ಡಿಸ್‌ಜಂಕ್ಷನ್ ಆಗಿ ∨ | Disjunction as a conditional | p ∨ q ≡ ¬p → q | p ∨ q ≡ ¬p → q |
→ ಅಸೋಸಿಯೇಟಿವ್ (Associative) ಅಲ್ಲ: (p → q) → r ಮತ್ತು p → (q → r) ಬೇರೆ. p = F, r = F ತೆಗೆದುಕೊಂಡರೆ ಮೊದಲನೆಯದು F, ಎರಡನೆಯದು T. | → is not associative: (p → q) → r and p → (q → r) differ. Take p = F, r = F: the first is F, the second is T.
ಡ್ಯುಯಲ್ (Dual) | The dual
ಡ್ಯುಯಲ್ (Dual) ಪಡೆಯಲು ∧ ಮತ್ತು ∨ ಅದಲುಬದಲು ಮಾಡಿ, T ಮತ್ತು F ಅದಲುಬದಲು ಮಾಡಿ. ¬ ಬದಲಾಗುವುದಿಲ್ಲ. ಎರಡು ಸೂತ್ರಗಳು ಸಮಾನವಾದರೆ ಅವುಗಳ ಡ್ಯುಯಲ್‌ಗಳೂ ಸಮಾನ. | To form the dual, swap ∧ with ∨ and T with F. ¬ is left alone. If two formulas are equivalent, so are their duals.
ನಾರ್ಮಲ್ ಫಾರ್ಮ್‌ಗಳು (Normal Forms) | Normal forms
- ಡಿಎನ್‌ಎಫ್ (DNF): ಲಿಟರಲ್‌ಗಳ ∧ ಗಳ ∨, ಅಂದರೆ ಸಮ್ ಆಫ್ ಪ್ರಾಡಕ್ಟ್ಸ್ (Sum of Products). | DNF: an OR of ANDs of literals, a sum of products.
- ಸಿಎನ್‌ಎಫ್ (CNF): ಲಿಟರಲ್‌ಗಳ ∨ ಗಳ ∧, ಅಂದರೆ ಪ್ರಾಡಕ್ಟ್ ಆಫ್ ಸಮ್ಸ್ (Product of Sums). | CNF: an AND of ORs of literals, a product of sums.
- ಪಿಡಿಎನ್‌ಎಫ್ (PDNF): ಪ್ರತಿ ಪದದಲ್ಲಿ ಎಲ್ಲಾ ವೇರಿಯೇಬಲ್‌ಗಳಿರುವ ಡಿಎನ್‌ಎಫ್; ಪ್ರತಿ ಪದ ಒಂದು ಮಿಂಟರ್ಮ್ (Minterm), ಅಂದರೆ ಸೂತ್ರ T ಆಗುವ ಒಂದು ಸಾಲು. | PDNF: a DNF in which every term has every variable; each term is a minterm, one row where the formula is T.
- ಪಿಸಿಎನ್‌ಎಫ್ (PCNF): ಪ್ರತಿ ಕ್ಲಾಸ್‌ನಲ್ಲಿ ಎಲ್ಲಾ ವೇರಿಯೇಬಲ್‌ಗಳಿರುವ ಸಿಎನ್‌ಎಫ್; ಪ್ರತಿ ಕ್ಲಾಸ್ ಒಂದು ಮ್ಯಾಕ್ಸ್‌ಟರ್ಮ್ (Maxterm), ಅಂದರೆ ಸೂತ್ರ F ಆಗುವ ಒಂದು ಸಾಲು. | PCNF: a CNF in which every clause has every variable; each clause is a maxterm, one row where the formula is F.
n ವೇರಿಯೇಬಲ್‌ಗಳಿಗೆ: ಮಿಂಟರ್ಮ್‌ಗಳ ಸಂಖ್ಯೆ + ಮ್ಯಾಕ್ಸ್‌ಟರ್ಮ್‌ಗಳ ಸಂಖ್ಯೆ = 2 ರ ಘಾತ n. | For n variables: number of minterms plus number of maxterms = 2 to the power n.
ಟಾಟಾಲಜಿ (Tautology) ಯ ಪಿಡಿಎನ್‌ಎಫ್ ನಲ್ಲಿ ಎಲ್ಲಾ 2 ರ ಘಾತ n ಮಿಂಟರ್ಮ್‌ಗಳು; ಅದರ ಪಿಸಿಎನ್‌ಎಫ್ ಖಾಲಿ. | A tautology has all 2 to the power n minterms in its PDNF, and an empty PCNF.
[(p ∨ q) ∧ ¬p] → ¬q: ಮೊದಲು (p ∨ q) ∧ ¬p ≡ ¬p ∧ q. ನಂತರ ¬(¬p ∧ q) ∨ ¬q ≡ p ∨ ¬q ∨ ¬q ≡ p ∨ ¬q. ಇದರಲ್ಲಿ p ಮತ್ತು q ಎರಡೂ ಇವೆ, ಆದ್ದರಿಂದ ಇದೇ ಪಿಸಿಎನ್‌ಎಫ್ (PCNF). | [(p ∨ q) ∧ ¬p] → ¬q: first (p ∨ q) ∧ ¬p ≡ ¬p ∧ q. Then ¬(¬p ∧ q) ∨ ¬q ≡ p ∨ ¬q ∨ ¬q ≡ p ∨ ¬q. Both p and q appear, so this single clause is the PCNF.
ಫಂಕ್ಷನಲ್ ಕಂಪ್ಲೀಟ್‌ನೆಸ್ (Functional Completeness) | Functional completeness
ಯಾವುದೇ ಟ್ರೂತ್ ಫಂಕ್ಷನ್ ಅನ್ನು ವ್ಯಕ್ತಪಡಿಸಬಲ್ಲ ಕನೆಕ್ಟಿವ್ ಸಮೂಹವನ್ನು ಫಂಕ್ಷನಲಿ ಕಂಪ್ಲೀಟ್ (Functionally Complete) ಎನ್ನುತ್ತಾರೆ. | A set of connectives is functionally complete if it can express every truth function.
- ಕಂಪ್ಲೀಟ್: {¬, ∧}, {¬, ∨}, {¬, →}, {NAND}, {NOR} | Complete: {¬, ∧}, {¬, ∨}, {¬, →}, {NAND}, {NOR}
- ಕಂಪ್ಲೀಟ್ ಅಲ್ಲ: {∧, ∨} (ನೆಗೇಶನ್ ಸಾಧ್ಯವಿಲ್ಲ), {∧, ∨, →, ↔} (ಎಲ್ಲಾ ಇನ್‌ಪುಟ್ T ಆದರೆ ಔಟ್‌ಪುಟ್ ಯಾವಾಗಲೂ T), {¬, ↔} | Not complete: {∧, ∨} (cannot negate), {∧, ∨, →, ↔} (all-T input always gives T), {¬, ↔}
- NAND ನಿಂದ ನೆಗೇಶನ್: ¬p ≡ p NAND p. NOR ನಿಂದ: ¬p ≡ p NOR p. | Negation from NAND: ¬p ≡ p NAND p. From NOR: ¬p ≡ p NOR p.
ರೂಲ್ಸ್ ಆಫ್ ಇನ್‌ಫರೆನ್ಸ್ (Rules of Inference) | Rules of inference
| ನಿಯಮ | Rule | ಪ್ರಿಮಿಸ್‌ಗಳು (Premises) | Premises | ತೀರ್ಮಾನ | Conclusion |
|---|---|---|
| ಮೋಡಸ್ ಪೋನೆನ್ಸ್ (Modus Ponens) | Modus Ponens | p, p → q | p, p → q | q | q |
| ಮೋಡಸ್ ಟೋಲೆನ್ಸ್ (Modus Tollens) | Modus Tollens | ¬q, p → q | ¬q, p → q | ¬p | ¬p |
| ಹೈಪೋಥೆಟಿಕಲ್ ಸಿಲಾಜಿಸಂ (Hypothetical Syllogism) | Hypothetical Syllogism | p → q, q → r | p → q, q → r | p → r | p → r |
| ಡಿಸ್‌ಜಂಕ್ಟಿವ್ ಸಿಲಾಜಿಸಂ (Disjunctive Syllogism) | Disjunctive Syllogism | p ∨ q, ¬p | p ∨ q, ¬p | q | q |
| ರೆಸಲ್ಯೂಶನ್ (Resolution) | Resolution | p ∨ q, ¬p ∨ r | p ∨ q, ¬p ∨ r | q ∨ r | q ∨ r |
| ಅಡಿಶನ್ (Addition) | Addition | p | p | p ∨ q | p ∨ q |
| ಸಿಂಪ್ಲಿಫಿಕೇಶನ್ (Simplification) | Simplification | p ∧ q | p ∧ q | p | p |
ವಾದ (Argument) ಮಾನ್ಯ (Valid) ಆಗುವುದು (ಪ್ರಿಮಿಸ್‌ಗಳ ∧) → ತೀರ್ಮಾನ ಎಂಬುದು ಟಾಟಾಲಜಿ (Tautology) ಆದಾಗ ಮಾತ್ರ. | An argument is valid exactly when (conjunction of premises) → conclusion is a tautology.
ಎರಡು ತಪ್ಪು ವಾದಗಳು (Fallacies): ಅಫರ್ಮಿಂಗ್ ದಿ ಕಾನ್ಸಿಕ್ವೆಂಟ್ (Affirming the Consequent): p → q, q ಆದ್ದರಿಂದ p. ಡಿನೈಯಿಂಗ್ ದಿ ಆಂಟಿಸಿಡೆಂಟ್ (Denying the Antecedent): p → q, ¬p ಆದ್ದರಿಂದ ¬q. | Two fallacies: affirming the consequent (p → q, q, therefore p) and denying the antecedent (p → q, ¬p, therefore ¬q).
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