- необходимые и достаточные условия;

- анализ и синтез релейно-контактных схем.

1. Элементы алгебры высказываний

1.1 Логические операции над высказываниями

Отрицанием высказывания х называется новое высказывание, которое является истинным, если высказывание X ложно, и ложным, если высказывание X истинно.

Отрицание высказывания X обозначается и читается «не X» или «неверно, что X».

Логические значения высказывания можно описать с помощью таблицы

Таблицы такого вида принято называть таблицами истинности.

Конъюнкцией двух высказываний X, Y называется высказывание, которое считается истинным, если оба высказывания X, Y истинны, и ложным, если хотя бы одно из них ложно.

Конъюнкция высказываний X, Y обозначается символом X&Y или (XY), читается «X и Y». Высказывания X и Y называются членами конъюнкции или конъюнктивными элементами.

Логические значения конъюнкции описываются следующей таблицей истинности:

Например, для высказываний «6 делится на 2», «6 делится на З» их конъюнкцией будет высказывание «6 делится на 2 и 6 делится на З», которое, очевидно, истинно.

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

Дизъюнкцией двух высказываний X, Y называется высказывание, которое считается истинным, если хотя бы одно из высказываний X, Y истинно, и ложным, если они оба ложны.

Дизъюнкция высказываний X, Y обозначается символом XY, читается «X или Y», где «или» используется в неразделительной форме. Высказывания X и Y называются членами дизъюнкции.

Логические значения дизъюнкции описываются следующей таблицей истинности:

Например, высказывание «В треугольнике DFE угол D или угол Е острый» истинно, так как обязательно истинно хотя бы одно из высказываний: «В треугольнике DFE угол D острый», «В треугольнике DFE угол Е острый».

Импликацией двух высказываний X,Y называется высказывание, которое считается ложным, если X истинно, а Y - ложно, и истинным во всех остальных случаях.

Импликация высказываний X, Y обозначается символом X Y, читается «если X, то Y» или «из X следует Y». Высказывание X называют посылкой, высказывание Y - заключением.

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

Например, высказывание «Если число 12 делится на 6, то оно делится на З», очевидно, истинно, так как здесь истинна посылка «Число 12 делится на 6» и истинно заключение «Число 12 делится на 3».

Употребление слов «если ..., то ...» в алгебре логики отличается от употребления их в обыденной речи, где мы, как правило, считаем, что, если высказывание X ложно, то высказывание «Если X, то Y» вообще не имеет смысла. Кроме того, строя предложение вида «если X, то Y» в обыденной речи, мы всегда подразумеваем, что предложение Y вытекает из предложения X. Употребление слов «если ..., то ...» в математической логике не требует этого, поскольку в ней смысл высказываний не рассматривается.

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

Эквиваленция высказываний X, Y обозначается символом X Y, читается «для того, чтобы X, необходимо и достаточно, чтобы Y» или «X тогда и только тогда, когда Y». Высказывания X, Y называются членами эквиваленции.

Логические значения операции эквиваленции описываются следующей таблицей истинности:

Например, эквиваленция «Треугольник SPQ с вершиной S и основанием PQ равнобедренный тогда и только тогда, когда P= Q » является истинной, так как высказывания «Треугольник SPQ с вершиной S и основанием PQ равнобедренный» и «В треугольнике SPQ с вершиной S и основанием PQ P= =Q» либо одновременно истинны, либо одновременно ложны.

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

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

Штрих Шеффера - функция, принимающая значение ложь, если X - истинно и Y - истинно.

Очевидно, имеют место равносильности:

1)

2)

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

Отметим, что .

Стрелка Пирса (функция Вебба) XY - функция, принимающая значение истина, когда X - ложно и Y - ложно.

Отметим, что XY =

Функция сложение по модулю 2 (функция разноименности, или сумма Жегалкина) - функция, принимающая значение истинно, когда X и Y принимают противоположные значения.

Отметим, что = .

С помощью логических операций над высказываниями из заданной совокупности высказываний можно строить различные сложные высказывания. При этом порядок выполнения операций указывается скобками. Например, из трех высказываний X, Y, Z можно построить высказывания

(X&Y)Z и X .

Первое из них есть дизъюнкция конъюнкции X, Y и отрицания выказывания Z, а второе высказывание есть импликация, посылкой которой является высказывание X, а заключением - отрицание дизъюнкции высказывания Y и конъюнкции высказываний X, Z.

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

Высказывания обозначаются большими буквами латинского алфавита А, В, С, …

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

В связи с этим формулы

(X&Y)Z и X

могут быть записаны так:

X&YZ и X .

Логическое значение формулы алгебры логики полностью определяется логическими значениями входящих в нее элементарных высказываний. Например, логическим значением формулы в случае, если X = 1, Y = 1, Z=0 будет истина, то есть = 1.

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

Например, для формулы таблица истинности имеет вид:

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

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

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

Равносильность формул будем обозначать знаком , а запись А В означает, что формулы А и В равносильны.

Например, равносильны формулы:

 Формула А называется тождественно истинной (или тавтологией), если она принимает значение 1 при всех значениях входящих в нее переменных.

Например, тожественно истинны формулы

Формула А называется тождественно ложной (или противоречием), если она принимает значение 0 при всех значениях входящих в нее высказываний.

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

Формула А называется выполнимой, если она принимает значение 1 при всех значениях входящих в нее высказываний.

Например, выполнима формула .

Ясно, что отношение равносильности рефлексивно, симметрично и транзитивно.

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

Важнейшие равносильности алгебры высказываний можно разбить на следующие группы.

1.Равносильности алгебры Буля:

1.Закон двойного отрицания:

2. Коммутативность:

3. Ассоциативность:

4. Дистрибутивность & относительно:

5. Дистрибутивность относительно &:

6. Законы де Моргана:

7. Законы поглашения:

8. Законы идемпотентности:

 9. Свойства констант:

10. Закон противоречия:

11. Закон исключения третьего:

2. Равносильности, выражающие одни логические операции через другие:

12.

13.

14.

15.

16.

17.

1.3 Нормальные формы

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

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

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

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

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

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

Определение 4. Формула равносильная данной и представляющая собой конъюнкцию элементарных дизъюнкций называется конъюнктивной нормальной формой данной формулы.(КНФ).

Обобщим существование ДНФ или КНФ для каждой формулы:

1. Все логические операции можно заменить тремя: конъюнкцией, дизъюнкцией и отрицанием.

2. Знак отрицания с помощью законов де Моргана можно отнести к пропозициональным переменным.

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

Для каждой формулы может быть составлено несколько ДНФ и КНФ. Но все ДНФ (или КНФ) данной формулы равносильны между собой.

Определение 5. Совершенной дизъюнктивной нормальной формой формулы А(x₁,x₂,…,x_n) называется ДНФ, обладающая следующими свойствами:

а) в ней нет одинаковых дизъюнктивных элементов;

б) ни одна элементарная конъюнкция не содержит двух одинаковых высказываний;

в) ни какая элементарная конъюнкция не содержит высказывание вместе с ее отрицанием;

г) в каждой элементарной конъюнкции содержится либо X_i, либо , где i=.

Условие а) - г) являются необходимыми и достаточными для того, чтобы ДНФ стала СДНФ. В свою очередь эти условия дают возможность составить алгоритм получения СДНФ из ДНФ:

1) если какая-нибудь элементарная конъюнкция не содержит высказывание X_i, то заменим выражением ;

2) если в полученном выражении окажутся одинаковые элементарные конъюнкции, то лишние опускаются;

3) если в некоторых элементарных конъюнкциях окажутся одинаковые высказывания, то лишние опускаются;

4) удаляем элементарные конъюнкции, в которых содержатся высказывания вместе с их отрицанием.

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

Определение 6. Совершенная конъюнктивная нормальная форма - это ее КНФ обладающая свойствами:

а) в ней нет двух одинаковых конъюнктивных элементов;

б) ни одна элементарная дизъюнкция не содержит двух одинаковых высказываний;

в) ни одна элементарная дизъюнкция не содержит какой-нибудь переменной с ее отрицанием;

г) каждая элементарная дизъюнкция содержит либо X_i, либо , где i=.

В свою очередь эти условия дают возможность составить алгоритм получения СКНФ из КНФ:

1) если какая-нибудь элементарная дизъюнкция не содержит высказывание X_i, то заменим выражением ;

2) если в полученном выражении окажутся одинаковые элементарные дизъюнкции, то лишние опускаются;

3) если в некоторых элементарных дизъюнкциях окажутся одинаковые высказывания, то лишние опускаются;

4) удаляем элементарные дизъюнкции, в которых содержатся высказывания вместе с их отрицанием.

Для тождественно истинных формул СКНФ не существует.

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

1.4 Логические следствия

Определение 1. Формула B называется логическим следствием формул A₁, A₂, …, A_n, если при любых значениях, входящих в них, элементарных высказываний формула B принимает значение истинно всякий раз, когда формулы A₁, A₂, …, A_n принимают значение истинно. Обозначается A₁, A₂, …, A_n ¦ B

Из определения логического следования вытекает:

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

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

Теорема 1. Из A логически следует B тогда и только тогда, когда тавтологией является AB.

Теорема 2. A₁, A₂,…, A_n¦ B тогда и только тогда, когда является тавтологией

A₁&A₂& …& A_n B.

Теорема 3. Из формул A₁, A₂,…, A_n , B логически следует C тогда и только тогда, когда из формул A₁, A₂, …, A_n логически следует BC.

Следствие 1. Из A и B логически следует C тогда и только тогда, когда тавтологией является

A (BC).

Следствие 2. Из формул A₁, A₂, …, A_n логически следует B тогда и только тогда, когда тавтологией является

A₁ (A₂ … (A_nB)…).

Отношение логического следования играет в математике большую роль.

Если из A¦B, то A называется достаточным условием для B, а B - необходимым условием для A.

Если вместе с A¦B из B¦A, то A называется необходимым и достаточным условием для B, а B - необходимым и достаточным условием для A.

2. Решение задач с помощью алгебры высказываний

2.1 Исследование рассуждений

Отношение логического следования используется при исследовании рассуждений.

Задача 1. Если 6 - составное число (S), то 12 - составное число (W). Если 12 - составное число, то существует простое число, больше чем 12 (P). Если существует простое число больше 12, то существует составное число больше 12 (C). Если 6 делится на 2 (D), то 6 - составное число. Число 12 составное. Следовательно, 6 - составное число.

Посылки: , , , , W

Заключение: S

Решение:

Данное высказывание тавтологией не является, значит из указанных посылок не следует высказывание «6 - составное число».

Задача 2. Я пойду в кино на новую комедию (A) или на занятия по математической логике (B). Если я пойду в кино, то я от всей души посмеюсь (C). Если я пойду на занятия по математической логике, то испытаю удовольствие от логических рассуждений (D). Следовательно, или я от всей души посмеюсь или испытаю удовольствие от логических рассуждений.

Посылки: , ,

Заключение:

Решение:

Значит из данных посылок следует .

Задача 3. Я пойду домой (H) или останусь здесь и выпью стаканчик (S). Я не пойду домой. Следовательно, я останусь и выпью.

Посылки: ,

Заключение: S

Решение:

Значит, высказывание «я останусь и выпью» является логическим следствием из данных посылок.

Задача 4. Если Джон ляжет сегодня поздно (S), он будет утром в отупении (D). Если он ляжет не поздно, то ему будет казаться, что не стоит жить (L). Следовательно, или Джон будет завтра в отупении, или ему будет казаться, что не стоит жить.

Посылки: ,

Заключение:

Решение:

Значит из данных посылок следует .

Задача 5. Или Сэлли и Боб одного возраста (S), или Сэлли старше Боба (O). Если Сэлли и Боб одного возраста, то Нэнси и Боб не одного возраста (N). Если Сэлли старше Боба, то Боб старше Уолтера (W). Следовательно, или Нэнси и Боб не одного возраста, или Боб старше Уолтера.

Решение:

Посылки: , ,

Заключение:

Значит из данных посылок следует .

2.2 Получение логических следствий из данных формул и посылок для данных логических следствий

Логические следствия находят следующим образом:

1) все посылки соединяются конъюнкцией и находятся СКНФ полученной формулы.

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

получаются все возможные заключения из данных посылок.

Задача 1. Даны посылки: A и AB

Решение:

Логические следствия:

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. .

Задача 2. Даны посылки:

Решение:

Логические следствия:

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. .

Задача 3. Даны посылки:

Решение:

Логические следствия:

 1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7.

;

Задача 4. Найти формулу F(X, Y), зависящую только от переменных X и Y и являющуюся логическим следствием указанных формул (посылок):

Решение:

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

В правом столбце звездочками отметим те строки, в которых все четыре посылки принимают значение 1. Этому требованию удовлетворяет лишь 15-я строка, в которой ? (X) = 0 и ? (Y) = 0. Следовательно, надо найти такую формулу F (X, Y), для которой F (0, 0) = 1, то такая формула будет логическим следствием четырех данных посылок. Ищем такую формулу, используя СДНФ и считаем, что на всех других наборах значений переменных искомая формула обращается в 0:

F (0, 1) = F (1, 0) = F (1, 1) = 0.

Получаем F (X, Y) .

Задача 5. Найти формулу F(X, Y), зависящую только от переменных X и Y и являющуюся логическим следствием указанных формул (посылок):

Решение:

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

Найдем такую формулу F (X, Y), для которой F (1, 1) = F (0, 1) = F (1, 0) = 1, которая будет логическим следствием двух данных посылок.

F (0, 0) = 0.

Получаем F (X, Y) .

Задача 6. Найти формулу F(X, Y), зависящую только от переменных X и Y и являющуюся логическим следствием указанных формул (посылок):

Решение:

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

Найдем такую формулу F (X, Y), для которой F (0, 0) = 1, которая будет логическим следствием трех данных посылок.

F (1, 0) = F (0, 1) = F (1, 1) = 0.

Получаем F (X, Y) .

Чтобы определить логическим следствием каких посылок является формула А (X₁,X₂,…,X_n), необходимо:

1) привести ее к СКНФ.

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

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

Задача 1.

Решение:

Недостающие дизъюнкции:

Посылка:

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

Задача 2.

Решение:

Недостающие дизъюнкции:

Посылка:

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

Задача 3.

Решение:

Недостающие дизъюнкции:

Посылки:

;

;

;

;

;

;

.

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

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

¦

Решение:

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

В правом столбце звездочками отметим те строки, в которых обе данные посылки принимают значение 1, а следствие принимает значение 0. Этому требованию удовлетворяет лишь 12-я строка, в которой ? (Z) = 1 и ? (V) = 1. Ясно, что при этих значениях Z и V искомая посылка F (Z, V) должна принимать значение 0, так как в противном случае формула не будет логическим следствием формул . Будем считать, что на других наборах значений высказываний Z и V формула F (Z, V) принимает значение 1. Итак, для искомой посылки F (Z, V) получаем следующую таблицу истинности:

Находим СКНФ для искомой формулы. Получаем F (Z, V) .

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

¦

Решение:

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

В правом столбце звездочками отметим те строки, в которых обе данные посылки принимают значение 1, а следствие принимает значение 0. Этому требованию удовлетворяет лишь 1-я строка, в которой ? (X) = 1 и ? (Y) = 1. Будем считать, что на других наборах значений высказываний X и Y формула F (X, Y) принимает значение 1. Итак, для искомой посылки F (X, Y) получаем следующую таблицу истинности:

Находим СКНФ для искомой формулы. Получаем F (X, Y) .

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

¦

Решение:

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

В правом столбце звездочками отметим те строки, в которых обе данные посылки принимают значение 1, а следствие принимает значение 0. Этому требованию удовлетворяет лишь 1-я строка, в которой ? (X) = 1 и ? (Y) = 1. Будем считать, что на других наборах значений высказываний X и Y формула F (X, Y) принимает значение 1. Итак, для искомой посылки F (X, Y) получаем следующую таблицу истинности:

Находим СКНФ для искомой формулы. Получаем F (X, Y) .

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

¦

Решение:

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

В правом столбце отметим строку, в которой данная посылка принимает значение 1, а следствие принимает значение 0. Этому требованию удовлетворяет лишь 6-я строка, в которой ? (X) = 0, ? (Y) = 1 и ? (Z) = 0. Будем считать, что на других наборах значений высказываний X, Y, Z формула F (X, Y, Z) принимает значение 1. Итак, для искомой посылки F(X, Y, Z) получаем следующую таблицу истинности:

Находим СКНФ для искомой формулы. Получаем

F (X, Y, Z) .