{"id":9270,"date":"2025-10-17T20:18:38","date_gmt":"2025-10-17T11:18:38","guid":{"rendered":"https:\/\/sasamath.com\/blog\/?page_id=9270"},"modified":"2026-09-27T12:20:44","modified_gmt":"2026-09-27T03:20:44","slug":"ch12-propositional-logic","status":"publish","type":"page","link":"https:\/\/sasamath.com\/blog\/invitation-to-mathematical-logic\/ch12-propositional-logic\/","title":{"rendered":"\uba85\uc81c\ub17c\ub9ac\uc758 \uac1c\ub150"},"content":{"rendered":"<div class=\"mathlogic2025\"><!-- ################## --><\/p>\n<p><!-- \n\n<h2>12. \uba85\uc81c\ub17c\ub9ac\uc758 \uac1c\ub150<\/h2>\n\n --><\/p>\n<p><span class=\"defined\">\uba85\uc81c\ub17c\ub9ac<\/span>(propositional logic)\ub294 \uba85\uc81c\ubcc0\uc218\uc640 \ub17c\ub9ac\uacb0\ud569\uc790, \uadf8\ub9ac\uace0 \uacf5\ub9ac\uc640 \ucd94\ub860\uaddc\uce59\uc73c\ub85c \uc774\ub8e8\uc5b4\uc9c4 \ud615\uc2dd\ub17c\ub9ac\uc758 \ud55c \uccb4\uacc4\uc774\ub2e4. <a href=\"\/blog\/invitation-to-mathematical-logic\/ch01-naive-logic\/\">1\uc7a5<\/a>\uc5d0\uc11c\ub294 \uba85\uc81c\uc640 \ub17c\ub9ac\uc5f0\uc0b0\uc744 \uc9c1\uad00\uc801\uc73c\ub85c \ub2e4\ub8e8\uc5c8\ub2e4. \uc774 \uc7a5\uc5d0\uc11c\ub294 \uac19\uc740 \ub300\uc0c1\uc744 \ubb38\uc790\uc5f4\uacfc \ud615\uc2dd\uc801 \uc99d\uba85\uc758 \uad00\uc810\uc5d0\uc11c \ub2e4\uc2dc \ub2e4\ub8ec\ub2e4.<\/p>\n<h3>1. \uad6c\ubb38\ub860<\/h3>\n<p><span class=\"defined\">\uad6c\ubb38\ub860<\/span>(syntax)\uc740 \uc8fc\uc5b4\uc9c4 \uae30\ud638\ub85c \uc5b4\ub5a4 \ubb38\uc790\uc5f4\uc744 \ub17c\ub9ac\uc2dd\uc73c\ub85c \uc778\uc815\ud560 \uac83\uc778\uc9c0 \uc815\ud558\ub294 \uaddc\uce59\uc744 \ub2e4\ub8ec\ub2e4. \uad6c\ubb38\ub860\uc5d0\uc11c\ub294 \ubb38\uc790\uc5f4\uc758 \uc758\ubbf8\ub098 \uc9c4\ub9bf\uac12\uc744 \ub530\uc9c0\uc9c0 \uc54a\uace0 \uae30\ud638\uc758 \ud615\uc2dd\ub9cc\uc744 \uace0\ub824\ud55c\ub2e4.<\/p>\n<p>\uac00\uc0b0 \uac1c\uc758 <span class=\"defined\">\uba85\uc81c\ubcc0\uc218<\/span>(propositional variable)<br \/>\n\\[\\{p_0,p_1,p_2,\\ldots\\}\\]<br \/>\n\uac00 \uc8fc\uc5b4\uc84c\ub2e4\uace0 \ud558\uc790. \uc774 \uc7a5\uc758 \ud615\uc2dd\ucd94\ub860\uacc4\uc5d0\uc11c\ub294 \ubd80\uc815\uae30\ud638 \\(\\neg\\)\uc640 \ud568\uc758\uae30\ud638 \\(\\to\\)\ub97c \uae30\ubcf8 \uacb0\ud569\uc790\ub85c \uc0ac\uc6a9\ud55c\ub2e4. \uad04\ud638\ub3c4 \ub17c\ub9ac\uc2dd\uc744 \ub9cc\ub4dc\ub294 \uae30\ud638\ub85c \uc0ac\uc6a9\ud55c\ub2e4.<\/p>\n<p>\uba85\uc81c\ub17c\ub9ac\uc758 <span class=\"defined\">\ub17c\ub9ac\uc2dd<\/span>\uc740 \ub2e4\uc74c \uaddc\uce59\uc744 \uc0ac\uc6a9\ud558\uc5ec \uc7ac\uadc0\uc801\uc73c\ub85c \uc815\uc758\ud55c\ub2e4.<\/p>\n<ul>\n<li>\ubaa8\ub4e0 \uba85\uc81c\ubcc0\uc218\ub294 \ub17c\ub9ac\uc2dd\uc774\ub2e4.<\/li>\n<li>\\(\\phi\\)\uac00 \ub17c\ub9ac\uc2dd\uc774\uba74 \\((\\neg\\phi)\\)\ub3c4 \ub17c\ub9ac\uc2dd\uc774\ub2e4.<\/li>\n<li>\\(\\phi\\)\uc640 \\(\\psi\\)\uac00 \ub17c\ub9ac\uc2dd\uc774\uba74 \\((\\phi\\to\\psi)\\)\ub3c4 \ub17c\ub9ac\uc2dd\uc774\ub2e4.<\/li>\n<li>\uc704 \uaddc\uce59\uc744 \uc720\ud55c \ubc88 \uc801\uc6a9\ud558\uc5ec \uc5bb\uc740 \uac83\ub9cc \ub17c\ub9ac\uc2dd\uc774\ub2e4.<\/li>\n<\/ul>\n<p>\ub17c\ub9ac\uacf1, \ub17c\ub9ac\ud569, \uc591\ubc29\ud5a5 \ud568\uc758\ub294 \ub2e4\uc74c \uc57d\uc5b4\ub85c \uc0ac\uc6a9\ud55c\ub2e4.<br \/>\n\\[<br \/>\n\\begin{aligned}<br \/>\n(\\phi\\wedge\\psi)&#038;:=\\neg(\\phi\\to\\neg\\psi),\\\\[3pt]<br \/>\n(\\phi\\vee\\psi)&#038;:=(\\neg\\phi\\to\\psi),\\\\[3pt]<br \/>\n(\\phi\\leftrightarrow\\psi)&#038;:=((\\phi\\to\\psi)\\wedge(\\psi\\to\\phi)).<br \/>\n\\end{aligned}<br \/>\n\\]<br \/>\n\ub530\ub77c\uc11c \\(\\wedge,\\vee,\\leftrightarrow\\)\ub97c \ud3ec\ud568\ud55c \uc2dd\uc740 \uc704 \uc57d\uc5b4\ub97c \ud480\uba74 \\(\\neg,\\to\\)\ub9cc\uc744 \uc0ac\uc6a9\ud55c \ub17c\ub9ac\uc2dd\uc774 \ub41c\ub2e4. \uc774 \uc120\ud0dd\uc740 \ub4a4\uc5d0\uc11c \uc0ac\uc6a9\ud560 \uacf5\ub9ac\ud2c0 (A1)\u2013(A3)\uacfc \uc5b8\uc5b4\ub97c \uc77c\uce58\uc2dc\ud0a4\uae30 \uc704\ud55c \uac83\uc774\ub2e4.<\/p>\n<p>\uc5b4\ub5a4 \uc720\ud55c\ud55c \ubb38\uc790\uc5f4\uc774 \ub17c\ub9ac\uc2dd\uc778\uc9c0 \uc5ec\ubd80\ub294 \uc704\uc758 \uc7ac\uadc0\uc801 \ubb38\ubc95\uc744 \ub530\ub77c \uc720\ud55c\ud55c \uc808\ucc28\ub85c \ud310\ubcc4\ud560 \uc218 \uc788\ub2e4. \uc774\ub7ec\ud55c \ub17c\ub9ac\uc2dd\uc744 well-formed formula, \uc904\uc5ec\uc11c <span class=\"defined\">wff<\/span>\ub77c\uace0 \ubd80\ub974\uae30\ub3c4 \ud55c\ub2e4.<\/p>\n<div class=\"problem\">\n<p class=\"marginbottomhalf\"><span class=\"problem\">\ubb38\uc81c 12.1.<\/span><br \/>\n\uc704\uc758 \uc7ac\uadc0\uc801 \uc815\uc758\ub97c \ubb38\uc790 \uadf8\ub300\ub85c \uc801\uc6a9\ud558\uc5ec \ub2e4\uc74c \uc9c8\ubb38\uc5d0 \ub2f5\ud558\uc2dc\uc624.<\/p>\n<ol class=\"parenthesis\">\n<li>\ub2e4\uc74c \ubb38\uc790\uc5f4\uc774 \ub17c\ub9ac\uc2dd\uc778\uc9c0 \ud310\uc815\ud558\uc2dc\uc624.<br \/>\n\\[<br \/>\np_0,<br \/>\n\\quad<br \/>\n(\\neg p_0),<br \/>\n\\quad<br \/>\n(p_0\\to p_1),<br \/>\n\\quad<br \/>\n(p_0\\,p_1),<br \/>\n\\quad<br \/>\n((p_0\\to p_1)),<br \/>\n\\quad<br \/>\n(p_0\\to).<br \/>\n\\]\n<\/li>\n<li>\ub17c\ub9ac\uc2dd<br \/>\n\\[<br \/>\n\\phi=((p_0\\to(\\neg p_1))\\to(p_2\\to p_0))<br \/>\n\\]<br \/>\n\uc758 \uac00\uc7a5 \ubc14\uae65\ucabd \uacb0\ud569\uc790\uc640 \uadf8 \uacb0\ud569\uc790\uc758 \ub450 \uc9c1\uc811 \ubd80\ubd84\ub17c\ub9ac\uc2dd\uc744 \ucc3e\uc73c\uc2dc\uc624.<\/li>\n<li>\\((p_0\\wedge p_1)\\vee p_2\\)\uc5d0\uc11c \\(\\wedge,\\vee\\)\ub97c \uc815\uc758\uc5d0 \ub530\ub77c \uc5c6\uc560\uace0 \\(\\neg,\\to\\)\ub9cc\uc744 \uc0ac\uc6a9\ud558\uc5ec \ub098\ud0c0\ub0b4\uc2dc\uc624.<\/li>\n<\/ol>\n<\/div>\n<h3>2. \uc758\ubbf8\ub860<\/h3>\n<p>\uad6c\ubb38\ub860\uc774 \ub17c\ub9ac\uc2dd\uc758 \ud615\uc2dd\ub9cc\uc744 \ub2e4\ub8ec\ub2e4\uba74, <span class=\"defined\">\uc758\ubbf8\ub860<\/span>(semantics)\uc740 \uba85\uc81c\ubcc0\uc218\uc5d0 \uc9c4\ub9bf\uac12\uc744 \ubd80\uc5ec\ud588\uc744 \ub54c \ubcf5\ud569\ub17c\ub9ac\uc2dd\uc758 \uc9c4\ub9bf\uac12\uc774 \uc5b4\ub5bb\uac8c \uacb0\uc815\ub418\ub294\uc9c0\ub97c \ub2e4\ub8ec\ub2e4.<\/p>\n<p>\uba85\uc81c\ubcc0\uc218 \uac01\uac01\uc5d0 \\(\\mathrm T\\) \ub610\ub294 \\(\\mathrm F\\)\ub97c \ub300\uc751\uc2dc\ud0a4\ub294 \ud568\uc218\ub97c \uba3c\uc800 \uc815\ud558\uc790. \uc774 \ud568\uc218\ub294 \ub2e4\uc74c \uc7ac\uadc0\uaddc\uce59\uc5d0 \uc758\ud558\uc5ec \ubaa8\ub4e0 \ub17c\ub9ac\uc2dd\uc5d0 \uc720\uc77c\ud558\uac8c \ud655\uc7a5\ub41c\ub2e4. \uc774\ub807\uac8c \ud655\uc7a5\ub41c \ud568\uc218\ub97c <span class=\"defined\">\uac12\ub9e4\uae40<\/span>(valuation) \\(v\\)\ub77c\uace0 \ud55c\ub2e4.<br \/>\n\\[<br \/>\n\\begin{aligned}<br \/>\nv(\\neg\\phi)=\\mathrm T<br \/>\n&#038;\\quad\\Longleftrightarrow\\quad v(\\phi)=\\mathrm F,\\\\<br \/>\nv(\\phi\\to\\psi)=\\mathrm F<br \/>\n&#038;\\quad\\Longleftrightarrow\\quad<br \/>\nv(\\phi)=\\mathrm T\\text{\uc774\uace0 }v(\\psi)=\\mathrm F.<br \/>\n\\end{aligned}<br \/>\n\\]<br \/>\n\uc57d\uc5b4\ub85c \uc815\uc758\ud55c \ub098\uba38\uc9c0 \uacb0\ud569\uc790\uc758 \uc9c4\ub9bf\uac12\uc740 \ub2e4\uc74c \uc9c4\ub9ac\ud45c\uc640 \uac19\ub2e4.<\/p>\n<p><a href=\"\/blog\/wp-content\/uploads\/2025\/10\/mathlogic2025-table02.png\" data-rel=\"penci-gallery-image-content\" ><img fetchpriority=\"high\" decoding=\"async\" src=\"\/blog\/wp-content\/uploads\/2025\/10\/mathlogic2025-table02.png\" alt=\"\uba85\uc81c\ub17c\ub9ac\uc758 \uc9c4\ub9ac\ud45c\" width=\"566\" height=\"144\" class=\"aligncenter size-full wp-image-9451\" srcset=\"https:\/\/sasamath.com\/blog\/wp-content\/uploads\/2025\/10\/mathlogic2025-table02.png 1414w, https:\/\/sasamath.com\/blog\/wp-content\/uploads\/2025\/10\/mathlogic2025-table02-300x77.png 300w, https:\/\/sasamath.com\/blog\/wp-content\/uploads\/2025\/10\/mathlogic2025-table02-1024x261.png 1024w, https:\/\/sasamath.com\/blog\/wp-content\/uploads\/2025\/10\/mathlogic2025-table02-768x196.png 768w, https:\/\/sasamath.com\/blog\/wp-content\/uploads\/2025\/10\/mathlogic2025-table02-1170x299.png 1170w, https:\/\/sasamath.com\/blog\/wp-content\/uploads\/2025\/10\/mathlogic2025-table02-585x149.png 585w\" sizes=\"(max-width: 566px) 100vw, 566px\" \/><\/a><!-- width=\"1414\" height=\"361\" --><\/p>\n<p>\ubaa8\ub4e0 \uac12\ub9e4\uae40 \\(v\\)\uc5d0 \ub300\ud558\uc5ec \\(v(\\phi)=\\mathrm T\\)\uc774\uba74 \\(\\phi\\)\ub97c <span class=\"defined\">\ud56d\uc9c4<\/span>(tautology)\uc774\ub77c\uace0 \ubd80\ub978\ub2e4. \ubaa8\ub4e0 \uac12\ub9e4\uae40\uc5d0 \ub300\ud558\uc5ec \\(v(\\phi)=\\mathrm F\\)\uc774\uba74 \\(\\phi\\)\ub97c <span class=\"defined\">\ubaa8\uc21c<\/span>(contradiction)\uc774\ub77c\uace0 \ubd80\ub978\ub2e4.<\/p>\n<p>\ub17c\ub9ac\uc2dd\uc758 \uc9d1\ud569 \\(\\varSigma\\)\uc5d0 \ub300\ud558\uc5ec, \uc5b4\ub5a4 \uac12\ub9e4\uae40 \\(v\\)\uac00 \ubaa8\ub4e0 \\(\\sigma\\in\\varSigma\\)\uc5d0 \ub300\ud558\uc5ec \\(v(\\sigma)=\\mathrm T\\)\ub97c \ub9cc\uc871\uc2dc\ud0a4\uba74 \\(v\\)\ub97c \\(\\varSigma\\)\uc758 <span class=\"defined\">\ubaa8\ud615<\/span>(model)\uc774\ub77c\uace0 \ubd80\ub978\ub2e4. \uc774\ub7ec\ud55c \uac12\ub9e4\uae40\uc774 \ud558\ub098\ub77c\ub3c4 \uc874\uc7ac\ud558\uba74 \u201c\\(\\varSigma\\)\uac00 <span class=\"defined\">\ub9cc\uc871 \uac00\ub2a5<\/span>(satisfiable)\ud558\ub2e4\u201d\ub77c\uace0 \ud45c\ud604\ud55c\ub2e4. \ud55c \ub17c\ub9ac\uc2dd \\(\\phi\\)\uac00 \ub9cc\uc871 \uac00\ub2a5\ud558\ub2e4\ub294 \uac83\uc740 \\(\\{\\phi\\}\\)\uac00 \ub9cc\uc871 \uac00\ub2a5\ud558\ub2e4\ub294 \ub73b\uc774\ub2e4.<\/p>\n<p>\ubaa8\ub4e0 \\(\\varSigma\\)\uc758 \ubaa8\ud615 \\(v\\)\uc5d0 \ub300\ud558\uc5ec \\(v(\\phi)=\\mathrm T\\)\uc774\uba74 \\(\\phi\\)\ub97c \\(\\varSigma\\)\uc758 <span class=\"defined\">\ub17c\ub9ac\uc801 \uadc0\uacb0<\/span>(logical consequence)\uc774\ub77c\uace0 \ubd80\ub974\uace0<br \/>\n\\[<br \/>\n\\varSigma\\models\\phi<br \/>\n\\]<br \/>\n\ub85c \ub098\ud0c0\ub0b8\ub2e4. \\(\\varSigma=\\varnothing\\)\uc774\uba74<br \/>\n\\[<br \/>\n\\models\\phi<br \/>\n\\]<br \/>\n\ub294 \uc815\ud655\ud788 \\(\\phi\\)\uac00 \ud56d\uc9c4\uc774\ub77c\ub294 \ub73b\uc774\ub2e4.<\/p>\n<div class=\"problem\">\n<p class=\"marginbottomhalf\"><span class=\"problem\">\ubb38\uc81c 12.2.<\/span><br \/>\n\uac12\ub9e4\uae40 \\(v\\)\uac00<br \/>\n\\[<br \/>\nv(p)=\\mathrm T,\\quad v(q)=\\mathrm F,\\quad v(r)=\\mathrm T<br \/>\n\\]<br \/>\n\ub97c \ub9cc\uc871\uc2dc\ud0a8\ub2e4\uace0 \ud558\uc790.<\/p>\n<ol class=\"parenthesis\">\n<li>\ub2e4\uc74c \uc9c4\ub9bf\uac12\uc744 \uac01\uac01 \uad6c\ud558\uc2dc\uc624.<br \/>\n\\[<br \/>\nv(\\neg p),\\quad<br \/>\nv(p\\to q),\\quad<br \/>\nv((p\\to q)\\to r),\\quad<br \/>\nv((p\\wedge r)\\vee q).<br \/>\n\\]\n<\/li>\n<li>\ub2e4\uc74c \ub17c\ub9ac\uc2dd\uc744 \ud56d\uc9c4, \ubaa8\uc21c, \uadf8 \uc5b4\ub290 \uac83\ub3c4 \uc544\ub2cc \uac83\uc73c\ub85c \ubd84\ub958\ud558\uc2dc\uc624.<br \/>\n\\[<br \/>\np\\to p,<br \/>\n\\quad<br \/>\np\\wedge\\neg p,<br \/>\n\\quad<br \/>\np\\to q,<br \/>\n\\quad<br \/>\n(p\\to q)\\vee(q\\to p).<br \/>\n\\]\n<\/li>\n<\/ol>\n<\/div>\n<div class=\"problem\">\n<p class=\"marginbottomhalf\"><span class=\"problem\">\ubb38\uc81c 12.3.<\/span><br \/>\n\ub17c\ub9ac\uc801 \uadc0\uacb0\uc758 \uc815\uc758\ub97c \uc0ac\uc6a9\ud558\uc5ec \ub2e4\uc74c\uc744 \ud310\uc815\ud558\uc2dc\uc624. \uc131\ub9bd\ud558\uc9c0 \uc54a\uc73c\uba74 \ubc18\ub840\uac00 \ub418\ub294 \uac12\ub9e4\uae40\uc744 \ud558\ub098 \uc81c\uc2dc\ud558\uc2dc\uc624.<\/p>\n<ol class=\"parenthesis\">\n<li>\\(\\{p,p\\to q,q\\to r\\}\\models r\\).<\/li>\n<li>\\(\\{p\\vee q\\}\\models p\\).<\/li>\n<li>\\(\\{p\\to q\\}\\models\\neg q\\to\\neg p\\).<\/li>\n<li>\\(\\{p,p\\to q,\\neg q\\}\\)\ub294 \ub9cc\uc871 \uac00\ub2a5\ud55c\uac00?<\/li>\n<\/ol>\n<\/div>\n<h3>3. \ud615\uc2dd\ucd94\ub860\uacc4<\/h3>\n<p>\uc774\uc81c \uba85\uc81c\ub17c\ub9ac\uc758 <span class=\"defined\">\ud615\uc2dd\ucd94\ub860\uacc4<\/span>(formal deduction system)\ub97c \uc815\ud55c\ub2e4. \uba3c\uc800 \ub2e4\uc74c \uc138 <span class=\"defined\">\uacf5\ub9ac\ud2c0<\/span>(axiom scheme)\uc744 \uc0ac\uc6a9\ud55c\ub2e4.<\/p>\n<p>&nbsp;&nbsp;(A1) \\(\\phi\\to(\\psi\\to\\phi)\\)<br \/>\n&nbsp;&nbsp;(A2) \\((\\phi\\to(\\psi\\to\\theta))\\to((\\phi\\to\\psi)\\to(\\phi\\to\\theta))\\)<br \/>\n&nbsp;&nbsp;(A3) \\((\\neg\\phi\\to\\neg\\psi)\\to(\\psi\\to\\phi)\\)<\/p>\n<p>\uc5ec\uae30\uc11c \\(\\phi,\\psi,\\theta\\)\ub294 \uc784\uc758\uc758 \ub17c\ub9ac\uc2dd\uc774\ub2e4. \uc774\ub4e4\uc744 \uc784\uc758\uc758 \ub17c\ub9ac\uc2dd\uc73c\ub85c \uce58\ud658\ud558\uc5ec \uc5bb\ub294 \ubaa8\ub4e0 \uc2dd\uc744 \uacf5\ub9ac\ub77c\uace0 \ud55c\ub2e4.<\/p>\n<p>\ucd94\ub860\uaddc\uce59\uc740 \ub2e4\uc74c \ud558\ub098\ubfd0\uc774\ub2e4.<br \/>\n\\[<br \/>\n\\frac{\\phi\\quad \\phi\\to\\psi}{\\psi}\\quad(\\mathrm{MP})<br \/>\n\\]<br \/>\n\uc774\ub97c modus ponens, \uc904\uc5ec\uc11c <span class=\"defined\">MP<\/span>\ub77c\uace0 \ub098\ud0c0\ub0b8\ub2e4.<\/p>\n<p><a href=\"\/blog\/invitation-to-mathematical-logic\/ch11-formal-logic\">11\uc7a5<\/a>\uc5d0\uc11c \uc815\uc758\ud55c \uc99d\uba85\uacfc \uc815\ub9ac\uc758 \uac1c\ub150\uc744 \uc774 \ud615\uc2dd\ucd94\ub860\uacc4\uc5d0 \uc801\uc6a9\ud55c\ub2e4. \ub530\ub77c\uc11c \uba85\uc81c\ub17c\ub9ac\uc758 \uc99d\uba85\uc740 \uc720\ud55c\ud55c \ub17c\ub9ac\uc2dd\uc758 \uc5f4\uc774\uba70, \uac01 \ud56d\uc740 \uacf5\ub9ac\uc774\uac70\ub098 \uc55e\uc758 \ud56d\ub4e4\uc5d0 MP\ub97c \uc801\uc6a9\ud558\uc5ec \uc5bb\uc5b4\uc9c4\ub2e4.<\/p>\n<p>\ub17c\ub9ac\uc2dd\uc758 \uc9d1\ud569 \\(\\varSigma\\)\uac00 \uc8fc\uc5b4\uc84c\uc744 \ub54c\uc5d0\ub294 \uacf5\ub9ac\ubfd0 \uc544\ub2c8\ub77c \\(\\varSigma\\)\uc758 \uc6d0\uc18c\ub3c4 \uc99d\uba85\uc758 \ucd9c\ubc1c\uc810\uc73c\ub85c \ud5c8\uc6a9\ud55c\ub2e4. \ub9c8\uc9c0\ub9c9 \ub17c\ub9ac\uc2dd\uc774 \\(\\phi\\)\uc778 \uc774\ub7ec\ud55c \uc99d\uba85\uc774 \uc874\uc7ac\ud558\uba74<br \/>\n\\[<br \/>\n\\varSigma\\vdash\\phi<br \/>\n\\]<br \/>\n\ub85c \ub098\ud0c0\ub0b8\ub2e4. \uc774\ub54c \\(\\varSigma\\)\ub97c <span class=\"defined\">\uac00\uc815 \uc9d1\ud569<\/span>\uc774\ub77c \ud55c\ub2e4. \ud2b9\ud788 \\(\\varSigma=\\varnothing\\)\uc774\uba74<br \/>\n\\[<br \/>\n\\vdash\\phi<br \/>\n\\]<br \/>\n\ub85c \uc4f0\uba70, \\(\\phi\\)\ub294 \uba85\uc81c\ub17c\ub9ac\uc758 \uc815\ub9ac\uc774\ub2e4.<\/p>\n<div class=\"problem\">\n<p class=\"marginbottomhalf\"><span class=\"problem\">\ubb38\uc81c 12.4.<\/span><br \/>\n\uacf5\ub9ac\ud2c0\uacfc MP\ub97c \uc9c1\uc811 \uc801\uc6a9\ud558\uc5ec \ub2e4\uc74c \uc9c8\ubb38\uc5d0 \ub2f5\ud558\uc2dc\uc624.<\/p>\n<ol class=\"parenthesis\">\n<li>\ub2e4\uc74c \uac01 \ub17c\ub9ac\uc2dd\uc774 (A1), (A2), (A3) \uc911 \uc5b4\ub290 \uacf5\ub9ac\ud2c0\uc5d0 \ud574\ub2f9\ud558\ub294\uc9c0 \ud310\uc815\ud558\uc2dc\uc624. \uc5b4\ub290 \uac83\ub3c4 \uc544\ub2c8\uba74 \uadf8\ub807\uac8c \ub2f5\ud558\uc2dc\uc624.<br \/>\n\\[<br \/>\n\\begin{aligned}<br \/>\n&#038;p\\to(q\\to p),\\\\[3pt]<br \/>\n&#038;(p\\to(q\\to r))\\to((p\\to q)\\to(p\\to r)),\\\\[3pt]<br \/>\n&#038;(\\neg(p\\to q)\\to\\neg r)\\to(r\\to(p\\to q)),\\\\[3pt]<br \/>\n&#038;p\\to(q\\to q).<br \/>\n\\end{aligned}<br \/>\n\\]\n<\/li>\n<li>\\(\\varSigma=\\{p,\\;p\\to q,\\;q\\to r\\}\\)\uc774\ub77c\uace0 \ud558\uc790. \\(\\varSigma\\vdash r\\)\uc784\uc744 \ubcf4\uc774\ub294 \uc99d\uba85\uc744 \uc4f0\uace0, \uac01 MP\uac00 \uc5b4\ub290 \ub450 \uc55e\uc120 \ub17c\ub9ac\uc2dd\uc5d0 \uc801\uc6a9\ub418\uc5c8\ub294\uc9c0 \ubc1d\ud788\uc2dc\uc624.<\/li>\n<\/ol>\n<\/div>\n<h3>4. \uc99d\uba85 \uc608\uc81c<\/h3>\n<div class=\"box theorem\">\n<p><span class=\"definition\">\uc815\ub9ac 12.1.<\/span><\/p>\n<p>\uc784\uc758\uc758 \ub17c\ub9ac\uc2dd \\(p\\)\uc5d0 \ub300\ud558\uc5ec \\(p\\to p\\)\ub294 \uba85\uc81c\ub17c\ub9ac\uc758 \uc815\ub9ac\uc774\ub2e4.<\/p>\n<\/div>\n<div class=\"proof\">\n<p class=\"proofbegin\"><span class=\"proof\">\uc99d\uba85<\/span><br \/>\n\ub2e4\uc74c\uc740 \uae38\uc774\uac00 5\uc778 \uc99d\uba85\uc774\ub2e4.<\/p>\n<p>\\[<br \/>\n\\begin{aligned}<br \/>\n&#038;\\vdash (p\\to((p\\to p)\\to p))\\to((p\\to(p\\to p))\\to(p\\to p)) &#038;&#038;\\text{(A2)},\\\\[3pt]<br \/>\n&#038;\\vdash p\\to((p\\to p)\\to p) &#038;&#038;\\text{(A1)},\\\\[3pt]<br \/>\n&#038;\\vdash (p\\to(p\\to p))\\to(p\\to p) &#038;&#038;\\text{(MP)},\\\\[3pt]<br \/>\n&#038;\\vdash p\\to(p\\to p) &#038;&#038;\\text{(A1)},\\\\[3pt]<br \/>\n&#038;\\vdash p\\to p &#038;&#038;\\text{(MP)}.<br \/>\n\\end{aligned}<br \/>\n\\]<\/p>\n<p>\uccab\uc9f8 \uc2dd\uacfc \ub458\uc9f8 \uc2dd\uc5d0 MP\ub97c \uc801\uc6a9\ud558\uc5ec \uc14b\uc9f8 \uc2dd\uc744 \uc5bb\uace0, \uc14b\uc9f8 \uc2dd\uacfc \ub137\uc9f8 \uc2dd\uc5d0 MP\ub97c \uc801\uc6a9\ud558\uc5ec \ub9c8\uc9c0\ub9c9 \uc2dd\uc744 \uc5bb\ub294\ub2e4.<span class=\"qed\"><\/span><\/p>\n<\/div>\n<p>\ub2e4\uc74c \uba54\ud0c0\uc815\ub9ac\ub294 \uac00\uc815\uc744 \ud568\uc758\uc758 \uc55e\ubd80\ubd84\uc73c\ub85c \uc62e\uae38 \uc218 \uc788\uc74c\uc744 \ubcf4\uc5ec \uc900\ub2e4.<\/p>\n<div class=\"box theorem\">\n<p><span class=\"definition\">\uc815\ub9ac 12.2. (\ucd94\ub860 \uc815\ub9ac)<\/span><\/p>\n<p>\\(\\varSigma\\cup\\{\\psi\\}\\vdash\\phi\\)\uc774\uba74 \\(\\varSigma\\vdash\\psi\\to\\phi\\)\uc774\ub2e4.<\/p>\n<\/div>\n<div class=\"proof\">\n<p class=\"proofbegin\"><span class=\"proof\">\uc99d\uba85<\/span><br \/>\n\\(\\varSigma\\cup\\{\\psi\\}\\)\ub85c\ubd80\ud130\uc758 \\(\\phi\\)\uc758 \uc99d\uba85\uc744<br \/>\n\\[<br \/>\n\\phi_1,\\phi_2,\\ldots,\\phi_n=\\phi<br \/>\n\\]<br \/>\n\ub77c \ud558\uc790. \uac01 \\(i\\)\uc5d0 \ub300\ud558\uc5ec \\(\\varSigma\\vdash\\psi\\to\\phi_i\\)\uc784\uc744 \\(i\\)\uc5d0 \ub300\ud55c \uadc0\ub0a9\ubc95\uc744 \uc0ac\uc6a9\ud558\uc5ec \ubcf4\uc778\ub2e4.<\/p>\n<p>\\(\\phi_i\\)\uac00 \uacf5\ub9ac\uc774\uac70\ub098 \\(\\varSigma\\)\uc758 \uc6d0\uc18c\uc774\uba74 \\(\\varSigma\\vdash\\phi_i\\)\uc774\ub2e4. (A1)\uc758<br \/>\n\\[<br \/>\n\\phi_i\\to(\\psi\\to\\phi_i)<br \/>\n\\]<br \/>\n\uc640 MP\ub97c \uc0ac\uc6a9\ud558\uba74 \\(\\varSigma\\vdash\\psi\\to\\phi_i\\)\uc774\ub2e4. \\(\\phi_i=\\psi\\)\uc774\uba74 \uc815\ub9ac 12.1\uc5d0 \uc758\ud558\uc5ec \\(\\varSigma\\vdash\\psi\\to\\psi\\)\uc774\ub2e4.<\/p>\n<p>\ub9c8\uc9c0\ub9c9\uc73c\ub85c \\(\\phi_i\\)\uac00 \uc55e\uc120 \ub450 \uc2dd \\(\\phi_j\\)\uc640 \\(\\phi_j\\to\\phi_i\\)\uc5d0 MP\ub97c \uc801\uc6a9\ud558\uc5ec \uc5bb\uc5b4\uc84c\ub2e4\uace0 \ud558\uc790. \uadc0\ub0a9\uac00\uc815\uc5d0 \uc758\ud558\uc5ec<br \/>\n\\[<br \/>\n\\varSigma\\vdash\\psi\\to\\phi_j,<br \/>\n\\quad<br \/>\n\\varSigma\\vdash\\psi\\to(\\phi_j\\to\\phi_i)<br \/>\n\\]<br \/>\n\uc774\ub2e4. (A2)\uc5d0\uc11c \ubb38\uc790\ub97c \ubc14\uafbc \uc2dd<br \/>\n\\[<br \/>\n(\\psi\\to(\\phi_j\\to\\phi_i))<br \/>\n\\to((\\psi\\to\\phi_j)\\to(\\psi\\to\\phi_i))<br \/>\n\\]<br \/>\n\uc5d0 MP\ub97c \ub450 \ubc88 \uc801\uc6a9\ud558\uba74 \\(\\varSigma\\vdash\\psi\\to\\phi_i\\)\ub97c \uc5bb\ub294\ub2e4. \ud2b9\ud788 \\(i=n\\)\uc77c \ub54c \uc6d0\ud558\ub294 \uacb0\ub860\uc774 \ub530\ub978\ub2e4.<span class=\"qed\"><\/span><\/p>\n<\/div>\n<p>\ucd94\ub860 \uc815\ub9ac\ub97c \uc0ac\uc6a9\ud558\ub294 \uc608\ub85c<br \/>\n\\[<br \/>\n\\vdash\\neg\\phi\\to(\\phi\\to\\psi)<br \/>\n\\]<br \/>\n\ub97c \ubcf4\uc774\uc790. \\(\\{\\neg\\phi\\}\\)\ub97c \uac00\uc815 \uc9d1\ud569\uc73c\ub85c \ub450\uba74<br \/>\n\\[<br \/>\n\\begin{aligned}<br \/>\n\\{\\neg\\phi\\}&#038;\\vdash \\neg\\phi\\to(\\neg\\psi\\to\\neg\\phi) &#038;&#038;\\text{(A1)},\\\\[3pt]<br \/>\n\\{\\neg\\phi\\}&#038;\\vdash \\neg\\phi &#038;&#038;\\text{(\uac00\uc815)},\\\\[3pt]<br \/>\n\\{\\neg\\phi\\}&#038;\\vdash \\neg\\psi\\to\\neg\\phi &#038;&#038;\\text{(MP)},\\\\[3pt]<br \/>\n\\{\\neg\\phi\\}&#038;\\vdash (\\neg\\psi\\to\\neg\\phi)\\to(\\phi\\to\\psi) &#038;&#038;\\text{(A3)},\\\\[3pt]<br \/>\n\\{\\neg\\phi\\}&#038;\\vdash \\phi\\to\\psi &#038;&#038;\\text{(MP)}.<br \/>\n\\end{aligned}<br \/>\n\\]<br \/>\n\ub530\ub77c\uc11c \ucd94\ub860 \uc815\ub9ac\uc5d0 \uc758\ud558\uc5ec \\(\\vdash\\neg\\phi\\to(\\phi\\to\\psi)\\)\uc774\ub2e4.<\/p>\n<div class=\"problem\">\n<p class=\"marginbottomhalf\"><span class=\"problem\">\ubb38\uc81c 12.5.<\/span><br \/>\n\\(\\varSigma=\\{p\\to q,\\;q\\to r\\}\\)\ub77c \ud558\uc790.<\/p>\n<ol class=\"parenthesis\">\n<li>\\(\\varSigma\\cup\\{p\\}\\vdash r\\)\uc784\uc744 MP\ub9cc \uc0ac\uc6a9\ud558\uc5ec \ubcf4\uc774\uc2dc\uc624.<\/li>\n<li>\ucd94\ub860 \uc815\ub9ac\ub97c \uc0ac\uc6a9\ud558\uc5ec \\(\\varSigma\\vdash p\\to r\\)\uc784\uc744 \ubcf4\uc774\uc2dc\uc624.<\/li>\n<li>\ucd94\ub860 \uc815\ub9ac\ub97c \ub450 \ubc88 \ub354 \uc801\uc6a9\ud558\uc5ec<br \/>\n\\[<br \/>\n\\vdash (p\\to q)\\to((q\\to r)\\to(p\\to r))<br \/>\n\\]<br \/>\n\uc784\uc744 \ubcf4\uc774\uc2dc\uc624.<\/li>\n<\/ol>\n<\/div>\n<div class=\"problem\">\n<p class=\"marginbottomhalf\"><span class=\"problem\">\ubb38\uc81c 12.6.<\/span><br \/>\n\uc774 \uc808\uc758 \uba85\uc81c\ub17c\ub9ac \ud615\uc2dd\ucd94\ub860\uacc4\ub97c \ubcc0\ud615\ud55c\ub2e4\uace0 \ud558\uc790. \ub2e4\uc74c \uc9c8\ubb38\uc5d0 \ub2f5\ud558\uc2dc\uc624.<\/p>\n<ol class=\"parenthesis\">\n<li>(A1)\u2013(A3)\uc744 \ubaa8\ub450 \uc81c\uac70\ud558\uace0 MP\ub9cc \ub0a8\uae30\uba74 \uc5b4\ub5a4 \uc815\ub9ac\ub97c \uc99d\uba85\ud560 \uc218 \uc788\ub294\uac00?<\/li>\n<li>MP\ub97c \uc81c\uac70\ud558\uace0 (A1)\u2013(A3)\ub9cc \ub0a8\uae30\uba74 \uc5b4\ub5a4 \uc815\ub9ac\ub97c \uc99d\uba85\ud560 \uc218 \uc788\ub294\uac00?<\/li>\n<li>\ubaa8\ub4e0 \ub17c\ub9ac\uc2dd\uc774 \uc815\ub9ac\uac00 \ub418\ub294 \ud615\uc2dd\uacc4\ub97c \ud558\ub098 \uc81c\uc2dc\ud558\uc2dc\uc624.<\/li>\n<\/ol>\n<\/div>\n<div class=\"contentbottombox\">\n<p class=\"contentbottomboxtitle\"><a href=\"\/blog\/invitation-to-mathematical-logic\/\">\uc9d1\ud569\uacfc \uc218\ub9ac\ub17c\ub9ac \uccab\uac78\uc74c \ubaa9\ucc28 \ubcf4\uae30<\/a><\/p>\n<p><span class=\"contentboxindex\"><a href=\"\/blog\/invitation-to-mathematical-logic\/ch01-naive-logic\/\">\uba85\uc81c\uc640 \ub17c\ub9ac<\/a><\/span><br \/>\n<span class=\"contentboxindex\"><a href=\"\/blog\/invitation-to-mathematical-logic\/ch02-sets\">\uc9d1\ud569\uc758 \uac1c\ub150<\/a><\/span><br \/>\n<span class=\"contentboxindex\"><a href=\"\/blog\/invitation-to-mathematical-logic\/ch03-algebra-of-classes\">\ub2e4\uc591\ud55c \uc9d1\ud569\uc758 \uc5f0\uc0b0<\/a><\/span><br \/>\n<span class=\"contentboxindex\"><a href=\"\/blog\/invitation-to-mathematical-logic\/ch04-relations-and-functions\">\uad00\uacc4\uc640 \ud568\uc218<\/a><\/span><br \/>\n<span class=\"contentboxindex\"><a href=\"\/blog\/invitation-to-mathematical-logic\/ch05-infinite-sets\">\uc720\ud55c\uc9d1\ud569\uacfc \ubb34\ud55c\uc9d1\ud569<\/a><\/span><br \/>\n<span class=\"contentboxindex\"><a href=\"\/blog\/invitation-to-mathematical-logic\/ch06-natural-numbers\">\uc790\uc5f0\uc218<\/a><\/span><br \/>\n<span class=\"contentboxindex\"><a href=\"\/blog\/invitation-to-mathematical-logic\/ch07-cardinal-numbers\">\uc9d1\ud569\uc758 \uae30\uc218<\/a><\/span><br \/>\n<span class=\"contentboxindex\"><a href=\"\/blog\/invitation-to-mathematical-logic\/ch08-ordinal-numbers\">\uc9d1\ud569\uc758 \uc11c\uc218<\/a><\/span><br \/>\n<span class=\"contentboxindex\"><a href=\"\/blog\/invitation-to-mathematical-logic\/ch09-axiomatic-set-theory\">\uc9d1\ud569\ub860\uc758 \uacf5\ub9ac<\/a><\/span><br \/>\n<span class=\"contentboxindex\"><a href=\"\/blog\/invitation-to-mathematical-logic\/ch10-axiom-of-choice\">\uc120\ud0dd \uacf5\ub9ac<\/a><\/span><br \/>\n<span class=\"contentboxindex\"><a href=\"\/blog\/invitation-to-mathematical-logic\/ch11-formal-logic\">\ud615\uc2dd\ub17c\ub9ac<\/a><\/span><br \/>\n<span class=\"contentboxindex\"><a href=\"\/blog\/invitation-to-mathematical-logic\/ch12-propositional-logic\">\uba85\uc81c\ub17c\ub9ac\uc758 \uac1c\ub150<\/a><\/span><br \/>\n<span class=\"contentboxindex\"><a href=\"\/blog\/invitation-to-mathematical-logic\/ch13-soundness-completeness-proplogic\">\uba85\uc81c\ub17c\ub9ac\uc758 \uac74\uc804\uc131\uacfc \uc644\uc804\uc131<\/a><\/span><br \/>\n<span class=\"contentboxindex\"><a href=\"\/blog\/invitation-to-mathematical-logic\/ch14-syntax-first-order-logic\">\uc77c\uacc4\ub17c\ub9ac\uc758 \uad6c\ubb38\ub860<\/a><\/span><br \/>\n<span class=\"contentboxindex\"><a href=\"\/blog\/invitation-to-mathematical-logic\/ch15-semantics-first-order-logic\">\uc77c\uacc4\ub17c\ub9ac\uc758 \uc758\ubbf8\ub860<\/a><\/span><br \/>\n<span class=\"contentboxindex\"><a href=\"\/blog\/invitation-to-mathematical-logic\/ch16-inference-rule-first-order-logic\">\uc77c\uacc4\ub17c\ub9ac\uc758 \ucd94\ub860\uaddc\uce59<\/a><\/span><br \/>\n<span class=\"contentboxindex\"><a href=\"\/blog\/invitation-to-mathematical-logic\/ch17-compactness-first-order-logic\">\uc77c\uacc4\ub17c\ub9ac\uc758 \ucf64\ud329\ud2b8\uc131<\/a><\/span><br \/>\n<span class=\"contentboxindex\"><a href=\"\/blog\/invitation-to-mathematical-logic\/ch18-peano-arithmetics\">\ud398\uc544\ub178 \uc0b0\uc220<\/a><\/span><br \/>\n<span class=\"contentboxindex\"><a href=\"\/blog\/invitation-to-mathematical-logic\/ch19-incompleteness-theorem\">\ubd88\uc644\uc804\uc131 \uc815\ub9ac<\/a><\/span>\n<\/div>\n<\/div>\n<p><!-- ################## --><\/p>\n","protected":false},"excerpt":{"rendered":"<p>\uba85\uc81c\ub17c\ub9ac(propositional logic)\ub294 \uba85\uc81c\ubcc0\uc218\uc640 \ub17c\ub9ac\uacb0\ud569\uc790, \uadf8\ub9ac\uace0 \uacf5\ub9ac\uc640 \ucd94\ub860\uaddc\uce59\uc73c\ub85c \uc774\ub8e8\uc5b4\uc9c4 \ud615\uc2dd\ub17c\ub9ac\uc758 \ud55c \uccb4\uacc4\uc774\ub2e4. 1\uc7a5\uc5d0\uc11c\ub294 \uba85\uc81c\uc640 \ub17c\ub9ac\uc5f0\uc0b0\uc744 \uc9c1\uad00\uc801\uc73c\ub85c \ub2e4\ub8e8\uc5c8\ub2e4. \uc774 \uc7a5\uc5d0\uc11c\ub294 \uac19\uc740 \ub300\uc0c1\uc744 \ubb38\uc790\uc5f4\uacfc \ud615\uc2dd\uc801 \uc99d\uba85\uc758 \uad00\uc810\uc5d0\uc11c \ub2e4\uc2dc \ub2e4\ub8ec\ub2e4. 1. \uad6c\ubb38\ub860 \uad6c\ubb38\ub860(syntax)\uc740 \uc8fc\uc5b4\uc9c4 \uae30\ud638\ub85c \uc5b4\ub5a4 \ubb38\uc790\uc5f4\uc744 \ub17c\ub9ac\uc2dd\uc73c\ub85c \uc778\uc815\ud560 \uac83\uc778\uc9c0 \uc815\ud558\ub294 \uaddc\uce59\uc744 \ub2e4\ub8ec\ub2e4. \uad6c\ubb38\ub860\uc5d0\uc11c\ub294 \ubb38\uc790\uc5f4\uc758 \uc758\ubbf8\ub098 \uc9c4\ub9bf\uac12\uc744 \ub530\uc9c0\uc9c0 \uc54a\uace0 \uae30\ud638\uc758 \ud615\uc2dd\ub9cc\uc744 \uace0\ub824\ud55c\ub2e4. \uac00\uc0b0 \uac1c\uc758 \uba85\uc81c\ubcc0\uc218(propositional variable) \\(\\{p_0,p_1,p_2,\\ldots\\}\\) \uac00 \uc8fc\uc5b4\uc84c\ub2e4\uace0 \ud558\uc790. \uc774 \uc7a5\uc758 \ud615\uc2dd\ucd94\ub860\uacc4\uc5d0\uc11c\ub294 \ubd80\uc815\uae30\ud638 \\(\\neg\\)\uc640 \ud568\uc758\uae30\ud638 \\(\\to\\)\ub97c \uae30\ubcf8&hellip;<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":9246,"menu_order":112,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_lmt_disableupdate":"no","_lmt_disable":"","footnotes":""},"class_list":["post-9270","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/sasamath.com\/blog\/wp-json\/wp\/v2\/pages\/9270","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/sasamath.com\/blog\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/sasamath.com\/blog\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/sasamath.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/sasamath.com\/blog\/wp-json\/wp\/v2\/comments?post=9270"}],"version-history":[{"count":13,"href":"https:\/\/sasamath.com\/blog\/wp-json\/wp\/v2\/pages\/9270\/revisions"}],"predecessor-version":[{"id":10089,"href":"https:\/\/sasamath.com\/blog\/wp-json\/wp\/v2\/pages\/9270\/revisions\/10089"}],"up":[{"embeddable":true,"href":"https:\/\/sasamath.com\/blog\/wp-json\/wp\/v2\/pages\/9246"}],"wp:attachment":[{"href":"https:\/\/sasamath.com\/blog\/wp-json\/wp\/v2\/media?parent=9270"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}