{"id":9274,"date":"2025-10-17T20:20:35","date_gmt":"2025-10-17T11:20:35","guid":{"rendered":"https:\/\/sasamath.com\/blog\/?page_id=9274"},"modified":"2026-09-27T12:23:20","modified_gmt":"2026-09-27T03:23:20","slug":"ch13-soundness-completeness-proplogic","status":"publish","type":"page","link":"https:\/\/sasamath.com\/blog\/invitation-to-mathematical-logic\/ch13-soundness-completeness-proplogic\/","title":{"rendered":"\uba85\uc81c\ub17c\ub9ac\uc758 \uac74\uc804\uc131\uacfc \uc644\uc804\uc131"},"content":{"rendered":"
<\/p>\n

<\/p>\n

\uba85\uc81c\ub17c\ub9ac\uc5d0\ub294 \uc11c\ub85c \ub2e4\ub978 \ub450 \uad00\uc810\uc774 \uc788\ub2e4. \uad6c\ubb38\ub860\uc801 \uad00\uc810\uc5d0\uc11c\ub294 \uacf5\ub9ac\uc640 \ucd94\ub860\uaddc\uce59\uc744 \uc0ac\uc6a9\ud558\uc5ec \ubb34\uc5c7\uc744 \uc99d\uba85\ud560 \uc218 \uc788\ub294\uc9c0\ub97c \ubb3b\uace0, \uc758\ubbf8\ub860\uc801 \uad00\uc810\uc5d0\uc11c\ub294 \uac12\ub9e4\uae40\uc5d0 \uc758\ud558\uc5ec \uc5b4\ub5a4 \ub17c\ub9ac\uc2dd\uc774 \ucc38\uc774 \ub418\ub294\uc9c0\ub97c \ubb3b\ub294\ub2e4. \uac74\uc804\uc131\uacfc \uc644\uc804\uc131\uc740 \uc774 \ub450 \uad00\uc810\uc774 \uc815\ud655\ud788 \uc77c\uce58\ud55c\ub2e4\ub294 \uc0ac\uc2e4\uc744 \ub098\ud0c0\ub0b8\ub2e4.<\/p>\n

1. \uac74\uc804\uc131 \uc815\ub9ac\uc640 \uc644\uc804\uc131 \uc815\ub9ac<\/h3>\n

\uac74\uc804\uc131<\/span>(soundness)\uc740
\n\\[
\n\\varSigma\\vdash\\phi\\quad\\Longrightarrow\\quad\\varSigma\\models\\phi
\n\\]
\n\uac00 \uc131\ub9bd\ud558\ub294 \uc131\uc9c8\uc744 \ub9d0\ud55c\ub2e4. \uc989, \ud615\uc2dd\uc801\uc73c\ub85c \uc99d\uba85 \uac00\ub2a5\ud55c \uacb0\ub860\uc740 \uc758\ubbf8\ub860\uc801\uc73c\ub85c\ub3c4 \uac00\uc815\uc758 \ub17c\ub9ac\uc801 \uadc0\uacb0\uc774\ub2e4.<\/p>\n

\uc644\uc804\uc131<\/span>(completeness)\uc740 \uadf8 \uc5ed\uc778
\n\\[
\n\\varSigma\\models\\phi\\quad\\Longrightarrow\\quad\\varSigma\\vdash\\phi
\n\\]
\n\uac00 \uc131\ub9bd\ud558\ub294 \uc131\uc9c8\uc744 \ub9d0\ud55c\ub2e4.<\/p>\n

\n

\uc815\uc758 13.1. (\ubb34\ubaa8\uc21c\uc131)<\/span><\/p>\n

\ub17c\ub9ac\uc2dd\uc758 \uc9d1\ud569 \\(\\varSigma\\)\uc5d0 \ub300\ud558\uc5ec \uc5b4\ub5a4 \ub17c\ub9ac\uc2dd \\(\\psi\\)\ub3c4
\n\\[
\n\\varSigma\\vdash\\psi,
\n\\quad
\n\\varSigma\\vdash\\neg\\psi
\n\\]
\n\ub97c \ub3d9\uc2dc\uc5d0 \ub9cc\uc871\uc2dc\ud0a4\uc9c0 \uc54a\uc73c\uba74 \\(\\varSigma\\)\uac00 \ubb34\ubaa8\uc21c<\/span>(consistent)\uc774\ub77c\uace0 \ud55c\ub2e4. \uadf8\ub807\uc9c0 \uc54a\uc73c\uba74 \ubaa8\uc21c\uc801<\/span>(inconsistent)\uc774\ub77c\uace0 \ud55c\ub2e4.<\/p>\n<\/div>\n

\n

\uc815\ub9ac 13.2. (\uac74\uc804\uc131 \uc815\ub9ac)<\/span><\/p>\n

\uc784\uc758\uc758 \ub17c\ub9ac\uc2dd \uc9d1\ud569 \\(\\varSigma\\)\uc640 \ub17c\ub9ac\uc2dd \\(\\phi\\)\uc5d0 \ub300\ud558\uc5ec
\n\\[
\n\\varSigma\\vdash\\phi
\n\\quad\\Longrightarrow\\quad
\n\\varSigma\\models\\phi
\n\\]
\n\uc774\ub2e4.<\/p>\n<\/div>\n

\n

\uc99d\uba85<\/span>
\n\\(\\varSigma\\)\uc758 \ubaa8\ub4e0 \ub17c\ub9ac\uc2dd\uc744 \ucc38\uc73c\ub85c \ub9cc\ub4dc\ub294 \uac12\ub9e4\uae40 \\(v\\)\ub97c \ud558\ub098 \uace0\uc815\uc2dc\ud0a4\uace0, \\(\\varSigma\\)\ub85c\ubd80\ud130\uc758 \uc99d\uba85 \uae38\uc774\uc5d0 \ub300\ud558\uc5ec \uc218\ud559\uc801 \uadc0\ub0a9\ubc95\uc744 \uc0ac\uc6a9\ud55c\ub2e4. \uacf5\ub9ac (A1)\u2013(A3)\uc740 \uc9c4\ub9ac\ud45c\ub85c \uc9c1\uc811 \ud655\uc778\ud558\uba74 \ubaa8\ub450 \ud56d\uc9c4\uc774\ub2e4. \uac00\uc815\uc740 \\(v\\)\uc758 \uc120\ud0dd\uc5d0 \uc758\ud558\uc5ec \ucc38\uc774\ub2e4. \ub610\ud55c MP\ub294 \uc9c4\ub9bf\uac12\uc744 \ubcf4\uc874\ud55c\ub2e4. \uc2e4\uc81c\ub85c \\(v(\\chi)=\\mathrm T\\)\uc774\uace0 \\(v(\\chi\\to\\eta)=\\mathrm T\\)\uc774\uba74 \ud568\uc758\uc758 \uc9c4\ub9ac\ud45c\uc5d0 \uc758\ud558\uc5ec \\(v(\\eta)=\\mathrm T\\)\uc774\ub2e4. \ub530\ub77c\uc11c \uc99d\uba85\uc758 \ubaa8\ub4e0 \ub17c\ub9ac\uc2dd\uc774 \\(v\\)\uc5d0\uc11c \ucc38\uc774\uace0, \ud2b9\ud788 \ub9c8\uc9c0\ub9c9 \ub17c\ub9ac\uc2dd \\(\\phi\\)\ub3c4 \ucc38\uc774\ub2e4.<\/span><\/p>\n<\/div>\n

\ub530\ub77c\uc11c \ub9cc\uc871 \uac00\ub2a5\ud55c \ub17c\ub9ac\uc2dd \uc9d1\ud569\uc740 \ubb34\ubaa8\uc21c\uc774\ub2e4. \uc2e4\uc81c\ub85c \\(\\varSigma\\)\uc758 \ubaa8\ud615\uc774 \uc788\ub294\ub370 \\(\\varSigma\\vdash\\psi\\)\uc640 \\(\\varSigma\\vdash\\neg\\psi\\)\uac00 \ub3d9\uc2dc\uc5d0 \uc131\ub9bd\ud558\uba74 \uac74\uc804\uc131 \uc815\ub9ac\uc5d0 \uc758\ud558\uc5ec \uac19\uc740 \uac12\ub9e4\uae40\uc5d0\uc11c \\(\\psi\\)\uc640 \\(\\neg\\psi\\)\uac00 \ubaa8\ub450 \ucc38\uc774\uc5b4\uc57c \ud558\ubbc0\ub85c \ubaa8\uc21c\uc774\ub2e4.<\/p>\n

\uc644\uc804\uc131\uc744 \uc99d\uba85\ud558\ub824\uba74 \ubb34\ubaa8\uc21c \uc9d1\ud569\uc73c\ub85c\ubd80\ud130 \ubaa8\ud615\uc744 \ub9cc\ub4e4\uc5b4\uc57c \ud55c\ub2e4. \ub2e4\uc74c \ubcf4\uc870\uc815\ub9ac\uac00 \uadf8 \ud575\uc2ec\uc774\ub2e4.<\/p>\n

\n

\ubcf4\uc870\uc815\ub9ac 13.3. (\uadf9\ub300 \ubb34\ubaa8\uc21c \ud655\uc7a5)<\/span><\/p>\n

\ubaa8\ub4e0 \ubb34\ubaa8\uc21c \ub17c\ub9ac\uc2dd \uc9d1\ud569 \\(\\varSigma\\)\ub294 \uc790\uc2e0\uc744 \ud3ec\ud568\ud558\ub294 \uadf9\ub300 \ubb34\ubaa8\uc21c \uc9d1\ud569 \\(\\Gamma\\)\ub97c \uac00\uc9c4\ub2e4.<\/p>\n<\/div>\n

\n

\uc99d\uba85 \uac1c\uc694<\/span>
\n\uc774 \uc7a5\uc758 \uba85\uc81c\ubcc0\uc218\ub294 \uac00\uc0b0 \uac1c\uc774\ubbc0\ub85c \ubaa8\ub4e0 \ub17c\ub9ac\uc2dd\ub3c4 \uac00\uc0b0 \uac1c\uc774\ub2e4. \uc774\ub97c
\n\\[
\n\\phi_0,\\phi_1,\\phi_2,\\ldots
\n\\]
\n\uc640 \uac19\uc774 \ub098\uc5f4\ud55c\ub2e4.<\/p>\n

\uc815\ub9ac 12.2\uc758 \ucd94\ub860 \uc815\ub9ac<\/a>\uc640 (A1)\u2013(A3)\uc73c\ub85c\ubd80\ud130 \ub2e4\uc74c \uc0ac\uc2e4\uc744 \uc5bb\uc744 \uc218 \uc788\ub2e4.
\n\\[
\n\\Delta\\cup\\{\\chi\\}\\text{\uac00 \ubaa8\uc21c\uc801}
\n\\quad\\Longleftrightarrow\\quad
\n\\Delta\\vdash\\neg\\chi.
\n\\]
\n\uc67c\ucabd\uc5d0\uc11c \uc624\ub978\ucabd \ubc29\ud5a5\uc740 \ucd94\ub860 \uc815\ub9ac\uc640 \uacf5\ub9ac\uacc4\uc5d0\uc11c \uc720\ub3c4\ub418\ub294 \uadc0\ub958\ubc95
\n\\[
\n(\\chi\\to\\theta)\\to((\\chi\\to\\neg\\theta)\\to\\neg\\chi)
\n\\]
\n\uc744 \uc0ac\uc6a9\ud55c\ub2e4. \uc624\ub978\ucabd\uc5d0\uc11c \uc67c\ucabd \ubc29\ud5a5\uc740 \\(\\chi\\)\uc640 \\(\\neg\\chi\\)\ub97c \ub3d9\uc2dc\uc5d0 \uc5bb\uc744 \uc218 \uc788\uc73c\ubbc0\ub85c \uc989\uc2dc \ub530\ub978\ub2e4. \ub610\ud55c \uc774 \uacf5\ub9ac\uacc4\uc5d0\uc11c\ub294 \uc774\uc911\ubd80\uc815 \uc81c\uac70
\n\\[
\n\\vdash\\neg\\neg\\chi\\to\\chi
\n\\]
\n\ub3c4 \uc720\ub3c4\ub41c\ub2e4.<\/p>\n

\\(\\Gamma_0=\\varSigma\\)\ub85c \ub450\uace0, \\(\\Gamma_n\\)\uc774 \uc815\ud574\uc84c\uc744 \ub54c
\n\\[
\n\\Gamma_{n+1}=
\n\\begin{cases}
\n\\Gamma_n\\cup\\{\\phi_n\\} & (\\Gamma_n\\cup\\{\\phi_n\\}\\text{\uc774 \ubb34\ubaa8\uc21c\uc77c \ub54c}),\\\\[5pt]
\n\\Gamma_n\\cup\\{\\neg\\phi_n\\} & (\\text{\uadf8\ub807\uc9c0 \uc54a\uc744 \ub54c})
\n\\end{cases}
\n\\]
\n\ub85c \uc815\uc758\ud55c\ub2e4. \ub450 \ubc88\uc9f8 \uacbd\uc6b0\uc5d0\ub3c4 \ubb34\ubaa8\uc21c\uc131\uc774 \uc720\uc9c0\ub41c\ub2e4. \ub9cc\uc57d \\(\\phi_n\\)\uacfc \\(\\neg\\phi_n\\)\uc744 \uac01\uac01 \ub354\ud55c \ub450 \uc9d1\ud569\uc774 \ubaa8\ub450 \ubaa8\uc21c\uc801\uc774\uba74 \uc704\uc758 \ub3d9\uce58\uc5d0 \uc758\ud558\uc5ec \\(\\Gamma_n\\vdash\\neg\\phi_n\\)\uc640 \\(\\Gamma_n\\vdash\\neg\\neg\\phi_n\\)\uc744 \ub3d9\uc2dc\uc5d0 \uc5bb\uace0, \uc774\uc911\ubd80\uc815 \uc81c\uac70\uc5d0 \uc758\ud558\uc5ec \\(\\Gamma_n\\) \uc790\uccb4\uac00 \ubaa8\uc21c\uc801\uc774 \ub418\uae30 \ub54c\ubb38\uc774\ub2e4.<\/p>\n

\uc774\uc81c
\n\\[
\n\\Gamma=\\bigcup_{n\\in\\mathbb N}\\Gamma_n
\n\\]
\n\ub85c \ub454\ub2e4. \\(\\Gamma\\)\uc5d0\uc11c \ubaa8\uc21c\uc774 \uc99d\uba85\ub41c\ub2e4\uba74 \uadf8 \ub450 \uc720\ud55c\ud55c \uc99d\uba85\uc5d0 \uc0ac\uc6a9\ub41c \uac00\uc815\ub4e4\uc740 \uc5b4\ub5a4 \ud558\ub098\uc758 \\(\\Gamma_N\\)\uc5d0 \ubaa8\ub450 \ub4e4\uc5b4\uac00\ubbc0\ub85c \\(\\Gamma_N\\)\uc774 \ubaa8\uc21c\uc801\uc774 \ub418\uc5b4 \ubaa8\uc21c\uc774\ub2e4. \ub530\ub77c\uc11c \\(\\Gamma\\)\ub294 \ubb34\ubaa8\uc21c\uc774\ub2e4. \uad6c\uc131\uc0c1 \ubaa8\ub4e0 \ub17c\ub9ac\uc2dd \\(\\phi\\)\uc5d0 \ub300\ud558\uc5ec \\(\\phi\\)\uc640 \\(\\neg\\phi\\) \uc911 \uc815\ud655\ud788 \ud558\ub098\uac00 \\(\\Gamma\\)\uc5d0 \uc18d\ud558\ubbc0\ub85c \\(\\Gamma\\)\ub294 \uadf9\ub300 \ubb34\ubaa8\uc21c\uc774\ub2e4.<\/span><\/p>\n<\/div>\n

\n

\ubcf4\uc870\uc815\ub9ac 13.4. (\uc9c4\ub9ac \ubcf4\uc870\uc815\ub9ac)<\/span><\/p>\n

\\(\\Gamma\\)\uac00 \uadf9\ub300 \ubb34\ubaa8\uc21c \uc9d1\ud569\uc774\uba74 \\(\\Gamma\\)\uc758 \ubaa8\ub4e0 \ub17c\ub9ac\uc2dd\uc744 \ucc38\uc73c\ub85c \ub9cc\ub4dc\ub294 \uac12\ub9e4\uae40\uc774 \uc874\uc7ac\ud55c\ub2e4.<\/p>\n<\/div>\n

\n

\uc99d\uba85<\/span>
\n\uba85\uc81c\ubcc0\uc218\uc5d0 \ub300\ud558\uc5ec
\n\\[
\nv(p_i)=\\mathrm T
\n\\quad\\Longleftrightarrow\\quad
\np_i\\in\\Gamma
\n\\]
\n\ub77c\uace0 \uc815\uc758\ud558\uace0, \uc774\ub97c \ubaa8\ub4e0 \ub17c\ub9ac\uc2dd\uc73c\ub85c \uc7ac\uadc0\uc801\uc73c\ub85c \ud655\uc7a5\ud55c\ub2e4.<\/p>\n

\uadf9\ub300 \ubb34\ubaa8\uc21c\uc131\uc73c\ub85c\ubd80\ud130 \uc784\uc758\uc758 \\(\\chi\\)\uc5d0 \ub300\ud558\uc5ec \\(\\chi\\)\uc640 \\(\\neg\\chi\\) \uc911 \uc815\ud655\ud788 \ud558\ub098\uac00 \\(\\Gamma\\)\uc5d0 \uc18d\ud55c\ub2e4. \ub610\ud55c \\(\\Gamma\\vdash\\chi\\)\uc774\uba74 \\(\\chi\\in\\Gamma\\)\uc774\ub2e4. \uc2e4\uc81c\ub85c \\(\\chi\\notin\\Gamma\\)\uc774\uba74 \\(\\neg\\chi\\in\\Gamma\\)\uc774\ubbc0\ub85c \\(\\Gamma\\)\uac00 \ubaa8\uc21c\uc801\uc774 \ub41c\ub2e4.<\/p>\n

\ub530\ub77c\uc11c MP\uc5d0 \ub300\ud55c \ub2eb\ud798\uacfc \uc55e\uc5d0\uc11c \uc99d\uba85\ud55c
\n\\[
\n\\vdash\\neg\\phi\\to(\\phi\\to\\psi)
\n\\]
\n\ubc0f (A1)\uc744 \uc774\uc6a9\ud558\uba74
\n\\[
\n(\\phi\\to\\psi)\\in\\Gamma
\n\\quad\\Longleftrightarrow\\quad
\n\\phi\\notin\\Gamma\\text{ \ub610\ub294 }\\psi\\in\\Gamma
\n\\]
\n\ub97c \uc5bb\ub294\ub2e4. \uc774\uc81c \ub17c\ub9ac\uc2dd\uc758 \uad6c\uc131\uc5d0 \ub300\ud55c \uadc0\ub0a9\ubc95\uc744 \uc0ac\uc6a9\ud558\uc5ec
\n\\[
\nv(\\chi)=\\mathrm T
\n\\quad\\Longleftrightarrow\\quad
\n\\chi\\in\\Gamma
\n\\]
\n\ub97c \uc99d\uba85\ud560 \uc218 \uc788\ub2e4. \ud2b9\ud788 \\(\\varSigma\\subseteq\\Gamma\\)\uc774\uba74 \\(v\\)\ub294 \\(\\varSigma\\)\uc758 \ubaa8\ud615\uc774\ub2e4.<\/span><\/p>\n<\/div>\n

\n

\uc815\ub9ac 13.5. (\ubb34\ubaa8\uc21c\uc131\uacfc \ub9cc\uc871 \uac00\ub2a5\uc131)<\/span><\/p>\n

\ub17c\ub9ac\uc2dd \uc9d1\ud569 \\(\\varSigma\\)\uac00 \ubb34\ubaa8\uc21c\uc77c \ud544\uc694\ucda9\ubd84\uc870\uac74\uc740 \\(\\varSigma\\)\uac00 \ub9cc\uc871 \uac00\ub2a5\ud55c \uac83\uc774\ub2e4.<\/p>\n<\/div>\n

\n

\uc99d\uba85<\/span>
\n\ub9cc\uc871 \uac00\ub2a5\ud558\uba74 \uac74\uc804\uc131 \uc815\ub9ac\uc5d0 \uc758\ud558\uc5ec \ubb34\ubaa8\uc21c\uc774\ub2e4. \ubc18\ub300\ub85c \ubb34\ubaa8\uc21c\uc774\uba74 \ubcf4\uc870\uc815\ub9ac 13.3\uc5d0 \uc758\ud558\uc5ec \uadf9\ub300 \ubb34\ubaa8\uc21c \ud655\uc7a5 \\(\\Gamma\\)\ub97c \uc5bb\uace0, \ubcf4\uc870\uc815\ub9ac 13.4\uc5d0 \uc758\ud558\uc5ec \\(\\Gamma\\), \ub530\ub77c\uc11c \\(\\varSigma\\)\uc758 \ubaa8\ud615\uc744 \uc5bb\ub294\ub2e4.<\/span><\/p>\n<\/div>\n

\n

\ubb38\uc81c 13.1.<\/span>
\n\ub2e4\uc74c \ub17c\ub9ac\uc2dd \uc9d1\ud569\uc774 \ub9cc\uc871 \uac00\ub2a5\ud55c\uc9c0 \ud310\uc815\ud558\uc2dc\uc624. \ub9cc\uc871 \uac00\ub2a5\ud558\uba74 \ubaa8\ud615\uc744 \ud558\ub098 \uc81c\uc2dc\ud558\uace0, \ub9cc\uc871 \uac00\ub2a5\ud558\uc9c0 \uc54a\uc73c\uba74 \uadf8 \uc774\uc720\ub97c \uc124\uba85\ud558\uc2dc\uc624. \uc815\ub9ac 13.5\uc5d0 \uc758\ud558\uc5ec \uac01 \uc9d1\ud569\uc774 \ubb34\ubaa8\uc21c\uc778\uc9c0\ub3c4 \ud568\uaed8 \ud310\uc815\ud558\uc2dc\uc624.<\/p>\n

    \n
  1. \\(\\Gamma_1=\\{p,p\\to q,\\neg q\\}\\).<\/li>\n
  2. \\(\\Gamma_2=\\{p\\to q,\\neg p\\}\\).<\/li>\n
  3. \\(\\Gamma_3=\\{p\\vee q,\\neg p,\\neg q\\}\\).<\/li>\n<\/ol>\n<\/div>\n
    \n

    \uc815\ub9ac 13.6. (\uc644\uc804\uc131 \uc815\ub9ac)<\/span><\/p>\n

    \uc784\uc758\uc758 \ub17c\ub9ac\uc2dd \uc9d1\ud569 \\(\\varSigma\\)\uc640 \ub17c\ub9ac\uc2dd \\(\\phi\\)\uc5d0 \ub300\ud558\uc5ec
    \n\\[
    \n\\varSigma\\models\\phi
    \n\\quad\\Longrightarrow\\quad
    \n\\varSigma\\vdash\\phi
    \n\\]
    \n\uc774\ub2e4.<\/p>\n<\/div>\n

    \n

    \uc99d\uba85<\/span>
    \n\ub300\uc6b0\ub97c \ubcf4\uc778\ub2e4. \\(\\varSigma\\nvdash\\phi\\)\ub77c\uace0 \ud558\uc790. \ub9cc\uc57d \\(\\varSigma\\cup\\{\\neg\\phi\\}\\)\uac00 \ubaa8\uc21c\uc801\uc774\uba74 \ubcf4\uc870\uc815\ub9ac 13.3\uc758 \uc99d\uba85\uc5d0\uc11c \uc0ac\uc6a9\ud55c \ub3d9\uce58\uc5d0 \uc758\ud558\uc5ec \\(\\varSigma\\vdash\\neg\\neg\\phi\\)\uc774\uace0, \uc774\uc911\ubd80\uc815 \uc81c\uac70\uc5d0 \uc758\ud558\uc5ec \\(\\varSigma\\vdash\\phi\\)\uac00 \ub418\uc5b4 \ubaa8\uc21c\uc774\ub2e4. \ub530\ub77c\uc11c \\(\\varSigma\\cup\\{\\neg\\phi\\}\\)\ub294 \ubb34\ubaa8\uc21c\uc774\uace0, \uc815\ub9ac 13.5\uc5d0 \uc758\ud558\uc5ec \uc774 \uc9d1\ud569\uc758 \ubaa8\ud615 \\(v\\)\uac00 \uc874\uc7ac\ud55c\ub2e4. \uadf8\ub7ec\uba74 \\(v\\)\ub294 \\(\\varSigma\\)\uc758 \ubaa8\ub4e0 \ub17c\ub9ac\uc2dd\uc744 \ucc38\uc73c\ub85c \ub9cc\ub4e4\uc9c0\ub9cc \\(v(\\phi)=\\mathrm F\\)\uc774\ubbc0\ub85c \\(\\varSigma\\not\\models\\phi\\)\uc774\ub2e4.<\/span><\/p>\n<\/div>\n

    \uba85\uc81c\ub17c\ub9ac\uc758 \uac74\uc804\uc131\uacfc \uc644\uc804\uc131\uc744 \uacb0\ud569\ud558\uba74 \ub2e4\uc74c\uc744 \uc5bb\ub294\ub2e4.
    \n\\[
    \n\\varSigma\\models\\phi
    \n\\quad\\Longleftrightarrow\\quad
    \n\\varSigma\\vdash\\phi
    \n\\]
    \n\ud2b9\ud788 \ub17c\ub9ac\uc2dd \\(\\phi\\)\uac00 \ud56d\uc9c4\uc77c \ud544\uc694\ucda9\ubd84\uc870\uac74\uc740 \\(\\vdash\\phi\\)\uc778 \uac83\uc774\ub2e4.<\/p>\n

    \n

    \ubb38\uc81c 13.2.<\/span>
    \n\uac74\uc804\uc131\uacfc \uc644\uc804\uc131\uc744 \uc774\uc6a9\ud558\uc5ec \ub2e4\uc74c\uc744 \ubcf4\uc774\uc2dc\uc624.<\/p>\n

      \n
    1. \\(\\vdash p\\to p\\)\ub77c\ub294 \uc0ac\uc2e4\ub9cc\uc73c\ub85c \\(p\\to p\\)\uac00 \ud56d\uc9c4\uc784\uc744 \uacb0\ub860\ub0bc \uc218 \uc788\ub294 \uc774\uc720\ub97c \uc124\uba85\ud558\uc2dc\uc624.<\/li>\n
    2. \uc9c4\ub9ac\ud45c\ub85c \\((p\\wedge q)\\to p\\)\uac00 \ud56d\uc9c4\uc784\uc744 \ud655\uc778\ud558\uace0, \uc644\uc804\uc131 \uc815\ub9ac\ub97c \uc0ac\uc6a9\ud558\uc5ec
      \n\\[
      \n\\vdash (p\\wedge q)\\to p
      \n\\]
      \n\uc784\uc744 \uacb0\ub860\ub0b4\ub9ac\uc2dc\uc624.<\/li>\n
    3. \\(\\varSigma\\nvdash\\phi\\)\uc774\uba74 \\(\\varSigma\\)\uc758 \ubaa8\ub4e0 \ub17c\ub9ac\uc2dd\uc744 \ucc38\uc73c\ub85c \ub9cc\ub4e4\uba74\uc11c \\(\\phi\\)\ub97c \uac70\uc9d3\uc73c\ub85c \ub9cc\ub4dc\ub294 \uac12\ub9e4\uae40\uc774 \uc874\uc7ac\ud568\uc744 \uc124\uba85\ud558\uc2dc\uc624.<\/li>\n<\/ol>\n<\/div>\n
      \n

      \ubb38\uc81c 13.3.<\/span>
      \n\ud615\uc2dd\uacc4\uc758 \ubb34\ubaa8\uc21c\uc131\uc5d0 \ub300\ud558\uc5ec \ub2e4\uc74c\uc744 \ub2f5\ud558\uc2dc\uc624.<\/p>\n

        \n
      1. MU-\uacc4\uc5d0\ub294 \ubd80\uc815\uae30\ud638\uac00 \uc5c6\ub2e4. \ub530\ub77c\uc11c \uc815\uc758 13.1\uc744 \uadf8\ub300\ub85c \uc801\uc6a9\ud560 \uc218 \uc5c6\ub2e4. \uc774 \uacbd\uc6b0 \ud615\uc2dd\uacc4\uac00 \ube44\uc790\uba85\ud558\ub2e4\ub294 \uc870\uac74\uc744 \uc5b4\ub5bb\uac8c \uc815\uc758\ud560 \uc218 \uc788\ub294\uc9c0 \uc124\uba85\ud558\uc2dc\uc624.<\/li>\n
      2. \ubaa8\ub4e0 \ub17c\ub9ac\uc2dd\uc774 \uc815\ub9ac\uac00 \ub418\ub294 \ud615\uc2dd\uacc4\ub294 \ubd80\uc815\uae30\ud638\uac00 \uc788\ub294 \uacbd\uc6b0 \ubb34\ubaa8\uc21c\uc77c \uc218 \uc788\ub294\uac00?<\/li>\n
      3. \uacf5\ub9ac\uac00 \uc5c6\ub294 \ud615\uc2dd\uacc4\uac00 \ubc18\ub4dc\uc2dc \ubb34\ubaa8\uc21c\uc778\uc9c0 \ub17c\ud558\uc2dc\uc624. \uc5ec\uae30\uc11c\ub294 \uc804\uc81c\uac00 0\uac1c\uc778 \ucd94\ub860\uaddc\uce59\ub3c4 \ud5c8\uc6a9\ud55c\ub2e4\uace0 \ud558\uc790.<\/li>\n<\/ol>\n<\/div>\n

        2. \uba85\uc81c\ub17c\ub9ac\uc758 \ucf64\ud329\ud2b8\uc131<\/h3>\n
        \n

        \uc815\ub9ac 13.7. (\uba85\uc81c\ub17c\ub9ac\uc758 \ucf64\ud329\ud2b8\uc131)<\/span><\/p>\n

        \ub17c\ub9ac\uc2dd\uc758 \uc9d1\ud569 \\(\\varSigma\\)\uc5d0 \ub300\ud558\uc5ec \ub2e4\uc74c \ub450 \uc870\uac74\uc740 \ub3d9\uce58\uc774\ub2e4.<\/p>\n

          \n
        1. \\(\\varSigma\\)\ub294 \ub9cc\uc871 \uac00\ub2a5\ud558\ub2e4.<\/li>\n
        2. \\(\\varSigma\\)\uc758 \ubaa8\ub4e0 \uc720\ud55c\ubd80\ubd84\uc9d1\ud569\uc740 \ub9cc\uc871 \uac00\ub2a5\ud558\ub2e4.<\/li>\n<\/ol>\n<\/div>\n
          \n

          \uc99d\uba85<\/span>
          \n(1)\uc5d0\uc11c (2)\ub294 \uc790\uba85\ud558\ub2e4. \ubc18\ub300\ub85c \\(\\varSigma\\)\uc758 \ubaa8\ub4e0 \uc720\ud55c\ubd80\ubd84\uc9d1\ud569\uc774 \ub9cc\uc871 \uac00\ub2a5\ud558\ub2e4\uace0 \ud558\uc790. \ub9cc\uc57d \\(\\varSigma\\)\uac00 \ub9cc\uc871 \uac00\ub2a5\ud558\uc9c0 \uc54a\uc73c\uba74 \uc815\ub9ac 13.5\uc5d0 \uc758\ud558\uc5ec \\(\\varSigma\\)\ub294 \ubaa8\uc21c\uc801\uc774\ub2e4. \ub530\ub77c\uc11c \uc5b4\ub5a4 \\(\\psi\\)\uc5d0 \ub300\ud558\uc5ec \\(\\varSigma\\vdash\\psi\\)\uc640 \\(\\varSigma\\vdash\\neg\\psi\\)\uc778 \ub450 \uc720\ud55c\ud55c \uc99d\uba85\uc774 \uc874\uc7ac\ud55c\ub2e4. \uc774 \ub450 \uc99d\uba85\uc5d0\uc11c \uc2e4\uc81c\ub85c \uc0ac\uc6a9\ub41c \uac00\uc815\uc740 \uc720\ud55c \uac1c\ubfd0\uc774\ubbc0\ub85c, \uadf8 \uac00\uc815\ub4e4\uc744 \ubaa8\ub450 \ud3ec\ud568\ud558\ub294 \uc720\ud55c\ubd80\ubd84\uc9d1\ud569 \\(\\varSigma_0\\subseteq\\varSigma\\)\uac00 \uc874\uc7ac\ud558\uc5ec \\(\\varSigma_0\\)\ub3c4 \ubaa8\uc21c\uc801\uc774\ub2e4. \uac74\uc804\uc131 \uc815\ub9ac\uc5d0 \uc758\ud558\uc5ec \\(\\varSigma_0\\)\ub294 \ub9cc\uc871 \uac00\ub2a5\ud558\uc9c0 \uc54a\ub2e4. \uc774\ub294 \uac00\uc815\uc5d0 \ubaa8\uc21c\uc774\ub2e4.<\/span><\/p>\n<\/div>\n

          \ub530\ub77c\uc11c \uc758\ubbf8\ub860\uc801 \uadc0\uacb0\ub3c4 \uc720\ud55c\ud55c \ubd80\ubd84\uc5d0 \uc758\ud558\uc5ec \uacb0\uc815\ub41c\ub2e4. \uc989,
          \n\\[
          \n\\varSigma\\models\\phi
          \n\\]
          \n\uc774\uba74 \uc5b4\ub5a4 \uc720\ud55c\ubd80\ubd84\uc9d1\ud569 \\(\\varSigma_0\\subseteq\\varSigma\\)\uac00 \uc874\uc7ac\ud558\uc5ec \\(\\varSigma_0\\models\\phi\\)\uc774\ub2e4.<\/p>\n

          \n

          \ubb38\uc81c 13.4.<\/span>
          \n\\[
          \n\\varSigma=\\left\\{p_0\\right\\}\\cup\\{p_n\\to p_{n+1}\\mid n\\in\\mathbb N\\}
          \n\\]
          \n\uc774\ub77c\uace0 \ud558\uc790.<\/p>\n

            \n
          1. \uc784\uc758\uc758 \\(k\\in\\mathbb N\\)\uc5d0 \ub300\ud558\uc5ec \\(\\varSigma\\models p_k\\)\uc784\uc744 \ubcf4\uc774\uc2dc\uc624.<\/li>\n
          2. \uc8fc\uc5b4\uc9c4 \\(k\\)\uc5d0 \ub300\ud558\uc5ec \\(p_k\\)\ub97c \ub17c\ub9ac\uc801 \uadc0\uacb0\ub85c \uac00\uc9c0\ub294 \uc720\ud55c\ubd80\ubd84\uc9d1\ud569 \\(\\varSigma_k\\subseteq\\varSigma\\)\ub97c \ud558\ub098 \uad6c\uccb4\uc801\uc73c\ub85c \uc81c\uc2dc\ud558\uc2dc\uc624.<\/li>\n
          3. \ud2b9\ud788 \\(p_5\\)\uc5d0 \ub300\ud558\uc5ec \ud544\uc694\ud55c \uac00\uc815\ub9cc\uc744 \ubaa8\ub450 \uc4f0\uc2dc\uc624. \uc774 \uc608\uac00 \uc704\uc758 \uc720\ud55c\uc131 \uacb0\ub860\uacfc \uc5b4\ub5bb\uac8c \uc5f0\uacb0\ub418\ub294\uc9c0 \uc124\uba85\ud558\uc2dc\uc624.<\/li>\n<\/ol>\n<\/div>\n

            3. \ucf64\ud329\ud2b8\uc131\uc758 \uc751\uc6a9: \uc0ac\uc0c9 \uc815\ub9ac\uc758 \uac00\uc0b0 \ubb34\ud55c \ud655\uc7a5<\/h3>\n

            \ub2e4\uc74c\uc740 \uc720\ud55c \ud3c9\uba74\uadf8\ub798\ud504\uc5d0 \ub300\ud55c \uc0ac\uc0c9 \uc815\ub9ac\uc774\ub2e4.<\/p>\n

            \n

            \uc815\ub9ac 13.8. (\uc720\ud55c \ud3c9\uba74\uadf8\ub798\ud504\uc758 \uc0ac\uc0c9 \uc815\ub9ac)<\/span><\/p>\n

            \ubaa8\ub4e0 \uc720\ud55c \ud3c9\uba74\uadf8\ub798\ud504\uc758 \uaf2d\uc9d3\uc810\uc740 \uc778\uc811\ud55c \ub450 \uaf2d\uc9d3\uc810\uc774 \uc11c\ub85c \ub2e4\ub978 \uc0c9\uc744 \uac16\ub3c4\ub85d \ub124 \uac00\uc9c0 \uc0c9\uc73c\ub85c \uce60\ud560 \uc218 \uc788\ub2e4.<\/p>\n<\/div>\n

            \uc774 \uc815\ub9ac\ub294 1976\ub144\uc5d0 \uc544\ud3a0\uacfc \ud558\ucf04\uc774 \ucef4\ud4e8\ud130\uc758 \ub3c4\uc6c0\uc744 \ubc1b\uc544 \ucc98\uc74c \uc99d\uba85\ud558\uc600\ub2e4. \uc5ec\uae30\uc11c\ub294 \uc774 \uacb0\uacfc \uc790\uccb4\ub294 \uc99d\uba85 \uc5c6\uc774 \uc0ac\uc6a9\ud558\uace0, \uba85\uc81c\ub17c\ub9ac\uc758 \ucf64\ud329\ud2b8\uc131\uc744 \uc0ac\uc6a9\ud558\uc5ec \ub2e4\uc74c\uacfc \uac19\uc774 \ud655\uc7a5\ub41c \uc815\ub9ac\ub97c \uc5bb\ub294\ub2e4.<\/p>\n

            \n

            \uc815\ub9ac 13.9. (\uac00\uc0b0 \ud3c9\uba74\uadf8\ub798\ud504\uc758 \uc0ac\uc0c9 \uc815\ub9ac)<\/span><\/p>\n

            \uaf2d\uc9d3\uc810 \uc9d1\ud569\uc774 \uac00\uc0b0\uc778 \ubaa8\ub4e0 \ud3c9\uba74\uadf8\ub798\ud504\ub294 \ub124 \uac00\uc9c0 \uc0c9\uc73c\ub85c \uc62c\ubc14\ub974\uac8c \uaf2d\uc9d3\uc810 \ucc44\uc0c9\ud560 \uc218 \uc788\ub2e4.<\/p>\n<\/div>\n

            \n

            \uc99d\uba85<\/span>
            \n\ud3c9\uba74\uadf8\ub798\ud504\ub97c \\(G=(V,E)\\)\ub77c \ud558\uc790. \\(V\\)\uac00 \uac00\uc0b0\uc774\ubbc0\ub85c \uac01 \\(a\\in V\\)\uc640 \uc0c9 \\(c\\in\\{1,2,3,4\\}\\)\uc5d0 \uba85\uc81c\ubcc0\uc218 \\(p_{a,c}\\)\ub97c \ub300\uc751\uc2dc\ud0ac \uc218 \uc788\ub2e4. \\(p_{a,c}\\)\ub294 \u201c\uaf2d\uc9d3\uc810 \\(a\\)\uc758 \uc0c9\uc774 \\(c\\)\uc774\ub2e4\u201d\ub77c\ub294 \ub73b\uc73c\ub85c \uc0dd\uac01\ud55c\ub2e4.<\/p>\n

            \ub2e4\uc74c \ub17c\ub9ac\uc2dd\ub4e4\uc744 \ubaa8\uc544 \uc9d1\ud569 \\(\\varSigma\\)\ub97c \ub9cc\ub4e0\ub2e4.<\/p>\n