Учебное пособие по математической логике для студентов заочного отделения




НазваниеУчебное пособие по математической логике для студентов заочного отделения
страница2/5
Дата публикации28.08.2013
Размер0.96 Mb.
ТипУчебное пособие
skachate.ru > Математика > Учебное пособие
1   2   3   4   5

^ 2. Алгебра (логика) высказываний
Алгебра или логика высказываний – это простейшая теория математической логики. Основное понятие этой теории – высказывание. Высказывание – это повествовательное предложение, о котором, хотя бы в принципе, можно сказать, истинно оно или ложно (конечно, эта фраза не является математически корректным определением: основные понятия любой теории не определяются, иначе они определялись бы через другие понятия, то есть не были бы основными). Например: ‘‘Волга впадает в Каспийское море’’, ‘‘2=3’’ – высказывания, причем первое – истинное, а второе – ложное, Но фраза: ‘‘Сумма корней приведенного квадратного уравнения равна свободному члену’’ высказыванием не является, поскольку бывают уравнения этого типа, для которых это справедливо, но для других это неправильно. Математическая логика не интересуется конкретным содержанием высказывания, высказывания рассматриваются как переменные , которые могут принимать только два значения: истина (и) и ложь (л) или 1 и 0 соответственно.
^ Логические связки и логические функции.

Из одного или нескольких высказываний можно получить другое высказывание, используя логические связки: (конъюнкция, логическое умножение, и), (дизъюнкция, логическое сложение, неисключающее или), (отрицание, не), (импликация), (стрелка Пирса), | (штрих Шеффера), (символ Жегалкина, исключающее или, сложение по модулю 2), ~ (эквиваленция), \ (логическое вычитание) и это высказывание называется логической функцией исходных высказываний. Таким образом, логическая функция исходных высказываний является отображением множества во множество , где – множество, состоящее из двух элементов: . Нетрудно установить, что всего таких функций может быть (доказательство предоставляется читателю в качестве упражнения).

Рассмотрим все логические функции одной логической переменной . Их удобно представить в виде следующей таблицы (таблицы истинности):
0001110101

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

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

Таб. 1
Каждая из этих функций имеет свой логический смысл. Функция – тождественно ложная функция. Функция истинна в том и только том случае, когда истинны и , и – это конъюнкция: . Функция истинна в том и только том случае, когда истинно , а ложно – это логическая разность этих высказываний: . Функция истинна в том и только том случае, когда истинно , независимо от : . Функция истинна в том и только том случае, когда истинно , а ложно – это логическая разность этих высказываний: . Функция истинна в том и только том случае, когда истинно , независимо от : . Функция истинна в том и только том случае, когда либо истинно, а ложно, либо, наоборот, истинно, а ложно: это сумма по модулю 2 и : . Функция ложна в том и только том случае, когда ложны и , и , это дизъюнкция: . Функция истинна в том и только том случае, когда и принимают одинаковые значения, это эквиваленция: . Функция истинна в том и только том случае, когда ложно , это отрицание : . Функция ложна в том и только том случае, когда ложно, а истинно, это импликация: . Функция истинна в том и только том случае, когда ложно , это отрицание : . Функция ложна в том и только том случае, когда истинно, а ложно, это импликация: . Функция ложна в том и только том случае, когда истинны и , и , это штрих Шеффера: . Функция истинна при любых и , это тождественно истинная функция.

Два первых столбца таб. 1 вместе со столбцом, соответствующим функции ( ), составляют таблицу истинности функции . Например, таблица истинности импликации имеет вид:




001

011

100

111

Это определение импликации следует обсудить особо. С точки зрения логики импликация означает: ``Если , то ''. Очевидно, это истинно, если из истинности следует истинность , а из ложности ложность , и ложно, если из истинности следует ложность . Но совсем не очевидна третья строчка таблицы, которая гласит, что импликация истинна, если из ложности следует истинность . Можно привести такой шуточный пример: если крокодилы летают, то дважды два – пять. Тут действует своеобразная презумпция истинности: высказывание считается истинным, пока не доказана его ложность. А чтобы доказать ложность нашего высказывания, необходимо доказать, во-первых, что крокодилы летают, во-вторых, что дважды два не равно пяти. Но первое доказать невозможно.

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

По номеру функции легко определить ее таблицу истинности и наоборот. Для этого надо представить номер в двоичной системе счисления, например, 7=4+2+1 в этой системе изображается в виде 0111 (добавляется 0 слева, чтобы число цифр было равно четырем). Самая правая цифра соответствует значению функции при , вторая справа – при и так далее. Таким образом, простейшая теория математической логики – логика высказываний – основана на определении логических операций (отрицания, конъюнкции, дизъюнкции, импликации и т. д.) с помощью таблиц истинности.

Можно пойти дальше и определить новые логические функции трех переменных с помощью таблиц истинности, каждая из которых содержит 9 строк и 4 столбца, например:
00010010010101111000101111011111

Порядок следования наборов значений переменных (строк) здесь по-прежнему определяется в соответствии с двоичной системой счисления: 000 соответствует нулю, 001 – единице, 010 – двум и так далее. Функции нумеруются аналогично: – тождественный нуль, в четвертом столбце ее таблицы истинности нули во всех строках. Чтобы получить таблицу истинности для функции , надо число представить в виде:

, где – либо нуль, либо единица. и есть то число, которое должно стоять на пересечении четвертого столбца и -ой строки в таблице истинности функции . Тождественная единица, или тождественно истинная функция имеет индекс 255: . Но любую такую функцию можно определить с помощью суперпозиции функций одной или двух переменных. Например, пусть , . Суперпозицию этих функций получим, подставив в функцию вместо , вместо . В результате получим: формулу. Формула может представлять собой только одну букву (независимую переменную) – такие формулы называются пропозициональными. Если – формула, то – тоже формула. Если и – формулы, то – тоже формулы. Других формул в логике высказываний нет. Таким образом, любое выражение, содержащее пропозициональные формулы, разделенные логическими связками, представляет собой формулу, которая представляет собой некоторое сложное высказывание. Для определения логического смысла этого высказывания необходимо учитывать правила приоритета логических операций. Именно, вначале выполняются операции, находящиеся под знаком отрицания, конъюнкции, штрихи Шеффера и стрелки Пирса, затем дизъюнкции, потом импликации, после них сложения по модулю 2 и эквиваленции. Для обеспечения другого порядка вычисления операций используются скобки. Составим таблицу истинности функции :

000111001111010101011111100011101011110000 111 111011

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

^ Основные равносильности (легко проверяемые по таблицам истинности).

1) законы идемпотентности конъюнкции и дизъюнкции.

2) (1 – истина).

3) (0 – ложь).

4) (закон противоречия).

5) (закон исключенного третьего).

6) (закон снятия двойного отрицания ).

7) (законы поглощения).

8) (формулы расщепления).

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

1)

2) .

3) .

4) .

5) первый закон де Моргана.

6) второй закон де Моргана.

7)

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

Равносильности, выражающие основные законы алгебры логики.

1) коммутативность конъюнкции и дизъюнкцци.

2) ассоциативность конъюнкции и дизъюнкции.

3) дистрибутивность конъюнкции относительно дизъюнкции.

4) дистрибутивность дизъюнкции относительно конъюнкции.

Используя равносильности, можно упрощать выражения.

Пример 1. Упростить выражение для

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

Основные тавтологии (логические законы):

1) закон исключенного третьего (tertium nondatum).

2) .

3) .

4) цепное рассуждение.

Итак, в математической логике все множество высказываний отображается на множество, состоящее из двух элементов: 0 и 1, и на этом множестве определяются три операции: одна унарная (отрицание) и две бинарных (конъюнкция и дизъюнкция), которые не выводят элементы из этого множества.
^ Булевы алгебры.

Любое множество , содержащее (может быть, наряду с другими) два выделенных элемента 0 и 1, на котором определены одна унарная операция (обозначим ее через ) и две бинарные операции (обозначим их через + и ), такие, что справедливы следующие равенства:

– коммутативные законы,

– ассоциативные законы,

– дистрибутивные законы,

– законы идемпотентности,

– законы де Моргана,

– закон двойного отрицания,

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

– особые свойства элементов 0 и 1, называется алгеброй Буля или булевой алгеброй.

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

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

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

Из таблицы видно, что существуют функции, двойственные сами себе. Такие функции называют самодвойственными.

Пример 1. Найти выражение для , если .

.
^ Нормальные формы.

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


(дизъюнкция по всем наборам переменных, при которых функция принимает значение1).

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

(конъюнкция по всем наборам переменных, при которых функция принимает значение 0).

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

00000011010001101001101111011110

Из таблицы видно, что значение 1 эта функция принимает, если , или , или . Для всех остальных наборов значений переменных эта функция принимает значение 0. Отсюда получаем:

СДНФ , (*)

СКНФ .

Но среди ДНФ могут быть и такие, которые содержат меньше переменных, чем СДНФ. Такие ДНФ целесообразно использовать при реализации логических функций в виде переключательных устройств или в машинных программах. Будем называть импликантой формулы такую элементарную конъюнкцию , которая, во-первых, содержит каждую из переменных не более чем один раз (то есть является правильной), во-вторых, удовлетворяет уравнению . Импликанта называется простой, если после удаления из нее любой переменной она перестает быть импликантой. Дизъюнкция простых импликант называется сокращенной ДНФ. Сокращенная ДНФ может содержать лишние импликанты, удаление которых не меняет таблицы истинности. Если их удалить, получается ДНФ, которая называется тупиковой. Тупиковая ДНФ, содержащая наименьшее число вхождений переменных, называется минимальной ДНФ (МДНФ).

Для получения сокращенной ДНФ используются две операции:

  1. неполное склеивание ;

  2. элементарное поглощение .

Например, рассмотрим функцию с приведенной выше таблицей истинности (знаки конъюнкции опускаем, как это обычно и делается):



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

В тупиковую ДНФ выбирается минимальное число простых импликант, дизъюнкция которых сохраняет таблицу истинности функции, то есть каждый столбец матрицы Квайна содержит по крайней мере одну звездочку, стоящую на пересечении со строкой, соответствующей одной из выбранных импликант. Затем из тупиковой ДНФ выбирается минимальная ДНФ. В нашем случае тупиковая ДНФ равна , она же будет равна МДНФ.
1   2   3   4   5

Похожие:

Учебное пособие по математической логике для студентов заочного отделения iconУчебное пособие по ботанике для студентов 3 курса заочного отделения...
Учебное пособие предназначено для самостоятельной работы студентов 3 курса заочного отделения фармацевтического факультета. Пособие...
Учебное пособие по математической логике для студентов заочного отделения iconУчебное пособие для самостоятельной работы студентов заочного отделения...
Учебное пособие предназначено для для самостоятельной работы студентов заочного отделения неязыков специальностей вузов, ранее изучавших...
Учебное пособие по математической логике для студентов заочного отделения iconУчебное пособие для самостоятельной работы студентов заочного отделения...
Учебное пособие предназначено для для самостоятельной работы студентов заочного отделения неязыков специальностей вузов, ранее изучавших...
Учебное пособие по математической логике для студентов заочного отделения iconУчебное пособие по органической химии для самостоятельной работы...
Учебное пособие предназначено для самостоятельной работы студентов II курса заочного отделения фармацевтического факультета при выполнении...
Учебное пособие по математической логике для студентов заочного отделения iconУчебное пособие по фармацевтической химии для студентов 4 курса заочного...
Авторы учебного пособия для студентов 4 курса заочного отделения фармацевтического факультета «Общие и частные методы анализа лекарственных...
Учебное пособие по математической логике для студентов заочного отделения iconУчебное пособие содержит характеристику основных разделов фармацевтической...
В пособии приведена рабочая программа по фармацевтической химии для студентов заочного отделения, даны рекомендации по её освоению...
Учебное пособие по математической логике для студентов заочного отделения iconУчебное пособие по органической химии для самостоятельной работы студентов
Учебное пособие предназначено для самостоятельной работы студентов II курса заочного отделения фармацевтического факультета при выполнении...
Учебное пособие по математической логике для студентов заочного отделения iconРекомендации о разработке методических указаний и контрольных заданий...
Разработчик: методист заочного учебного отделения высшего профессионального образования С. С. Кудрявцева
Учебное пособие по математической логике для студентов заочного отделения iconСамостоятельная работа, часов
Смолова Л. М. Химия. Рабочая программа, методические указания, элементы теории, вопросы для самопроверки и контрольные задания для...
Учебное пособие по математической логике для студентов заочного отделения iconКонтрольная работа №2 по английскому языку для студентов заочного...
Данное пособие можно взять в библиотеке Политехнического колледжа или получить в электронном виде. Также необходимо изучить материалы...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2014
контакты
skachate.ru
Главная страница