Лекции по дискретной математике

Тема: «Алгебра высказываний».

1. Понятие высказывания. Под высказыванием понимается такое предложение, которое либо истинно, либо ложно. Высказывание что может быть одновременно и истинным, и ложным.

Первоначальная со­вокупность некоторых простейших высказываний, называемых эле­ментарными или исходными, о каждом из которых точно извест­но, истинно оно или ложно. Высказывания обозначаются заглавными буквами латинского алфавита А, В, С, D, ... или теми же буквами с индексами внизу.

Пример:

А: «Москва – столица России»

В: «7

Обозначив истинное высказывание символом 1, а ложное - введем функцию λ, заданную на совокупности всех высказывании и принимающую значения в двухэлементном множестве {0, 1 } по следующему правилу:

λ = 1, если высказывание Р истинно,

0, если высказывание Р ложно.

Функция λ называется функцией истинности, а значение λ(Р) - логическим значением или значением истинности высказывания Р. Для приведенных высказываний имеем логические значения λ (А) = 1, λ (В) = 0.

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

2. Основные логические операции.

1) Отрицанием выска­зывания Р называется новое высказывание, обозначаемое Р (чи­тается: «не Р» или «не верно, что Р»), которое истинно, если высказывание Р ложно, и ложно, если высказывание Р истинно. Таблица истинности операции отрицания:

Пример. Применим операцию отрицания к высказыванию А: «Москва – столица России». Данное отрицание можно читать так: «Неверно, что А» т. е. «Москва – столица России».

λ (¬А) = λ¬ (А) = ¬ 1 = 0, т.е. высказывание ¬ А ложно.

2) Конъюнкцией двух высказываний Р и Q называется новое высказывание, обозначаемое Р ˄ Q или Р & Q (читается: «Р и Q»), которое истинно лишь в единственном случае, когда истинны оба исходных высказывания Р и Q и ложно во всех остальных случаях. Таблица истинности операции конъюнкции:

Пример. Применим операцию конъюнкции к высказывани­ям А, и В. Получим высказывание А ˄ В: «Москва – столица России, и 7 λ(А˄В) = λ(А)˄λ(В) = 1˄0 = 0.

3) Дизъюнкцией двух высказываний Р и Q называется новое высказывание, обо­значаемое Р v Q (читается «Р или Q»), которое истинно в тех случаях, когда хотя бы одно из высказываний Р или Q истинно, и ложно в единственном случае, когда оба высказывания Р и Q ложны. Таблица истинности операции дизъюнкции:

Пример. Применим операцию дизъюнкцию к высказывани­ям А и В. Получим составное высказывание А v В: «Москва – столица России, или 7λ(А˅В)= λ(А)˅λ(В)=1˅0=1.

4) Импликацией двух высказываний Р и Q называется новое высказывание, обозначаемое Р → Q «читается: «если Р, то Q», или «из Р следует Q», или «Р влечет Q » или «Р достаточно для Q», или «О необходимо для Р»), которое ложно единственном случае, когда высказывание Р истинно, а Q ложно, а во всех остальных случаях — истинно. Таблица истинности операции импликации:

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

Пример. Высказывание А →В: «Если Москва – столица России, то 7В)=λ(А)→λ(В)=1→0=0

5) Эквивалент­ностью двух высказываний Р и Q называется новое высказывание обозначаемое Р ↔ Q (читается: «Р эквивалентно Q», или «Р необ­ходимо и достаточно для Q», или «Р тогда и только тогда, когда Q» или «Р, если и только если Q»), которое истинно в том и только в том случае, когда одновременно оба высказывания Р и Q либо истинны, либо ложны, а во всех остальных случаях - ложно. Таблица истинности операции эквивалентности:

Пример. Высказывание «Москва – столица России тогда и только тогда, когда 7А и В, ложно, так как

λ(А↔В)=λ(А)↔(В)=1↔0 = 0.

3. Формулы логики. С помощью логических операций из простейших высказываний можно строить высказывания более сложные. Например, можно построить такое высказывание: «Если Саратов находится на берегу Невы и все люди смертны, то

А. С. Пушкин - русский математик». Построенное высказывание символически записывается так: (А ˄В) → С. Конечно, оно звучит несколько странно, поскольку соединяет в себе столь разнородные понятия которые обычно существуют раздельно друг от друга. Но нас интересует не содержание этого высказывания, а его логическое значение. Оно может быть определено, исходя из логических значений исходных высказываний А, В, С и той схемы, по которой из исходных высказываний построено сложное высказывание. Так как λ(А) = 0, λ(В) = 1, λ(С) = 0, то находим:

λ[(А˄В)→С]=λ(А ˄ В)→λ(С)=( λ(А) ˄λ(В))→ λ(С)=(0˄1)→0=0→0=1 Итак, высказывание (А ˄ В) → С истинно.

Для конструирования данного сложного высказывания из простейших высказываний А, В и С нужно применить операцию конъюнкции к первым двум высказываниям, а затем к полученному высказыванию и к третьему исходному высказыванию применить операцию импликации. Это словесное описание схемы конструирования данного сложного высказывания можно заменить описанием символическим: (X ˄ Y) → Z, где X, Y, Z — некоторые символы (переменные), вместо которых можно под любые конкретные высказывания. Такая схема конструирования составного высказывания может быть применена к различным конкретным высказываниям, а не только к высказываниям А, В, С.

В формулу (X ˄ Y) → Z вместо переменных X, Y, Z можно подставлять конкретные высказывания, после чего вся формула будет превращаться в некоторое составное высказывание. Переменные, вместо которых можно подставлять высказывания, т.е. переменные, пробегающие множество высказываний, называют пропозициональными переменными, или высказывательными переменными, или переменными высказываниями. Будем обозначать пропозициональные переменные заглавными буквами латинского алфавита Р, Q, R, S, X, Y, Z или так же буквами с индексами. Теперь дадим точное определение формулы алгебры высказывание:

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

2. Если F₁и F₂ формулы алгебры высказываний, то выражения

¬F₁ , (F₁˄F₂), (F₁ v F₂), (F₁ → F₂), (F₁ ↔ F₂) также являют формулами алгебры высказываний.

1. Никаких других формул алгебры высказываний, кроме полу­чающихся согласно п. 1 и 2, нет.

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

Такую последовательность всех подформул данной формулы иногда называют порождающей последовательностью для формулы. Наличие такой последовательности у логического выражения служит критерием того, что выражение является формулой. Это свойство отличает формулы.

Пример. (X ˄ ¬Y) → Z – формула, (X ¬Y) → Z – не является формулой.

4. Таблица истинности и методика её построения. Для каждой формулы F алгебры высказываний найти логические значения всех тех высказываний, в которые формула превращается при подстановке вместо всех ее пропози­циональных переменных различных конкретных высказываний. При нахождении логических значений формулы, соответствующих все­возможным наборам значений ее пропозициональных перемен­ных, удобной формой записи является табличная форма.

Пример. Составим таблицу истинности для формулы (Х→ Y) v (Y→ X).

Первые два столбца и последний столбец составленной табли­цы задают соответствия между логическими значениями исходных высказываний и логическим значением составного высказывания, получаемого по данной формуле. Эти три столбца и образуют таблицу истинности данной формулы. Остальные два столбца носят вспомогательный, промежуточный характер.

Пример. Составим таблицу истинности для формулы

F(P, Q, R) = (Р ˄ Q) → (Р↔¬R).

5. Законы логики. Тавтологии представляют собой схемы построения истинных высказываний, независимо от содержания и истинности составляющих высказываний. Так, если для уста­новления того, истинны или нет высказывания «Саратов основан в 1590 году», «Солнце вращается вокруг Земли», необходимо об­ладать специальными знаниями или заглянуть в специальную ли­тературу, то для выяснения значения истинности высказываний «Треугольник ABC прямоугольный, или треугольник ABC не пря­моугольный», «Неверно, что информация о наследственных при­знаках хранится в генах, и эта информация в генах не хранится» уже не нужно обладать знаниями ни в математике, ни в генетике. Вывод об истинности последних высказываний делаем, исходя не из их содержания, а из их формы, структуры. Структура первого из последних высказываний выражается формулой Xv ¬Х, а второ­го — формулой ¬(Xv ¬Х). Легко убедиться в том, что обе эти формулы суть тавтологии. Данные формулы дают две схемы по­строения всегда истинных высказываний. И такова каждая фор­мула, являющаяся тавтологией. Но главное значение тавтологий не в этом.

Основное значение тавтологий состоит в том, что некоторые из них предоставляют правильные способы построения умозаключе­ний, т.е. такие способы, которые от истинных посылок всегда приводят к истинным выводам. Термин «тавтология» имеет греческое происхождение и означает повторение одного и того же определения, суждения иными, близкими по смыслу словами. В тавтологиях, относящихся к ма­тематической логике, заключительной логической связкой явля­ется эквивалентность ↔ . Например, тавтология (Р ˄ (Q v R))↔ ((Р ˄ Q) v (Р ˄ R)) выражает одинаковость форм (формул) в ее левой и правой частях, т. е. имеется в виду семантическая одинаковость, выражаемая разными словами — формами (фор­мулами).

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

1) закон исключенного третьего Р v ¬Р;

2) закон отрицания противоречия ¬(Р ˄¬Р);

3) закон двойного отрицания ¬¬Р ↔ Р;

4) закон тождества Р→Р;

5) закон контрапозиции (Р → Q)↔(¬Q→¬Р);

6) закон силлогизма (правило цепного заключения)

((Р→Q) ˄ (Q→R)) →(Р→R);

7) закон противоположности (Р ↔ Q)↔(¬Р ↔¬Q);

8) правило добавления антецедента («истина из чего угодно») Р→ (Q →Р);

9) правило «из ложного что угодно» ¬Р→(Р→Q);

10) правило «модус поненс» (Р ˄ (Р→Q))→Q;

11) правило «модус толленс» ((Р →Q) ˄¬Q)→¬Р;

12) правило перестановки посылок (Р →(Q→ R))↔(Q→(Р→ R));

13) правило объединения (и разъединения) посылок (Р→( Q → R)) ↔((Р ˄ Q) → R);

14) правило разбора случаев ((Р→R) ˄ (Q → R)) ↔ ((Р v Q) → R);

15) правило приведения к абсурду ((¬Р→Q) ˄ (¬P→¬Q))→Р, (¬P→( Q ˄ ¬ Q)) →Р;

16) законы идемпотентности (Р ˄ Р) ↔Р, (Рv Р)↔Р;

17) законы упрощения (Р ˄ Q)→Р, Р→(Р v Q);

18) законы коммутативности (Р ˄ Q)↔(Q ˄ Р), (Р v Q)↔(Q v Р);

19) законы ассоциативности (Р˄(Q˄R))↔((Р˄Q)˄Р), (Рv(QvR))↔((Р v Q) v R);

20) законы дистрибутивности (Р˄(Q v R))↔((Р˄Q)v(Р˄R)),

(Pv(Q˄R))↔((РvQ)˄ (Рv R));

21) законы поглощения (Р ˄ (Р V Q) ↔ Р, (Р V (Р ˄ Q) ↔Р;

22) законы де Моргана ¬(Р ˄ Q)↔ (¬Р V ¬ Q), ¬(Р v Q)↔(¬Р ˄¬ Q);

23) (Р→(Q →R))→((Р → Q) →(Р→ R));

24) Р→(Q→ (Р ˄ Q));

25) (Р→R) → ((Q→ R)→((Р v Q )→Р));

26) (Р→ Q) →((Р→¬ Q) →¬Р));

27) (¬Q ˄ (Р → Q) → ¬Р;

28) (¬Р ˄ (Р v Q))→ Q

29) (Р →Q) →((Р v R) → (Q v R))_;

30) (Р →Q) →((Р ˄ R) → (Q ˄ R));

31) (Р→Q)→((Q→R)→(Р→R));

32) (Р → Q) v (Q→Р);

33) (¬Q →¬Р)→((¬ Q→Р) → Q);

34) ((Р →Q)˄(R→Q)↔((Рv R)→ Q);

35) ((Р→ Q) ˄(Р→R))↔(Р→( Q ˄ R));

36) Р ↔ Р;

37) (Р ↔ Q)↔(Q ↔ Р);

38) ((Р ↔ Q) ˄ (Q ↔ R)) → (Р ↔R).

39) (Р → Q)↔(¬Р v Q);

40) (Р→ Q)↔¬(P ˄ ¬Q);

41) (Р ˄ Q) ↔¬(¬Р v¬ Q);

42) (Р ˄ Q) ↔ ¬(P →¬ Q);

43) (Pv Q)↔¬(¬Р ˄ ¬ Q);

44) (Pv Q)↔ (¬Р→Q);

45) (Р↔ Q) ↔ ((Р→ Q) ˄ (Q → Р)).

6. Равносильные преобразования. Определение. Формулы F(X₁, X ₂, ..., Х_п) и Н(X₁, X ₂, ..., Х_п) алгебры высказываний называются равносильными (эквивалентными), если при любых значениях вхо­дящих в них пропозициональных переменных логические значе­ния получающихся из формул F и Н высказываний совпадают. Для указания равносильности формул используют обозначениеFН .

При­мер. Проверим равносильность формул ¬Х₁, и ¬Х₂˄(Х₂ v ¬Х₁). Для этого составим таблицы истинности обеих формул и убедимся, что значения истинности получающихся из них высказываний одинаковы для любых одинаковых наборов значений пропозициональных переменных X₁ и Х₂:

Теорема (признак равносильности формул). Две формулы Fи Н алгебры высказываний равносильны тогда и только тогда, когда формула F↔Н является тавтологией:

F H=F↔H.

Отметим, что равносильность формул — это не (логическая) операция над формулами, а отношение между формулами логики высказываний. Это означает, что если Fи H — формулы, то выра­жение F H уже не является формулой алгебры высказываний; оно — утверждение о некотором взаимоотношении между форму­лами F и Н, лишь сокращенная (символическая) запись утвержде­ния (высказывания) «F равносильна H» об этих формулах. Это ут­верждение либо истинно, либо ложно, т.е. F и H либо находятся в отношении равносильности, либо нет.

Следствие. Отношение равносильности между формулами алгебры высказываний:

а) рефлексивно: F  F;

б) симметрично: если F₁  F ₂, то F₂  F₁,

в) транзитивно: если F₁  F ₂ и F ₂ F ₃, то F₁  F₃,

т. е. отношение равносильности является отношением эквивалент­ности.

Теорема. Справедливы следующие равносильности:

1) ¬¬РР;

2) Р→Q ¬Q→¬Р;

3) Р↔ Q¬Р↔¬ Q;

4) Р→(Q→R)(Р ˄ Q)→ R;

5)(Р → R) ˄ (Q→ R)(Р v Q) → R;

6) Р ˄ Р  Р;

7) Р v Р  Р;

8) Р ˄ QQ ˄ Р;

9) Р v Q Q v Р;

10) Р ˄ (Q ˄ R)  (Р ˄ Q) ˄ R;

11) Р v (Q v R)  (Р v Q) v R;

12) Р ˄ (Q v R)  (Р ˄ Q) v (Р ˄ R);

13)Pv(Q ˄ R) (Pv Q) ˄ (Р v R);

14) Р ˄ (Р v Q) Р;

15) Р v(Р ˄ Q) Р;

16) ¬(P ˄ Q) ¬Pv¬ Q;

17) ¬(Рv Q) ¬Р ˄¬Q;

18) Р ↔ QQ↔Р;

19) Р→Q¬Р v Q;

20) Р→ Q¬(P ˄¬ Q);

21) Р ˄ Q  ¬(Р → ¬ Q);

22) Р v Q ¬Р→ Q;

23) Р↔ Q(Р→ Q) ˄ (Q→Р);

24) Р v ¬P  1, Р ˄ ¬P0;

25) Pv11,P˄1P;

26) Р v0Р, Р˄00

Используя приведенные в теореме равносильности, можно от од­ной формулы переходить к равносильной ей формуле. Такой переход называется равносильным преобразованием исходной формулы. Равносильные преобразования формул применяются прежде всего для упрощения формул.

Пример. Упростим формулу

¬(Х₁→¬X₂) ˄¬(Х₂→¬Х₁)¬(¬X₁ v ¬Х₂)˄¬(¬X₂v¬Х₁)  ¬(¬X₁ v ¬Х₂)˄¬(¬X₁v¬Х₂)  ¬(¬X₁ v ¬Х₂) ¬¬X₁ ˄ ¬¬Х₂ Х₁ ˄ Х₂.

7. Нормальные формы для формул алгебры высказываний.

Для каждой формулы алгебры высказываний можно указать равносильную ей формулу, содержащую из логических связок лишь отрицание, конъюнкцию и дизъюнкцию. Например: XvY, (X˄¬Y)vY, (Х˄¬Y)v((Xv¬X) ˄Y).

Среди всевозможных выражений формулы через конъюнкцию, дизъюнкцию и отрицание некоторые играют важную роль как в алгебре высказываний, так и в ее приложениях. Рассмотрение таких выражений, называемых совершенными нормальными формами.

Конъюнктивным одночленом от переменных Х₁, Х₂, ..., Х_п называется конъюнкция этих переменных их отрицаний. Здесь «и» употребляется в неисключающем смысле, т. е. в конъюнктивный одночлен может входить одновременно и переменная, и ее отрицание. Например: Х₁˄Х₂, Х₁˄¬Х₂˄Х₃.

Дизъюнктивным одночленом от переменных Х₁, Х₂, ..., Х_п называется дизъюнкция этих переменных их отрицаний. Здесь «или» употребляется в неисключающем смысле, т. е. в дизъюнктивный одночлен может входить одновременно и переменная, и ее отрицание. Например: Х₁vХ₂, Х₁v¬Х₂vХ₃.

Дизъюнктивной нормальной формой называется дизъюнкция конъюнктивных одночленов. Например: (Х₁˄Х₂)v(Х₁˄¬Х₂˄Х₃).

Конъюнктивной нормальной формой называется конъюнкция дизъюнктивных одночленов. Например: (Х₁vХ₂) ˄(Х₁v¬Х₂vХ₃).

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

Среди множества дизъюнк­тивных (равно как и конъюнктивных) нормальных форм, кото­рыми обладает данная формула алгебры высказываний, существует уникальная форма: она единственна для данной формулы. Это так называемая совершенная дизъюнктивная нормальная форма (среди конъюнктивных форм - совершенная конъюнктивная нормаль­ная форма).

Одночлен (конъюнктивный или дизъюнктив­ный) от переменных Х₁, Х₂, ..., Х_n называется совершенным, если в него от каждой пары X_i, ¬X_i, (i = 1, 2,..., п) входит только один представитель (X_i или ¬X_i). Нормальная форма (дизъюнктивная или конъюнктивная) от переменных Х_1, Х₂, ..., Х_п называется совершенной от этих переменных, если в нее входят лишь совершен­ие одночлены (конъюнктивные или дизъюнктивные соответствен­но) от Х_1, Х₂, Х_п.

Например: совершенная конъюнктивная нормальная форма от четырех переменных Х₁, Х₂, Х₃, Х₄: (X₁v X₂v X₃ v Х₄) ˄(¬X₁v X₂v ¬X₃ v Х₄);

совершенная дизъюнктивная нормальная форма: (Х˄У)v (¬Х˄У)v(Х˄¬У).

Введем обозначение, которое будет удобно в дальнейшем:

Х^α = X, если α = 1,

¬X, если α = 0.

Легко проверить, что 0⁰ = 1, 0¹ = 0, 1° = 0, 1¹ = 1, т. е. Х^α = 1 тогда и только тогда, когда X = α, и Х^α = 0 тогда и только тогда, Х≠α. Введем еще одно обозначение. Вместо дизъюнкции Х₁ v Х₂ v ... vХ_n будем писать Vⁿ_i=1X_i. Например: V_{(α, β)}(X^α ˄ Х^β) = (Х⁰˄У⁰) v (Х⁰ ˄ У¹) v (X¹ ˄ У⁰) v (X¹ ˄ У¹) =

(¬Х˄¬У) v (¬Х˄У) v (X ˄ ¬У) v (X˄ У).

Теорема (о представлении формул алгебры высказываний совершенными дизъюнктивными нормальными формулами). Каж­дая не тождественно ложная формула алгебры высказываний от п аргументов имеет единственную (с точностью до перестановки дизъ­юнктивных членов) совершенную дизъюнктивную нормальную форму.

Введем обозначение, которое будет удобно в дальнейшем:

^βХ = X, если β = 0,

¬X, если β = 1.

Легко проверить, что ⁰0=0, ¹0 =1, ⁰1 =1, ¹1= 0, т. е. ^βХ = 1 тогда и только тогда, когда Х≠β и ^βХ= 0 тогда и только тогда, Х=β.

Введем еще одно обозначение. Вместо дизъюнкции Х₁ v Х₂ v ... vХ_n будем писать ˄ ⁿ_i=1X_i.

Например: ˄ _{(α, β)}(^αХ v ^βХ) = (⁰Хv ⁰У) ˄ (⁰ Хv ¹У) ˄ (¹Хv ⁰У) ˄ (¹Х v ¹У) =

(Х v У) ˄ (Х v ¬У) ˄ (¬X v У) ˄ (¬X v ¬У).

Теорема (о представлении формул алгебры высказываний совершенными конъюнктивными нормальными формулами). Каж­дая формула алгебры высказываний от п переменных, не являющаяся тавтологией, имеет единственную (с точностью до перестановки конъ­юнктивных членов) совершенную конъюнктивную нормальную форму.

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

Правило (алгоритм) отыскания совершенной дизъюнктивной нормальной формы для данной формулы: нужно выбрать все те наборы значений ее переменных, на которых формула принимает значение 1, для каждого такого набopa выписать совершенный конъюнктивный одночлен, принимающий значение 1 на этом наборе и только на нем, полученные совершенные конъюнктивные одночлены соединить знаками дизъюнкциии.

Правило (алгоритм) отыскания совершенной конъюнктивной нормальной формы для данной формулы: нужно выбрать все те наборы значений ее переменных, на которых формула принимает значение 0, для каждого такого набора выписать совершенный дизъюнктивный одночлен, принимающий зна­чение 0 на этом наборе и только на нем, полученные совершенные дизъюнктивные одночлены соединить знаками конъюнкции.

Пример. Пусть формула F(X, У, Z) задана следу­ющей таблицей своих значений:

Таким образом, она принимает значения 1 на следующих на­борах значений своих переменных (или при следующих конкрети­зациях): (0, 0, 0), (0, 1,0), (0, 1, 1), (1, 0, 0), (1, 1, 1). Запишем пре­дыдущую формулу разложения в СДН-форму для случая п = 3 и применим ее в нашей ситуации:

F(X,Y,Z)=(Х⁰˄У⁰˄Z⁰) v (Х⁰˄ У¹˄Z⁰) v (Х⁰˄У¹˄Z¹) v (X¹˄У⁰˄Z°) v (Х¹˄У¹ ˄ Z¹) = (¬Х˄¬У˄¬Z)v(¬Х˄У˄¬Z)v (¬Х˄Y˄Z)v(X˄¬У˄¬Z)v(Х˄ У˄ Z).

Пример. Для формулы F(X, У,Z) из предыдущего примера найдем ее СКН-форму. Для этого сначала отметим все те наборы значений переменных, на которых она принимает значение 0: (0, 0, 1), (1, 0, 1), (1, 1, 0). Теперь запишем формулу разложения в СКН-форму для случая п = 3 и применим ее в нашей ситуации:

F(X,Y,Z)=(⁰Х v ⁰У v ¹Z) ˄ (¹Х v ⁰У v ¹Z) ˄ (¹Х v ¹У v ⁰Z) =

= (ХvУv¬Z) ˄ (¬Хv Уv ¬Z) ˄ (¬Хv ¬УvZ).

Второй способ приведения формул алгебры высказываний к с вершенной нормальной форме основан на равносильных преобразованиях данной формулы. В этом случае формула должна быть задана в аналитической форме. Для приведения формулы к совершенной нормальной форме нужно сначала привести ее к дизъюнктивной (или конъюнктивной) нормальной форме. Отметим, что одной из сфер применения нормальных форм является та, где требуется получить аналитическое выражение для формулы алгебры высказываний, которая задана своей таблицей значений (таблицей истинности).

Тема: «Булевы функции»

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

Элементы двухэлементного множества будем обозначать 0 и 1. Таким образом f: {0,1}→{0,1}. Нетрудно перечислить все буле­вы функции от одного аргумента:

Составленная таблица означает, что, например, булева функ­ция f₂ на аргументах 0 и 1 действует следующим образом: f₂(0) =1 и f₂(1) = 0. Всего имеется четыре различных булевых функций от одного аргумента:

f₀(x) =0 — функция, тождественно равная 0 (тождественный нуль);

f₁(x)=х — тождественная функция;

f₂(х) = х — функция, называемая отрицанием;

f₃(х) = 1 — функция, тождественно равная 1 (тождественная единица).

Булевой функцией от двух аргументов называется функция f, заданная на множестве {0,1} х {0,1} и принимающая значения в двухэлемент­ном множестве {0,1}. Другими словами, булева функция от двух аргументов сопоставляет любой упорядоченной паре, составленой элементов 0 и 1 (а таких упорядоченных пар будет четыре), ниш о, либо 1.

Перечислим все возможные булевы функции от двух аргумен­тов в форме следующей таблицы:

Заметим: функции пронумерованы так, что номер функции, за­писанный в двоичной системе счисления, дает последовательность значений соответствующей функции. Например, двоичная запись числа 13имеет вид: 1101. Соответствующая функция f₁₃(x, у) прини­май следующие значения: f₃(0, 0)=1, f₁₃(0,1)=1, f₃(1, 0)=0, f₃(1,1) = 1.

f₀(x,у)=0 и f₁₅(x,у)=1 - тождественный ноль и тождественная единица;

f₁(x, у) называется конъюнкцией;

f₁₄ (x, у)=х  у, называется штрихом Шеффера или отрицание конъюнкции;

f₇(x, у) = х v у называется дизъюнкцией;

f₈(x, у) = х↓у, называется стрелкой Пирса (функция Вебба) или отрицание дизъюнкции;

f₁₃(x, у)=х→у, называется импликацией;

f₁₁(x, у) =х←у, называется антиимпликацией или обратной импликацией; потому что представляет собой импиликацию с по­сылкой у и следствием х.

f ₉ (х, у) называется эквивалентностью и обозначает­ся х ↔у

f ₆(x, у), являющаяся отрицанием функции f ₉ (х, у), называется сложением по модулю два, или суммой Жегалкина, и обозначается х+ у.

f _l2(x, у) = х' – отрицание х.

f _l0(x, у) = у' – отрицание у.

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

а) (идемпотентность дизъюнкции и конъюнкции);
б) (коммутативность дизъюнкции и конъюнкции);
в) (ассоциативность дизъюнкции и конъюнкции);
г) ;
д) ;
е) (дистрибутивность дизъюнкции относительно конъюнкции и дистрибутивность конъюнкции относительно дизъюнкции);
ж) (законы поглощения);
з) (законы де Моргана);
и) ;
к) .

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

а) ;
б) (коммутативность эквивалентности);
в) (ассоциативность эквивалентности);
г) ;
д) ;
е) ;
ж) ;
з) ;
и) ;
к) ;
л) ;
м) ;
н) .

Теорема. Справедливы следующие равенства, выражающие одни булевы функции через другие:

а) ;
б) ;
в) ;
г) ;
д) ;

е) x↔y=(x→y)∙(y→x);
ж) ;
з) ;
и) ;
к) ;
л) ;
м) .

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

Булевы функции широко применяются при описании работы дискретных управляющих систем (контактных схем, схем из функциональных элементов, логических сетей и т.д.), при исследовании некоторых электрических цепей, так называемых релейно-контактных схем.

Под релейно-контактной схемой понимается Устройство из проводников и двухпозиционных контактов. Оно может быть предназначено, например, для соединения (или разъединения) полюсов источника тока с некоторым потребителем. Контакты релейно-контактной схемы могут быть двух типов: замыкающие и размыкающие. Каждый контакт подключен к некоторому реле (переключателю). К одному реле может быть подключено несколько контактов — как замыкающих, так и размыкающих. Технически реле представляет собой катушку с металлическим сердечником (магнитопроводом), вблизи которого находится соответствующий контакт.

Когда через катушку пропускается электрический ток, металлический сердечник намагничивается и замыкает все находящиеся при нем замыкающие контакты. Одновременно все размыкающие контакты, относящиеся к данному реле, размыкаются. Поскольку замыкающие контакты при отсутствии в реле электрического тока разомкнуты, то они называются также нормально разомкнутыми. Аналогично, размыкающие контакты называются также нормально замкнутыми. При обесточивании обмоток реле (т.е. когда реле отключается) все замыкающие контакты снова размыкаются, а все размыкающие, замыкаются.

Каждому реле ставится в соответствие своя булева переменная х₁, или х₂, …или х_n, которая принимает значение 1, когда реле срабатывает, и принимает значение 0 при отключении реле. На чертеже все замыкающие контакты, подключенные к реле х, обозначаются тем же символом х, а все размыкающие контакты, подключенные к этому реле, обозначаются отрицанием х^/. Это означает, что при срабатывании реле  х все его замыкающие контакты х проводят ток и им сопоставляется значение 1, а все размыкающие контакты  х^/ не проводят электрический ток и им сопоставляется значение 0. При отключенном реле  создается противоположная ситуация: все его замыкающие контакты х разомкнуты, т. е. в этот момент им сопоставляется (переменная  принимает) значение 0, а все его размыкающие контакты  замкнуты, т. е. в этот момент им сопоставляется (другими словами, переменная х^/ принимает) значение 1.

Всей релейно-контактной схеме тогда ставится в соответствие булева переменная у, зависящая от булевых переменных х₁,  х₂, … х_n, сопоставленным тем реле, которые участвуют в схеме. Если при данном наборе состояний реле х₁,  х₂, … х_n (некоторые из этих реле находятся в рабочем состоянии под током, остальные отключены, т.е. "обесточены") вся релейно-контактная схема проводит электрический ток, то переменной  ставится в соответствие (другими словами, переменная  принимает) значение 1. Если же при этом наборе состояний реле  х₁,  х₂, … х_n схема не проводит электрический ток, то считаем, что переменная у принимает значение 0. Поскольку каждый набор состояний реле х₁,  х₂, … х_n характеризуется набором, составленным из нулей и единиц и имеющим длину n, то данная релейно-контактная схема определяет некоторое правило, по которому каждому такому набору длины n, составленному из нулей и единиц, сопоставляется либо 0, либо 1. Таким образом, каждая релейно-контактная схема, в которой занято независимых реле (контактов в ней может быть  n или больше), определяет некоторую булеву функцию  y от  n аргументов. Она принимает значение 1 на тех и только тех наборах значений аргументов х₁,  х₂, … х_n, которые соответствуют тем состояниям реле , при которых данная схема проводит электрический ток. Такая булева функция  y=f(х₁,  х₂, … х_n ) называется функцией проводимости данной релейно-контактной схемы.

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

Рассмотрим некоторые релейно-контактные схемы и найдем их функции проводимости. Первая схема состоит из двух последовательно соединенных контактов  x и y, т. е. контактов, связанных с двумя независимыми реле  x и y, каждое из которых срабатывает независимо от другого:

Ясно, что данная схема проводит электрический ток тогда и только тогда, когда оба контакта  x и y  замкнуты, т. е. только тогда, когда оба переменных x и y  принимают значение 1. Булева функция от двух аргументов x и y, удовлетворяющая такому условию, нам хорошо известна. Это конъюнкция x∙y. Таким образом, функцией проводимости релейно-контактной схемы, состоящей из двух последовательно соединенных контактов x и y, является конъюнкция. Говорят, что последовательное соединение двух контактов реализует конъюнкцию соответствующих этим контактам булевых переменных.

Вторая релейно-контактная схема состоит из двух параллельно соединенных контактов  x и y:

Ясно, что эта схема проводит электрический ток в том и только в том случае, когда по меньшей мере один из контактов (х или у) замкнут, т.е. лишь в случае, когда хотя бы одна из булевых переменных ( х или у) принимает значение 1. Булева функция от двух аргументов  x и y , удовлетворяющая этому условию, также хорошо нам известна. Это, дизъюнкция. Таким образом, функцией проводимости релейно-контактной схемы, состоящей из двух параллельно соединенных контактов x и y, является дизъюнкция. Говорят, что параллельное соединение двух контактов реализует дизъюнкцию соответствующих этим контактам булевых переменных.

Итак, с помощью релейно-контактных схем можно реализовывать булевы функции: конъюнкцию, дизъюнкцию и отрицание. Поскольку всякая булева функция может быть выражена через конъюнкцию, дизъюнкцию и отрицание, причем отрицание стоит лишь непосредственно около переменных и не стоит ни около каких внутренних скобок, а конъюнкция, дизъюнкция и отрицание, как показано только что, реализуются на релейно-контактных схемах, то и всякая булева функция может быть реализована с помощью релейно-контактной схемы, т. е. может быть построена такая схема, для которой данная булева функция служит функцией проводимости.

Реализуем, например, в виде релейно-контактных схем булевы функции — импликацию и эквивалентность. Для этого выразим их через конъюнкцию, дизъюнкцию и отрицание. Такие выражения известны: , x↔y=(x→y)∙(y→x)=(х^/˅у) ∙(у^/˅х). Предлагается самостоятельно нарисовать схему, реализующую функцию x→y. Релейно-контактная схема, реализующая функцию x↔y, будет состоять из двух последовательно соединенных ветвей, первая из которых реализует булеву функцию (х^/˅у), а вторая — булеву функцию (у^/˅х). В свою очередь, первая из ветвей будет состоять из двух параллельных участков, один из которых содержит контакт х^/, а второй — контакт у. Аналогично, вторая ветвь также будет состоять из двух параллельных участков, один из которых содержит контакт х, а другой — контакт у^/. Изображаем полученную релейно-контактную схему (чтобы упростить рисунки, не будем изображать сами контакты, а ограничимся символом булевой переменной, соответствующей данному контакту):

Составление релейно-контактных схем с заданными условиями работы называется задачей синтеза релейно-контактных схем и является первой важной задачей, состоящей в том, что требуется построить схему, которая проводила бы электрический ток лишь при вполне определенных задаваемых условиях.

Естественно было бы выбирать для каждой булевой функции самую простую или одну из самых простых реализующих ее релейно-контактных схем. Поэтому упрощение релейно-контактных схем называется задачей анализа таких схем и является второй важной задачей теории релейно-контактных схем. Две релейно-контактные схемы, составленные из одних и тех же реле, называются равносильными, если одна из них проводит ток тогда и только тогда, когда другая схема проводит ток. Другими словами, две схемы, составленные из одних и тех же реле, равносильны, если они обладают одинаковыми функциями проводимости, зависящими от одних и тех же переменных. Из двух равносильных схем более простой считается та, которая содержит меньшее число контактов. Задача упрощения релейно-контактной схемы состоит в нахождении более простой равносильной ей схемы. Обычно она решается следующим образом. Для данной релейно-контактной схемы записывается ее функция проводимости. Затем эта функция с помощью тождественных преобразований, использующих известные свойства булевых функций, упрощается, т.е. сводится к функции, имеющей меньшее число вхождений переменных, нежели исходная функция. Наконец строится релейно-контактная схема, отвечающая упрощенной булевой функции.

Тема: «Предикаты»

1. Понятие предиката. Логические операции над предикатами.

В высказывании все четко: это — конкрет­ное утверждение о конкретных объектах — истинное или ложное. Предикат — предложение, похожее на высказывание, но все же им не являющееся: о нем нельзя судить, истинно оно или ложно. Дадим точное определение.

Определенным на множествах М₁, М₂, ..., М_п п-местным предикатом называется предложение, содержащее п переменных х₁, х₂, ..., х_п, превращающееся в высказывание при подстановке вместо этих переменных любых конкретных элемен­тов из множеств М₁, М₂, ..., М_п соответственно.

Для п -местного предиката будем использовать обозначение Р(х₁, х₂, ..., х_п). Переменные х₁, х₂, х_п называют предметными, а элементы множеств М₁, М₂, ..., М_п, которые эти переменные про­бегают, — конкретными предметами. Всякий п-местный предикат Р(х₁, х₂,… х_п), определенный на множествах М₁, М₂, ..., М_п представляет собой функцию п аргументов, заданную на указан­ных множествах и принимающую значения в множестве всех высказываний. Поэтому предикат называют также функцией-выска­зыванием.

Например. Предложение «Река х впадает в озеро Байкал» является одноместным предикатом, определенным над множеством всех названий рек. Подставив вместо предметной пе­ременной х название «Баргузин», получим высказывание «Река Баргузин впадает в озеро Байкал». Это высказывание истинно. Поставив вместо предметной переменной х название «Днепр», полу­чим ложное высказывание «Река Днепр впадает в озеро Байкал».

Отметим еще один подход к понятию предиката. Как отмеча­лось, предикат Р(х₁, х₂,… х_п), определенный на множествах М₁, М₂, ..., М_п, превращается в конкретное высказывание Р(а₁, а₂, ..., а_п), если вместо предметных переменных х₁, х₂,… х_п подставить в него конкретные предметы (элементы а₁, а₂, ..., а_п) из множеств М₁, М₂, ..., М_п соответственно. Это высказывание может быть либо истинным, либо ложным, т.е. его логическое значение равно 1 или 0. Следовательно, данный предикат определяет функцию п аргумен­тов, заданную на множествах М₁, М₂, ..., М_п и принимающую зна­чение в двухэлементном множестве {0, 1}. Иногда эту функцию и называют предикатом.

Предикат Р(х₁, х₂,… х_п), заданный на множествах М₁, М₂, ..., М_п, называется:

а) тождественно истинным, если при любой подстановке вместо

переменных х₁, х₂,… х_п любых конкретных предметов а₁, а₂, ..., а_п из множеств М₁, М₂, ..., М_п соответственно он превращается в истинное высказывание Р(а₁, а₂, ..., а_п);

б) тождественно ложным, если при любой подстановке вмес­то переменных х₁, х₂,… х_п любых конкретных предметов из мно­жеств М₁, М₂, ..., М_п соответственно он превращается в ложное высказывание;

в) выполнимым (опровержимым), если существует по меньшей мере один набор конкретных предметов а₁, а₂, ..., а_п из мно­жеств М₁, М₂, ..., М_п соответственно, при подстановке которых вместо соответствующих предметных переменных в предикат Р(х₁, х₂,… х_п) последний превратится в истинное (ложное) выска­зывание Р(а₁, а₂, ..., а_п).

Например. Одноместный предикат «Город х распо­ложен на берегу реки Волги», определенный на множестве назва­ний городов, является выполнимым, потому что существуют го­рода, названия которых превращают данный предикат в истин­ное высказывание, или, иначе, удовлетворяют этому предикату (например, Ульяновск, Саратов и т. д.). Но данный предикат не будет тождественно истинным, потому что существуют города, названия которых превращают его в ложное высказывание, или, иначе, не удовлетворяют этому предикату (например, Прага, Якутск и т.д.). Этот же предикат являет собой пример опровержи­мого, но не тождественно ложного предиката.

Логические операции

1) Отрицанием п-местного предиката Р(х₁, х₂, ..., х_п), определенного на множествах М₁, М₂,…, М_п, называется новый п-местный предикат, определен­ный на тех же множествах, обозначаемый ¬Р (х₁, х₂, ..., х_п) (читается: «неверно, что Р(х₁, х₂, ..., х_п)»), который превращается в истинное высказывание при всех тех и только тех значениях пред­метных переменных, при которых исходное высказывание превращается в ложное высказывание.

Например, нетрудно понять, что отрицанием одноместного предиката

«х ≤3», определенного на множестве R, является одно­местный предикат

«х 3», определенный на том же множестве R. Отрицанием предиката «Река х впадает в озеро Байкал» является предикат «Река х не впадает в озеро Байкал» (оба одноместных предиката определены на множестве названий рек).

2) Конъюнкцией п- местного предиката Р(х₁, х₂, ..., х_п), определенного на множествах М₁, М₂,…, М_п, и т-местного предиката Q(y₁, у₂, …, у_т), определенный на множествах N₁, N₂, ..., N_m, называется новый (п + т) -местным предикат, определенный на множествах М₁, М₂,…, М_п, N₁, N₂, ..., N_m, обозначаемый Р(х₁, х₂, ..., х_п) ^ Q(y₁, у₂, …, у_т) (читается «Р(х₁, х₂, ..., х_п) и Q(y₁, у₂, …, у_т)»), который превращается в истинное высказывание при всех тех и только тех значениях предметных переменных, при которых оба исходных предиката пре­вышаются в истинные высказывания.

Например, конъюнкцией двух одноместных предикатов «х -3» и «х3», определенных на R, будет одноместный предикат «(х -3)^(х х 3», который равносилен предикату «|х|