Практические приложения алгебры высказываний

Министерство общего и профессионального образования РФ Сочинский государственный университет туризма и курортного дела Социально-педагогический институт Математический факультет Кафедра общей математики

Дипломная работа

«Практические приложения алгебры высказываний»

Выполнил: студент V курса

^{(подпись)} дневной формы обучения

специальность 10 100

«Математика»

Галайджян А. С.

студенческий билет № 98-МА011

Заведующий кафедрой: доцент, кандидат ф.-м. наук

^{(подпись)} Симонян А. Р.

⁽Сочи — 2002

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

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

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

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

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

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

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

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

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

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

Заключение

Как самостоятельная наука логика оформилась в трудах греческого философа Аристотеля (384−322 г. до н.э.). Он систематизировал известные до него сведения, и эта система стала в последствии называться формальной или Аристотелевой логикой.

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

Впервые в истории идеи о построении логики на математической основе были высказаны немецким математиком Г. Лейбницем в конце XVII века. Он считал, что основные понятия логики должны быть обозначены символами, которые соединяются по особым правилам. Это позволит всякое рассуждение заменить вычислением.

«Мы употребляем знаки не только для того, чтобы передать наши мысли другим лицам, но и для того, чтобы облегчить сам процесс нашего мышления» (Лейбниц).

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

Введение

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

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

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

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

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

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

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

Для достижения цели работы в первой части рассматриваются основные понятия и теоретические сведения, касающиеся данной проблемы:

— логические операции над высказываниями;

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

— нормальные формы;

— логические следствия.

Во второй части приводится подробное описание и задачи практических приложений, как:

— исследование рассуждений;

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

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

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

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) .

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

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

Задача 1. Пусть на отрезке [a, b] определена непрерывная функция f (x) имеющая на промежутке [a, b] конечные производные, тогда:

Для того, чтобы функция f (x) была постоянной на отрезке [a, b] необходимо и достаточно, чтобы =0 для .

Решение:

F (x)=const на [a, b] - истина

F (x)=const на [a, b] - истина

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

+ - истина

+ - истина

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

имело действительные корни

имело действительные корни

Задача 4. Для того, чтобы в точке x₀ функция f (x) имела экстремум, необходимо, чтобы

Решение:

функция f (x) в точке x₀ имеет экстремум — истина

функция f (x) в точке x₀ имеет экстремум — ложь контрпример: .

Задача 5. Для того, чтобы четырехугольник был квадратом, необходимо, но не достаточно, чтобы его диагонали были перпендикулярны.

Решение:

ABCD — квадрат — истина

ABCD — квадрат — ложь

B

контрпример: A C

D

Задача 6.Для того, чтобы уравнение cos x = a имело решение, необходимо, но не достаточно, чтобы .

Решение:

Cos x = a — имеет решение

Cos x = a — имеет решение — ложь контрпример: a = 3.

Задача 7. Для того, чтобы в точке x₀ функция f (x) имела разрыв второго рода, достаточно, чтобы = ?.

Решение:

функция f (x) в точке x₀ имеет разрыв второго рода — истина.

Задача 8. Для того, чтобы выражение x² — 2x — 3 равнялось нулю, достаточно, но не необходимо, чтобы x = -1.

Решение:

x² — 2x — 3 = 0 — ложь контрпример: x = 3.

x² — 2x — 3 = 0 — истина

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

Одно из применений алгебры высказываний — анализ и синтез релейно-контактных схем.

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

Рассмотрим 2-х-полюсные переключатели, т. е. такие, которые имеют два состояния: «замкнуто» — 1, «разомкнуто» — 0. На схеме будем изображать:

Определение 7. Переключатель, который сблокирован с X так, что он замкнут, если X разомкнут, и разомкнут, если X замкнут, называется инверсным и обозначается .

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

Эта схема пропускает ток тогда и только тогда, когда истины и X, и Y одновременно, то есть истина конъюнкция X&Y.

X&Y

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

XY

Эта схема пропускает ток в случае, если истинно высказывание X или истинно высказывание Y, то есть истина дизъюнкция XY.

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

Определение 8. Две схемы называются равносильными, если имеют одинаковые функции проводимости.

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

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

Задача 1. Составить РКС, обладающая следующей функцией проводимости:

Решение:

Задача 2. Составить РКС обладающая следующей функцией проводимости:

Решение:

Задача 3. Составить РКС обладающая следующей функцией проводимости:

Решение:

Задача 4. Упростить РКС:

Решение:

Ей соответствует функция проводимости:

F (X, Y, Z)

F (X, Y, Z)

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

Задача 5. Упростить РКС:

Решение:

Ей соответствует функция проводимости:

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

Задача 6. Упростить РКС:

Решение:

Ей соответствует функция проводимости:

Задача 7. Какой контакт необходимо вставить в вакантное место, чтобы функция проводимости полученной схемы стала бы равна данной булевой функции:

Данной схеме соответствует функция проводимости:

Решение:

Задача 8. Какой контакт необходимо вставить в вакантное место, чтобы функция проводимости полученной схемы стала бы равна данной булевой функции:

Данной схеме соответствует функция проводимости:

Решение:

Задача 9. Какой контакт необходимо вставить в вакантное место, чтобы функция проводимости полученной схемы стала бы равна данной булевой функции:

Данной схеме соответствует функция проводимости:

Решение:

Задача 10. Построить РКС с четырьмя переключателями, которая проводит ток тогда и только тогда, когда замыкаются не все переключатели, а только некоторые из них.

Решение:

Составим таблицу значений функции проводимости F (X, Y, Z, T) этой схемы:

В правом столбце звездочками отметим те строки, на которых функция F (X, Y, Z, T) обращается в 0, запишем для неё выражение, используя СКНФ, потому что наборов значений аргументов, на которых функция обращается в 0, значительно меньше, чем наборов значений аргументов, на которых функция обращается в 1, и значит, СКНФ будет более простой, чем СДНФ:

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

Решение:

Составим таблицу значений функции проводимости F (X, Y, Z) этой схемы:

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

F (X, Y, Z, T) обращается в 1, запишем для неё выражение, используя СКНФ, потому что наборов значений аргументов, на которых функция обращается в 0, значительно меньше, чем наборов значений аргументов, на которых функция обращается в 1, и значит, СКНФ будет более простой, чем СДНФ:

Задача 12. Требуется составить схему с четырьмя переключателями X, Y, Z, T. Схема должна проводить ток тогда и только тогда, когда будут замкнуты переключатели X и Y или Z и T.

Решение:

Составим таблицу значений функции проводимости F (X, Y, Z, T) этой схемы:

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

F (X, Y, Z, T) обращается в 1, запишем для неё выражение, используя СДНФ:

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

Работа РКС описывается функцией Буля трех переменных F (X, Y, Z), где переменные высказывания X, Y, Z означают:

X — судья X голосует «за»

Y — судья Y голосует «за»

Z — судья Z голосует «за»

Таблица истинности функции F (X, Y, Z) имеет вид:

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

Заключение

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

— исследование рассуждений;

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

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

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

Устройство релейно-контактного действия широко используются в технике автоматического управления, в электронно-вычислительной технике и т. д.

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

1. Игошин В. И. Задачник — практикум по математической логике. М.: Просвещение, 1986.

2. Л. М. Лихтарников, Т. Г. Сукачева Математическая логика. Издательство «Лань», 1998

3. М. А Айзерман, Л. А. Гусев, Л. И. Розоноэр, И. М. Смирнов, А. А. Таль. Логика. Автоматы. Алгоритмы. М., Физматгиз, 1963 г.

4. Математическая логика (Под общей редакцией А.А. Столяра) — Минск, 1991

5. Новиков П. С., Элементы математической логики. Физматгиз, М., 1959

6. Яблонский С. В., Гаврилов Г. П., Кудрявцев В. Б. Функции алгебрылогики и классы Поста. — М.: Наука, 1966

Рецензия

на дипломную работу «Практические приложения алгебры высказываний» студента 5-го курса

математического факультета СГУТ и КД

Галайджяна Аркадий Сетракович.

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

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

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

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

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

Рецензент доцент, кандидат ф.-м. наук

Симонян А. Р.