Бид өдөр тутмын амьдралдаа тасралтгүй логикийн дүгнэлт хийдэг. Жишээлбэл, "Бороо орвол газар норно" гэсэн хууль болон "Одоо бороо орж байна" гэсэн мэдээлэл өгөгдөхөд бид аяндаа "Удахгүй газар норно" гэж дүгнэдэг. Ийм дүгнэлт нь логикийн сэтгэлгээний үндсэн хэлбэр юм.
Өөр жишээ дурдвал, "Бүх хүн хэзээ нэгэн цагт үхдэг" гэсэн хууль болон "Сократ бол хүн" гэсэн урьдач нөхцлөөс "Сократ хэзээ нэгэн цагт үхнэ" гэсэн дүгнэлт гаргах үйл явцыг дурдаж болно. Энэ нь сонгодог гурван шатлалт аргументын жишээ бөгөөд бидний өдөр тутмын сэтгэлгээний үйл явцад байнга ашиглагддаг логикийн бүтэц юм.
Ингээд бид өдөр тутмын амьдралдаа мэдэхгүйдээ логикийн дүгнэлт хийж амьдардаг. Математикт ийм логикийн сэтгэлгээ илүү чухал байр суурь эзэлдэг. Математикт ямар нэгэн үзэл бодлын үнэн болохыг нотлохын тулд тэр нотлолын явц логиктой байх ёстой. Өөрөөр хэлбэл шат бүр өмнөх шатнаас үндэслэлтэй гарах ёстой, ерөнхий урсгал нь тогтвортой бүтэцтэй байх ёстой.
Тэгвэл математикт хэлж буй 'логик' гэдэг яг юуг хэлэх вэ? Өдөр тутамд хэрэглэдэг логиктой ямар ялгаа байдаг вэ? Эдгээр асуултад хариулахын тулд математикийн логикийн ертөнц рүү илүү гүнзгий ороцгооё.
Мэдэгдлийн логик: Логик судлалын үндэс
Мэдэгдлийн логик (propositional logic) нь логик судлалын хамгийн үндсэн хэлбэр бөгөөд мэдэгдлүүдийн хоорондын харьцаа болон мэдэгдлийн үнэн худлын утгыг авч үздэг логикийн систем юм. Илүү нарийвчлан тодорхойлбол мэдэгдлийн логик нь дараах элементүүдээс бүрддэг.
- Атом мэдэгдэл (atomic propositions): Цаашид задалж болохгүй хамгийн үндсэн мэдэгдэл.
- Логикийн холбогч (logical connectives): 'үгүй', 'ба', 'эсвэл', 'хэрэв...бол', 'хэрэв, зөвхөн хэрэв' гэх мэт.
- Хаалт: Мэдэгдлийн бүтцийг тодорхой болгох тэмдэг.
- Дүгнэлтийн дүрэм (inference rules): Өгөгдсөн мэдэгдлээс шинэ мэдэгдэл гаргах дүрэм.
Мэдэгдлийн логикт эдгээр элементийг ашиглан нийлмэл мэдэгдэл бүтээж, мэдэгдлийн үнэн худлын утгыг тогтоож, логикийн дүгнэлт хийдэг.
Мэдэгдлийн логик ашигласан нотлолын энгийн жишээг харцгаая. Дараах урьдач нөхцлүүд өгөгдсөн гэж үзье:
- "Хэрэв бороо орвол удахгүй газар норно." (P → Q)
- "Бороо орж байна." (P)
Эндээс бид "Удахгүй газар норно" (Q) гэсэн дүгнэлт гаргаж чадна. Энэ нь 'Modus Ponens' (товчоор 'M.P.') гэж нэрлэгддэг дүгнэлтийн дүрмийг ашигласан явдал юм.
Энэ үйл явцад бид гурван шатлалт аргумент (syllogism) ашигласан. Гурван шатлалт аргумент гэдэг нь хоёр урьдач нөхцлөөс нэг дүгнэлт гаргах логикийн дүгнэлтийн дүрэм юм. (Гэвч хожим тайлбарлахаар бүх гурван шатлалт аргумент төгс логиктой биш байдаг.)
Мэдэгдлийн логикийн чухал шинж чанар нь бүрэн байдал (completeness), эрүүл мэнд (soundness), компакт байдал (compactness) юм.
- Бүрэн байдал: Мэдэгдлийн логикт утгын талаас үнэн бүх мэдэгдлийг синтаксийн талаас нотолж чаддаг.
- Эрүүл мэнд: Мэдэгдлийн логикт синтаксийн талаас нотолж чадах бүх мэдэгдэл утгын талаас үнэн байдаг.
- Компакт байдал: Мэдэгдлийн логикийн хэлэнд сайн тодорхойлогдсон өгүүлбэрийг элемент болгон агуулсан ямар нэгэн хязгааргүй олонлогийн дурын хязгаарлагдмал дэд олонлог загвартай бол тэр хязгааргүй олонлог ч загвартай байдаг.
Мэдэгдлийн логикийн бүрэн байдал, эрүүл мэндийн ачаар бид мэдэгдэл нотлохдоо дүгнэлтийн дүрэм ашиглах ч, үнэн худлын хүснэгт ашиглах ч адилхан үр дүн авдаг. Энэ нь мэдэгдлийн логикт олон төрлийн нотлолын арга нь хоорондоо тогтвортой байдгийг баталгаажуулдаг.
Гэвч мэдэгдлийн логикт хязгаарлалт байдаг. Жишээлбэл, өмнө дурдсан "Бүх хүн хэзээ нэгэн цагт үхдэг" болон "Сократ бол хүн" гэсэн урьдач нөхцлөөс "Сократ хэзээ нэгэн цагт үхнэ" гэсэн дүгнэлт гаргах дүгнэлт нь үнэндээ бүрэн гурван шатлалт аргумент биш юм.
Энэ нь мэдэгдлийн логикт 'бүх' гэсэн хязгаарлагч (quantifier)-ийг илэрхийлж чадахгүйтэй холбоотой. Мэдэгдлийн логик нь тусгай объектын шинж чанар эсвэл харьцааг илэрхийлэхэд хязгаарлалттай бөгөөд 'бүх', 'зарим' зэрэг хязгаарлагчийг агуулсан илүү төвөгтэй логикийн бүтцийг хэлэлцэхэд хэцүү байдаг.
Нэгдүгээр эрэмбийн логик: Илүү хүчирхэг логикийн систем
Нэгдүгээр эрэмбийн логик (first-order logic) нь мэдэгдлийн логикийг өргөжүүлсэн илүү хүчирхэг логикийн систем юм. ('Нэгдүгээр эрэмбийн логик'-ийг 'нэгдүгээр зэргийн логик' гэж нэрлэх ч байдаг.) Энгийнээр хэлбэл нэгдүгээр эрэмбийн логик нь объект (individuals), шинж чанар (properties), харьцаа (relations), мөн хязгаарлагч (quantifiers)-ийг хэлэлцэж чаддаг логикийн систем юм. Илүү нарийвчлан тодорхойлбол нэгдүгээр эрэмбийн логик нь дараах элементүүдээс бүрддэг:
- Мэдэгдлийн логикийн бүх элемент (атом мэдэгдэл, логикийн холбогч, хаалт, дүгнэлтийн дүрэм).
- Хувьсагч (variables): Объектыг илэрхийлэх тэмдэг.
- Тогтмол (constants): Тодорхой объектыг илэрхийлэх тэмдэг.
- Функц (functions): Объектуудын хоорондын харгалзуулалтыг илэрхийлэх тэмдэг.
- Предикат (predicates): Объектуудын шинж чанар эсвэл харьцааг илэрхийлэх тэмдэг.
- Хязгаарлагч (quantifiers): 'Бүх'-ийг илэрхийлэх ерөнхий хязгаарлагч (∀) болон 'зарим'-ыг илэрхийлэх оршихуйн хязгаарлагч (∃).
Нэгдүгээр эрэмбийн логик болон мэдэгдлийн логикийн гол ялгаа нь нэгдүгээр эрэмбийн логик объектуудын дотоод бүтэц болон тэдгээрийн хоорондын харьцааг илэрхийлж чаддаг явдал юм. Үүгээр дамжуулан бид "Бүх x-ийн хувьд P(x) үнэн" эсвэл "Зарим x байж P(x) үнэн" гэх мэт илүү төвөгтэй логикийн бүтцийг хэлэлцэж чаддаг.
Нэгдүгээр эрэмбийн логик ашигласан нотлолын жишээг харцгаая. Дараах урьдач нөхцлүүд өгөгдсөн гэж үзье:
- Бүх хүн хэзээ нэгэн цагт үхдэг. (∀x(H(x) → D(x)))
- Сократ бол хүн. (H(Сократ))
Эндээс бид "Сократ хэзээ нэгэн цагт үхнэ" (D(Сократ)) гэсэн дүгнэлт гаргаж чадна. Энэ нь ерөнхий тусгайлалт (Universal Instantiation) болон Modus Ponens гэсэн дүгнэлтийн дүрмийг ашигласан явдал юм.
Нэгдүгээр эрэмбийн логик ч мэдэгдлийн логиктой адилаар бүрэн байдал, эрүүл мэнд, компакт байдалтай байдаг. Нэгдүгээр эрэмбийн логикийн ийм шинж чанар нэгдүгээр эрэмбийн логикийн хүчирхэг байдлыг харуулахын зэрэгцээ түүний хязгаарлалтыг ч тогтоодог.
Нэгдүгээр эрэмбийн логикийн компакт байдал онцгой ач холбогдолтой. Үүгээр дамжуулан бид хязгаарлагдмал дөрвөн өнгийн теорем (Finite Four Color Theorem)-ийг хязгааргүй дөрвөн өнгийн теорем (Infinite Four Color Theorem) болгон өргөжүүлж чаддаг. Өөрөөр хэлбэл, дурын хязгаарлагдмал хавтгай графыг дөрвөн өнгөөр хилийг ялгахаар будаж чаддаг гэдгээс дурын хязгааргүй хавтгай графыг ч дөрвөн өнгөөр хилийг ялгахаар будаж чаддаг гэсэн дүгнэлт гаргаж чаддаг.
Гэвч нэгдүгээр эрэмбийн логикт ч хязгаарлалт байдаг. Жишээлбэл, байгалийн тоог тодорхойлдог Пеаногийн аксиомын системийг харцгаая. Пеаногийн аксиомын систем нь дараах аксиомуудаас бүрддэг:
- 0 нь байгалийн тоо.1Солонгосын боловсролын хөтөлбөрт 1-ээс дээш бүхэл тоог байгалийн тоо гэж нэрлэдэг. Гэвч олонлогийн онолд сөрөг биш бүхэл тоог байгалийн тоо гэж нэрлэдэг.
- Бүх байгалийн тоо n-ийн хувьд n-ийн дараачийн (successor) S(n) ч байгалийн тоо. (n-ийн дараачийн нь зөн совинд n+1-ийг заана.)
- 0 нь ямар ч байгалийн тооны дараачийн биш.
- Өөр өөр байгалийн тоо өөр өөр дараачийнтай байдаг.
- (Индукцийн зарчим) Ямар нэгэн шинж чанар P-ийн хувьд P(0) үнэн бөгөөд 'бүх байгалийн тоо n-ийн хувьд P(n) үнэн бол P(S(n)) ч үнэн' үед бүх байгалийн тоо шинж чанар P-ийг хангана.
Энд сүүлийн аксиом болох индукцийн зарчмыг нэгдүгээр эрэмбийн логикоор илэрхийлж болохгүй. Энэ нь индукцийн зарчим байгалийн тооны бүх дэд олонлогийн хувьд тэгш байдаг шинж чанарыг тодорхойлдог учраас. Ийм 'бүх дэд олонлог'-ын хувьд квантификаци хийх нь нэгдүгээр эрэмбийн логикийн хүрээнээс давдаг.
Олонлогийн онолын аксиомын систем
Олонлогийн онолын аксиомын систем нь нэгдүгээр эрэмбийн логикийг өргөжүүлж олонлог болон байгалийн тоог хэлэлцэх боломжтой болгосон аксиомын систем юм. Орчин үеийн математикийн ихэнх салбар олонлогийн онолыг үндэслэдэг бөгөөд энэ нь математикийн үндсийг бүрдүүлдэг.
Хамгийн өргөн хэрэглэгддэг олонлогийн онолын аксиомын систем нь Zermelo-Fraenkel (ZF) аксиомын систем болон үүнд сонголтын аксиом (Axiom of Choice)-ийг нэмсэн ZFC аксиомын систем юм. ZF аксиомын систем нь дараах аксиомуудаас бүрддэг:
- Гадаад байдлын аксиом: Адилхан элементтэй хоёр олонлог ижил байдаг.
- Хоосон олонлогийн аксиом: Элемент байхгүй олонлог байдаг.
- Хосын аксиом: Дурын хоёр олонлог a, b-ийн хувьд {a, b} гэсэн олонлог байдаг.
- Нэгдлийн аксиом: Дурын олонлог A-ийн хувьд A-ийн бүх элементийн элементээс бүрдсэн олонлог байдаг.
- Хүчний олонлогийн аксиом: Дурын олонлог A-ийн хувьд A-ийн бүх дэд олонлогоос бүрдсэн олонлог байдаг.
- Хязгааргүй байдлын аксиом: Хязгааргүй олонлог байдаг.
- Орлуулалтын аксиом: Функцээр тодорхойлогдсон олонлог байдаг.
- Тогтмол байдлын аксиом: Хоосон биш дурын олонлог A-ийн хувьд A болон A-ийн элементийн аль нэгтэй ч нийтлэг элемент үгүй элемент A-д байдаг.
- Ялгалтын аксиомын схем2Энд 'аксиомын схем' гэдэг нь үнэндээ нэг аксиом биш, хязгааргүй олон аксиом юм. Өөрөөр хэлбэл 'ялгалтын аксиомын схем' гэдэг нь шинж чанар P өгөгдөх болгонд P-д харгалзах аксиом өгөгддөг явдал юм. 'Аксиомын схем'-ийг 'аксиомын хэв' гэж нэрлэх ч байдаг.: Дурын шинж чанар P-ийн хувьд өгөгдсөн олонлогийн элементийн дотроос P-ийг хангадаг элементүүдийн олонлог байдаг.
Эдгээр аксиом нь олонлогийн үндсэн шинж чанар болон үйлдлийг тодорхойлдог.
Сонголтын аксиом (Axiom of Choice) нь ZF аксиомын системд нэмэгдэж ZFC аксиомын системийг бүрдүүлдэг чухал аксиом юм. Энэ аксиом нь дараах байдалтай:
"Хоосон биш олонлогуудын олонлог A-ийн хувьд A-ийн элемент бүрээс нэгээс нэг элемент сонгож бүтээсэн олонлог байдаг."
Энэ аксиомыг эхэнд бусад аксиомуудаас нотолж болно гэж үздэг байсан. Гэвч 1938 онд Kurt Gödel-ээр сонголтын аксиом ZF-ийн бусад аксиомуудтай зөрчилдөхгүй болох нь нотлогдсон бөгөөд 1963 онд Paul Cohen-ээр сонголтын аксиомын үгүйсгэл ч ZF-тэй зөрчилдөхгүй болох нь нотлогдсон.
Энэ нь сонголтын аксиом ZF аксиомын системийн бусад аксиомуудаас хараат бус гэсэн үг юм. Өөрөөр хэлбэл, сонголтын аксиомыг хүлээн зөвшөөрч ч, няцаач ч хоёулаа математикийн хувьд боломжтой. Үүний улмаас ZF аксиомын системд сонголтын аксиом нэмсэн ZFC аксиомын систем орчин үеийн математикийн стандарт үндэс болон ашиглагдах болсон.
Сонголтын аксиом математикийн олон салбарт чухал үүрэг гүйцэтгэдэг. Жишээлбэл, сонголтын аксиом дараах теоремуудын нотлолт ашиглагддаг.
- Оршихуйтай холбоотой теоремууд. (Жишээ: Бүх вектор орон зай суурьтай байдаг.)
- Тихонофын теорем. (Дурын компакт топологийн орон зайн үржвэр орон зай ч компакт орон зай байдаг.)
- Hahn-Banach теорем. (Функцийн анализын гол теоремийн нэг.)
Гэвч сонголтын аксиом хэд хэдэн зөн совинд харшлах үр дүнг ч гаргадаг. Хамгийн алдартай жишээ нь Banach-Tarski парадокс бөгөөд 3 хэмжээст орон зайд нэг бөмбөрцгийг хязгаарлагдмал хэсэгт хувааж дахин эмхлэн анхны бөмбөрцөгтэй адилхан хэмжээтэй хоёр бөмбөрцөг бүтээж чаддаг гэсэн явдал юм.
Ийм шинж чанарын улмаас сонголтын аксиомыг хүлээн зөвшөөрөх эсэх нь заримдаа математичдын дунд маргааны сэдэв болдог байсан. Гэсэн хэдий ч өнөөдөр сонголтын аксиом математикийн олон хэсэгт зайлшгүй үүрэг гүйцэтгэж байна.
ZFC аксиомын систем нь байгалийн тоог хэлэлцэх хангалттай хүчирхэг аксиомын систем юм. Энэ нь ZFC бүрэн бус байдалтай гэсэн үг юм. Kurt Gödel-ийн бүрэн бус байдлын теорем байгалийн тоог хэлэлцэх хангалттай хүчирхэг бүх аксиомын систем дараах шинж чанартай болохыг хэлдэг:
- (1-р бүрэн бус байдлын теорем) Хэрэв аксиомын систем (загвар) зөрчилгүй бол тэр аксиомын систем дотор үнэн боловч нотолж болохгүй мэдэгдэл байдаг.
- (2-р бүрэн бус байдлын теорем) Хангалттай хүчирхэг зөрчилгүй аксиомын систем өөрийн зөрчилгүй байдлыг тэр систем дотор нотолж чадахгүй.
ZFC-г үндэслэсэн олонлогийн онол байгалийн тоог бүтээж чаддаг тул бүрэн бус байдалтай. Өөрөөр хэлбэл, ZFC дотор үнэн боловч ZFC-ийн аксиомуудаас нотолж болохгүй мэдэгдлүүд байдаг бөгөөд ZFC зөрчилгүй гэдэг баримт (хэрэв тийм бол)-ыг ZFC дотор нотолж болохгүй.
Бүрэн бус байдлын теоремийн нэг жишээ болгон өнгөрсөн нийтлэлд дурдсан тасралтгүй байдлын таамаглалыг дурдаж болно. Тасралтгүй байдлын таамаглал гэдэг нь хязгааргүй олонлог S байхад S-ээс олон элементтэй боловч түүний хүчний олонлог P(S)-ээс цөөн элементтэй олонлог байхгүй гэсэн таамаглал юм. Gödel болон Cohen-ээр тасралтгүй байдлын таамаглал ZFC аксиомын системээс хараат бус болох нь тогтоогдсон.
Математикийн логик судлал болон загварын онол
Математикийн логик нь орчин үеийн математикийн үндэс болдог суурь юм. Гэвч математикийн логикийг багаж болгон ашиглахад зогсохгүй логик өөрөө судлах шинжлэх ухаан ч байдаг. Тэр нь математикийн логик судлал болон загварын онол юм.
Математикийн логик судлал нь логик судлалыг математикийн аргаар судалдаг салбар юм. Үүнд нотлолын онол, рекурсийн онол, загварын онол, олонлогийн онол зэрэг багтдаг. Энэ салбар математикийн дүгнэлтийн мөн чанарыг ойлгож, математикийн бүтцийн үндсэн шинж чанарыг судлахад чухал үүрэг гүйцэтгэдэг.
Загварын онол нь математикийн логик судлалын нэг салбар бөгөөд математикийн бүтэц болон формаль хэлний хоорондын харьцааг судалдаг. Загварын онол өгөгдсөн аксиомын системийн загвар (тэр аксиомын системийг хангадаг математикийн бүтэц)-ийг судалж, үүгээр дамжуулан аксиомын системийн шинж чанарыг ойлгохыг зорьдог.
Эдгээр салбарууд зөвхөн математикийн үндсийг бүрдүүлэхэд зогсохгүй өөрөө баялаг судалгааны сэдэв болгодог. Жишээлбэл дараах зүйлс байдаг.
- Нотлолын онол математикийн нотлолын бүтэц, шинж чанарыг судалж, энэ нь компьютерийн шинжлэх ухааны формаль баталгаажуулалт (formal verification) салбартай нягт холбоотой.
- Рекурсийн онол тооцоологдох чадвар болон алгоритмын хязгаарлалтыг судалж, энэ нь компьютерийн шинжлэх ухааны тооцооллын нарийн төвөгтэй байдлын онолын үндэс болдог.
- Загварын онол нь алгебр, геометр, тооны онол зэрэг математикийн олон салбарт шинэ үр дүн гаргахад ашиглагддаг.
Ингээд математикийн логик нь математикийн олон салбарыг дэмждэг шинжлэх ухаан төдийгүй өөрөө ч гүн гүнзгий судалгааны объект болдог салбар юм.
Аяллыг дуусгахад
Одоо хүртэл бид мэдэгдлийн логикоос эхлэн нэгдүгээр эрэмбийн логик, мөн олонлогийн онолын аксиомын систем хүртэл математикийн логикийн хөгжлийн явцыг дагаж үзлээ. Бидний харсанчлэн математикийн логик нь зөвхөн өдөр тутмын дүгнэлтийг формальчилсан зүйлээс илүү юм. Математикийн логик нь математикийн үндсийг бүрдүүлж, математикийн үнэний мөн чанарт гүн ойлголт өгдөг. Зэрэгцээ математикийн логик судлал нь өөрөө баялаг бүтэцтэй судалгааны объект ч байдаг.
Цаашилбал, математикийн логик нь хиймэл оюун ухаан, машин сургалт зэрэг орчин үеийн технологийн үндэс болдог. Компьютер программын хэлний үндэс, алгоритмын загвар болон шинжилгээ, өгөгдлийн сангийн системийн асуулгын хэл зэрэг бүгд математикийн логикт суурилдаг. Тиймээс математикийн логикийг ойлгох нь орчин үеийн технологийн нийгмийг ойлгож түүний хөгжилд хувь нэмэр оруулахад чухал үүрэг гүйцэтгэдэг.
Математикийн логикийг судлах аялал хэзээ ч амар биш боловч тэр аяллаас олж авах ойлголт, оюуны өсөлт нь бүх хүчин чармайлтыг хангалттай нөхөх хэмжээнд сэтгэл хөдөлгөм байдаг. Математикт гүн сонирхолтой бол, эсвэл логик судлалд гүн сонирхолтой бол математикийн логик судлалын ертөнцөд амтлаж үзэх нь яаж байх вэ?
(Гэхдээ математикийн логик судлал сурахын тулд бакалаврын хөтөлбөрийн математикаас баттай суралцах хэрэгтэй.)
🍭