47524 (597342), страница 4

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

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

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

Функция F7 носит название функции неравнозначности или суммы по модулю два. Для ее обозначения будем использовать:

Функция F8 носит название дизъюнкции или логическое ИЛИ. Для ее обозначения принято использовать знак :

Функцию F9 будем называть отрицанием дизъюнкции или стрелкой Пирса, и обозначать через:

Функция F10 носит название функции равнозначности или эквивалентности и обозначается:

Функции F12 и F14 носят название импликации. Для их обозначения будем использовать:

Здесь следует отметить, что импликация соответствует высказыванию «Если А, то В». При этом возникает ситуация, что это высказывание с ложным А и истинным В истинно. Прежде всего, это соглашение, причем это соглашение ничему не противоречит. В повседневном языке утверждения с ложным А не употребляются.

Пример типа «Если бы я был космонавтом, я бы полетел на Луну» не опровергает наше утверждение. Здесь 1. Имеем дело не с «Если А, то В», а с «Если бы А, то бы В»; 2. Считать ложным такое утверждение не имеет смысла.

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

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

является также корнем уравнения

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

Функция F15 носит название отрицание конъюнкции или штрих Шеффера. Для ее обозначения используется:

Оставшиеся функции F3 и F5 назовем отрицание импликации:

Для построения исчисления высказываний важным является вопрос о построении функционально полной системы функций.

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

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

Функции F7, F9, F15, F5, F3 уже выражены через эти операции. Выразим функции F10, F12, F14.

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

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

Отрицание (дополнение):

Конъюнкция:

Дизъюнкция:

Тогда:

Сумма по модулю 2:

Стрелка Пирса:

Эквивалентность:

Импликация:

Штрих Шеффера:

Отрицания импликации:

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

Законы булевой алгебры.

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

Первая группа.

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

2.

3. (первый закон поглощения).

4. (второй закон дистрибутивности).

5. (закон идемпотентности для дизъюнкции).

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

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

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

3. (второй закон поглощения).

4. (первый закон дистрибутивности)

5. (закон идемпотентности для конъюнкции).

Каждый из законов 1 - 5 называется двойственным к соответствующему закону 1 – 5.

Вторая группа

1.

2.

3.

4.

5.

6.

Третья группа

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

2.

3.

Четвертая группа

1.

2. (закон контрапозиции).

3.

Сформулируем некоторые полезные следствия из приведенных законов.

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

С2. Если в дизъюнкции хотя бы один из элементов равен 1, то вся дизъюнкция равна 1.

С3. Выбрасывая из произвольной конъюнкции все сомножители равные 1, мы не изменим ее величины.

С4. Если в конъюнкции хотя бы один сомножитель равен 0, то все произведение равно 0.

С5. Дизъюнкция или произведение любого числа одинаковых элементов равняется А.

Эти следствия можно доказать по индукции.

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

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

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

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

В силу определения:

являются элементарными дизъюнкциями, а не являются.

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

Дизъюнкция любого числа первичных термов равна либо 1, либо элементарной дизъюнкции. Произведение любого числа первичных термов равно либо 0, либо элементарному произведению.

Нормальной дизъюнктивной формой (ДНФ) называется дизъюнкция любого конечного множества попарно различных произведений.

Конъюнктивной нормальной формой (КНФ) называется произведение любого конечного множества попарно различных дизъюнкций.

Алгоритм приведения к ДНФ и КНФ заключается в следующем.

1. Преобразовать выражение в соответствии с операциями отрицания.

2. Использовать первый (ДНФ) или второй (КНФ) законы дистрибутивности.

Пример: Привести к ДНФ и КНФ выражение.

На первом этапе обрабатываем знаки отрицания:

Раскрывая скобки, приведем к ДНФ:

При приведении к КНФ последовательно применяем второй закон к первой скобке выражения

Рассмотрим некоторое множество М булевых переменных. В качестве такого множества будем выбирать множество аргументов той или иной булевой функции.

Элементарные дизъюнкции называются конституантами 0 для данного множества М булевых переменных, если они содержат в прямом либо инверсном виде все переменные множества М.

Элементарные конъюнкции называются конституантами 1 для данного множества М булевых переменных, если они содержат в прямом либо инверсном виде все переменные множества М.

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

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

Справедливо следующее: Любая булева функция имеет одну и только одну СДНФ/СКНФ.

Рассмотри процесс приведения к СДНФ/СКНФ.

Рассмотрим произвольную ДНФ от переменных x₁, . . ., x_n. Пусть некоторые элементарные произведения p, входящие в эту форму, не содержат какой либо переменной x_j. Тогда эти произведения можно заменить равными им выражениями

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

Назовем этот процесс приведением ДНФ к совершенному виду.

Характеристики

Список файлов книги