Diskretka

Diskretka.doc20.02.2014

121

Таблицаистиннкон ости

ъюнкции

P

Q

P Q

И

И

И

И

Л

И

Л

И

И

Л

Л

Л

Вестественномязыкедизъюнкциясоответствуетвысказыванийдинениюсоюзом

«или»внеразделитсмысле.

льном

Рассмотримтеперьсложноевыс,котороеазываниеесте

ственномязыкевыражают,

например,фразой«

еслиР,то

Q» (или«

изРследует

Q», или«

Рвлечет Q»). Жизненный

опытодсказывает,чтоистиннэтогвысказываниядолжнастьобо

значатьследующее:

если Р истинно,

Q «обязано»бытьистин

нымследовать( изР);

есжеРложнои,тона

Q нетограниче ний,ономбытьжеткакист,такинным

ложнымиз(ложногоутвержденияничегонеследует).

Q» ложновединственслучае:Ристи, номно

Q ложно.

Значит,из«Рследует

Следующиевысказыванияслужатпримерами:

1) если0то=1 0,= 1;

2) если0то=0 1,

= 0;

Первоеутверждениеистинно

,таккак,используяравенст0другие=свойства0

чисел,можновывести1прибавляя= по1,единицекобеимчастямравенства0 = 0.

Второеутверждение

тожеестественносчитать

стинным,таккак,умнанульожая

обечастиравенства0получим= 1,0= 0.

Третьеприходится

считатьложным,таккакисходяиз

тинногоравенства0 = 0

помощьюумозаключенийникогданепридемложному.

Четвертое естественсчиститать.Прибавляннымо

якобе

имчастямравенства0 = 1

по1,получим1 = 2.

еслиР,то

Q» каклогичоперацию,опрскуюслд дующимлим

Используяоборот«

образом.

Определение5.

Импликацией

двухысказыванийР

Q

называетсявысказывание

ложнтогдаитолькотогдае,когдаР

истинно,

a Q ложно.

Импливысобознкациязывачаетсяний

Р => Q , или Р Q

ичитается: «

Рвлечет Q»,

или« еслиРто

Q», или«

изРследует

Q»,или«

пустьР,тогда

Q»,или«

Рявляется

достаточнымдля

Q», или «Q являетсянеобходимымдлР

».

Высказывание Р называется посылкой импликации,

a Q -заключением.

Табл4Табл. ицастицамнностипликацииэквивалентности

P Q

P ≈ Q

P

Q

И

И

И

И

И

Л

Л

Л

Л

И

И

Л

Л

Л

И

И

Определение6.

Эквивалентностью двухыс

казыванРий

Q называетсявысказывание,

истинногдатолько,когдаеистРинности

Q совпадают.Эквивалентностьобо

-

значается Р~

Q ичитается: «

Рэквивалентно

Q»,или«

Ртогдаитолькотогда,когда

Q»,

или« Рявляетсянеобходимымдоста

точным для Q».

Формулылогикивысказываний

Теперьперейдемкпонятиюформулылогикивысказываний.Средиспособовзадания

. Формулылогикивы

множестврассматривалсяпроцедур

ный,илирекурсивный

сказываний

образуютперечислиммножество,которзадаое

димрекурс

ивнымспособом.

Diskretka.doc20.02.2014

122

Определение7.

Алфавитом называетлюбоенепумножс.Элятоеэтогствоменты

множестваназываются

символами (букв)данноголфавитами.

Определение8.

Словом вданномалф зываетсявитепроизвольнаяконечная

последовательностьсимволов(

озможно,пустая).

Слово а называется подсловомслова

b, если b = b1 a b2 длянекоторыхслов

b1 и b2.

Всякоеподмножествословданногоалф зыввитается

языком вэтомалфавите.

Рассмотримязыклогикивысказываний,.е.подмсловожествоекоторм

формулами

выделенномалфавите.Словаязыкелогикивысказыванийпринятоназывать

логикивысказыва

ний. Этиформулыисподмоделированияьзуютсявысказы

ваний.

Определение9.

Пустьизвестно.

1.

Алфавитлогикивысказываний

содержитследующиесимволы:

высказывателъные

переменные Х1,Х 2, логическиесвязки

& , , ← ,

=>, ~;

символыскобок

(,которые),в

дальнейшембудутигратьразныероли.

атомарной.

2. Всякаявысказывательнпеременнаяестьформул,кото ая

раяназывается

3.

Если а — формула,то

( ← а) — формула.Если

а и b — формулы,то

(а&b), (а V b), (а

=> b), (а ~ b) — формулы.

4. Другихправилобразованияформулнет.

Замечание1.

Вместовысказывательныхпеременных

Х1,

Х. . .,

п, ...

иногдаудобно

пользоватьсяпрописнымилатинскимибуквамибезиндексов.

Пример 1. Слово ((( ← А)&В

=> (B А)) — формула.

Слово ( ← А&В)

=> В A неявляетсяформулойнет(скобок).

Слово ((А ← В)

=> (В

A )) — неформула,таккакзнак

← небинарнаясвязка.

Замечание 2. Удобнопризаписиф порумулопусчанию

катьвнешниескобки

скобкиприотрицаниивысказывательныхпере

менных,напрфорипримеразмула

1:

( ← А& В) => (В A ).

Определение 10. Логическиесвязкилогвысказыва

нийзадаюталгебраические

операциинамножестве

Ф всехвы

сказываний.

Отрицание — унарная алгебраическаяоперация,остачетырельныеогическиесвязки:

конъюнкц,дизъюн, мпликация,э в валентность

-

бинарные

алгебраические

операции.

Всвязиэтлогикавысказывам

ний — алгебраспятьюалгебраическимиоперациями

(Ф, &, V, =>, ~, ← ),котораяназывается

алгебройлогикивысказываний

.

Обсудим синтаксис,семантикупрагматику

языкалогикивысказываний.

Синтаксис языкалогикивысказыванийзучпр вильет

ностьнапиформулс(аниялов

языка),согласноопределениюформулылогикивыска

зываний.Нетпреудлножить

алгоритмотыскаошибоквслове,напримерия,указатьнасимволнеизалфавлогикита

выск,нотсутствиеазыванийнеобходи

могоилиприсутствиелишнегооперандалогической

операции,наотсутствиеилнесоответствиескобсл к

еит.д.

Семантика языкалогикивысказыванийзучаетсмыслфор

мулс(языкаов)сточки

зренияихоцениванаисти.Вопросынсемияностьчасрешаютсяикипомощью

таблицистин

ностиформул.

Прагматика языкалогикивысказыванийзучцели( дает

чи) использованиятехили

иныхформулязыка.Вопросыпраг

матикирешв функционированияютсямках

(назначения)ки

бернетичесинтеллексистем,в оихиспользууальныхорых

етсялогика

высказываний.

Diskretka.doc20.02.2014

123

Этиформулыназываются

равносильными,

есналюбойиоценкепеременныхони

принодинзначениям.ютковые

а и b логикивысказыванийбудемобозначать

a ≡ b,такжекак

Равносильностьформул

равносильностьформулэлемен

тарнойалгеб,например

a3 — b3 ≡( a - b)(a2 + ab + b ).

Пояснение.

Оцпенкаременных

— набористизнаностных

ченийданныхпеременных.

Равносильностьформулимеетсвойалгебраическийаналогтождественном

равенстве

алгебраическихвыражений.

Замечание. Нужноразличатьсимволы«

≡»и«

~».

Символ«~»

являетсясимволомлогическойоперацииформальногоязыкаэто(

необходимодостаточно).

Символ«

≡»

являетметасимволом.Оннепринадяалфавитуязыкаежитогики

высказыиговоритравносильанийсловточкизреихсемантикиияости.

Осноравносильности. ые

Длялюбыхформул

a, b, c справследравносильностиующиеливы.

1.

a&b=b&a (коммутативностьоперации

&).

2.

a & a = а (идемпотентностьоперации

&).

3.

а& ( b & с)

= (а& b)с&

(ассоциативностьоперации

&).

4.

а b = b а (коммутативностьоперации

).

5.

а а=а

(идемпотентностьоперации

).

6.

а (b с)

=а (

b) сассоциативность( операции

).

7.

a (b&с)

= (а b)&(a с)

(дистрибутивнос тьоперации отноперациисительно

&).

8.

a&(b с) =

(a&b) (а&с)

(дистрибутивностьоперации

& отноперациисительно

).

14.

а= ( a&b) (а&

← b ) (перваяформуларасще

пления).

15.

а = (a b)&(а

← b ) (втораяформуларасщепления).

Любизэтихраявносильнослегкоможетбытьдоказанапомощьютейаблиц

истинности.

Ещеоднагруппаравносильностейпоказывает,что

однисвяз

кимогутбытьвыражены

черездругие.

а~ b ≡ (а b)&(b а) ≡ ( a & b ) ( ← a & ← b ).

16.

Рассмотдоказательствоприравносильностейведенныхмнапримерахтождеств8, 10,

15Приэтомв. методическихцеляхприведемазличныхспособадоказательства.

a , b,с

a = А, b = B,с=С.

Пустьвтож

дествеформулы8

— атомарные,..

Таблицаистинравносильныхформулости

Т а б л и ц а 6

A B C B C A & (B C)

A & B A & C (A & B) (A & C)

И

И

И

И

И

И

И

И

И

И

Л

И

И

Л

И

И

И

Л

И

И

И

Л

И

И

И

Л

Л

Л

Л

Л

Л

Л

Л

И

И

И

Л

Л

Л

Л

Л

И

Л

И

Л

Л

Л

Л

Л

Л

И

И

Л

Л

Л

Л

Diskretka.doc20.02.2014

124

Л

Л

Л

Л

Л

Л

Л

Л

Рассмотримтабл. Пятый6.во тольмойвтабсовпадаютцылице,сл довательно,

табличным.

тождедоказано.Этотспособтво

казательстваравно

сильнназостивем

Теперьдокатождествоемвтор10закп (йглощения)пу

логическим.

темлогических

рассуждений.Этотспособназывается

Онимеетдваходарассуждения:слева«

—

направо»исправа«

— налево».

b) =Л .

Ходслева«

—направо».

Пустьвтождест

веслева10будет

ложь,

т.е.

а (а&

Тогдапоопределениюдизъюнкциибудет:

а = Л и (а&

b) = Л.Темсамымполучили,что

справатождестве10имеем

ложь:а=

Л.

. a = Л.Тогдадля

Ходсправа«

— налево».

Пустьвтождестбудет10справа

ложь,

т.е

левойчаститождества10имеем

ложь.

Всамомделе

(а&

b) =Л .Темсамым

а (а&

b) =Л .

Тождествополностьюдок10 .Разаноссматриватьотдельнослучай,когдаслева

истина нетнеобходимости

спрвдатождественномва

,таккакегод казательствоможно

провестирас

суждениемпротивногоиспользоваужедоказанного. ием

— истина,

истина,

На,пусримерслеватождествеь

тогдаиспра

вабудет

таккакв

противномслучае, липравабу

дет ложь,

то,подоказанному,сле

вабудет

ложь.

Аэто

противоречитпредположению.Аналогичнорассматриваетсяслучайсправа«

- налево».

Итак,влогическомспособедоказательстваравносильносдостаточнорассма ривать

одинслучай

— илидля

истины,

илидля

лжи, обязательновдвахода

:с« лева — направо»

испра«

ва— налево».

Теперьдокатождествоемвторая15формула(расщепле

ния)третьимспособом,

которыйназовем

алгебраическим.

Сутьспособасостоитвиспользовужедоказравандляосильностейииных

преобразованиялевойправойчастей

ождествакоднитомужевиду.

РассмотримправуючастьтождестваВосп15. жльзуемся

дествомкоторое7,

предоказанпола.Товынесемгдааемым

а заскобки,будемиметь

(a b)&(а

← b )≡а

( b & ← b )≡а

, таккак

( b & ← b )≡ Л.

Темсамымправаячастьтождествапреоб15 левуюравносильностьзована

доказана.

Рассмотримправила,помкоторыхудобнощьюпереходитьодних

равносильностейкдругим.

Теорема1

(правилоравнд сильныхбавленийудаленийформул).

Если а,

b ис

— произвформул,тследующиеьнравносильы выполняютсяости

невыполняютсяодновременно:

a ≡ b;

← a ≡ ← b;

a&с ≡ b&с;

с&a ≡с&b;

a с ≡ b с;с

a≡ c b;

a => с ≡ b => с;с=>

a ≡ с= b;

Доказательство.

a ~с ≡ b ~с;с~

a ≡ с~ b.

Рассмотримтабличныйметодпереборав

сехоценокформул.Надодля

восьмипочему( ?)случаевоценокфор

мул a, b,с

a =И,

b =И,с=И;

ит.д.

а =И,

b =И,с=Л;

а=Л;

b =Л,с=Л

Diskretka.doc20.02.2014

125

Теорема2

(правилоравнзаменперсильных

еменных).

Пусть а = b и с — формула,вкоторойвыделеноодновх перждеменнойние

X. Пусть

са получаетсяиз

с заменэтоговх йжде

ния X на а,а сb

из с заменойтогожевхождения

X на

b.Тогда cа ≡ cb.

Этутеоремудокажемметодоммате ати

ческойиндукциипочислу

п

Доказательство.

логичессвязокформулеих

с.

Для п = 0 формула с = X

(неимеетлогичессвязок)Тогда. их

са

=а

и сb = b.

Следо,утвтеоремыерждениеательвер. но

о п

Пустьтеоремавернадляформусчиссвязок,лнепреомы

восходящимнатуральног

> 0.

п + 1 логическаясвязка.Тогдафоримеетодинула

Рассмслучай,коимеетсятримгда

изпятивозможныхвидов

с = ← d, с= f g,с=

f&g,с=

( f => g),с

= (f ~g).Здесь

d, f, g —

формусчислогическихомы

связокнеболее

n,

длякотеоремаорыхспра

ведлива.

Заметим,что

са = ← da, cb = ← db или са = fa gа,с b = fb gb,или са = fa & ga,с b

= fb

gb или

т.д.Таккакдляформул

d, f, g теоремасправедлива,имеем

da ≡ db,

fa ≡ fb,

ga ≡gb. Тогдав

силупредыдущейтеоремыполучимто, ребдо.квазатьлось

Определение12.

Подформулой формулы с называетсялюбоеподслово

с, само

являющеесяформул

ой.

СледующиеправбездоказательведемлаНефедов[ В..Курсди твкретной

математика.

– М.Изд:

-воМАИ, 1992].

Теорема3

(правилоравнзаменподформулсильных).

Пусть са — формула,содержащая

а вкачествесвоейподформу

лы.Пусть

сb получается

из са заменой а вэтомвхождениина

b. Тогда,если

а ≡b, то са ≡cb,.

Теорема4

(правилоустраненимпликацийэкв явалентностей).

Длякаждойформулыможноуказатьравносиль

нуюейформулу,несодержащую

логическихсимволов

и~.

Правило переходакбулевымфункциям.

Нетруднопоказать,чтовсякаяформулалогикивысказможетбытьпредставленаваний

булевойфуинаоборот, кцией,всякаябу

левафункциясоответствуетнекоторойформуле

логикивыска

зываний.Дляэтогодостаточноперекодировать

(пе реоб)лозначитьгическое

истина

значениеистинностнойоценкиязыко

выхтекстследующимобразомв.Значение

обозначитьчислом1,значение

ложь числом0Далее.,всякуюатомар

нуюформулу

X, Y, ...

логикивысказываний,помкотощью

роймоделируемязык

овыйтекст,надооб значить

булперевой

менной х,у, ... Теперьвсякаяоценкаатомаформулыбудетсоответствоватьной

заданиюзначениябулп ременнойвой.Всякаяформулалогикивысказыванийбудет

соответствоватьсвоейбу

левойфункции.Приэтаблицаомис

тинностиформулыбудет

соответствоватьтабличзаданиюбулевойфункцииому,анал

тическоезаданиеформулы

аналитическзаданиюбулевойфункц.Л гмусвязкилогческиевысказыванийбудут

знакамиалгебраическоперацийнадбул выреиконмхенными

стантами.

Напри,форлогикимвысказыванийерула

Здесь X, Y обозначеночерез

х,у, знакконъюнкции&

— череззнак•,отрицания

← X —

через x .

Рассмотекслогтровуюзадачуическую.м

Нормальнформыформуллогикивысказыванийе

Опртенопдерлимформымальформул.Снзыеачала

метим,что,всилу

ассоциативностиопераций&

, какбынерасскобкитавляли

выражениях:

А1 &А

2 &А... & к; A1 A2 ... Ak (к> 3),

Diskretka.doc20.02.2014

126

всегбуприходитьемакравносильнымформулам.

Определение13.

Формулуназывают

элемеконтарнойъюнкцией

,

или конъюнктом,

если онаявляетсяконъюнк

ципейременныхилиихотрицаний.

& Х2.

Пример 3. Элемеконъюнкции:тарные

Х2& ← Х3;

Х1 & ← Х2 & Х4

Определение14.

Говорят,чтоф находитсярмулав

дизъюнктивнойнормальнойформе

(ДНФ),

еслионаявляетсядизъюнкциейэлемеко .тарнкцийых

(X1

&Х

2 & ← Х3)

(X1

& ← Х2 &Х 3). Этаформула

Пример 4.

Рассмотримформулу

находитсявДНФ.

Справедливаследующаятеорема,которую

ривбдоездем

казательства.

Теорема5.

Длялюбойформулы

а можнонайтитакуюформулу

b, находящуюсяв

ДНФ,

что а=

b. Вэтомслучаефор

мула b называется дизъюнктивнормальнойформой

формулы

а.

Определение15

. Пустьформула

а несодержитсимволов

=>, ~ .Формула а* называется

двойственной формуле а, еслионаполученаиз

а одноврзамесменнойехимволов

&,

наимдвойственные,..

& на ,

на &.

Определение16

. Говорят,чтоф рму

ла

а

находитсяв

конъюнктивнормальной

форме (КНФ),еслиформула

а* находитсявДНФ.

Сформулируембездоказательстваещеоднуважнуютеорему.

а можнонайтитакуюформулу

b, что b находитсяв

Теорема6.

Длялюбойформулы

КНФи

а = b.

Вэтомслучаеформу

ла b называется конъюнктивнонормальнойформой

формулы а.

Замечание4.

ДНФиКНФформулы

а, неявляютсяоднознач

ноопределенными.Кроме

ДНФиКНФввоещедругиеятсянормаль

ныеформы,например

совершенные

дизъюнктивныеконъюнктивнормальформыные

(С ДНФиСКНФ) [4,каки6, 10, 11],

длябулевыхфункцийсм(.подразд. 6.2).

Заклогикивыскны.Тавтологиизываний

Пустьформула

а зависит от множествапеременных

Х1, Х...,

n.

Определение17

. Формула а

называется тавтологией (илитождественно

-истинной

формулой),есналюбыхиоцен

кахспискапеременныхонаприз ачениеимает

И,т.е.

а≡И.

Здесьпод

оценкой спискапеременныхпонимаесопостсяавле

ниекаждойпеременной

этогосписканекоторогоистиз .ачеостнияого

Формула а называется выполнимой,

еслинанеко

торойоценкеспискапеременных

Х1,

...Х, п онапризначениеимает

И.Формула

а называется опровержимой,

еслинанекоторой

оценкеспискапеременных

Х1, Х..., п онапризначениеимает

Л.

Формула а называется тождественно-ложной, есналюбыхиоценкахсписка

переменных Х1, Х...,

п онапризначениеимаетЛ,..

а ≡ Л.

миследанныхствиями

Рассмонекотоу верим,являющыежденочевидныяеся

определений:

• а — тавттогдаитолькологиятогда,когда,

а неявляетсяопровержимой;

• а - тождественно-ложнатогдаитольк

отогда,когда

а неявляетсявыполнимой;

• а — тавттогдаитолькологиятогда,когда

← а тождественно-ложна;

• а — тождественно-ложнатогдаитолькотогда,когда

← а тавтология;

• а ~ b — тавттогдаитолькологиятог

да,когда а и b равносильны.

Сточкизрениялогикитавтология

— нечтоиное,как

логическиезаконы,

ибопри

любойподстановкевмеспеременавтонлогиивысказыванийкретныхполучим

истинноевыска

зывание.

ается проблемойразрешимости.

Основнаяпроблемалогикивыскназываний

Она

состоитввы,яснениивлпрояется

извольнаяформулатавтологией.Влогике

Diskretka.doc20.02.2014

127

высказыванийвсегдаестьвозможностьесть(алгоритм)решитьтакуюзадачу.Напри

мер,

решитьееможно:

(табличны й способ);

использованиемтаблицистинности

приведеформулыккониемИстанте»помощью« правилравносильных

преобразований (алгебраический способ);

имеютсядругиеспособы.

алгоритмическиразрешима.

Темсамымпроблемаразрешлогвысказыванийкимости

Пример 5. Доказать,чтоф рмула

( ← а=> ← b ) => (b => а)

естьтавтология.

Рассмдветеовтавтологияхтримремы[4, 10].

Пусть а, b,с

Теорема7

(опростейшихлогическихзаконах).

— произвольнформул. ые

Тогда:

1) a ← a — законисключ

енноготретьего

(tertim non datur), егочитают: или«не»;

2)

а => а (сравнитеп. 1);

3)

а => (b =>а) ;

4)

(а=> b) => ((b => с) а=> ( => с))

— цепноерасспусть( изждение

а следует b;тогда,

еслииз

b,всвоюочер,следуеть

с,тоиз

а следует с);

5)

(а => (b =>с))а=> ((

b) а=>с)) (

(еслиизаследует,что

b влечет с,тоизтого,

что а влечет b,следует,что

а влечет с);

Теорема8

(о

логическихзаконахрассужденияпротив

ного).

Пусть a, b,с —

произвольнформул.Тогдатавтологияые

мибудут:

11)

(а =>b) ~

( ← (a=>b)=>(с&

← с))

(утверждениеиз«

а следует

b»эквивалентно

утверждениюотом,чтоизотрицанияэтогоследует

ложь);

12)

(а =>b) ~ ( ← b => ← а)

(утверждение,чтоиз

а следует b эквивалентноутверждению,

чтоиз

← b следует ← a);

13)

(a=>b) а~&((

← b) => ← а)

(из

а следует b тогдаитолькотогда,когдаиз

а и

отрицания b следуетотрицание

а);

14)

(а=>

b) ~ ((а&

← b) =>b) (из

а следует b втомитольковтомслучае,когдаиз

а и

отрицания b следует b).

Diskretka.doc20.02.2014

128

Целоеимееттакуюжеприроду,какЯ,чтомы

постигаЦелоепутвсбоеглмееубокогопостижения

Я.

ЛейбницГ.В.Сочинениявт4.М.Мысль: , 1983т. .254..

Лекция№13

ЛОГИКАПРЕДИКАТОВ

Предикаты – этоотобпроизажениямножествовольныхвысказываний.

Логикапредикатовпредстасобойразлогикивляетвысказыванийитие.Историческипонят

ие

опредявиследствикатахосьлогичанализавыскескогом,т.е.выяснениязыванийих

логическойструктуры.

Определениепредиката

Пусть Х1,Х

2, Х..., п

произвольпеременныепереме.Эти будназывать

X,которыебудем

предметными. Пустьнаборыпеременныхв бираю

тсяизмножества

называть предметнойобластью

. Предикатом местности n (n - местнымпредикатом),

определеннымнапредметнойобласти

X,называютотобрамножениеества

X множество

высказываний.Обозначение: P( )

- n - местныйпредикат,опре

деленныйнаX:=( ).

Пример:

«х простчислое

».

х заменитьна

Этовыражениенеявляетсявысказыванипеременную,ноеслинем

опредечис,тополучимвысказываниеенное.Причемпризамене

е х напо8 ложноеучимвысказывание.

х начисло

3 получим

истиннвысказывание, окакгдапримен

Такимобразом,выражение:

«х простчисло»можнорассматриватьекакфункцию

Р(х) ,

зависящуюотпеременной

х. Областьопределения

Р(х)

— множествочисел,аоб асть

значения — высказывание.

Предикаты - отобпроизважения

ольмнвомножествоыхвысказываний.Пусть

х1, х2, .х. . ,

n - произвольпеременныепереме.Этинбудназывать

предметными.

Пустьнаборыпеременных

х1,

х2, .х . . , n выбираютизмножесятва

X, которыебудем

называть предметнойобластью

.

Предикатомместности

n (n-местнымпредикатом

),определеннымнапредметной

области X,называютотобрамножениеества

X множествовысказываний.

Обозначение:

P(х 1, х2, .х. . ,

n) - n-местныйпредик,определенныйнат

X:={х

1, х2, . . . ,

хn}.

Дадимдругоеопр

еделпред.ниеката

N-местныйпредикат

- этосвязноеповествовательноепредложение,содержащее

n

переменныхиобладающееследующимсвойст:приф вспеременныхкомациионем

(предложен)можносказать,истоноилнноиожнои.

Примеры.

1) Р(х 1,х 2) "Нату ральноечисло

х1 делитсябез(ост)ннатураткачисльное

х2" -

двуместныйпредик,определенныйнамножествепарнатуральныхчисел

(х 1,х 2 N ).

Очевидно Р(4,Р(5,2) =1;3)=

0

2) Р(х) = “ x2 < -1, x R” - одноместный предик,определенныйнат

R.

Ясно,чт

Р( -1)

= 0 ивообщепредикат

P(x) - тождественноложен,..

Р( x) = 0

Diskretka.doc20.02.2014

129

3) Р(х, y, z) = “x2 + y2 ≤ z,

x,y,x R” - трехмпр,определенныйдикстнаыйт

R3. Р(1,

1, -2)Р(1,=0,1, 2) = 1

Предикат — этофункция,значениямикоторойвляютсявысказыванияо

п

объектах,представляющихзн ченияргументов.

Спомфощьюрмальныхтеорийжнописатьобширныйклассвысказываний,

называемыхпредикатами.Дадимопреде

лениеисчисленияпредикатовкакформальн

ой

теории,азатемподробостановимсянаинтерпретации.

Р(х 1, х... , п), определеннаянекотором

Определение1

(предиката).

Функция

множестве М ипринодноидвухзмающаязначений:

Иистина( )

или Лложь( )

:

называется п-местнымпредикато

м.

Р:М

→ {И,Л}

,

n →В,

Произвольнаяфункция

Р:М

заданнаяпроизвольноммножестве

М,

называется n-местным предикатом Р(х

1 ,х

2 , . .

.,xn ),т.е.

Р задаетсемантическую

характеристику.

S = <A, F,Р,

R> называется исчислениемпредикатов

Формальнаятеория

первого

порядка,ес

лизаданыал,фавитормулы,ак

сиомыправила. вода

х,у,

z... — предметныепереме,приконкретимающиеные

ныезначизекоегония

множества D. Тогда х0, y0 , z0 ... — значенияпредметныхпер,..предметныеменных

постк(оянные

станты);

чения: истина1)(0

р,

q, r ...

— переменнпринимающиевысказ, ыдзнавания

(ложь)Тогда.

p0

, q0 , r0

... — фиксированныезначения;

ние;

Р0 ,

Q0 ( ) —

Р,

Q, F

— переменные,символизирующиесамовысказыва

постоянныепредикаты;

зуютсясимволы

, ;

→, ← — симвлогическлыпераций;дополнительнохсполь

, — кванторыобщностисуществования;

служебныесимволы

), ( — нужныдляустановленияпорядкавыполнениясвязок

областидействиякванторов;

! — единственность,

: — «та кой,что...идругие»

можноисптакжельзоватьзнаки

симетаязыкаволы.Например,

x {3,4,...,25}, ! y (0, ∞): x = y 2 .

2.Формулы: F:

переменныеестьформулы;

А(х) , (

),

(A → B)

xA(x,...)

xA(x,...)

если А,В

— формулы,

х — переменная,то

,

и

A

R1 :

A, A → B

modus ponens;

B

R2 :

A → B(x)

введекваобщностииетора

;

A → xB(x)

Diskretka.doc20.02.2014

130

R3 :

A(x) → B

введекваниетора

существования.

xA(x) → B

S описываетвесьмаобщиеобъ,поэнужноктееомуы

Построформальнаяеннаяори

интерпретирвто,счемможнработать. вать

Заметим,чтопредикатыдаютвозможность

матеманатически

лизироватьсуждения.В

классическойлогике

предикатом

называется

сказуемое

суждения,т..то,что

утверждаетсяилиотрицаетсяотносисубъэ суждогоельнокта,имепредметания

мысли,фиксирующееегоопределенныесвойс.Аматваематическойлогикепонятие

предикатарассматриваетсякактождественноесуждению,содержащемумес,..оимения

имена.

пропозиционнаяфун

кция,аргументамикоторойслужат

Пример.

ОвысказыватформеОн«получилспециальностьльнойпрограммиста»нельзя

сказать,истонаилннаожнаи,покнепроизвзаместоимениянаде»«аа

существи: М.А.Иванов« тпроельное

граммистом»истин(

но),Домстал«

программистом»ложно().

Далееподробноопишемвсоставляющиеформальнойтео

рисчисленияпредикатов

втакойинтерпретации.

п-местныйпредикат

Р(х

1,х 2, х...,

п), следуетуказатьмножества

Х1,Х 2, ...,

Чтобызадать

Хп — областиизменения

переменных х1,х 2, х...,

п,причемчащевсегорассматривается

случай,когда

Х1 =Х 2 =Х...=

п.

Стеоретико -множествточкизренияпропределяетсядикатннойзаданием

подмножества М вдекапроизведениитовом

X1 x Х2 x ... x Хп.

Переменные х1,х 2, х...,

п называются предметнымипеременными.

Элементымножеств

Х1,Х 2, Х..., п называются предметами.

Множество М — множествокортежейдлины

п <х1,х 2,

...х, п>называется полемпредиката

Р(х

1,х 2, х...,

п).

латинского

Будемобозначатьпредметнпеременныемалбуквамионца

x, y, z, х…,

1,х 2, х...,

алфавитаиногд( будемснэтиуквыжатьиндексами)

п .

Предметыизмножеств

Х1,Х 2, Х..., п — малымибукваминачалалаталфавитанского

а,

b,с, ..., a1, a2, …

саннымипредметными

Предикаты — большимибуквамилатинскогоалфавитаприпи

перемилибезнихнными

А(х,х)В.,

F(x, y),Р(х

1,х 2, х...,

п).

РK(х1,х 2, х..., k) —

Числопеременныхбудемуказыватькакверхнийиндекспредиката:

Р(х)

k-местныйпредикат,

Q2(x,у)

— двуместныйпредикат,

— одноместныйпредикат.

Итак, k-местныйпредикат

— Рk(х1,х 2, х..., k)

естьфункция,предметныепеременные

которойпризниачнмаютзекониямножестварого

(0),т.е.