mat_logika

F (x1; x2; x3) = F (1; 1; 1) x1 x2 x3 F (1; 1; 0) x1 x2 x3 F (1; 0; 1) x1 x2 x3 F (1; 0; 0) x1 x2 x3 F (0; 1; 1) x1 x2 x3 F (0; 1; 0) x1 x2 x3 F (0; 0; 1) x1 x2 x3 F (0; 0; 0) x1 x2 x3 ≡ 0 x1 x2 x3

1 x1 x2 x3 1 x1 x2 x3 0 x1 x2 x3 0 x1 x2 x3 0 x1 x2 x3 0 x1 x2 x3 1 x1 x2 x3 ≡ x1 x2 x3 x1 x2 x3 x1 x2 x3 =

Так как любую формулу алгебры логики можно представить в виде СДНФ, то в этой формуле будут содержаться только операции конъюнкции, дизъюнкции и отрицания.

Операции конъюнкции и дизъюнкции называются двойственными друг другу.

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

Пример 4. Функции A = x y z и A = x y z являются двойственными друг другу.

Теорема 1. A(x1; x2; : : : ; xn) ≡ A (x1; x2; : : : ; xn):

Теорема 2. Если функции A и B равносильны (A ≡ B); то равносильны и двойственные им функции (A ≡ B ):

Теоремы 1 и 2 объясняют формулу СКНФ (A) ≡ СДНФ (A); рассмотренную в § 4.

Все функции алгебры логики можно разбить на три класса: 1) тождественно истинные функции;

33

Глава 1. Математическая логика

2)тождественно ложные функции;

3)выполнимые функции.

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

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

Теорема 3. Элементарная дизъюнкция является тождественно истинной тогда и только тогда, когда она содержит некоторую переменную вместе с ее отрицанием.

Пример 5. D = x y z t t ≡ 1; то есть данная элементарная дизъюнкция является тождественно истинной.

Теорема 4. Для того чтобы функция была тождественно истинной необходимо и достаточно, чтобы каждая элементарная дизъюнкция ее КНФ содержала некоторую переменную и ее отрицание.

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

1 шаг. Функцию приводят к КНФ и применяют теорему 4. Если функция оказывается тождественно равной 1; то задача решена: функция тождественно истинная.

2 шаг. Если функция тождественно не равна 1; то составляют отрицание этой функции, находят КНФ отрицания функции и применяют теорему 4. Если получают 1; то задача решена: функция тождественно ложная. В противном случае функция оказывается выполнимой, и задача решена.

Иногда возникают ситуации, когда функцию удобнее привести к ДНФ.

Теорема 5. Элементарная конъюнкция является тождественно ложной тогда и только тогда, когда она содержит некоторую переменную вместе с ее отрицанием.

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

34

§ 5. Функции алгебры логики

ДНФ содержала некоторую переменную и ее отрицание.

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

1 шаг. Функцию приводят к ДНФ и применяют теорему 6. Если функция оказывается тождественно равной 0; то задача решена: функция тождественно ложная.

2 шаг. Если функция тождественно не равна 0; то составляют отрицание этой функции, находят ДНФ отрицания функции и применяют теорему 6. Если получают 0; то задача решена: функция тождественно истинная. В противном случае функция оказывается выполнимой, и задача решена.

Пример 6. Выяснить, является ли тождественно истинной функция

A(x; y) = (y y) (x x) y:

I способ. A(x; y) = (y y) (x x) y = КНФ(A); причем по теореме 3 первые две элементарные дизъюнкции тождественно истинные, а последний множитель не является тождественно истинным. Тогда по теореме 4 функция A(x; y) не является тождественно истинной.

Найдем отрицание этой функции A(x; y) = (y y) (x x) y ≡ (y y) (x x) y = ДНФ(A); причем по теореме 5 первые две элементарные конъюнкции тождественно ложные, а последнее слагаемое не является тождественно ложным. Тогда по теореме 6 функция A(x; y) не является

Из таблицы истинности следует, что функция A(x; y) не является тождественно истинной, она выполнимая.

Упражнения

5.1. Найдите формулу, определяющую функцию (x; y; z); по задан-

35

Глава 1. Математическая логика

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

5.2.Для функции A(a; b; c) = a (b c → a b) найдите:

1)СДНФ при помощи равносильных преобразований;

2)СКНФ путем равносильных преобразований;

3)СДНФ путем составления таблицы истинности;

4)СКНФ путем составления таблицы истинности.

5.3. По таблицам истинности найдите функции F1(x; y; z); F2(x; y; z);

5.4. Для следующих функций найдите СДНФ и СКНФ, каждую двумя способами (путем равносильных преобразований и используя таблицы истинности):

1)x (x → y);

2)(x y → x) x y → y;

3)(x → y) → (y → x);

4)(x z) → y z;

5) (x y → x z) →(x → x y z; )

6)(a b → b c) → (a → b) → (c → b) ;

7)(a → c) → b → a;

8)(a → b) → (b c → a c);

36

§ 6. Приложение алгебры логики к построению релейно-контактных схем

()

9)x → y → (z → t) ;

10)x y z → t u v:

5.5.Найдите СДНФ для всякой тождественно истинной функции, содержащей:

1)одно переменное;

2)два переменных;

3)три переменных.

5.6.Найдите СКНФ для всякой тождественно ложной функции, содержащей:

1)одно переменное;

2)два переменных;

3)три переменных.

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

1)x y ↔ x x y;

2)(x ↔ y) (x y x y);

3)(x → y) → x y y;

4)x y → (x ↔ y);

5)x y → (x ↔ y);

6)x y → z;

7)(x → z) (y → z) → (x → y):

§6. Приложение алгебры логики к построению релейно-контактных схем

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

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

37

Глава 1. Математическая логика

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

Каждому переключателю ставится в соответствие некоторая переменная (x; y; z): Если переключатель замкнут, то значение переменной равно 1; если переключатель разомкнут, то значение переменной равно 0: Параллельному соединению переключателей соответствует дизъюнкция (x y); последовательному соединению – конъюнкция (x y): Если x

– замыкающий, то его отрицание x – это размыкающий переключатель (и наоборот).

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

Пример 1. Найти функцию проводимости данной РКС.

Данная РКС состоит из двух ветвей, соединенных между собой параллельно. Первая ветвь содержит последовательное соединение двух контактов x и y; поэтому можем написать функцию проводимости f1(x; y) = x y: Вторая ветвь содержит последовательное соединение двух контактов x и y : f2(x; y) = x y: Так как первая и вторая ветви соединены параллельно, то f(x; y) = f1(x; y) f2(x; y) = (x y) (x y);

f(x; y) = (x y) (x y) – функция проводимости РКС.

Для нахождения условий работы данной РКС составим таблицу истинности ее функции проводимости.

Таким образом, f(1; 1) = f(0; 0) = 1; f(1; 0) = f(0; 1) = 0 – условия работы РКС.

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

38

§6. Приложение алгебры логики к построению релейно-контактных схем

1)анализ РКС;

2)синтез РКС;

3)оптимизация РКС.

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

Пример 2. Найти условия работы данной РКС.

xz

Эта задача на анализ РКС. По принятым ранее соглашениям составим

Глава 1. Математическая логика