Монотонные функции

Определение. Если a = (a₁, …, a_n) и b = (b₁, …, b_n) - наборы длины n из 0 и 1, то a £ b, если a₁ £ b₁, …, a_n £ b_n.

Пример 47.

Наборы ( 0, 1, 0) и (1, 1, 0) сравнимы, причем ( 0, 1, 0) £ (1, 1, 0).

Наборы (0, 1) и (1, 0) несравнимы. Также несравнимы наборы (0, 1) и ( 1, 1, 0).

Определение. Функция f(x₁, x₂, …, x_n) называется монотонной, если для всяких наборовa = (a₁, …, a_n) и b = (b₁, …, b_n) условие a £ b влечет f(a) £ f(b).

Утверждение. Функция монотонна тогда и только тогда, когда ее сокращенная ДНФ не содержит отрицаний.

Следствие. Функция монотонна тогда и только тогда, когда ее МДНФ не содержит отрицаний.

Пример 48.

Выяснить, являются ли функции монотонными:

1. f = 00100110;
2. f = 00110111.

Решение.

1. Сокращенная ДНФ для функции f = 00100110 имеет вид Поскольку сокращенная ДНФ содержит отрицания, то функция не является монотонной.

2. Сокращенная ДНФ для функции f = 00110111 имеет вид Поскольку сокращенная ДНФ не содержит отрицаний, то функция является монотонной.

Теорема. Класс M = {f | a£ b Þ f(a)£ f(b)} монотонных функций замкнут относительно суперпозиций.

2.2.3.4. Теорема Поста о функциональной полноте

Теорема Поста (признак полноты системы булевых функций). Для того чтобы система булевых функций {f₁, …, f_m} была полной, необходимо и достаточно, чтобы для каждого из пяти функционально замкнутых классов T₀, T₁, L, M, S нашлась хотя бы одна функция f_i из системы, не принадлежащая этому классу.

Пример.

Выяснить к каким функционально замкнутым классам принадлежит булева функция f=01001110, используя теорему Поста.

Решение.

Строим таблицу значений и треугольник Паскаля (табл. 59):

Таблица 59

Полином Жегалкина имеет вид: f = x₃ + x₂x₃ + x₁ + x₁ x₃.

1. f(0, 0, 0) = 0 Þ fÎT₀;
2. f(1, 1, 1) = 1 Þ fÏT₁;
3. f(0, 0, 0) = f(1, 1, 1), а наборы (0, 0, 0) и (1, 1, 1) являются противоположными, то f Ï S;
4. так как в полиноме Жегалкина присутствуют слагаемые, представляющие собой конъюнкцию нескольких переменных, то f Ï L;
5. сокращенная ДНФ функции имеет вид: , так как она содержит отрицания, то f Ï M.

Сведем полученные данные:

Пример 49.

Доказать полноту системы {+, Ú, 1}.

Решение.

Введем обозначения: f₁ = x₁ + x₂, f₂ = x₁ Ú x₂, f₃ = 1. Построим единую таблицу для функций (табл. 60).

Таблица 60

Полином Жегалкина:

Поскольку для каждого из пяти функционально замкнутых классов нашлась функция, не принадлежащая этому классу (в каждом столбце имеется хотя бы один минус), то система булевых функций {+, Ú, 1} является полной.

2.2.4. Существенные и несущественные переменные. Производная булевой функции первого порядка. Вес переменной

Определение. Булева функция fÎP_n существенно зависит от переменной x_i, если существует такой набор значений a₁, …, a_i-1, a_i+1, …, a_n, что

В этом случае x_i называют существенной переменной, в противном случае x_i называют несущественной переменной.

Определение. Производная первого порядка от булевой функции f по переменной x_i есть сумма по модулю 2 соответствующих остаточных функций:

где f(x₁, x₂, …, x_i-1, 1, x_i+1, …, x_n) – единичная остаточная функция; f(x₁, x₂, …, x_i-1, 0, x_i+1, …, x_n) – нулевая остаточная функция; Å - сумма по модулю 2.

Единичная остаточная функция получается в результате приравнивания переменной x_i единице, нулевая – приравниванием x_i нулю.

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

Утверждение. Чем больше вес производной , тем больше функция f зависит от переменной x_i.

Пример 50.

Определить переменную x_i, по которой производная функции

имеет минимальный (максимальный) вес, т. е. функция f(x₁, x₂, x₃, x₄, x₅) зависит от нее менее (более) существенно.

Решение.

Определим вес каждой переменной, найдя сначала соответствующую производную.

Имеем

Итак,

Аналогично вычислим вес производных (i = 2, 3, 4, 5) (табл. 62, 63, 64, 65). Имеем:

Таблица 64

Таблица 65

Выяснили, что минимальное значение получено при дифференцировании функции f по переменным х₂ и х₄, максимальное значение получено при дифференцировании функции f по переменной х₃.

2.3. Исчисление высказываний

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

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

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

Определение. Процесс получения новых знаний, выраженных высказываниями, из других знаний, также выраженных высказываниями, называется рассуждением (умозаключением). Исходные высказывания называются посылками (гипотезами, условиями), а получаемые высказывания – заключением (следствием).

Логика – это наука о способах доказательства.

В логике высказываний все доказательства строятся на отношении порядка, т.е. на отношении, которое существует между причиной и следствием. Отдельные звенья цепи связаны символом импликации «®» при логическом выводе мы будем заменять на символ «Þ», подобно тому, как используются два символа эквивалентности «»» и «=». Во избежании путаницы вместо конъюнкции «Ù» будем использовать символ запятой «,», а вместо дизъюнкции «Ú» - символ точка с запятой «;». Тогда утверждение, которое требуется доказать, в логике высказываний оформляется в виде следующего причинно-следственного отношения:

P₁, P₂, …, P_n-1, P_n Þ C,

где P_i – посылка, С – заключение. Условимся формальную запись такого рода называть клаузой. Смысловой текст, отвечающий некоторой конкретной клаузе, будем называть её легендой.

Пример 51.

Для данной легенды построить соответствующую клаузу:

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

Решение.

Выделим простые высказывания и введем обозначения:

А – «фирма приглашает на работу крупного специалиста в области новейшей технологии»;

B – «фирма считает данную новейшую технологию привлекательной»;

С – «фирма разворачивает работу по изменению технологии производства своего традиционного продукта»;

D - «фирма начинает разработку нового продукта».

С учетом принятых обозначений умозаключение примет вид:

«Если А, то В и (С или D). А. Следовательно, С или D.»

Используя логические связки, получим окончательно:

((А®(ВÙ(СÚD)))ÙA)Þ(CÚD).

Используя равносильности логики высказываний получаем:

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

2.3.1. Основные схемы логически правильных рассуждений

Приведем примеры наиболее употребимых схем логически правильных рассуждений (некоторые их них приведем без пояснений) (табл. 62):

Таблица 62

№
1	Правило заключения – утверждающий модус (Modus Ponens)	Если из высказывания А следует высказывание В и справедливо (истинно) высказывание А, то справедливо В
2	Правило отрицания – отрицательный модус (Modus Tollens)	Если из А следует В, но высказывание В неверно, то неверно А
3	Правила утверждения-отрицания (Modus Ponendo-Tollens)	Если справедливо или высказывание А, или высказывание В (в разделительном смысле) и истинно одно из них, то другое ложно
4	Правила отрицания-утверждения (Modus Tollen-Ponens)	Если истинно или А, или В (в разделительном смысле) и неверно одно из них, то истинно другое
Если истинно А или В (в неразделительном смысле) и неверно одно из них, то истинно другое
5	Правило транзитивности	Если из А следует В, а из В следует С, то из А следует С
6	Закон противоречия	Если из А следует В и , то неверно А
7	Правило контрапозиции	Если из А следует В, то из того, что неверно В, следует, что неверно А
8	Правило сложной контрапозиции	Если из А и В следует С, то из А и следует
9	Правило сечения	Если из А следует В, а из В и С следует D, то из А и С следует D
10	Правило импортации (объединения посылок)
11	Правило экспортации (разъединения посылок)
12	Правила дилемм

Пример 52.

Следующие рассуждения не являются правильными:

.

2.3.2. Метод Вонга

Пусть дана клауза в своей наиболее общей форме:

В₁, В₂, …, В_n Þ А₁, А₂, …,A_n

Шаг 1.Снятие отрицаний с посылок и заключений. С этой целью нужно опустить знак отрицаний у A_i и B_j и перенести их в противоположные стороны относительно символа Þ.

Шаг 2. Если слева от символа Þ встречается конъюнкция, а справа дизъюнкция, то их следует заменить на запятые.

Шаг 3. Если после предыдущих шагов оказалось, что связкой, расположенной слева от Þ, является дизъюнкция, а справа – конъюнкция, то образуются две новые клаузы, каждая из которых содержит одну из двух подформул, заменяющих исходную клаузу.

Шаг 4. Если одна и та же буква находится с обеих сторон символаÞ, то такая строка считается доказанной. Исходная клауза является теоремой, если все ветви оканчиваются истинными клаузами. В противном случае переходим к шагу 3.

Пример 53.

Выяснить, является ли клауза теоремой:

.

Решение.

Шаг 1. .

Избавляемся от отрицаний. В результате получаем: .

Шаг 2. Поскольку слева от символа Þ не встречается конъюнкция, а справа не встречается дизъюнкция, то шаг 2 как таковой отсутствует.

Шаг 3. Построим дерево доказательств (рис. 11):

Так как есть не доказанные строки, то исходная клауза теоремой не является.

Пример 54.

Выяснить, является ли клауза теоремой:

.

Решение.

Представим ход доказательства в виде дерева (рис. 12). Поскольку все строки доказаны, то исходная клауза является теоремой.

2.3.3. Метод резолюций

Методику продемонстрируем на примере. Пусть требуется доказать:

.

Сначала поступают точно так же, как и по методике Вонга, только необходимо преобразовать клаузу таким образом, чтобы слева от символа Þ был ноль Æ:

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

Выпишем по порядку все посылки и далее начнем их «склеивать». Дизъюнкты можно перебирать автоматически в соответствии с возрастанием порядковых номеров. Такая стратегия поиска нуля очень непродуктивна. К решению данной задачи можно подойти творчески.

В итоге получим:

1. АÚ В	5. (1; 4)
2. СÚ А	6. (2; 4) С
3.	7. (3; 5)
4.	8. (6; 7) Æ

Иначе, произведенные раннее преобразования, можно представить в следующем виде:

2.4. Логика предикатов

2.4.1. Основные понятия, связанные с предикатами

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

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

Определение. N-местным предикатом, определенном на множествах М₁, М₂, …, М_n, называется предложение, содержащее n переменных х₁, х₂, …, х_n, превращающееся в высказывание при подстановке вместо этих переменных любых конкретных элементов из множеств М₁, М₂, …, М_n соответственно.

Обозначение. Чаще всего предикаты обозначают большими латинскими буквами, а число переменных указывает на его размерность: P(x₁, x₂, …, x_n).

Предикат также называют функцией-высказыванием.

Пример 55.

Рассмотрим три высказывания:

А – «Рубль – валюта России»;

В – «Доллар – валюта России»;

С – «Доллар – валюта США».

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

P(x): «х – валюта России», где х Î М.

Если же в высказывания подставить не только предметную переменную х, определенную на множестве М, но и вместо наименований стран ввести предметную переменную у, определенную на множестве названий стран У, то получим двуместный предикат:

Q(x, у): «х - валюта страны у», где х Î М, у Î У.

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

Пример 56.

Пусть задан одноместный предикат P(x), хÎМ, где М = {1, 2, 3, 4, 5}. Значение предиката можно задать таблицей (табл. 63):

Таблица 63

Пример 57.

Предикат задан высказывательной формой Р(х): «в слове х буква «а» встречается не более двух раз», хÎМ, где М = {конь, стол, карандаш, зал, чаша, барабан}.

Построим таблицу значений для данного предиката (табл. 64):

Таблица 64

Определение. Множеством истинности предиката Р(х₁, х₂, …, х_n), заданного на множествах М₁, М₂, …, М_n, называется совокупность всех упорядоченных n-систем (а₁, а₂, …, а_n), в которых таких, что данный предикат обращается в истинное высказывание при подстановке х₁=а₁, х₂=а₂, …, х_n=а_n.

Это множество будем обозначать Р⁺.

Пример 58.

Определить множество истинности предикатов, заданных на соответствующих множествах:

1. Р(х): «х кратно 3», хÎМ, где М = {1, 2, 3, 4, 5, 6, 7, 8, 9};

2. G(x, y): «x² + y² < 0», (x, y) Î R´R;

3. Q(x): «sin²x + cos²x = 1», хÎ R.

R – множество действительных чисел.

Решение.

1. Р⁺ = {3, 6, 9};

2. G⁺ = Æ;

3. Q⁺ = R.

2.4.2. Классификация предикатов

Определение. Предикат Р(х₁, х₂, …, х_n), заданный на множествах М₁, М₂, …, М_n, называется:

1. тождественно-истинным, если при любой подстановке вместо переменных х₁, х₂, …, х_n любых конкретных предметов а₁, а₂, …, а_n из множеств М₁, М₂, …, М_n соответственно он превращается в истинное высказывание Р(а₁, а₂, …, а_n);
2. тождественно-ложным, если при любой подстановке вместо переменных х₁, х₂, …, х_n любых конкретных предметов из множеств М₁, М₂, …, М_n соответственно он превращается в ложное высказывание;
3. выполнимым (опровержимым), если существует, по крайней мере, один набор конкретных предметов, при подстановке которого вместо соответствующих переменных в предикат, последний обращается в истинное (ложное) высказывание.

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

Утверждение.

1. Если предикат Р(х₁, х₂, …, х_n), заданный на множествах М₁, М₂, …, М_n является тождественно-истинным, то его множество истинности Р⁺=М₁ ´ М₂´ …´ М_n.
2. Если предикат Р(х₁, х₂, …, х_n), заданный на множествах М₁, М₂, …, М_n является тождественно-ложным, то его множество истинности Р⁺=Æ.
3. Если предикат Р(х₁, х₂, …, х_n), заданный на множествах М₁, М₂, …, М_n является выполнимым, то его множество истинности Р⁺¹ Æ.
4. Если предикат Р(х₁, х₂, …, х_n), заданный на множествах М₁, М₂, …, М_n является опровержимым, то его множество истинности Р⁺¹ М₁ ´ М₂´ …´ М_n.

Определение. Дваn-местных предиката Р(х₁, х₂, …, х_n) и Q(х₁, х₂, …, х_n), заданных над одними и теми же множествами М₁, М₂, …, М_n, называются равносильными, если набор элементов превращает первый предикат в истинное высказывание Р(а₁, а₂, …, а_n) в том и только в том случае, когда этот набор превращает в истинное высказывание Q(а₁, а₂, …, а_n) второй предикат.

Утверждение о равносильности двух предикатов P и Q символически будем записывать так: P Û Q.

Пример.

Необходимо решить уравнение (или, другими словами, найти множество истинности предиката): 4х – 2 = -3х – 9.

Решение.

Делая равносильные преобразования, найдем множество истинности предиката:

4х – 2 = -3х – 9 Û 4х + 3х = -9 + 2 Û х = -1.

Определение. Предикат Q(х₁, х₂, …, х_n), заданный над множествами М₁, М₂, …, М_n, называется следствием предикатаР(х₁, х₂, …, х_n), заданного над теми же множествами, если он превращается в истинное высказывание на всех наборах значений предметных переменных на соответствующих множествах, на которых в истинное высказывание превращается предикат Q(х₁, х₂, …, х_n).

Другими словами (в терминах множеств истинности), можно сказать, что предикат Q является следствием предиката Р тогда и только тогда, когда Р⁺ Í Q⁺.

Теорема. Каждые два тождественно истинных (тождественно ложных)предиката, заданных на одних и тех же множествах, равносильны. Обратно, всякий предикат, равносильный тождественно истинному (тождественно ложному) предикату, сам является тождественно истинным (тождественно ложным) предикатом.

Теорема. Каждый тождественно истинный n-местный предикат является следствием любого другого n-местного предиката, определенного на тех же множествах. Каждый n-местный предикат является следствием любого тождественно ложного n-местного предиката, определенного на тех же множествах.

2.4.3. Логические операции над предикатами

Над предикатами можно проделывать те же самые логические операции, что и над высказываниями. Рассмотрим основные три операции в их связи с операциями над множествами.

Определение. Отрицанием n – местного предиката Р(х₁, х₂, …, х_n), определенного на множествах М₁, М₂, …, М_n, называется новый n-местный предикат, определенный на тех же множествах, обозначаемый ØР(х₁, х₂, …, х_n), который превращается в истинное высказывание при всех тех значениях предметных переменных, при которых исходный предикат превращается в ложное высказывание.

Теорема. Для n-местного предиката Р(х₁, х₂, …, х_n), определенного на множествах М₁, М₂, …, М_n, множество истинности его отрицания ØР(х₁, х₂, …, х_n) совпадает с его дополнением множества истинности данного предиката:

или .

Определение. Конъюнкциейn – местного предиката Р(х₁, х₂, …, х_n), определенного на множествах М₁, М₂, …, М_n, и т-местного предиката Q(у₁, у₂, …, у_т), определенного на множествах N₁, N₂, …, N_m, называется новый (n + m)-местный предикат, определенный на множествах М₁, М₂, …, М_n, N₁, N₂, …, N_m, обозначаемый Р(х₁, х₂, …, х_n)Ù Q(у₁, у₂, …, у_т), который превращается в истинное высказывание при всех тех и только тех значениях предметных переменных, при которых оба исходных предиката превращаются в истинные высказывания.

Теорема. Для n-местных предикатов Р(х₁, х₂, …, х_n) и Q(х₁, х₂, …, х_n), определенных на множествах М₁, М₂, …, М_n, множество истинности конъюнкции Р(х₁, х₂, …, х_n) Ù Q(х₁, х₂, …, х_n), совпадает с пересечением множеств истинности исходных предикатов:

.

Определение. Дизъюнкциейn – местного предиката Р(х₁, х₂, …, х_n), определенного на множествах М₁, М₂, …, М_n, и т-местного предиката Q(у₁, у₂, …, у_т), определенного на множествах N₁, N₂, …, N_m, называется новый (n + m)-местный предикат, определенный на множествах М₁, М₂, …, М_n, N₁, N₂, …, N_m, обозначаемый Р(х₁, х₂, …, х_n)Ú Q(у₁, у₂, …, у_т), который превращается в истинное высказывание при всех тех и только тех значениях предметных переменных, при которых в истинное высказывание превращается по меньшей мере один исходный предикат.

Теорема. Для n-местных предикатов Р(х₁, х₂, …, х_n) и Q(х₁, х₂, …, х_n), определенных на множествах М₁, М₂, …, М_n, множество истинности дизъюнкции Р(х₁, х₂, …, х_n) Ú Q(х₁, х₂, …, х_n), совпадает с объединением множеств истинности исходных предикатов:

.