авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 || 3 | 4 |   ...   | 5 |

«УДК 002; 004.3(075.8) МИНОБРНАУКИ РОССИИ ББК 32.81; 32.97я73 ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ ...»

-- [ Страница 2 ] --

В-третьих, каждая формальная аксиоматическая теория должна располагать конечным множеством правил вывода, устанавливающих отношения между формулами. Каждое прави ло вывода представляет собой утверждение, указывающее, что одна формула, называемая заключением, при определенных этим правилом условиях выводится из некоторой совокуп ности других формул, называемых посылками правила. Формула – заключение называется также непосредственным следствием формул- посылок по данному правилу вывода.

Понятия формулы, аксиомы и правила вывода должны быть определены эффективно.

Под эффективностью здесь понимаются не какие-то количественные характеристики, а су ществование процедур, позволяющих за конечное число шагов получить ответы на вопросы:

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

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

мож но ли рассматривать данную совокупность формул как посылки и заключение по данному правилу вывода? То есть эффективность понимается как принципиальная возможность по лучения ответов на эти вопросы.

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

Формула A называется теоремой теории тогда и только тогда, когда существует дока зательство, в котором заключительной формулой является формула A. Такое доказательство называется доказательством формулы A.

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

Формула A называется выводимой из множества формул Г (следствием множества формул Г) в данной теории, если существует последовательность A1,...An формул такая, что An есть A и для любого i формула Ai есть либо аксиома, либо одна из формул множества Г, либо непосредственное следствие предыдущих формул последовательности по одному из правил вывода. В этом случае последовательность формул A1,...An называется выводомфор мулы A из Г. Формулы множества Г называются гипотезами (допущениями, посылками) вы вода.

Для сокращения записи утверждения "A есть следствие множества формул Г" употреб ляется обозначение Г | A. Если множество Г конечно, Г = {B1,...Bn}, то вместо {B1,...Bn} | A пишут B1,...Bn | A. Если Г – пустое множество (вывод является доказательством), то пишут | A, что равнозначно утверждению "A есть теорема".

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

1. Правило повторения посылки: Г, A | A.

2. Правило введения посылки: если Г | B, то Г, A | B.

3. Правило удаления посылки: если Г, A | B и Г | A, то Г | B.

4. Правило силлогизма: если Г | A1,..., Г | Ak и A1,..., Ak | B то Г | B.

2.1.2. Булевы функции 2.1.2.1. Высказывание. Логические операции Высказыванием называется любое повествовательное предложение, которое истинно либо ложно.

Примерами высказываний в математической логике являются следующие предложе ния:

Сократ – человек.

2 + 2 = 4.

5 7.

Не являются высказываниями в математической логике предложения:

х 5 (здесь х (–, ) и считается переменной).

Закройте книгу!

Данное предложение ложно.

Какое же у меня есть дело на земле?

Высказывания будем обозначать заглавными печатными латинскими буквами (А, B, С,...) и этими же буквами с числовыми индексами.

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

Таким образом, высказывание рассматривается как величина, которая может прини мать два значения: «истина» либо «ложь». В дальнейшем для краткости будем обозначать значение «истина» через И, а «ложь» – Л. Если высказывание А истинное, то будем говорить, что А принимает значение И (истина), и писать: А = И. Если высказывание А ложное, то бу дем говорить, что А принимает значение Л (ложь), и писать: А = Л. Заметим, что мы не будем определять, что такое истина и что такое ложь, но считаем себя способными охарактеризо вать некоторые высказывания как истинные, другие – как ложные.

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

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

отрицанием для высказывания «2 – четное число» может служить: «2 не является четным числом», «неверно, что 2 – четное число», «не имеет места, что 2 – четное число» и т.п. Мы будем строить отрицание для данного высказывания одним способом, помещая знак отрица ния перед всем высказыванием.

Отрицание – логическая операция, с помощью которой из данного высказывания А об разуется новое высказывание, обозначаемое А, которое истинно тогда и только тогда, когда А ложно. Следовательно, имеем следующую таблицу, которая называется таблицей истинно сти.

A A И Л Л И Высказывание А читается «не А» и логическая операция отрицания соответствует об разованию нового высказывания из высказывания А с помощью частицы «не». Отрицание является одноместной логической операцией. Другие логические операции, которые введем ниже, – двуместные операции, сложное высказывание строится из двух данных высказыва ний А и В.

2. Конъюнкция – логическая операция, с помощью которой из двух данных высказыва ний А и В образуется новое высказывание, обозначаемое А&В, которое истинно тогда и только тогда, когда А и В оба истинны.

Высказывание А&В читается «А и В» и называется конъюнкцией А и В, а А и В называ ются конъюнктивными членами. По определению конъюнкции имеем следующую таблицу истинности.

Для конъюнкции высказываний А и В в литературе встречаются и другие обозначения, например: А В, А В или просто АВ.

Из определения следует, что операция конъюнкция соответствует образованию нового высказывания из двух данных соединением их союзом "и". Выражение А&В может служить обозначением не только для высказывания А и В, но и для высказываний: «как А, так и В»;

«А вместе с В»;

«А, в то время как В»;

«не только А, но и В», «А, хотя и В». Очевидно, что этот список можно продолжить.

Однако, А&В не является моделью для каждого случая употребления союза «и». Пояс ним это. Согласно определения конъюнкции истинностные значения А&В и В&А одинаковы, т.е. А&В и В&А понимаются как равносильные (равнозначные) высказывания. В то же время высказывания «Таня проснулась и солнце взошло над горизонтом», «Солнце взошло над го ризонтом и Таня проснулась» понимаются как различные. Также различны высказывания «Иванову стало жарко и он пошёл искупаться», «Иванов пошёл искупаться и ему стало жар ко».

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

Высказывание «А В» читается «А или В», а А и В называются дизъюнктивными члена ми. Из определения видно, что операция дизъюнкции соответствует образованию нового вы сказывания из данных А и В соединением их связкой «или», где «или» понимается в соеди нительном (хотя бы одно), а не в разделительном (либо – либо) смысле.

Согласно определению дизъюнкции получим таблицу истинности:

A B A Л Л Л Л И И И Л И И И И Другие, кроме А В, обозначения дизъюнкции в литературе встречаются очень редко, например, дизъюнкцию А В обозначают иногда А В или А + В.

4. Прежде чем ввести следующую операцию, отметим, что в разговорной речи, а также в литературном языке мы привыкли к тому, что в высказываниях «если А, то В» между по сылкой А и заключением В имеется определенная (обычно причинная) связь. Если же такого рода связи между А и В нет, то не всегда ясно, истинно либо ложно высказывание «если А, то В». Неясно, например, истинными или ложными будут высказывания:

1) если 2 х 2 = 4, то Л. Н. Толстой – автор романа «Война и мир», 2) если 2 х 2 4, то Л. Н. Толстой – автор романа «Война и мир», 3) если 2 х 2 4, то А. П. Чехов – автор романа «Война и мир».

Введем правила, по которым можно будет определять истинность высказывания «если А, то В», зная только истинностные значения А и В вне зависимости от того, существует ли между А и В какая-нибудь содержательная связь или нет.

Импликация (следование) – логическая операция, с помощью которой из двух данных высказываний А и В образуется новое высказывание, обозначаемое А В, которое ложно то гда и только тогда, когда посылка А истинна, а заключение В ложно.

Высказывание А В читается «если А, то В» или «из А следует В» и называется импли кацией А и В.

Согласно определению импликации получим таблицу истинности:

A B AB Л Л И Л И И И Л Л И И И Из определения следует, что если посылка А ложна, то вне зависимости, истинно или ложно В, высказывание А В считается истинным, т.е. из лжи следует что угодно. Таким образом, высказывания 1 – 3 будут считаться истинными.

Такое определение истинности высказывания «если А, то В» не противоречит обычной практике. Иногда встречается некоторое не истинностно-функциональное употребление связки «если..., то...», связанное с законами причинности и в так называемых условных кон трафактических предложениях. Но мы будем использовать, введенную импликацию, только там где не используются законы причинности и условные контрафактические предложения.

Другие обозначения импликации (следования): А В, А В.

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

Высказывание А В читается «А тогда и только тогда, когда В» и называется эквива лентностью А и В. Другие обозначения для А В: А В, АВ, А В.

Из определения эквивалентности получаем следующую таблицу истинности.

A B AB Л Л И Л И Л И Л Л И И И Таким образом, для произвольных данных высказываний, введены пять операций. С помощью этих операций из данных высказываний можно образовать новые, более сложные высказывания, истинность или ложность которых можно выяснить по таблицам истинности.

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

2.1.2.2. Пропозициональные буквы, связки и формы (формулы логики высказы ваний). Построение таблиц истинности Символы, &,,, называются пропозициональными связками.

Заглавные буквы алфавита (А, В, С,...) и те же буквы с числовыми индексами (А1, А2,..., В1, В2,..., С1, С2,...) называются пропозициональными буквами. Считается, что каждая пропо зициональная буква может принимать значение И либо Л.

Выражением называется конечная последовательность определенных символов. На пример, А& В – выражение, построенное из символов, &, А и В, а ? !! – выражение, по строенное из символов ?, и !.

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

Индуктивное определение пропозициональной формы:

1) все пропозициональные буквы суть пропозициональные формы, 2) если А и В пропозициональные формы, то ( А), (А&В), (А В), (А B), (А B) тоже пропозициональные формы, 3) только те выражения являются пропозициональными формами, для которых это сле дует из пп.1,2.

Примеры пропозициональных форм: A, (В), ((А&В) (C)), ((( А) В) С).

Пропозициональные формы часто называют формулами логики высказываний.

Жирные заглавные буквы латинского алфавита (А, В, C,...) или те же буквы с числовы ми индексами (А1, А2,..., В1, В2,..., С1, С2,...) употребляются для обозначения произвольных пропозициональных форм, тогда как обычное написание этих букв применяется лишь для пропозициональных букв.

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

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

Как определено выше, каждая пропозициональная буква может принимать значения И либо Л. Будем считать, что пропозициональные формы (А), (А&В), (А В), (А В) и (А ) имеют те же таблицы истинности, что и обозначаемые таким образом высказывания (см. 1).

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

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

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

букв А, В, С,..., А1, А2,..., В1, В2,..., С1, С2,... с помощью пропозициональных связок согласно правилам 1, 2, 3 и ничего более. В частном случае пропозициональные буквы могут обозна чать высказывания, пропозициональные связки – логические операции, тогда пропозицио нальная форма будет обозначать некоторое высказывание. Истинностное значение получен ного высказывания можно определить с помощью таблиц истинности.

Так как добавление каждой новой пропозициональной буквы увеличивает количество строк в таблице истинности вдвое, то пропозициональная форма, содержащая n различных n пропозициональных букв, имеет таблицу истинности с 2 строками. Например, для формы (((А&В) С) А) имеем следующую таблицу истинности.

(A&B) А B C ((А&В) С) (((А&В) С) А) Л Л Л Л Л И Л Л И Л И Л Л И Л Л Л И Л И И Л И Л И Л Л Л Л И И Л И Л И И И И Л И И И И И И И И И Составление таблицы истинности можно сократить, выписывая шаг за шагом под каж дой пропозициональной связкой истинностные значения той составляющей пропозицио нальной формы, для которой применяется эта связка. Например, для той же формы (((А&В) С) А) получаем таблицу:

A B C (((А & В) С) А) Л Л Л ЛЛИ Л Л И ЛИЛ Л И Л ЛЛИ Л И И ЛИЛ И Л Л ЛЛИ И Л И ЛИИ И И Л ИИИ И И И ИИИ Следующий метод построения таблиц истинности, называют алгоритмом Квайна. В форме выбирается некоторая буква, например, та буква, которая чаще всего встречается в рассматриваемой форме. Выбранной букве (для формы D = (((А&В) С) А) это будет буква А) приписывается значение И либо Л. Далее проводят вычисления, где возможно, при вы бранном значении этой буквы. Если А = И, то для формы D = (((А&В) С) А), вне зависимо сти от значении букв В и С, легко получить, что D = И. При А = Л и С = Л получим снова, что D = И. Наконец, если А = Л и С = И, то D = Л. В результате получим сокращенную запись таблицы истинности содержащую всего три строки (в данном случае результат не зависит от значений буквы В, а при А = И не зависит и от значений С):

A B C (((А&В) С) А) Л Л И Л И Л И И 2.1.2.3. Упрощения в записях пропозициональных форм Введем некоторые соглашения о более экономном употреблении скобок в записях форм. Эти соглашения облегчат нам чтение сложных выражений.

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

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

Пример. А В С А пишется вместо (((А В) С) А), а В В А (С А) пишется вместо (((В В) А) (С А)).

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

Каждое вхождение знака относится к наименьшей пропозициональной форме, сле дующей за ним;

после расстановки всех скобок, относящихся ко всем вхождениям знака, каждое вхождение знака & связывает наименьшие формы, окружающие это вхождение;

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

Пример 2.1. В форме А А&В С D скобки восстанавливаются следующими шагами:

А (А)&В С (D), А ((А)&В) С (D), А ((А)&В) (C (D)), А ((( А)&В) (С (D))), (А ((( А)&В) (С (D)))).

Однако не всякая форма может быть записана без скобок. Например, нельзя опустить оставшиеся скобки в формах: А&(В С), А (В C), (А В).

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

Таблица истинности тавтологии имеет результирующий столбец, состоящий только из И.

Примером тавтологии является пропозициональная форма (А А), в чем легко убедить ся, составив таблицу истинности. Другие примеры тавтологий: А А, (А В) (В А).

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

Примеры противоречий: А&А, (А А), (А А).

Истинностная таблица для противоречия, очевидно, имеет в результирующем столбце только значения Л.

Очевидно, что пропозициональная форма А является тавтологией тогда и только тогда, когда А есть противоречие.

Тавтологию будем обозначать через Т, а противоречие – через П.

Сформулируем и докажем две несложные теоремы.

Теорема 2.1. Если А и (А В) – тавтологии, то В – тавтология.

Доказательство. Пусть А и (А В) – тавтологии. Допустим, что при некотором распре делении истинностных значений для пропозициональных букв, входящих в А и В, В прини мает значение Л. Поскольку А есть тавтология, то при этом распределении истинностных значений А принимает значение И. Тогда (А В) получит значение Л. Это противоречит предположению о том, что (А В) есть тавтология. Теорема доказана.

Теорема 2.2. Если А есть тавтология, содержащая пропозициональные буквы А1, А2,..., Аn, и В получается из А подстановкой в А пропозициональных форм А1, А2,... Аn вместо букв А1, А2,..., Аn соответственно, то В есть тавтология, т.е. подстановка в тавтологию приводит к тавтологии.

Доказательство. Пусть задано произвольное распределение истинностных значений для пропозициональных букв, входящих в В. Формы А1, А2,..., Аn примут тогда некоторые значения х1, х2,..., хn (каждое хi есть И или Л). Если мы придадим значения х1, х2,..., хn соответ ственно буквам А1, А2,..., Аn, то так как А есть тавтология, то А будет истинно, и это же зна чение принимает В. Таким образом, при произвольных значениях пропозициональных букв форма В принимает значение И, что и требовалось доказать.

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

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

Например, высказывание: "Если Иванов – студент, то Иванов – студент".

Всегда истинно (логически истинно), в то время как высказывание: "Иванов – студент", если и истинно, то в силу уже других причин.

Высказывание, которое можно получить с помощью подстановки в противоречие, на зывается логически ложным высказыванием. Примером логически ложного высказывания может служить высказывание: "2 х 2 = 4 и 2 х 2 4", где имеет место одновременно какое-то высказывание и отрицание этого же высказывания.

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

Например, А&В является выполнимой пропозициональной формой, так как принимает значения И, когда А = И и В = И, а форма А&А не будет выполнимой, так как всегда ложна.

Очевидно, что пропозициональная форма А выполнима тогда и только тогда, когда А не является противоречием.

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

Ясно, что выяснение выполнимости А равносильно выяснению, является ли А противо речием или нет, что, в свою очередь, равносильно выяснению, является ли А тавтологией или нет. Таким образом, если есть метод, позволяющий для произвольной формы конечным числом действий выяснить, тавтология это или нет, то можно решить вопрос выполнима или нет произвольная форма А. Для этого достаточно выяснить А – тавтология или нет. Если А – тавтология, то А – противоречие, следовательно, А невыполнимо, если же А – не тав тология, то А выполнимо.

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

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

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

Например, форма А В равносильна форме А В, в чем легко убедиться с помощью таблиц истинности:

A B ИЛ И Л ИЛ И И ЛИ Л Л ЛИ И И A B Л И Л Л И И И Л Л И И И В этих таблицах результирующие столбцы совпадают, т. е. при одинаковых значениях букв А и В значения форм А В и А В равны, следовательно, эти формы равносильны. Да лее, форма А А&В равносильна А. Действительно, имеем следующую таблицу:

A A & B A Л Л Л Л Л Л Л Л Л Л И Л И И И Л Л И И И И И И И Также, очевидно, А А равносильно В В.

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

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

Высказывание "А равносильно В" будем обозначать следующим образом: А ~ B.

Пусть А, В, C – произвольные пропозициональные формы. Отношение равносильности пропозициональных форм, как легко видеть, обладает следующими свойствами:

1) А ~ А – рефлексивность;

2) если А ~ В, то В ~ А – симметричность;

3) если А ~ В и В ~ C, то А ~ C – транзитивность.

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

Теорема 2.3. Пропозициональные формы А и В равносильны тогда и только тогда, ко гда А В является тавтологией.

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

Достаточность. Пусть А В тавтология, т.е. принимает всегда значение И. Это озна чает, что А и В имеют всегда одинаковые истинностные значения, т.е. они равносильны. Тео рема доказана.

2.1.2.6. Важнейшие пары равносильных пропозициональных форм Пусть А, В, С – пропозициональные буквы, Т – тавтология и П – противоречие. Исполь зуя таблицу истинности, легко показать, что 1) ( А) равносильно А.

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

Аналогичным образом можно показать, что имеют место следующие законы.

2) А В ~ B A;

законы коммутативности;

3) А В ~ B A;

4) ( А В) C ~ A ( B C );

законы ассоциативности;

  5) ( А В) C ~ A ( B C );

6) A ( В C ) ~ A B A C первый закон дистрибутивности;

7) A ( В C ) ~ ( A B) ( A C ) второй закон дистрибутивности;

8) ¬( A В) ~ ¬A ¬B, законы де Моргана;

  9) ¬( A В) ~ ¬A ¬B 10) A A ~ A, законы идемпотентности;

11) A A ~ A, 12) A ¬A ~ T закон исключения третьего;

13) A ¬A ~ П закон противоречия 14) A Т ~ А;

15) A Т ~ T ;

свойство операций с Т и с П;

16) A П ~ П ;

17) A П ~ А 18) A A В ~ A;

законы поглощения;

19) A ( A В) ~ A;

20) A B ~ ¬B ¬A закон контропозиции.  Как уже замечено выше, соотношения 1) – 20) доказываются с помощью таблиц истин ности.

Можно показать, что соотношения 1) – 20) будут иметь место и тогда, когда вместо пропозициональных букв А, В и С будут подставлены произвольные пропозициональные формы. Соотношения 1) – 20) позволяют находить для заданных пропозициональных форм равносильные упрощенные формы или равносильные формы, имеющие более удобный с не которых позиций вид. Из этих же соотношений видно, что над пропозициональными форма ми можно производить преобразования: раскрытие скобок, заключение в скобки, вынесение за скобки общего множителя.

Из соотношений 2) – 6) видно, что операция & напоминает умножение (обладает неко торыми свойствами умножения), а – сложение, поэтому часто конъюнкцию двух высказы ваний называют (логическим) произведением их, а дизъюнкцию – (логической) суммой.

2.1.2.7. Зависимости между пропозициональными связками Связки ¬, &,, =, не являются независимыми друг от друга в том смысле, что одни из них можно выражать через другие так, что при этом получаются равносильные пропози циональные формы.

Например, связка может быть выражена через связки и & на основании соотноше ния:

А В ~ (А В) & (В А). (2.1) Для доказательства (1.1) достаточно составить таблицы истинности и убедиться, что результирующие столбцы этих таблиц совпадают.

Для импликации имеем:

(2.2) А В ~ ¬ А В.

Таким образом, связку можно выразить через ¬, & и :

А В ~ (¬ А В) & (¬ В А). (2.3) Так как А равносильно ¬ (¬ А), то А&В равносильно ¬ (¬ А)&¬ (¬ В), а последнее со гласно закону де Моргана равносильно ¬ (¬ А ¬ В), следовательно, А&В ~ ¬ (¬ А ¬ В). (2.4) Из (1.4) видно, что & можно выразить через ¬ и. Покажем, что можно выразить че рез ¬ и &. Действительно, так как А равносильно ¬ (¬ А), то А В равносильно ¬ (¬ А) ¬(¬ В), последнее по закону де Моргана равносильно ¬ (¬ А&¬ В). Итак, А В ~ ¬ (¬ А &¬ В). (2.5) Из соотношения (1.2) заменой ¬ А на А получаем, что А В ~ ¬ А В. (2.6) Т.е. можно выразить через ¬ и.

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

Теорема 2.4. Для каждой пропозициональной формы А существует равносильная ей форма, содержащая только связки ¬, &,, причем связка ¬ относится только к пропозицио нальным буквам.

Доказательство. Связки и можно исключить согласно соотношениям (2.2) и (2.3).

При этом останутся только связки ¬, &,. Если пропозициональная связка ¬ стоит перед не которой скобкой, например, ¬ (А&В С ¬ В), то на основании законов де Моргана можно внести ¬ под скобки, при этом связка & меняется на, а на &, а связки и нигде не по являются. Внеся ¬ под скобки, перед которыми они стоят, добьемся, чтобы ¬ относилась только к пропозициональным буквам. Теорема доказана.

Теорема 2.5. Для каждой пропозициональной формы А существует равносильная ей форма, содержащая либо только связки ¬, &, либо только ¬,, либо только ¬,.

Доказательство. Покажем, что можно оставить только связки ¬ и &. Связки и можно исключить (если они есть) на основании соотношений (2.2) и (2.3), а затем по (2.5) исключим. В результате останутся только ¬ и &. Остальные случаи доказываются анало гичным образом на основании соотношений (2.1) – (2.6).

Будем рассматривать пропозициональные формы, содержащие только связки ¬, &,.

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

Будем говорить, что связка & двойственна связке, и наоборот.

Пропозициональные формы А и А* называются двойственными, если одна получается из другой заменой каждой связки & и на двойственную.

Например, если А = (А ¬ В)&С, то А* = (А &¬ В) С.

Отношение двойственности взаимно: если А двойственно А*, то А* двойственно А.

Следующую теорему считают законом двойственности.

Теорема 2.6. Если пропозициональные формы А и В равносильны, то и двойственные им формы А* и В* также равносильны.

Доказательство. Пусть А и В равносильны, а А1, А2,..., Аn – буквы, входящие в А или В.

Будем считать, что А1, А2,..., Аn входят и в А, и в В. Если бы это было не так, например, В не содержала бы Аk(1 k n), входящего в А, то В можно заменить равносильной формой В Аk&¬ Аk, содержащей эту букву. Таким образом, всегда можем добиться, чтобы А и B со держали все буквы А1, А2,..., Аn.

По условию А(А1, А2,..., Аn) ~ В(А1, А2,..., Аn). (2.7) Если формы А и В равносильны, то, очевидно, равносильны и их отрицания, поэтому из (2.7) получим, что ¬ А(А1, А2,..., Аn ) ~ ¬ В(А1, А2,..., Аn). (2.8) В пропозициональных формах соотношения (2.8) добьемся, чтобы ¬ относилась только к буквам. При этом согласно законам де Моргана связки & и поменяются на двойственные.

Следовательно, получим А* (¬ А1,¬ А2,...,¬ An) ~ B* (¬ А1,¬ А2,...,¬ An ) (2.9) По определению равносильности форм равносильность А*(¬ А1,¬ А2,...,¬ An) и B*(¬ А1,¬ А2,...,¬ An) означает, что они принимают одинаковые значения при любых совокупностях значений букв А1, А2,..., An. Поэтому, если вместо букв А1, А2,..., An подставить ¬ А1,¬ А2,...,¬ An, то формы останутся равносильными. Учитывая, что ¬ ¬ А равносильно А, из (2.9) полу чим А*(А1, А2,..., Аn ) ~ B*(А1, А2,..., Аn), что и требовалось доказать.

2.1.2.8. Нормальные формы Известно, что в математическом анализе среди всевозможных функций выделяют эле ментарные (основные) функции: степенные, показательные, тригонометрические и т.п. Сре ди пропозициональных форм, выделим некоторые как элементарные, а далее из них можно получать более сложные.

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

Примеры элементарных сумм: А, А В, А В ¬А С.

Примеры элементарных произведений: ¬А, А&В, ¬А&С&А&В.

Теорема 2.7. Чтобы элементарная сумма была тавтологией (общезначимой формулой), необходимо и достаточно, чтобы в ней содержалась хотя бы одна пара слагаемых, из кото рых одно есть некоторая буква, а другое – отрицание этой буквы.

Доказательство. Достаточность. Пусть такая пара букв существует, т.е. сумма имеет вид А ¬А.... Для нас важно, что имеются слагаемые А и ¬А, остальные слагаемые могут быть, но могут и отсутствовать. Форма А и ¬А всегда принимает значение И, поэтому и вся элементарная сумма будет И при любых значениях букв, в нее входящих. Следовательно, наша элементарная сумма – тавтология.

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

Также легко доказать следующую теорему.

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

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

А ¬В,А В&С, ¬А А&С А&В&¬С.

Теорема 2.9. Для каждой пропозициональной формы существует равносильная ей д.н.ф. (не единственная).

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

Пример 2.2. Пусть задана формула ¬(А В)&С. Исключим связку, затем :

¬ ((А В)&(В А))&С, ¬((¬А В)&(¬ В А))&С.

Теперь добьемся, чтобы ¬ относилась только к пропозициональным буквам:

(А&¬ В В&¬А)&С.

Раскрыв скобки, получим А&¬ В&С В&¬А&С. Последнее и есть д.н.ф. Полученная д.н.ф., очевидно, равносильна следующей д.н.ф.: А&¬ В&С ¬А&В&С А&¬А. Из примера видно, что д.н.ф., равносильная заданной форме, определяется не единственным образом.

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

Доказательство. Пусть для А равносильной ей д.н.ф. является форма В 1 В2... Вk (k 1), (2.10) где Вi (1 i k) есть элементарное произведение. Дизъюнкция (2.10) будет противоречием тогда и только тогда, когда будет противоречием каждая Вi (1 i k). Вi – элементарное про изведение и по теореме 2.8 будет противоречием тогда и только тогда, когда содержит хотя бы одну пару множителей, из которых один – некоторая буква, а второй – отрицание этой буквы. Теорема доказана.

Следствие 1.1. Форма А будет выполнимой, если равносильная ей д.н.ф. содержит хотя бы одно слагаемое, в котором нет таких множителей, что один из них – некоторая пропози циональная буква, а другой множитель – отрицание этой буквы.

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

Теорема 2.11. Для каждой пропозициональной формы существует равносильная ей к.н.ф. (не единственная).

Можно сформулировать правила для нахождения д.н.ф. и к.н.ф., равносильных задан ной форме. Пусть задана форма А:

1) исключить из А все связки, кроме ¬, &,, 2) добиться, чтобы ¬ относилась только к пропозициональным буквам, 3) если раскрыть скобки по первому дистрибутивному закону, то получится д.н.ф., 4) если сгруппировать в скобки, пользуясь вторым дистрибутивным законом, то полу чится к.н.ф.

Легко доказать следующую теорему.

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

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

Также просто по теореме 1.12 выяснить выполнима форма А или нет. Для этого нахо дим к.н.ф. для ¬ А и если найденная к.н.ф. тавтология, то А не выполнима, если же найденная к.н.ф. не тавтология, то форма А выполнима.

2.1.2.9. Совершенные нормальные формы Совершенной дизъюнктивной нормальной формой (с.д.н.ф.) пропозициональной фор мы А(A1, A2,…, An) называется д.н.ф. этой формы удовлетворяющая следующим условиям:

– нет одинаковых слагаемых;

– в каждое слагаемое входят все буквы A1, A2,…, An один и только один раз (и только они) с отрицанием либо без отрицания.

С.д.н.ф. для А можно построить по таблице истинности этой формы. Для этого выбира ем строки, где А равна И;

пусть это будут строки k1, k2,…, km. Для каждой выбранной строки ki, 1 i m, строим элементарное произведение 29 (конституенту единицы) Ki следующим образом. Если в выбранной строке ki буква Aj принимает значение И, то в Ki она входит без отрицания, если же Aj = Л, то в Ki она входит с отрицанием. Дизъюнкция построенных произ ведений и будет с.д.н.ф. и можно доказать, что эта с.д.н.ф. равносильна А.

A B C A(A, B, C) Л Л Л И Л Л И И Л И Л И Л И И Л И Л Л И И Л И Л И И Л Л И И И И Рассмотрим пример на построение с.д.н.ф. Пусть форма А(A, B, C) ложна тогда и только тогда, когда ложен один и только один из аргументов. Найти с.д.н.ф. для А(A, B, C).

Решение. Составим таблицу истинности.

Выберем строки, где А принимает значение И, т.е. строки с номерами: 1, 2, 3, 5 и 8. Для первой строки элементарное произведение представляется в виде конъюнкции ¬А&¬ В&¬С, для второй – ¬А&¬ В&С. Построив, таким образом элементарные произведения для этих строк, получим с.д.н.ф.:

¬А&¬ В&¬С ¬А&¬ В&С ¬А&В&¬С А&¬ В&¬С А&В&С.

Второй метод нахождения с.д.н.ф. – метод равносильных преобразований, который со стоит в следующем. Для заданной формы А находим д.н.ф. (которая всегда существует) и пусть д.н.ф. равна:

D1 D2 … Dm (m 1), где Di(1 i m) – элементарное произведение. Построенная д.н.ф. может удовлетворять тре буемым условиям, тогда это с.д.н.ф.

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

Если в некоторое Di не входит одна из букв Аj формы А, то заменяем Di на равносиль ную:

(Di& Аj) (Di&¬Аj).

Таким образом, добиваемся, чтобы каждое слагаемое содержало все аргументы формы А.

Если в полученной форме окажутся одинаковые слагаемые, то оставляем только одно из них. В результате получим с.д.н.ф Совершенной конъюнктивной нормальной формой (с.к.н.ф.) пропозициональной фор мы А(A1, A2,…, An) называется к.н.ф. этой формы удовлетворяющая следующим условиям:

– нет одинаковых множителей;

– в каждый множитель входят все буквы из пропозициональной формы А один и только один раз (и только они) с отрицанием, либо без отрицания.

С.к.н.ф. для пропозициональной формы А можно построить по таблице истинности этой формы. Для этого выбираем строки, где А = Л. Для каждой строки, где А = Л строим элементарную сумму (конституенту нуля) K следующим образом. Если в выбранной строке буква Аj принимает значение И, то в K она входит с отрицанием, если Аj = Л, то Аj входит в K без отрицания. Конъюнкция построенных конституент нуля и будет с.к.н.ф.

Рассмотрим пример на построение с.к.н.ф. для пропозициональной формы, рассмот ренной выше. Решение. Таблица истинности уже построена. Выберем строки, где А прини мает значение Л, т. е. строки с номерами: 4, 6 и 7. Для четвертой строки элементарная сумма (конституента нуля) представляется в виде А ¬ В ¬С;

для шестой в виде: ¬ А В ¬ С, а для седьмой – ¬ А ¬ В С. В результате получим с.к.н.ф.:

(А ¬ В ¬ С)&(¬ А В ¬ С)&(¬ А ¬ В С).

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

Для заданной формы А находим к.н.ф., которая имеет вид К1&K2&…&Km, затем доби ваемся выполнения указанных выше условий.

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

Если некоторый множитель к.н.ф., например Ki, не содержит букву А, то вводим ее со гласно равносильности Ki (Ki А)&(Ki ¬А).

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

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

2.1.2.10. Булева (переключательная) функция Булевой переменной назовем переменную, которая принимает одно из двух возможных значений. Ясно, что высказывание можно рассматривать как частный случай булевой пере менной, ибо высказывание принимает только одно из двух значений: Л или И.

Функция (А1, А2,..., An) называется булевой (переключательной) функцией, если она может принимать одно из двух возможных значений, когда ее аргументы принимают тоже одно из этих двух значений.

Очевидно, что истинностная функция является частным случаем булевой функции.

Значения булевой функции и булевых переменных можно обозначать любыми симво лами, например, + и –, либо 1 и 0. В дальнейшем значения булевых переменных и функций будем обозначать через 1 и 0.

При исследовании высказываний, истинностных функций и пропозициональных форм нигде не использовалась природа значений "истина" (И) и "ложь" (Л). Тогда всюду И и Л можно рассматривать как символы, служащие для различения двух значений. Поэтому И можно переобозначить через 1, а Л – через 0, и все результаты, полученные для истинност ных функций, будут справедливы для булевых функций. Более того, булевы функции можно отождествить с истинностными функциями.

Выражения (¬А), (А&В), (А В), (А В), (А В) можно рассматривать как булевы функ ции, значения которых определяются по таблицам построенным для пропозициональных форм (¬А), (А&В), (А В), (А В), (А В) соответственно, если в них всюду заменить И на 1, а Л на 0. Эти таблицы будем тоже называть таблицами истинности.

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

Можно показать, что число различных булевых функций от n переменных равно N =.

Например: для n = 1 N = 4, для n = 2 N = 16, для n = 3 N = 256, для n = 5 N – более четырех миллиардов. n Булеву функцию можно задать с помощью таблиц, аналитически, графически и т.п.

2.1.2.11. Приложение алгебры высказываний к анализу и синтезу контактных (пе реключательных) схем Алгебра высказываний находит весьма широкое практическое применение. Рассмотрим приложение алгебры высказываний к анализу и синтезу контактных (переключательных) схем.

Контакты (переключатели) можно рассматривать как переменные и обозначать буква ми А, В, С,... или теми же буквами с числовыми индексами: А1, А2,..., В1, В2,..., С1, С2,....

Каждая из переменных может принимать одно и только одно из двух возможных значений:

если контакт А разомкнут, то по определению А = 0, если контакт А замкнут, то по определе нию А = 1.

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

Отрицанием контакта А называется контакт, равный 1, если А = 0, и равный 0, если А = 1. Отрицание контакта А обозначается через ¬А.

Очевидно, что последовательное соединение двух контактов А и В моделируется конъ юнкцией переменных А и В, а параллельное соединение – их дизъюнкцией, см. рис. 2.1.

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

Используя булевы функции, можно строить контактные схемы, удовлетворяющие за данным требованиям (производить синтез контактных схем), а также преобразовывать, уп рощать схемы (производить анализ контактных схем). Покажем это на примере.

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

При голосовании "за" – нажатием кнопки свет должен загораться тогда и только тогда, когда "за" проголосовало большинство.

Решение. В нашем случае имеем три переменные. Обозначим их через А, В, и С. По ус ловию свет должен загораться тогда и только тогда, когда большинство этих переменных принимает значение 1, т.е. имеем таблицу:

А В С 1 1 1 0 1 1 1 0 1 0 0 1 1 1 0 0 1 0 1 0 0 0 0 0 Используя эту таблицу, находим булеву функцию, выбирая строки, оканчивающиеся на 1:

A&B&C ¬A&B&C A&¬ B&C A&B&¬C. (2.11) По этой функции строим схему, которая имеет четыре параллельные ветви в каждой из которых по три контакта, см. рис. 2.2.

Рис. 2.2. Схема с четырьмя параллельными ветвями Эта схема выполняет поставленную задачу. Полученная схема содержит 12 контактов, и естественно попытаться проанализировать данную схему: нельзя ли, например, уменьшить количество контактов в переключательной схеме.

Можно получить, что форма (2.11) равносильна форме А&В А&С В&С, которую пре образуем к виду: А&В С&(А В). Тогда схема будет содержащей всего пять контактов, см.

рис. 2.3.

Очевидно, что анализ позволил сильно упростить контактную схему.

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

Рис. 2.3. Схема с пятью контактами Не касаясь структуры и физических основ этих устройств, называемых функциональ ными элементами, обозначим их условно следующим образом:

устройство, реализующее отрицание;

устройство, реализующее конъюнкцию;

устройство, реализующее дизъюнкцию.

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

устройство, реализующее отрицание имеет один вход и один вы ход. Сигнал появляется на выходе, когда на входе нет сигнала, и не появляется сигнал, когда на вход подан сигнал.

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

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

Этих свойств элементов достаточно для решения задач синтеза и анализа схем из этих элементов.

Рассмотрим пример построения одноразрядного сумматора двоичных чисел. Заданы двоичные числа а1а2…аk…аn и b1b2…bk…bn. Требуется построить сумматор для k-го разряда.

Задача состоит в конструировании схемы (рис. 2.4) с тремя входами А, В, С и двумя выхода ми S и Р, чтобы при подаче на входы А и В сигналов, изображающих двоичные цифры – сла гаемые данного разряда, а на вход С – сигнала, изображающего значение переноса из сосед него младшего разряда, получить на выходе S значение суммы в данном разряде, а на выходе Р – значение переноса в соседний старший разряд.

Рис. 2.4. Схема с тремя входами и двумя выходами Напомним, что сложение чисел в двоичной системе производится следующим образом:

0 + 0 = 0, 0 + 1 = 1 + 0 = 1, 1 + 1 = 10, 1 + 1 + 1 = 11 и т.д. Воспользовавшись этой таблицей сложения чисел в двоичной системе, получим таблицу:

A B C S P 1 1 1 1 0 1 1 0 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 0 0 1 0 0 0 0 Считая, что 0 и 1 есть значения булевой функции, и выбирая строки, оканчивающиеся на 1, получим:


(2.12) S = А&В&С ¬А&¬ В&С ¬А&В&¬С А&¬ В&¬С, Р = А&В&С ¬А&В&С A&¬ В&С А&В&¬С Имея выражение (2.12), уже можно построить схему из функциональных элементов, выполняющих поставленную задачу. Но поскольку схема построена из функциональных элементов, выполняющих некоторые операции, то возникает задача такого упрощения, что бы она содержала как можно меньше знаков операций. Можно показать, что Р = А&ВvА&СvВ&С, S = А&В&Сv(АvВvС)&¬ Р.

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

Рис. 2.5.

2.1.3. Формальные языки. Комбинаторика 2.1.3.1. Основные понятия и определения Определение: алфавит – это конечное множество символов.

Предполагается, что термин "символ" имеет достаточно ясный интуитивный смысл и не нуждается в дальнейшем уточнении.

Определение: цепочкой символов в алфавите V называется любая конечная последова тельность символов этого алфавита.

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

Более формально цепочка символов в алфавите V определяется следующим образом:

(1) – цепочка в алфавите V;

(2) если – цепочка в алфавите V и a – символ этого алфавита, то a – цепочка в алфа вите V;

(3) – цепочка в алфавите V тогда и только тогда, когда она является таковой в силу (1) и (2).

Определение: если и – цепочки, то цепочка называется конкатенацией (или сце плением) цепочек и.

Например, если = ab и = cd, то = abcd.

Для любой цепочки всегда = =.

Определение: обращением (или реверсом) цепочки называется цепочка, символы ко торой записаны в обратном порядке.

Обращение цепочки будем обозначать R.

Например, если = abcdef, то R = fedcba.

Для пустой цепочки: = R.

Определение: n-ой степенью цепочки (будем обозначать n) называется конкатенация n цепочек.

0 = ;

n = n-1 = n-1.

Определение: длина цепочки – это число составляющих ее символов.

Например, если = abcdefg, то длина равна 7.

Длину цепочки будем обозначать ||. Длина равна 0.

Определение: язык в алфавите V – это подмножество цепочек конечной длины в этом алфавите.

Определение: обозначим через V* множество, содержащее все цепочки конечной дли ны в алфавите V, включая пустую цепочку.

Например, если V = {0,1}, то V* = {, 0, 1, 00, 11, 01, 10, 000, 001, 011,...}.

Определение: обозначим через V+ множество, содержащее все цепочки конечной дли ны в алфавите V, исключая пустую цепочку.

Следовательно, V* = V+ {}.

Ясно, что каждый язык в алфавите V является подмножеством множества V*.

Известно несколько различных способов описания языков [3]. Один из них использует порождающие грамматики. Именно этот способ описания языков чаще всего будет исполь зоваться нами в дальнейшем.

Определение: декартовым произведением A B множеств A и B называется множество { (a,b) | a A, b B}.

Определение: порождающая грамматика G – это четверка (VT, VN, P, S), где VT – алфавит терминальных символов (терминалов), VN – алфавит нетерминальных символов (нетерминалов), не пересекающийся с VT, P – конечное подмножество множества (VT VN) + (VT VN)*;

элемент (, ) мно жества P называется правилом вывода и записывается в виде, S – начальный символ (цель) грамматики, S VN.

Для записи правил вывода с одинаковыми левыми частями 1 2... n будем пользоваться сокращенной записью 1 | 2 |...| n.

Каждое i, i = 1, 2,...,n, будем называть альтернативой правила вывода из цепочки.

Пример грамматики: G1 = ({0,1}, {A,S}, P, S), где P состоит из правил S 0A 0A 00A A Определение: цепочка (VT VN)* непосредственно выводима из цепочки (VT VN)+ в грамматике G = (VT, VN, P, S) (обозначим ), если = 12, = 12, где 1, 2, (VT VN)*, (VT VN)+ и правило вывода содержится в P.

Например, цепочка 00A11 непосредственно выводима из 0A1 в грамматике G1.

Определение: цепочка (VT VN)* выводима из цепочки (VT VN)+ в грамма тике G = (VT, VN, P, S) (обозначим _ ), если существуют цепочки 0, 1,..., n (n = 0), та кие, что = 0 1... n =.

Определение: последовательность 0, 1,..., n называется выводом длины n.

Например, S _ 000A111 в грамматике G1 (см. пример выше), т.к. существует вывод S 0A1 00A11 000A111. Длина вывода равна 3.

Определение: языком, порождаемым грамматикой G = (VT, VN, P, S), называется множество L(G) = { VT* | S _ }.

Другими словами, L(G) – это все цепочки в алфавите VT, которые выводимы из S с по мощью P.

Например, L(G1) = {0n1n | n 0}.

Определение: цепочка (VT VN)*, для которой S =, называется сентенциальной формой в грамматике G = (VT, VN, P, S).

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

Определение: грамматики G1 и G2 называются эквивалентными, если L(G1) = L(G2).

Например, G1 = ({0,1}, {A,S}, P1, S) и G2 = ({0,1}, {S}, P2, S) P1: S 0A1 P2: S 0S1 | 0A 00A A эквивалентны, т.к. обе порождают язык L(G1) = L(G2) = {0n1n | n 0}.

Определение: грамматики G1 и G2 почти эквивалентны, если L(G1) {} = L(G2) {}.

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

Например, G1 = ({0,1}, {A,S}, P1, S) и G2 = ({0,1}, {S}, P2, S) P1: S 0A1 P2: S 0S1 | 0A 00A A почти эквивалентны, т.к. L(G1)={0n1n | n 0}, а L(G2) = {0n1n | n = 0}, т.е. L(G2) состоит из всех цепочек языка L(G1) и пустой цепочки, которая в L(G1) не входит.

2.1.3.2. Классификация грамматик и языков по Хомскому (грамматики классифицируются по виду их правил вывода) ТИП 0:

Грамматика G = (VT, VN, P, S) называется грамматикой типа 0, если на правила выво да не накладывается никаких ограничений (кроме тех, которые указаны в определении грам матики).

ТИП 1:

Грамматика G = (VT, VN, P, S) называется неукорачивающей грамматикой, если каждое правило из P имеет вид, где (VT VN)+, (VT VN)+ и | | = | |.

Грамматика G = (VT, VN, P, S) называется контекстно-зависимой (КЗ), если каждое правило из P имеет вид, где = 1A2;

= 12;

A VN;

(VT VN)+;

1,2 (VT VN)*.

Грамматику типа 1 можно определить как неукорачивающую либо как контекстно зависимую.

Выбор определения не влияет на множество языков, порождаемых грамматиками этого класса, поскольку доказано, что множество языков, порождаемых неукорачивающими грам матиками, совпадает с множеством языков, порождаемых КЗ-грамматиками.

ТИП 2:

Грамматика G = (VT, VN, P, S) называется контекстно-свободной (КС), если каждое правило из Р имеет вид A, где A VN, (VT VN)+.

Грамматика G = (VT, VN, P, S) называется укорачивающей контекстно-свободной (УКС), если каждое правило из Р имеет вид A, где A VN, (VT VN)*.

Грамматику типа 2 можно определить как контекстно-свободную либо как укорачи вающую контекстно-свободную.

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

ТИП 3:

Грамматика G = (VT, VN, P, S) называется праволинейной, если каждое правило из Р имеет вид A tB либо A t, где A VN, B VN, t VT.

Грамматика G = (VT, VN, P, S) называется леволинейной, если каждое правило из Р име ет вид A Bt либо A t, где A VN, B VN, t VT.

Грамматику типа 3 (регулярную, Р-грамматику) можно определить как праволиней ную либо как леволинейную.

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

Соотношения между типами грамматик:

(1) любая регулярная грамматика является КС-грамматикой;

(2) любая регулярная грамматика является УКС-грамматикой;

(3) любая КС- грамматика является УКС-грамматикой;

(4) любая КС-грамматика является КЗ-грамматикой;

(5) любая КС-грамматика является неукорачивающей грамматикой;

(6) любая КЗ-грамматика является грамматикой типа 0.

(7) любая неукорачивающая грамматика является грамматикой типа 0.

(8) любая УКС-грамматика является грамматикой типа 0.

Замечание: УКС-грамматика, содержащая правила вида A, не является КЗ грамматикой и не является неукорачивающей грамматикой.

Определение: язык L(G) является языком типа k, если его можно описать грамматикой типа k.

Соотношения между типами языков:

(1) каждый регулярный язык является КС-языком, но существуют КС-языки, которые не являются регулярными ( например, L = {anbn | n 0}).

(2) каждый КС-язык является КЗ-языком, но существуют КЗ-языки, которые не явля ются КС-языками (например, L = {anbncn | n 0}).

(3) каждый КЗ-язык является языком типа 0.

Замечание: УКС-язык, содержащий пустую цепочку, не является КЗ-языком.

Замечание: следует подчеркнуть, что если язык задан грамматикой типа k, то это не значит, что не существует грамматики типа k’ (k’ k), описывающей тот же язык. Поэтому, когда говорят о языке типа k, обычно имеют в виду максимально возможный номер k.

Например, грамматика типа 0 G1 = ({0,1}, {A,S}, P1, S) и КС-грамматика G2 = ({0,1}, {S}, P2, S), где P1: S 0A1 P2: S 0S1 | 0A 00A A описывают один и тот же язык L = L(G1) = L(G2) = {0n1n | n 0}. Язык L называют КС языком, т.к. существует КС-грамматика, его описывающая. Но он не является регулярным языком, т.к. не существует регулярной грамматики, описывающей этот язык [3].

Примеры грамматик и языков Замечание: если при описании грамматики указаны только правила вывода Р, то будем считать, что большие латинские буквы обозначают нетерминальные символы, S – цель грам матики, все остальные символы – терминальные.


1) Язык типа 0: L(G) = {a2 bn2 1 | n = 1} G: S aaCFD F AFB | AB AB bBA Ab bA AD D Cb bC CB C bCD 2) Язык типа 1: L(G) = { an bn cn, n = 1} G: S aSBC | abC CB BC bB bb bC bc cC cc 3) Язык типа 2: L(G) = {(ac)n (cb)n | n 0} G: S aQb | accb Q cSc {a,b}+, где нет двух рядом стоящих а} 4) Язык типа 3: L(G) = { | G: S A | B A a | Ba B b | Bb | Ab 2.1.3.3. Конечный автомат и регулярные языки В кибернетике автоматами называют технически или программно реализованные мо дули, предназначенные для переработки поступающей информации. Конечный автомат – это модуль, имеющий конечное число возможных состояний и функционирующий в дис кретном времени. В данном пособии конечные автоматы изучаются как абстрактные алго ритмические устройства, предназначенные для обработки слов фиксированного входного алфавита. Считаем, что обработку произвольного слова во входном алфавите А автомат начинает из специально выделенного начального состояния. В каждый такт дискретного времени на вход автомата поступает очередная буква обрабатываемого слова, под ее воздействием автомат меняет свое состояние;

состояние, в которое автомат перейдет, определяется предыдущим его состоянием и прочитанной буквой входного слова. Над сло вом длины l автомат работает l тактов. Результат работы автомата определяется состоянием, в котором он оказывается по ее завершении.

Формально конечный автомат K определяем как совокупность K = {Q, A, q0, g, F}, где Q = {q0, q1, q2,..., qm} – множество состояний автомата;

А = {а1, а2,..., аn} – входной ал фавит;

q0 – специально выделенное состояние автомата, именуемое начальным состоянием;

g – функция переходов конечного автомата, представляющая собой отображение типа QxАQ (если g(qi,аj)=qk, то автомат из состояния qi под воздействием буквы аj должен перейти в со стояние qk);

F – специально выделенное подмножество состояний автомата, которые мы ус ловно будем именовать «хорошими», F Q.

Пусть – входное слово, l() = р. Через q(t) обозначим состояние, в кото ром оказывается автомат К через t тактов работы над этим словом (здесь t = 0, 1, 2,..., р):

q (0) = q0 ;

q (1) = g (q (0), ai1 ) q (2) = g (q (1), ai2 )...

q ( p ) = g (q ( p 1), ai p ) Будем говорить, что слово принимается автоматом K, если q(р) F.

Введем в рассмотрение язык L(K): слово принадлежит языку L(K), если данное слово принимается автоматом K. Язык L(K) именуем языком, распознаваемым данным конечным автоматом. Язык L назовем регулярным, если для него можно построить распознающий ко нечный автомат.

Конечный автомат удобно задавать диаграммой его переходов. Диаграмма представля ет собой ориентированный граф, вершины которого одноименны состояниям автомата;

дуга из вершины qi, в вершину qk с надписанной над ней буквой аj проводится тогда и только то гда, когда g(qi,аj)=qk. В случае, когда переход из qi в qk осуществляется под воздействием лю бой из букв некоторого подмножества S, S А, все буквы этого подмножества подписывают ся над соответствующей дугой (вместо перечня всех букв допускается сокращенная запись «x S» или просто «S»). Если произвольное состояние qi входит в F, то данный факт на диа грамме отмечается жирным кружком, выделяющим вершину qi.

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

На рис. 3.1 показана диаграмма автомата K1, работающего над словами алфавита A = {a, b, c}. Автомат имеет два состояния, q0 и q1, причем «хорошим» является только состояние q1. Начав работу в состоянии q0, автомат под воздействием букв a, b из этого состояния не выходит;

под воздействием буквы с реализуется переход в состояние q1;

любая далее посту пающая буква оставляет автомат в том же состоянии. Таким образом, автомат K1 распознает язык L1, состоящий из слов, имеющих в своем составе букву с. Данный язык является регу лярным.

Рис. 3.1. Диаграмма автомата, работающего со словами алфавита A = {a, b, c}.

Приведем еще несколько примеров регулярных языков в том же алфавите: L2 – множе ство слов, в которых буква а встречается четное число раз;

L3 – множество слов, начинаю щихся и заканчивающихся одинаковой буквой;

L4 – множество слов, содержащих подслово = abbc;

L5 – множество слов, при чтении которых слева направо разность между числом встреченных букв a и b никогда не превосходит 2. Диаграммы конечных автоматов K2 – K5, распознающих языки L2 – L5 соответственно, представлены на рисунках 3.2 – 3.5. Информа цию об обработанной части входного слова автомат “помнит” своим состоянием. Так, на пример, автомат K5, обработав некоторую часть входного слова, оказывается в состоянии qx, если в прочитанной им части входного слова число встреченных букв а превышает число встреченных букв b на x;

здесь x {–2, –1, 0, 1, 2};

автомат оказывается в состоянии qплох, ес ли в некоторый момент работы автомата абсолютная величина разности между числом обра ботанных букв а и числом обработанных букв b превысила 2.

Рис. 3.2. Диаграмма конечного автомата, распознающего язык L Рис. 3.3. Диаграмма конечного автомата, распознающего язык L Рис. 3.4. Диаграмма конечного автомата, распознающего язык L Рис. 3.5. Диаграмма конечного автомата, распознающего язык L Состояние конечного автомата назовем поглощающим, если любая входная буква не выводит автомат из этого состояния. Поглощающее состояние назовем положительно по глощающим, если оно принадлежит F, и отрицательно поглощающим в противном слу чае. В автоматах K1 и K4 полижительно поглощающими являются состояния q1 и q4 соответ ственно, в автомате K5 отрицательно поглощающим является состояние qплох.

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

Обычно в диаграмме переходов отрицательно поглощающее состояние не изображается;

ес ли из некоторого состояния по некоторой букве переход не указан, то предполагается, что он ведет в отрицательно поглощающее состояние. Представленный на рисунке 3.6 конечный автомат распознает в алфавите А язык, состоящий из слов, в которые буква с входит ровно один раз. Этот автомат имеет 3 состояния, отрицательно поглощающее состояние qплох (в не го автомат переходит из состояния q1 по букве с) в диаграмме не указано.

Рис. 3.6. Диаграмма конечного автомата, распознающего язык А Введем алфавит B = {0, 1, 2, …, 9}, каждое слово в этом алфавите трактуем как целое неотрицательное число. Пусть L(p) обозначает множество слов – записей в десятичной систе ме счисления всех целых неотрицательных чисел, кратных натуральной константе p;

будем считать, что языку L(p) дополнительно принадлежит также пустое слово. Покажем, что L(p) – регулярный язык. Распознающий L(p) конечный автомат K(p) можно построить следующим образом. Состояниями автомата считаем q0, q1, q2, qp–1;

из произвольного состояния qi по цифре х, х {0, 1, 2,...,9}, автомат переходит в состояние qj, если остаток от деления числа iх (т.е. числа, получаемого приписыванием к числу i цифры х справа) на p равен j. Благодаря указанной структуре переходов автомат, обработавший, начиная от начального состояния q0, записанное в десятичной системе счисления целое неотрицательное число, оказывается в состоянии qy тогда и только тогда, когда остаток от деления на p равен у. Единственным «хорошим» состоянием автомата K(p) следует считать q0. На рис. 3.7 и 3.8 представлены диа граммы конечных автоматов, распознающих числа, делящиеся на 2 и на 3 соответственно.

Рис. 3.7. Рис. 3.8.

Отметим, что в ряде случаев, исходя из иных принципов, можно построить распознаю щие делимость на p автоматы c меньшим числом состояний. На рис. 3.9 представлен имею щий два состояния конечный автомат, распознающий числа, кратные пяти (используется тот факт, что кратное пяти число имеет своей последней цифрой 0 или 5).

Рис. 3.9.

По конечному автомату K(p) легко строится автомат K(p)[], распознающий язык L(p)\{}.

Для получения диаграммы переходов автомата K(p)[] в имеющейся диаграмме переходов автомата К(p) делаются следующие изменения: начальное состояние q0 автомата K(p) переиме новываем в q0;

вводим новое начальное состояние q0;

по произвольной цифре х из q0 автомат K(p)[] реализует переход в то же состояние, что и автомат K(p) из своего начального состоя ния (при этом вместо перехода в q0 всегда реализуется переход в q0);

единственным «хоро шим» состоянием автомата K(p)[] следует считать q0.

Согласно изложенному, начальное состояние автомата K(p)[] является невозвратным – в процессе обработки любого входного слова, выйдя из этого состояния, автомат в него ни когда не вернется. На рис. 3.10 представлен конечный автомат K(3)[], распознающий числа, кратные трем (пустое слово, в язык, распознаваемый данным автоматом, не входит).

Отметим, что язык, распознаваемый произвольным конечным автоматом, содержит пустое слово тогда и только тогда, когда начальное состояние этого автомата принадлежит множеству F.

Рис. 3.10. Конечный автомат, распознающий числа, кратные Теорема 3.1. Пустой язык, универсальный язык, любой конечный язык в произвольном фиксированном алфавите А = {а1, а2,..., аn} являются регулярными языками.

Любой конечный автомат с пустым множеством «хороших» состояний F распознает пустой язык. Любой конечный автомат, в котором каждое состояние «хорошее», распознает универсальный язык. Конечные автоматы, q0 распознающие пустой и универсальный языки и имеющие только одно состояние, представлены на рис. 3.11 и 3.12 соответственно (x– произвольная буква алфавита A).

Рис. 3.11. Рис. 3.12.

Сейчас предположим, что язык L конечен, пусть L = { 1, 2,..., p}. Диаграмму конеч ного автомата K(L), распознающего слова языка L, строим в виде дерева, корнем которого является вершина q0, образующая нулевой уровень. В вершине q0 реализуем ветвление (далее эта операция будет выполняться и для других вершин): проводим из данной вершины n дуг, над первой надписываем а1, над второй – а2,..., над n-ой – аn, концами этих дуг являются n вершин следующего (в данном случае – первого) уровня. Выполнив ветвление в каждой из вершин первого уровня, получаем n2 вершин второго уровня;

выполнив ветвление в каждой из вершин второго уровня, получаем n3 вершин третьего уровня, и т. д. Процесс продолжает ся до тех пор, пока не будут построены вершины r-го уровня, где r – число букв в самом длинном слове языка L. Операции ветвления в вершинах r-го уровня не выполняются;

если на вход автомата, находящегося в некотором состоянии из r-го уровня, поступает еще одна буква, он переходит в неотображенное диаграммой отрицательно поглощающее состояние qплох. Между вершинами-состояниями построенного r- уровневого дерева и имеющими дли ну не больше, чем r, словами алфавита А существует взаимно однозначное соответствие – каждому такому слову сопоставляется состояние, в котором оказывается автомат, обрабо тавший, начиная от q0, данное слово. Каждое отображенное в дереве состояние автомата K(L) называем именем соответствующего ему слова (состояние q0 получает при этом имя пустого слова). Множество F «хороших» состояний автомата K(L) считаем следующим: 1, 2,... p.

Построение распознающего язык L конечного автомата закончено. Теорема доказана полно стью.

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

3.13 представлен автомат, распознающий конечный язык A = {0, 01, 10, 001, 101, 1100}.

Рис. 3.13. Конечный автомат, распознающий конечный язык А Теорема 3.2. Класс регулярных языков замкнут относительно основных теоретико множественных операций – объединения, пересечения и дополнения.

Приводимое доказательство конструктивно – излагаются алгоритмы построения соот ветствующих автоматов. Пусть L1 и L2 – регулярные языки, распознаваемые конечными ав томатами K1 = {Q1, A, q10, g1, F1} и K2 = {Q2, A, q20, g2, F2} соответственно;

считаем, что Q1 = {q10, q11, q12,..., q1f} и Q2 = {q20, q21, q22,..., q2h}. Автомат K = {Q, A, q0, g, F }, распознающий язык L1 L2, строим следующим образом. Полагаем Q = Q1хQ2;

каждое состояние конструи руемого автомата содержит две компоненты, левую и правую. Начальным состоянием ново го автомата считаем (q10,q20), а функцию переходов g определяем следующим образом:

g((q1i,q2j),аk) = (g1(q1i,ak), g2(q2j,аk)) Очевидно, по первой компоненте автомат K моделирует действия автомата K1, а по второй компоненте – действия автомата K2. Входное слово принадлежит объединению языков L1 и L2 тогда и только тогда, когда после его обработки автомат K окажется в состоя нии, у которого либо первая компонента принадлежит совокупности F1, либо вторая компо нента принадлежит совокупности F2. Таким образом, следует положить:

F = (F1хQ2) (Q1хF2).

Все компоненты автомата K определены, его построение закончено. Автомат K = {Q, A, q0, g, F}, распознающий язык L1L2, отличается от K только последней своей компонен той. Следует положить F=F1хF2.

Пусть K = {Q, A, q0, g, F} – конечный автомат, распознающий язык L.

Произвольное слово из А* принадлежит языку Lс = А*\L тогда и только тогда, когда после его обработки автомат K оказывается в состоянии, не принадлежащем F. Поэтому ав томатом, распознающим язык Lс, является конечный автомат Kс = {Q, A, q0, g, Q\F}. Образно говоря, для того, чтобы получить конечный автомат, распознающий дополнение регулярного языка, надо в автомате, распознающем исходный язык, поменять местами «хорошие» и «плохие» состояния.

Теорема доказана.

На рис. 3.14 представлены два конечных автомата, распознающих языки L1 и L2. На рис.

3.15 и 3.16 изображены автоматы, распознающие языки L1 L2 и L1L2 соответственно.

Рис. 3.14. Конечные автоматы, распознающие языки L1 и L Рис. 3.15. Конечный автомат, распознающий языки L1 L Рис. 3.16. Конечный автомат, распознающий языки L1L На рис. 3.17 представлен автомат, распознающий язык L3, представляющий собой до полнение к языку L2. На рис. 3.18 изображен автомат, распознающий разность языков L1 и L (или пересечение языков L1 и L3).

Рис. 3.17. Конечный автомат, распознающий язык L Рис. 3.18. Конечный автомат, распознающий разность языков L1 и L Заметим, что часто автоматы, распознающие объединение и пересечение языков, стро ятся существенно проще. Это связано с тем, что некоторые состояния из множества состоя ний Q = Q1 х Q2 могут быть недостижимыми.

Рассмотрим следующий пример. Пусть требуется построить автомат, распознающий объединение языков L1 и L2;

автоматы K1 и K2, распознающие эти языки, изображены на рис.

3.19.

Рис. 3.19. Конечные автоматы, распознающие объединение языков L1 и L Диаграмму переходов автомата K (рис. 3.20), распознающего язык L1 L2, строим сле дующим образом. Вводим вершину, соответствующую начальному состоянию (q01,q02). По букве a автомат K1 из состояния q01 переходит в состояние q11, а автомат K2 – из q02 в q12. Сле довательно, автомат K из состояния (q01,q02) перейдет в состояние (q11,q12). Добавим в диа грамму соответствующую вершину и ведущую в нее дугу. Т.к. по букве b автомат K1 перехо дит из q01 в q21, а автомат K2 – из q02 в q22, то автомат K из состояния (q01,q02) перейдет в со стояние (q21,q22). Соответствующая вершина и дуга добавляются в диаграмму. Рассмотрим вершину (q21,q22). По букве a автомат K1 из q21 переходит в q11, а автомат K2 – из q22 в q12, сле довательно;

автомат K из состояния (q21,q22) перейдет в состояние (q11,q12), которое уже при сутствует на диаграмме. Поэтому в диаграмму добавляется только соответствующая дуга. По букве b автомат K1 остается в состоянии q21, а автомат K2 переходит из q22 в q02, поэтому авто мат K по букве b из состояния (q21,q22) переходит в состояние (q21,q02). В диаграмму добав ляются вершина (q21,q02) и ведущая в нее дуга.

Рассматривая далее вершины (q11,q12) и (q21,q02), мы обнаружим, что новых вершин не возникает, в диаграмму добавляются лишь дуги, ведущие в уже существующие вершины.

«Хорошими» будут являться состояния (q21,q02) и (q21,q22).

Рис. 3.20. Рис. 3.21.

Точно так же строится диаграмма конечного автомата K, распознающего язык L1L (рис. 3.21). Автомат K отличается от автомата K только множеством «хороших» состояний.

Сейчас приведем пример языка, не являющегося регулярным. Пусть хf, здесь х – произ вольная буква рассматриваемого алфавита, обозначает слово, состоящее из буквы х, повто ренной f раз, f {1, 2, 3,...}. Запись хfуh, где х и у – произвольные буквы алфавита, f {1, 2, 3,...} и h {1, 2, 3,...}, обозначает результат приписывания справа к слову хf слова уh. Через La b обозначим бесконечный язык, каждое слово которого имеет вид anbn, т.е. в слове, принад лежащем языку, сначала n раз повторяется буква а, затем такое же число раз повторяется бу ква b, где n = 1, 2, 3,....

Теорема 3.3. Язык La-b нерегулярен.

Доказательство проводим методом от противного. Пусть данный язык регулярен. Тогда существует распознающий La-b конечный автомат Ka-b, число состояний этого автомата обо значим w. Далее через qz условно обозначим состояние, в котором оказывается автомат Ka-b после того, как он, начиная от своего начального состояния q0, обработал z букв а подряд, z = 1, 2, 3,....Учитывая, что общее число состояний Ka-b равно w, делаем вывод, что среди состоя ний, обозначаемых q1, q2,..., qw+1, имеется по меньшей мере одно с двумя обозначениями.

Пусть qi и qj, здесь i j, – два обозначения некоторого состояния qk. Так как слова aibi и ajbj принадлежат языку La-b, то как слово bi, так и слово bj переводит автомат Ka-b из состояния qk, в которое он попадает в результате обработки из начального состояния слова ai или слова aj, в состояние из множества F. Но тогда процесс работы данного автомата над не принадлежа щим языку La-b словом = aibj протекает следующим образом: обработав, начиная от состоя ния q0 начальную часть ai слова, автомат оказывается в состоянии qk;

далее, обработав, на чиная от состояния qk заключительную часть bj входного слова, автомат оказывается в «хо рошем» состоянии. Таким образом, слово принадлежит языку, распознаваемому автоматом Ka-b. Полученное противоречие означает справедливость сформулированной теоремы.

Как отмечалось выше, требуемая информация об обработанной части входного слова «помнится» состояниями автомата. Так как число состояний конечно, то память конечного автомата является ограниченной, не достаточной для запоминания сколь угодно большого числа букв a, прошедших перед появлением на входе первой буквы b.

Через L,, где,, – фиксированные слова алфавита А = {a, b, c}, обозначим язык, состоящий из слов вида i, здесь i обозначает повторенное i раз слово, i = 0, 1, 2,... (сло во 0 считаем по определению пустым).

Рассмотрим в качестве примера язык Labcbca,cab (здесь = bca, = abc, = cab), данный язык регулярен, диаграмма соответствующего конечного автомата представлена на рис. 3.22.

В результате обработки начальной части bca слова i автомат из начального состояния q переходит в состояние q3;

далее, обрабатывая подслово, автомат реализует цикл q3, q4, q5, q (этот цикл выполняется i раз);



Pages:     | 1 || 3 | 4 |   ...   | 5 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.