Diskretka

Diskretka.doc20.02.2014

101

1

1

1

умножение (нулейиединиц).

Заметим,чток нъюнкция

– этофактическиобычное

Иногдаэтуфункциюобозначают

X&Y или X Y.

2) дизъюфу( нкция

ИЛИ ( )) двухысказываний

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

X Y, котороеис олькоинновтомслучае,когда

дизъюнкций

X и Y обаистинны.

Таблицаистинностидля

X Y

X

Y

0

0

0

0

1

1

1

0

1

1

1

1

3) импликацияследование( )

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

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

X →Y,

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

импликации

X истинно,а

Y ложно.

Таблицаистинностидля

X →Y

X

Y

0

0

1

0

1

1

1

0

0

1

1

1

Иногдаимпликациюобозначают

x→y

(читаетсяиз“

x следует y”).

Этооченьважнаяфун

кция,особенновлогике.Ееможнорассматриватьследующим

образом:если

х = 0 (т.е.

х “ложно”),тоизэтогофактам вывестижнол“”,жьистину“ ”

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

у = 1 (т.е.

у “ист”),тоинностинавыводизлжи“” зтся

“истины”,эт

отожеправильно.Тольковыводизистины“ ложь”являетсяневерным.

Заметим,что

любая теорема всегда фактическисодержэтулогическуюфункциют.

4) сложениепомодулю2

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

будем

обозначатьтакоесложение)двухысказываний

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

X Y,

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

X истинно,а

Y ложноили

X ложно,а

Y истинно.

Супомодулюмадва

,или антиэквивалентность,поопределени ю X Y =

X↔ Y

Таблицаистинностидля

импликации

X Y

X

Y

0

0

0

0

1

1

1

0

1

1

1

0

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

X

5) эквивалентность или подобие двухысказываний

↔ Y, котороеис инно

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

X и Y обаистинныложны.

Таблицаистинностидля

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

X ↔ Y

X

Y

0

0

1

0

1

0

1

0

0

1

1

1

Эта f9

= 1 тогдаитолькотогда,когда

ху= . Заметим,чтобудемприменятьоба

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

ху (в основномприизучениифункций)

ху~

(когдаречьбуидтиоет

Diskretka.doc20.02.2014

102

6) штрихШеффера

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

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

X

Y , которое

ложнотолько, гдавысказываниябаистины.Поопределению

штрих Шеффера является

антиконъюнкцией (X

Y ) =

.

X Y

Таблицаистинностидля

штрихаШе(ффера

антиконъюнкции)

X

Y

X

Y

0

0

1

0

1

1

1

0

1

1

1

0

Замечание.

Конъюнкция,дизъюнкц,отрицаниебылопределеныдляобъектов,

принлидвазначенияшьмющих

0 и 1.Однакобываютслучаи,когдаможноввеститакиеоперации

длянекоторыхдругихобъекэти(операциитовакженазываютиногдаконъюнкцией,дизъюнкци

ейи

отрицанием),дляко акжеорыхвыполненысвойства1

–6Вэтом. случаеговорят,чтонаэтих

объектахвведена

булеваалгебра.

7) стрелкаПирс

(иногдаэтуфуназываюткцию

штрихЛукасевича

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

X и Y

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

X ↓ Y ,

котороеис олькоинно, обагдавысказыванияложны.По

определению стрелкаПирсаштрих( Лукасевича)

является антидизъюнкцией X ↓Y =

.

X Y

Таблицаистинностидля

стрелкиПирса

(антидизъюнкцией)

X

Y

X ↓ Y

0

0

1

0

1

0

1

0

0

Этафункцияявляетсяотрицаниемдизъюнкциипоэтинееназываютмугда

1

1

0

“не

или” .

Заметим,чтосвойпосдвухтваледфукакн(будеткцихвиднодалеей)похомеждуи

.называют f8

штрихом

соби,мобытьйжет,поэтомувлитераихчаспутт.уре(оают

Шеффера,а

f14 – стрелкойПирса

).

Замечание.

Вовсехвышеприведенныхтаблицахистинностилогическихопераций

числостр к

2n,где

n – числопростыхвысказываний.

Триоставшиесяфункции, (

f2 , f4 и f11)особогозначениявдискретнойм

атематикене

имеют.

суперпозиции

Заметим,чточастобудутрассматриватьсяфункцииотфункций,.е.

перечисленныхвышефункций.Приэтомпоследовательностьдействийуказываетсякак(

обычно)скобками.Исключениесоставляетконъюнкциякоторая( насамомделе

является

обычумнвдвоожениымс )чнойстПоэтому. емконъюнкцияесовершаетсяпервой,даже

xy yz означает(

xy)

(yz).

еслиотсутствуютскобки.Например,запись

Изперечифункцийособуюленныхрольигр

аюттрифункции,аименноконъюнкция,

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

Помэтсвязокииспользуютсяхмоещетрисвязкиполученныеизвышеуказанных

связок

Название

Прочтение

Обозначение

ШтрихШеффера

Антиконъюнкция

СтрелкаПирс

Антидизъюнкция

↓

Супомодулюмадва

Антиэквивалентность

ШтрихШеффера

X

Y или антиконъюнкция,поопределению

(X

Y )=

X Y

Diskretka.doc20.02.2014

103

СтрелкаПирс

X ↓ Y или антидизъюнкция,поопределению

(X ↓ Y )=

X Y

Супомодулюмадва

X Y

или антиэквивалентность,поопределению

(X Y )=

X ↔Y

Таблицыистинносэтихоперацийти

X

Y

Штрих

СтрелкаПирса

Суммапо

X Y

0

0

Шеффера X

Y

X ↓ Y

модулю2

1

1

0

0

1

1

0

1

1

0

1

0

1

1

1

0

0

0

Порядоквыполн

ения операций

Евслвыраженииожномскобокнет,тооперациинадовыполнятьследующем

порядке:конъюнкция,дизъюнкци

я,импликация,эквивалент,отрица. ностьие

Соглашенияотносительнорас кобтан. вки

1Внешние. скобкипишутся.

((X Y )→ Z ) пишут (X Y )→ Z

При.Вместоер

2На.множестве

{¬, , ,→,↔,

,↓, } вводятсятранзитивноеотношение

<быть«более

сильным»отношениеэквивалентности~бытьравносильным« »поправпоказаннымлам

нарис.

←

~

~ ↓

→

Согласотношениямэтим едостающиескобкивформулерасставляются

↔ ~

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

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

лняетсяслеванаправо.

Конечностьобластиопределфункцииимважноепреимуществонияет

– такие

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

n перемен,надоопределитьзныхаче

Длятого,чтобызадатьзначениефункцииот

ниядля

каждогоиз2

n

наборов.Этизначениязаписываюттаблицупорядкесоответствующих

двочи.Врчныхсезультатеполучатабслеицавидатсядующего:

Булевафункция

f(x1, x2, … ,xn) полноопределяетьювоей

тся

таблицейистинности

x1

x2

x3

… xn-1

xn

f(x1, x2, … ,xn)

0

0

0

…

0

0

f(0, 0, … 0, 0)

0

0

0

…

0

1

f(0, 0, … 0, 1)

.

.

.

… .

.

.

.

.

.

… .

.

.

.

.

.

… .

.

.

Diskretka.doc20.02.2014

104

1

1

1

…

1

0

f(1, 1, … 1, 0)

1

1

1

…

1

1

f(1, 1, … 1, 1)

(δ 1, δ2, …

Вкаждстртаблицыоистинностийкезадазначенийетсяборпеременных

,δ n),азатем

- значениефункцииэтомнаборе.

φ имеютоднутужетаблицуистинности,то

Еслибулевафункция

f

иформула

формулаφпредставляетфункцию

f.

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

Различныеформулымогутиметьодинаковыетаблицыистинности.Таквоз

никает

понятиеэквивалентностиформул.

Формулы φ( x1,..., xn) и

ψ( x1,..., xn) называются

эквивалентными (φψ)~

,если

совпихтаблицыистинностидают,.е.совпадаютпредставляемыеэтимиформулами

функции fφ(x1,..., xn) и fψ(x1,..., xn)

x → y и

Пример1Проверк.

анаэквивалентностьследующихформул

→

.Построим

y

x

таблицыистинностиформул

x → y и

→

,

y

x

x

y

x → y

→

y

x

0

0

1

1

0

1

1

1

1

0

0

0

1

1

1

1

убеждаемсявтом,что

(x → y) ~

(

→

).

Действительноэ

тоотношениеявляется~

y

x

отношениемэквивал,..онор флекнтносивноти

(φφ~)

,симметрично (φψ~)

=> (ψφ~)

итранзитивно

(φ~ψ,ψ~χ

=> φ~χ) .

Основныеэквивалентностимеждуформулами:

(ассоциативность и

1.

((ϕ ψ ) χ) ~ (ϕ (ψ χ)); ((ϕ ψ ) χ) ~ (ϕ (ψ χ)) -

).

(коммутативность и ).

2.

(ϕ ψ ) ~ (ψ ϕ);

(ϕ ψ ) ~ (ψ ϕ) -

3.

(ϕ ϕ) ~ φ; (ϕ ϕ) ~ φ -

(идемпотентность и ).

(законы

4.

(ϕ (ψ χ))

~

((ϕ ψ ) (ϕ χ));

(ϕ (ψ χ)) ~

((ϕ ψ ) (ϕ χ)) -

дистрибутивности и ).

5.

(ϕ (ϕ ψ )) ~ φ; (ϕ (ϕ ψ )) ~ φ - (закпоглощенияны

и ).

6.

←(ϕ ψ ) ~ ¬ϕ ¬ψ ;

←(ϕ ψ ) ~ ¬ϕ ¬ψ

- (законыдеМоргана)

.

7.

¬¬ϕ ~ φ; -

(закондвойного

отрицания - инволютивность)

.

11За.склеиванияон:

x x = x x = 1 .

12. Дляфункций:конъюнкция,дизъюнкциясупоммаодулюдвасправедливы

следующиетождества:

x x = x ;

x x = x ;

x x = 0 ;

x x = 0 ;

x x = 1;

x x = 1;

x 0 = 0 ;

x 0 = x ;

x 0 = x ;

x 1 = x ;

x 1 = 1;

x 1 = x ;

13Дляфункций. конъюнкциядизъюнкциясправедливытожде

ства:

x1 x1 x2 = x1 x2 ;

Diskretka.doc20.02.2014

105

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

x1 (x2 x1 ) = x1 x2 ;

дествнужносоставить

таблицыистинностидлябулевыхфункций.

Булевуфункциюлюбогочислаперемеможнозадатьформулойных,содержащей

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

вместопеременныхдругиебулевыфункции,

т.е.посредствсуперпбулевыхомзиции

функций.

Формула φ( x1,..., xn)

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

еслиуществуеттакой

наборзначенийпеременных,прикотформулаприомзначениеимает

1 (соответственно

0).

ПримерФормула1.

х у являетсяодновременновыпиопровержимойлнимой,

поскольку 0 0 = 0,а

1 1 = 1.

Формула φ( x1,...,

xn) называется

тождественноистинной,

общезначимойили

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

1

привсехнаборахзначений

пер,те..фуменкцияных

f являетсяконстантой

1.

Пример2Формула.

x

являетсятождественноисти,одновременнонойвыполнимой

x

0 1 = 1, 1 1 = 1.

Формула φ( x1,..., xn)

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

или противоречием,еслиэта

формулапризначениеимает

0.

0 привсехнаборахзначенийпер,т..фуменкцияных

f

являетсяконстантой

x

ку 0 0 = 0,а

Пример3Формула.

являетсятождестопро,поскольвенноржимой

x

0 1 = 0.

Если φ - тождественноистиннаяформула, будемписать|=

φ Пример.|=

x

.В

x

противномслучаепишем|

≠ φ.Пример|

≠ x

.

x

Очеявиднымляследующеется

Замечание

1. Формула φ тождественноложнатогдаитолькотогда,когда

неφ тождественно

истинна (|=неφ)

;

2. Формула φ опровержиматогдатолькотогда, онгдаявляется

тождественноистинной(|

≠ φ);

3. Формула φ выполнима тогдаитолькотогда, гданявляетсятождественно

ложной.

Тождеистинные(оответственнотождественноложные)формулыобразуют

классэквивалентностипоотношению~.

φ1 тождественноистин

φ0 - тождественноложна, юбыхя

4. Еслиформула

на,

формул φ иψсправследующиеыэкв валентности:

φ φ1 ~φ;φ

φ0 ~φ 0;

φ φ1 ~φ 1;φ φ0 ~φ;

(ϕ →ϕ ψ ) ~ φ1; (ϕψ →ϕ) ~ φ1;

ϕ ϕ ~ φ0; ϕ ϕ1 ~

; ϕ ϕ0 ~ φ.

ϕ

Графическийспособзадания

булевойфункции

Единичный n-мерныйкубфункции

w = f(x, y, z)

Задняя 00

1

Задняя011 101

111

Грань

передняя

000

001

100

110

Фактор-алгебраалгебрыфо

рмул

Diskretka.doc20.02.2014

106

Обозначимчерез

Фn

множествовсехформулалгебрылогикипеременнымиз

множества {х 1,х 2, х... , n}.

Намножестве

Фn определеныдвухместныеоперацконъюнкциизъюнкции

— :

(ϕ,ψ )!ϕ ψ , : (ϕ,ψ )!ϕ ψ — иодноместнаяоперацияотрицания

: ϕ !

.

ϕ

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

Фn

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

x

и x

.Такполучается

алгебра

x

x

формул Fn =

Φn ; , ,

, x

, x

.

x

x

Отношениеэквивалентности~ формулявляетсяконгруэнциейнаалгебре

Fn,ипоэтому

можнозадать

фактор-алгебру Fn/~.

Нафактор

-множестве Фn/~операции

, и

опредследуляющимтся

образом:

~(φ) ~(ψ) = ~ (φ ψ),

~(φ) ~(ψ) = ~ (φ ψ),

← ~(φ) = ~( ← φ),.

Намножестве Фn/~выдвееляюконстанты: 0 =ся~(

x

)и1 = ~(

x

). Полученная

x

x

система Φn / ≈; , ,

,0,1 являетсяфактор

-алгеброй Fn/~.

Теорема.

Фактор-алгебра Fn/~изоморалгебребулевыхфункцийна

Bn

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

ξ: Fn/~→

Bn

Искомыйизоморфизм

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

эквивалентности ~(φ) сопоставляетсяфункция

fφ, имеющаятаблицуистинности

произвольнойформулымножества

~(φ).Посколькуразнымклассамэквивалентности

соотверазличныетаблицыствуютистинности,отображение

ξ инъективно,атаккакдля

любойбулевойфункции

f

из Вп найдетсяформула

ϕ Φn ,представляющаяфункцию

f, то

отображение ξ сюръективно.Сохраненоперацией

, ,

,

при0,отображении1

ξ

проверяетсянепосредственно.ЧТД.

f Bn ,неявляющейся

По теофункциональнойремеполнотекаждойфункции

константой 0,соответствуетнекотораяСДНФ

ψ,принадлежащаяклассу

~(φ) = ξ-1(f) формул,

представляющихфункцию

f.Возадникаетхождениячавклассе

~(φ) дизъюнктивной

нормальнойформы,имеющейнаибпрстроениелеест. е

Контрольныевопросы

1.

Чтотакоеб

улевафункции

?

Понятиебул«функция»,булевывафункцииодной

переменной.Булевыфункциидвухпеременных.

2.

Чтоназываетсявысказыванием

? Понятиевысказывание« »

.

Приведите

примеры

высказ.Какиевыскваназываийстинными,какиеютсянияложными?

5.

Какиеосновныеоперациииспользуютсятеориив

ысказываний?Простейшиесвязки.

Назодругисвязки.ите

6.

Чтотакоетаблицаистинностивыскаонастроитсязыванияк?

7.

Сформулируйтеосновнзаконыалгебрывысказываний.Какихдоказать?

8.

Булевыфункции:понятияподформула, ,базис.Равн сильные

мулы.

Diskretka.doc20.02.2014

107

Лекция№9

Таккакзданвсегомиравершивозведенонно

премудрымТворцо,томиренепроисходитни,вчемго

небыловиденсмыслкакого

-нибудьмаксилимума

минимума.

Эйлер

ДИЗЪЮНКТИВНЫЕКОНЪЮНКТИ

ВНОРМАЛЬНЫЕФОРМЫ

Определение

Если х — логическаяпеременная,