Логіка
Аркадзь Бабко
Памер: 184с.
Мінск 2017
A A А| A
п X X
X п п
Разгледзім наступны выпадак, у якім праз антыкан’юнкцыю спалучаюцца дзве ідэнтычныя антыкан’юнкцыі: (A | В) | ( A | В). Мы ведаем ужо, што антыкан’юнкцыя выказванняў A і В з’яўляецца хібнай толькі ў першым радку табліцы. Значыцца, антыкан’юнкцыя такіх антыкан’юнкцый можа быць праўдзівай у гэтым і толькі ў гэтым радку, што супадае, відавочна, з умовай праўдзівасці кан’юнкцыі. Таму A | В <=> A A В, пра што сведчыць і іх супольная табліца праўдзівасці:
122
A в A A В А|В (А | В) | (А | В)
п п П X П
п X X 11 X
X п X п X
X X X п X
I, завяршаючы разгляд антыкан'юнкцыі, звернем увагу на выказванне, якое ўяўляе сабой антыкан’юнкцыю дзвюх антыкан’юнкцый, кожная з якіх утворана праз спалучэнне свайго кампанента з самім сабой: (A | A) | (В | В). Відавочна, што выказванне A | A з’яўляецца хібным у тых радках табліцы, дзе А мае праўдзівае лагічнае значэнне, гэта значыць у першых двух. Выказванне В | В адпаведна выступае як хібнае там, дзе праўдзівае В, гэта значыць у першым і трэцім. Значыцца, выніковая антыкан’юнкцыя з’яўляецца праўдзівай у першых трох радках і хібнай у чацвёртым, што мае месца ў выпадку нястрогай дыз’юнкцыі. Таму (A | А) | (В | В) <=> A v В, што пацвярджаецца і адпаведнай табліцай праўдзівасці:
A в AvB А | A в|в (А | А) | (В | В)
п п П X X П
п X п X п п
X п п п X п
X X X п п X
Разгледжаных прыкладаў дастаткова, каб упэўніцца, што мноства лагічных злучнікаў, у якое ўваходзіць толькі антыкан'юнкцыя, выступае як адэкватнае.
Мінімізацыя адэкватнага мноства лагічных злучнікаў: антыдыз ’юнкцыя
У нас няма ніякіх падстаў лічыць разгледжаныя вышэй уласцівасці антыкан’юнкцыі ўнікальнымі. Калі злучнік, што грунтуецца
123
на спалучэнні кан’юнкцыі і адмаўлення, дазваляе перадаць усе функцыянальныя залежнасці, што аналізуюцца ў рамках логікі выказванняў, дык цалкам заканамерна паўстае думка пра аналагічныя здольнасці злучніка, у якім спалучаецца нястрогая дыз’юнкцыя і адмаўленне. Мы будзем называць яго антыдыз’юнкцыяй і абазначаць |. A | В гэта фармальны запіс утворанага пры дапамозе антыдыз’юнкцыі выказвання, табліца праўдзівасці якога супадае, натуральна, з табліцай праўдзівасці адмоўленай нястрогай дыз’юнкцыі:
A в A v В (A v В) A 1 В
п п п X X
п X п X X
X п п X X
X X X п п
Такім чынам, антыдыз’юнкцыя гэта лагічны злучнік, пры дапамозе якога атрымліваецца складанае выказванне, праўдзівае пры ўмове хібнасці ўсіх яго кампанентаў. (Для дадзенага лагічнага злучніка, як і для яго папярэдніка, у англасаксонскім культурным асяродку існуюць сінанімічныя назвы nor, што выступае як скарот для notor, і joint denial, у чым знаходзіць адбітак той факт, што ўтвораны пры яго дапамозе складаны выраз з’яўляецца праўдзівым толькі пры ўмове хібнасці ўсіх яго кампанентаў [24, с. 44].)
Як і выпадку антыкан’юнкцыі, мы разгледзім спачатку найпрасцейшае складанае выказванне, што атрымліваецца з дапамогай дадзенага злучніка A I А. Відавочна, што як і найпрасцейшая антыкан’юнкцыя (A | А) антыдыз’юнкцыя A | А выступае як праўдзівая ў выпадку хібнасці А і як хібная у выпадку яго праўдзівасці. Умова праўдзівасці такога выказвання супадае з умовай праўдзівасці адмоўленага A (■ А). Таму A | A <=> ~' A.
Унутраная ўзаемасувязь кан’юнкцыі і нястрогай дыз’юнкцыі, пэўная сіметрыя, што мае месца ў дачыненнях паміж імі, выяўляецца і ў стасунках антыдыз'юнкцыі і антыкан’юнкцыі. Так,
124
схема выбудоўвання эквівалентнага кан’юнкцыі складанага выказвання, у якім задзейнічана антыдыз’юнкцыя, (A | А) | (В | В) ідэнтычная той, што выступае як аснова для канструявання эквівалента дыз'юнкцыі пры дапамозе антыкан’юнкцыі (А | А) | (В | В). Праверым, аднак, пры дапамозе табліцы праўдзівасці, ці сапраўды выказванне (A | A) j, (В j В) раўназначна кан’юнкцыі выказванняў A і В:
A в A A В A 1 A В 1 в (A 1 AM (B 1 В)
п п П X X п
п X X X п X
X п X п X X
X X X п п X
Выказванне (A J, A) j (В | В), як і кан’юнкцыя A A В, мае праўдзівае лагічнае значэнне толькі ў першым радку табліцы, паколькі толькі ў гэтым радку адначасова хібнымі з’яўляюцца яго кампаненты (A | A) і (В j В). Таму (A j, A) j (В j В) <=> A A В.
Аналагічную сітуацыю мы маем і ў выпадку з перадачай функцыянальнай залежнасці, што фіксуецца нястрогай дыз’юнкцыяй, на аснове антыдыз’юнкцыі: яе схема ((A | В) | (A | В)) супадае са схемай выбудоўвання пры дапамозе антыкан’юнкцыі выказвання, эквівалентнага кан’юнкцыі ((A | В) | (A | В)). Прааналізуем суадносіны выказванняў (A | В) | (A j В) і A v В на аснове іх супольнай табліцы праўдзівасці:
A в A v В A 1 В (АІВН(АІВ)
п п П X п
п X п X п
X п п X п
X X X п X
125
Для хібнасці антыдыз’юнкцыі A j В дастаткова праўдзівасці, прынамсі, аднаго яе кампанента. Дадзеная ўмова выконваецца ў трох першых радках табліцы, і ў іх выказванне А| В з’яўляецца, натуральна, хібным. Але яно паўтараецца ў выніковай антыдыз’юнкцыі ў якасці антыдыз’юнкта, і таму ў кожным з гэтых радкоў выконваецца ўмова праўдзівасці антыдыз’юнкцыі. Умова яе хібнасці выковаецца толькі ў чацвёртым радку, што мае месца, як мы ведаем, і ў выпадку выказвання, утворанага пры дапамозе нястрогай дыз’юнкцыі. Значыцца, (A j В) | (А | В) <=> A v В. Праведзены намі аналіз дазваляе, такім чынам, зрабіць выснову аб адэкватнасці мноства лагічных злучнікаў, якое змяшчае ў сабе толькі антыдыз’юнкцыю.
Нармальныя формы: дыз ’юнктыўная нармальная форма
Неабходна адзначыць, што ўніфікацыя і стандартызацыя запісу выразаў у абсягу логікі выказванняў не з’яўляецца самамэтай; не заўжды ёсць неабходнасць у такой радыкальнай рэдукцыі сістэмы лагічных злучнікаў, да якой мы прыйшлі ў выніку нашага аналізу. Акрамя таго, у логіцы выпрацаваны і больш памяркоўныя формы згаданай стандартызацыі. Так, пры запісе выказванняў у нармальных формах задзейнічаны тры лагічныя злучнікі: кан’юнкцыя, нястрогая дыз’юнкцыя і адмаўленне. Гэты запіс грунтуецца на аналізе адпаведных табліц праўдзівасці, бо для паспяховага правядзення дадзенай працэдуры надзвычай важна выявіць, пры якіх размеркаваннях лагічных значэнняў сваіх кампанентаў выказванні, што праз яе праходзяць, выступаюць як праўдзівыя і пры якіх як хібныя.
Калі, напрыклад, мы маем на мэце запісаць пэўнае выказванне ў дыз’юнктыўнай нармальнай форме, мы павінны зыходзіць з радкоў табліцы, дзе яно мае праўдзівае лагічнае значэнне. (Таму ўмовай запісу з’яўляецца наяўнасць прынамсі аднаго радка ў табліцы праўдзівасці дадзенага выказвання, дзе яно выступае як праўдзівае, гэта значыць яго формула не павінна быць супярэчнасцю.) Кожны з такіх радкоў можа быць запісаны ў выглядзе кан’юкцыі наяўных у ім зменных са знакам адмаўлення, калі зменная павінна абазначаць выраз з хібным лагічным значэннем (хібнасць зыходнага выказвання азначае праўдзівасць яго адмаў
126
лення), і без яго, калі адпаведны выраз мусіць быць праўдзівым. Дыз’юнкцыя такіх кан’юнкцый з’яўляецца лагічным эквівалентам выказвання, на аснове якога яна атрымана: ва ўсіх радках табліцы, у якіх яно мае праўдзівае лагічнае значэнне, праўдзівая і адпаведная дыз’юнкцыя. Сапраўды, кожны з яе кан’юнктыўных кампанентаў з’яўляецца праўдзівым у пэўным з такіх радкоў, паколькі ўсе кан’юнкты выступаюць у гэтым (і толькі ў гэтым) радку як праўдзівыя. Ва ўсіх іншых радках (у якіх зыходнае выказванне мае хібнае лагічнае значэнне) дадзеная дыз’юнкцыя хібная, бо адпаведныя размеркаванні лагічных значэнняў зменных абумоўліваюць хібнасць усіх кан’юнктыўных кампанентаў: яны не могуць быць праўдзівымі больш чым у адным радку. Відавочна, што любое складанае выказванне, калі не з’яўляецца супярэчнасцю, мае ў якасці эквівалента такую дыз’юнкцыю, якая і завецца ў логіцы дыз’юнктыўнай нармальнай формай (ДНФ). Атрымаць яе на аснове табліцы праўдзівасці пэўнага выказвання значыць запісаць яго ў дыз’юнктыўнай нармальнай форме.
Разгледзім дадзеную працэдуру на канкрэтным прыкладзе. Няхай нам патрэбна знайсці ДНФ наступнай імплікацыі: ДА A В) —► " С. Спачатку мы павінны скласці табліцу яе праўдзівасці:
A в с ААВ (A A В) с (A A В) — С
п п п п X X П
п п X п X п п
п X п X п X X
п X X X п п п
X п п X п X X
X п X X п п п
X X п X п X X
X X X X п п п
127
Наступны крок гэта вызначэнне тых радкоў, дзе дадзеная імплікацыя праўдзівая (яны вылучаны ў нашай табліцы). Затым мы вызначаем, якое лагічнае значэнне маюць у іх зменныя, і, зважаючы на гэта, спалучаем іх ці іх адмаўленні ў кан’юнкцыі, кожная з якіх перадае, такім чынам, пэўны радок табліцы з праўдзівым выніковым лагічным значэннем: A A В A С; A A В A ^ C; A A В A ’ С\ ’ A A В A ~ С; ~ A A ^ В A ^ С. Спалучыўшы іх праз дыз’юнкцыю, мы атрымаем ДНФ: (A A В A С) v (A A В A ■ С) v (A A В A С) v ( A A В A С) v ( A A В A С). Такім чынам, ДНФ ( (A A В) * С) = (A A В A С) v (A A В A С) v (A A B A C) v ( A A B A C) v ( A A B A C).
У тым выпадку, калі формула з’яўляецца супярэчнасцю, у якасці яе дыз’юнктыўнай нармальнай формы фігуруе выказванне A A ^ А: яно выступае як канцэнтраванае лагічнае выяўленне ўсякай супярэчнасці і з’яўляецца раўназначным у дачыненні да любой супярэчлівай формулы.
Кан ’юнктыўная нармальная форма (КНФ)
Другая разнавіднасць нармальнай формы, якую мы разгледзім, называецца кан’юнктыўнай. Для таго каб запісаць у ёй пэўнае выказванне X, мы павінны засяродзіцца на тых радках табліцы, дзе яно мае хібнае лагічнае значэнне. Відавочна, што ў гэтых радках праўдзівым з’яўляецца яго адмаўленне ■ X. Запісаўшы ў дыз’юнктыўнай нармальнай форме, мы атрымаем яго лагічны эквівалент: ’ X <=> ДНФ (^ X). Але адмаўленні эквівалентных выразаў, як мы ўжо ведаем, таксама з’яўляюцца эквівалентнымі. Таму • ’ X <=> ’ ДНФ (' X) і пасля выдалення падвойнага адмаўлення X <=> ^ ДНФ (^ X). Але ДНФ (~■ X) пэўнае дыз’юнктыўнае выказванне, a • ДНФ (^ X) яго адмаўленне. Паводле законаў А. Дэ Моргана адмаўленне дыз’юнкцыі раўназначна кан’юнкцыі адмаўленняў. Трансфармаваўшы ■ ДНФ (■ X) згодна з гэтым законам, мы атрымаем кан’юнкцыю адмоўных кан’юнкцый. Цяпер неабходна выдаліць тыя адмаўленні, што стаяць перад дужкамі: у рамках нармальных форм дапускаецца толькі адмаўленне паасобных зменных. Пры вырашэнні гэтай задачы нам зноў патрэбна звярнуцца да законаў А. Дэ Моргана і пераўтварыць кожны кампанент атрыманага намі ў выніку
КНІГІ ОНЛАЙН
