close

Вход

Забыли?

вход по аккаунту

?

Chernicina

код для вставкиСкачать
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное автономное
образовательное учреждение высшего образования
САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ
В. Я. Черницина
ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ
ЛОГИКИ
Учебно-методическое пособие
Санкт-Петербург
2016
УДК 510.6
ББК 22.12
Ч49
Рецензент:
Д. Я. Каспин
Утверждено
редакционно-издательским советом университета
в качестве учебно-методического пособия
Черницина, В. Я.
Ч49 Элементы математической логики: учеб.-метод. пособие /
В. Я. Чериницина. – СПб.: ГУАП, 2016. – 52 с.
В учебно-методическом пособии излагаются основные разделы,
необходимые для студентов начального и среднего образования,
изучающих математическую логику (алгебру логики, исчисление
высказываний и логику предикатов). Содержание теоретического материала и предлагаемых задач определяются требованиями
к подготовке студентов данных специальностей. В пособии содержится большое количество примеров, необходимых как для освоения теоретического материала, так и для приобретения практических навыков по решению задач логического характера. Часть задач
дана с решениями, большое количество задач предлагается для самостоятельного решения.
Учебно-методическое пособие адресовано студентам факультета
среднего профессионального образования, обучающимся по специальностям 09.02.03 «Программирование в компьютерных системах»
и 09.02.01 «Компьютерные системы и комплексы».
УДК 510.6
ББК 22.12
©
©
Черницина В. Я., 2016
Санкт-Петербургский государственный
университет аэрокосмического
приборостроения, 2016
Предисловие
Настоящее учебно-методическое пособие дает возможность
студенту самостоятельно освоить начало математической логики,
которая изучается при подготовке специалистов среднего звена
специальности 09.02.03 «Программирование в компьютерных системах» и является основой дисциплины «Элементы математической логики», а также составляет часть дисциплины «Дискретная
математика» специальности 09.02.01 «Компьютерные системы и
комплексы».
В работе в доступной форме представлены основные разделы,
традиционно изучаемые в рамках математической логики: алгебра
логики и исчисление высказываний, логика и исчисление предикатов, – рассмотрены вопросы содержательного и формального определения логики высказываний и логики предикатов. Содержание
разделов пособия взаимно связано друг с другом, в них представлено большое количество примеров и решенных задач, помогающих
освоить и закрепить изучаемый материал.
Основное назначение пособия – помочь студенту среднего профессионального образования, как очного, так и заочного обучения,
самостоятельно, без помощи преподавателя достичь понимания начальных основ математической логики, ее проблемных задач и доступных методов решения. С этой целью достаточно подробно рассмотрен первый раздел «Алгебра логики», так как здесь заложены
основные приемы и методы логических преобразований. Следующие разделы представлены кратко, в виде основных положений,
которые, однако, позволяют проиллюстрировать постановку задач
и простейшие методы решения.
В результате освоения соответствующей учебной дисциплины
с помощью настоящего учебно-методического пособия студент будет уметь формулировать простые задачи логического характера и
применять средства математической логики для их решения.
Кроме того, студент будет знать:
– основные принципы математической логики, теорию множеств и теорию алгоритмов;
– формулы алгебры высказываний;
– методы минимизации алгебраических преобразований;
– основы языка и алгебры предикатов.
3
I. АЛГЕБРА ЛОГИКИ
1. Понятие высказывания
Математическая логика – это анализ методом рассуждений. При
этом исследуются формы рассуждений, а не содержание. То есть
математическая логика исследует соотношения между основными
понятиями математики, на базе которых доказываются математические утверждения. Простейшую из формальных логических теорий называют алгеброй высказываний, поэтому знакомство с элементами математической логики начинают с понятия «высказывание», которое лежит в основе математико-логической теории.
Логическое высказывание есть повествовательное предложение, о котором в данной ситуации можно сказать, что оно истинно
или ложно, но ни то ни другое одновременно. Например, «Москва –
столица России», «два больше трех».
Ясно, что не все высказывания могут быть логическими. Например, высказывание «Да здравствуют наши спортсмены» не является логическим.
Логическому высказыванию можно поставить в соответствие
логическую переменную х, которая принимает значение 1, если
высказывание истинно, и 0, если оно ложно.
Из отдельных простых высказываний можно построить новое
высказывание (составное), которое может быть использовано в качестве одного из простых составляющих какого-то другого, более
сложного составного высказывания. Такие высказывания получаются с помощью простейших связок НЕ, И, ИЛИ и т. д., которые
рассматриваются в дальнейшем. Значение истины составного высказывания определяется значениями истинности его компонент.
2. Простейшие связки (или логические операции
над высказываниями)
Высказывания будем обозначать буквами латинского алфавита
Х, Y, Z, ...
При рассмотрении очередной связки для определения истинности составного высказывания удобно строить таблицы истинности.
В каждой строке этой таблицы указывается набор составляющих
высказываний и соответствующее значение составного высказывания. При этом наборы из нулей и единиц, отвечающих составляющим высказываниям, в каждой строке таблицы имеют стандартное
расположение, т. е. расположены в порядке возрастания.
4
Отрицанием высказывания Х называется новое высказывание
X , которое истинно, когда X ложно, и наоборот, ложно, если X истинно (обозн. ).
Таблица истинности для отрицания:
X
X
0
1
1
0
Конъюнкцией (обозн. ∧, &, ·) двух высказываний Х и Y называется новое высказывание Х∧Y, которое истинно только в том случае, когда Х и Y оба истинны.
Таблица истинности для конъюнкции:
X
Y
X∧Y
0
0
0
0
1
0
1
0
0
1
1
1
Дизъюнкцией (обозн. ∨, +) двух высказываний Х и Y называется
новое высказывание Х∨Y, которое истинно, когда хотя бы одно из
них истинно.
Таблица истинности для дизъюнкции:
X
Y
X∨Y
0
0
0
0
1
1
1
0
1
1
1
1
Импликацией (или следованием, обозн. →) двух высказываний
Х и Y называется новое высказывание Х→Y, которое ложно тогда и
только тогда, когда Х истинно, а Y ложно.
5
Таблица истинности для импликации:
X
Y
X→Y
0
0
1
0
1
1
1
0
0
1
1
1
Эквиваленцией (или эквивалентностью, обозн. ↔, ~ , = ) двух высказываний Х и Y называется новое высказывание Х~Y, которое истинно тогда и только тогда, когда Х и Y оба истинны или оба ложны.
Таблица истинности для эквиваленции:
X
Y
X~Y
0
0
1
0
1
0
1
0
0
1
1
1
Для образования составных высказываний каждой новой связкой можно пользоваться многократно, получая более сложные
составные высказывания (по аналогии с получением сложных алгебраических выражений). Всякое сложное высказывание, полученное из элементарных высказываний посредством применения
указанных логических операций, называется формулой алгебры
логики. Порядок выполнения операций – сначала в скобках (как
обычно в математике). Если скобок нет, то приоритет следующий:
∧, ∨, →, ~, . Логическое значение формулы алгебры логики полностью определяется логическими значениями входящих в нее
элементарных высказываний и может быть определено с помощью
таблицы истинности.
Две формулы алгебры логики называются равносильными, если
они принимают одинаковые значения при одинаковых значениях
аргументов. Например, Õ ∨ Y = Õ ∧ Y. (Проверить с помощью таблицы истинности).
Если при любых значениях аргументов, входящих в формулу
получается всегда истина, то такую формулу называют тавтологией (тождественно истинной).
6
Если же при любых значениях аргументов, входящих в формулу, получается всегда ложь, то такую формулу называют противоречием (тождественно ложной).
Например, тождественно истинны формулы Х→(Y→Х), Õ ∨ Õ .
А формула Õ ∧ Õ тождественно ложна (с помощью таблицы истинности это легко проверить).
Если существует хотя бы один набор аргументов, при котором
формула будет истинной, то такую формулу называют доказуемой.
3. Основные законы логических операций
(или законы булевой алгебры)
Законы коммутативности: Õ ∨ Y = Y ∨ Õ; Õ ∧ Y = Y ∧ Õ .
Законы
ассоциативности:
Õ ∨ (Y ∨ Z) = (Õ ∨ Y ) ∨ Z;
Х ∧ Y ∧ Z.
Õ ∧ (Y ∧ Z) =
Законы
дистрибутивности:
Õ ∧ (Y ∨ Z) = (Õ ∧ Y ) ∨ (Õ ∧ Z);
Õ ∨ (Y ∧ Z) = (Õ ∨ Y ) ∧ (Õ ∨ Z) .
Законы поглощения: Õ ∨ (Õ ∧ Y ) =
Õ.
Õ; Õ ∧ (Õ ∨ Y ) =
Законы склеивания: (Õ ∨ Y ) ∧ (Õ ∨ Y ) =
Õ; (Õ ∧ Y ) ∨ (Õ ∧ Y ) =
Õ.
Законы де Моргана: Õ ∨ Y = Õ ∧ Y; Õ ∧ Y = Õ ∨ Y.
Законы 0 и 1: Õ ∨ 0 =
Õ; Õ ∨ 1 =
1; Õ ∧ 0 =
0; Õ ∨ 1 =
Õ.
Закон исключения третьего: X ∨ Õ =
1.
Законы идемпотентности: Õ ∧ X; Õ ∨ X =
X.
Закон двойного отрицания: Õ = Õ.
Сформулированные законы легко проверить с помощью таблицы истинности.
Для проверки любых равенств необходимо составить таблицу
истинности для левой и правой части ∀ равенства. При этом необходимо добиться, чтобы левая часть равенства имела в каждой
строке одинаковые значения с правой частью. Тогда проверяемая
формула будет доказуемой.
Любую формулу алгебры логики путем равносильных преобразований можно привести к формуле, содержащей только операции
отрицания, дизъюнкции и конъюнкции.
Примеры: Доказать равносильность формул с помощью таблицы истинности.
Õ → Y = Õ ∨ Y. (1)
Õ ~ Y = ( Õ → Y ) ∧ ( Y → Y ) = (Õ ∨ Y ) ∧ (Y ∨ Õ). (2)
4. Дополнительные связки (или новые логические операции)
Штрих Шеффера (обозн. ) – антиконъюнкция:
7
Õ | Y= Õ ∧ Y.
Стрелка Пирса (обозн. ↓ ) – антидизъюнкция:
Õ ↓ Y = Õ ∨ Y.
Сумма по модулю два (обозн. ⊕) – антиэквивалентность:
Õ⊕Y = Õ ~Y =
( Õ → Y ) ∧ ( Y → Õ ).
Логическая разность (обозн. –) – антиимпликация:
Õ - Y = Õ → Y.
Так как новые логические операции отрицают известные раннее
логические операции, то таблицу истинности легко составить самостоятельно.
Примеры на закрепление логических операций:
1. Составить таблицу истинности формулы Õ ⊕ Y → Z ∨ |Y ∧ Õ .
Решение: Расставим скобки: (Õ ⊕ Y ) → (Z ∨ (Õ |(Y ∧ Õ))) и обозначим через f все выражение.
X
Y
Z
X
Y
Z
X⊕Y
Y∧X
X |(Y ∧ X)
Z ∨ (X |(Y ∧ X))
f
0
0
0
1
1
1
0
1
1
1
1
0
0
1
1
1
0
0
1
1
1
1
0
1
0
1
0
1
1
0
1
1
1
0
1
1
1
0
0
1
0
1
1
1
1
0
0
0
1
1
1
0
1
1
1
1
0
1
0
1
0
1
0
1
1
1
1
1
0
0
0
1
0
0
1
1
1
1
1
1
0
0
0
0
0
1
1
1
2. Доказать тождественную истинность формулы Õ → ( Õ → Y ).
Решение: Составим таблицу истинности:
8
Х
Y
Õ
Х→Y
Õ → (Õ → Y)
0
0
1
1
1
0
1
1
1
1
1
0
0
0
1
1
1
0
1
1
Последний столбец состоит из 1, следовательно, тождественная
истинность формулы доказана.
3. Доказать эквивалентность
Õ ∧ (X ∨ Z) ∧ (Y ∨ Z) ↔ (X ∧ Y ) ∨ (X ∧ Z) .
Для решения следует обозначить выражение слева от операции
эквивалентности, например, через f1, а через f2 – выражение справа. Для f1 и f2 следует построить таблицы истинности, и если эти
таблицы совпадают, то эквивалентность будет доказана.
Можно эквивалентность в этом примере доказать другим способом, используя основные законы логических операций. Рассматривая левую часть от операции эквивалентности, заметим,
что Õ ∧ (X ∨ Z) =по
X
закону поглощения. В левой части остается
Õ ∧ (Y ∨ Z), и, используя закон дистрибутивности, получаем выражение равное правой части от знака эквивалентности.
4. Доказать, что булево выражение (X ∧Y ) ∧ (X ∨ Y ) эквивалентно Х.
Для решения используем основные законы логических операций:
(X ∧Y ) ∧ (P ∨ Q) = (X ∨ Y ) ∧ (X ∨ Y ) = (закон де Моргана)
= (X∨ Y ) ∧ (X ∨ Y ) = (закон двойного отрицания)
= Х (закон склеивания).
Далее самостоятельно решить следующие примеры:
1. Используя законы булевой алгебры, проверить соотношение
(( X ∨ Y ) ∧ ( Z ∨ ( X ∧ Y ))) = X ∨ Y.
2. Доказать равносильность выражения, используя основные
законы логических операций:
( X ∧ Y ) ∨ (Y ∧ Z) = (X ∧ Y) ∨ (X ∧ Z) ∨ (Y ∧ Z).
3. Упростить выражение (X ∨ Y ) → X ∨ Y ) ∧ Y . Ответ: Y.
4. Доказать тождественную истинность формулы, используя основные законы логических операций: (X→Y)→((Y→Z)→(X∨Y→Z).
Ответ: 1.
5. Булевы функции
(функции алгебры логики)
Любая формула алгебры логики является на самом деле функцией аргументов (или элементарных высказываний), которые при9
нимают два значения: 0 и 1, при этом значение формулы может
быть равно 0 или 1.
Функцией алгебры логики от n переменных (или функцией
n
Буля) называется любая формула f : {0,1} → {0,1}, которая произвольному набору нулей и единиц из n элементов ставит в соответствие значение 0 или 1.
Булеву функцию можно задать таблицей истинности:
x1, x2 ,..., xn -1,xn
f (x1, x2 ,..., xn -1,xn )
00…00
00…01
00…10
…………….
111…11
f(0 0 … 0 0)
f(0 0 … 0 1)
f(0 0 … 1 0)
……………..
f(1 1 … 1 1)
Из таблицы видно, что число различных двоичных наборов длины n x1, x2 , …, xn -1, xn конечно и равно 2n. Ясно, что тавтологии
и противоречия представляют собой постоянные функции, а две
равносильные формулы выражают одну и ту же функцию. Каждая
функция определяется таблицей истинности, состоящей
из 2n
n
2n
строк. Общее же число наборов из 0 и 1 длины 2 равно 2 . Таково
число различных функций алгебры логики от n переменных (т. е.
число булевых функций с ростом n растет очень быстро).
Две булевы функции называются равными, если для любых одинаковых наборов значений переменных обе функции принимают
одинаковые значения.
Булевых функций одной переменной всего 4, двух переменных –
16, а трех – уже 256.
Рассмотрим функции одной и двух переменных.
Таблица истинности при n = 1:
x
f0
f1
f2
f3
0
0
0
1
1
1
0
1
0
1
Здесь f0 и f3 – константы 0 и 1:
=
f1 (x) x=
, f2 ( x ) x.
10
Таблица истинности булевой функции двух переменных (n = 2):
x
y
f0
f1
f2
f3
f4
f5
f6
f7
f8
f9
f10
f11
f12
f13
f14
f15
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
0
1
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
1
0
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
1
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
Просматривая значение функций по столбцам, с учетом определения логических операций получим аналитические выражения
для всех 16 функций при n = 2:
f0 = 0;
f4= y - x;
f8= x ↓ y;
f12 = x ;
f1= x ∧ y ;
f5 = y ;
f9= x ↔ y;
f13 = x → y;
f2= x - y;
f6= x ⊕ y;
f10 = y ;
f14 = x | y;
f3 = x;
f7= x ∨ y ;
f11= y → x ;
f15 = 1.
Свойства элементарных булевых функций
Для булевых функций справедливы равенства, аналогичные
формулам, сформулированным ранее, как основные законы логических операций. Настоящие свойства обобщают эти законы с учетом новых логических операций:
1. Функции ∧, ∨, ⊕, ↓, | обладают свойством коммутативности.
2. Функции ∧, ∨, ⊕ обладают свойством ассоциативности и дистрибутивности.
3. Закон де Моргана: x ∧ y = x ∨ y; x ∨ y = x ∧ y.
4. Закон двойного отрицания: x = x.
5. Выражение ∨ через ∧ и ⊕: x ∨ y = x ∧ y ⊕ x ⊕ y.
6. Выражение ∨ через →: x ∨ y = (x→y)→y.
7. Выражение отрицания через | , ↓, ⊕ и ↔: x | x = x ↓ x = x =
= x ⊕ 1 = x ↔ 0.
8. Выражение ∧ через |: x ∧ y =
(x | y) | (x | y).
9. Выражение ∨ через↓: x ∨ y = (x ↓ y) ↓ (x ↓ y).
10. Закон поглощения: (x ∧ y) ∨ x= x; x ∧ (x ∨ y=
) x.
11. Для функций ∨, ∧, ⊕ справедливы следующие тождества:
x ∧ x= x; x ∨ x= x; x ⊕ x= 0;
x∧x=
0; x ∨ x =
1; x ⊕ x =
1;
11
x∧0
= 0; x ∨ 0
= x; x ⊕ 0
= x;
x ∧ 1= x; x ∨ 1= 1; x ⊕ 1= x.
12. Для функций ∨, ∧ справедливы тождества:
x ∨ y = x ∨ x ∧ y; x ∧ y = x ∧ (y ∨ x) .
Для доказательства справедливости любого из приведенных
тождеств нужно составить таблицы истинности для булевых функций.
Булеву функцию любого числа переменных можно задавать
формулой, содержащей функции одной и двух переменных посредством постановки одних булевых функций вместо переменных
в другие булевы функции, т. е. посредством суперпозиции булевых
функций.
Примеры на представление булевых функций, содержащих любые известные логические операции через три основные операции:
∧, ∨ и :
1. (x | y ) → x ↓ y = по определению штрих Шеффера и стрелка
Пирса, а также используя равенство (1);
(
)
( x ∧ y ) ∨ ( x ∨ y ) = де Моргана;
(
)
(x ∧ y ) ∧ x ∨ y = де Моргана и закон двойного отрицания;
(x ∧ y) ∧=
(x ∨ y) òàê êàê
=
x∧x x ;
õ ∨ y – ответ.
ïî ðàâåíñòâó (1);
2. ((x → ó ) | x) ↓ y =
((x ∨ ó ) | x) ↓ y =
ïî îïðåäåëåíèþ øòðèõ Øåôôåðà ;
(õ ∧ ó ) ∧ õ =
де Моргана и закон двойного отрицания;
((õ ∨ ó ) ∨ x) ↓ y =
де Моргана и закон двойного отрицания;
закон поглощения;
((õ ∧ ó) ∨ x) ↓ y =
определение стрелки Пирса;
õ↓y=
õ ∨ ó = де Моргана;
õ ∧ ó – ответ.
Следующие примеры решить самостоятельно:
1. ((x | y ↓ õ) → y. Ответ: õ ∨ ó .
2. (õ → y ) → (x | y) . Ответ: (õ ∧ ó) ∨ (õ ∨ ó ).
3. (((x | y) ↓ õ) | ó ). Ответ: 1.
4. õ ∨ y ⊕ z ∧ (x ∨ z). Ответ: (õ ∨ ó)(ó ∨ z).
Примечание: здесь и далее в более громоздких выражениях знак
конъюнкции для упрощения формулы не указываем (как в обычной математике операция умножения).
5. ((x → y) ~ y) ⊕ (õ → y). Ответ: х.
12
6. Дизъюнктивные и конъюнктивные нормальные формы
Конъюнктивным одночленом от n переменных õ1, õ2 ,..., õn называется конъюнкция этих переменных или их отрицаний.
Дизъюнктивным одночленом от n переменных õ1, õ2 ,..., õn называется дизъюнкция этих переменных или их отрицаний.
Формула, определяющая дизъюнкцию элементарных конъюнктивных одночленов, называется дизъюнктивной нормальной формой (ДНФ).
Например, (õ ∧ ó ∧ z) ∨ (õ ∧ ó) ∨ (z ∧ y) ∨ z – ДНФ.
Определение для конъюнктивной нормальной формы (КНФ)
аналогично.
Например, (õ ∨ ó ∨ z) ∧ (õ ∨ z) ∧ y – КНФ.
Любая булева функция может иметь несколько представлений
в виде ДНФ и КНФ. Предыдущие примеры приведения булевых
функций к трем основным операциям (∧, ∨, ), как раз демонстрируют алгоритм получения ДНФ и КНФ методом равносильных преобразований.
Совершенная дизъюнктивная нормальная форма (СДНФ) – это
ДНФ, в которой каждый конъюнктивный одночлен содержит каждую переменную õi из набора аргументов в булевой функции
f (õ1, õ2 ,..., õn ) ровно один раз, при этом в конъюнкт входит либо
сама переменная õi, либо ее отрицание õi.
Для нахождения СДНФ методом равносильных преобразований
данную формулу представляем сначала в виде ДНФ, а затем преобразуем ее конъюнкции с помощью следующих действий:
1) если в конъюнкт входит некоторая переменная вместе со своим отрицанием, то удаляем этот конъюнкт из ДНФ;
2) если в конъюнкт входит одна и та же переменная несколько
раз, то удаляем все эти переменные, кроме одной;
3) если в некоторый конъюнкт, например, õ ∧ z, не входит переменная y, то этот конъюнкт заменяем на эквивалентную формулу
õ ∧ z(y ∧ ó ) и, применяя закон дистрибутивности, приводим формулу к ДНФ. Если недостающих переменных несколько, то для каждой из них добавляем формулу вида (y ∧ ó );
4) если в полученной ДНФ имеется несколько одинаковых конъюнктов, то оставляем только один.
В результате таких действий получается СДНФ.
Определение для совершенной конъюнктивной нормальной
формы (СКНФ) аналогично; предлагается записать его самостоятельно.
13
Примеры СДНФ:
f1 (x, y, z) = xyz ∨ xyz ∨ xyz;
f2 (x, y, z) = xyz ∨ xyz ∨ xyz ∨ xyz ∨ xyz.
Примеры CКНФ:
f3 (x, y, z) = (x ∨ y ∨ z) ∧ (x ∨ y ∨ z) ∧ (x ∨ y ∨ z);
f4 (x, y, z) = (x ∨ y ∨ z) ∧ (x ∨ y ∨ z) ∧ (x ∨ y ∨ z) ∧ (x ∨ y ∨ z) ∧ (x ∨ y ∨ z).
Определения для СДНФ и СКНФ позволяют сформулировать
следующие утверждения:
1. Каждая булева функция, отличная от 0, имеет единственную
СДНФ.
2. Каждая булева функция, не равная 1, имеет единственную
СКНФ.
Эти утверждения называются теоремой о функциональной полноте булевых функций.
Например, имея выражение в виде ДНФ для булевой функции,
применяя этот алгоритм, можно получить следующую СДНФ:
f1 (x, y, z) = x ∧ x ∨ x ∨ y ∧ x ∧ y;
x ∧ x ∨ x ∨ y ∧ z ∧ y = x ∨ yz =
= x(y ∨ y) ∨ yz(x ∨ x) =
= xy ∨ xy ∨ xyz ∨ xyz =
= xy(z ∨ z) ∨ xy(z ∨ z) ∨ xyz ∨ xyz=
= xyz ∨ xyz ∨ xyz ∨ xyz ∨ xyz ∨ xyz =
= xyz ∨ xyz ∨ xyz ∨ xyz ∨ xyz.
Описание алгоритма приведения КНФ к СКНФ аналогично вышеизложенному алгоритму для получения СДНФ и имеет вид:
1) если в дизъюнкт не входит какая-то переменная, то этот дизъюнкт повторяем дважды: с этой переменной и ее отрицанием;
2) если в дизъюнкт переменная входит дважды, то лишнюю переменную отбрасываем;
3) если КНФ содержит два одинаковых сомножителя, то оставляем один из них;
4) если в дизъюнкт входит, например, пара х ∨ õ , то ее отбрасываем.
Напр. для нахождения СКНФ для функции
f (x, y, z) =
(x ∨ y)(y ∨ z),
14
правая часть которой есть КНФ, следует записать ее в виде
f (x, y, z) = x ∨ y ∨ z)(x ∨ y ∨ z)(x ∨ y ∨ z)(x ∨ y ∨ z),
так как первый дизъюнкт не содержал переменную z, а второй – переменную x. В результате сразу получаем СКНФ.
Для нахождения СДНФ и СКНФ вторым способом следует исходную формулу для булевой функции представить таблицей истинности и строить по ней требуемую совершенную форму.
Затем, просматривая строки, для которых функция равна 1, составлять конъюнкты таким образом: если переменная в очередной
строке равна 1, то в конъюнкт она запишется без отрицания, а если
переменная равна 0, то в конъюнкте будет с отрицанием. Так, выписывая все конъюнкты, объединяем их, проставляя знаки дизъюнкции. В результате получается СДНФ.
Для получения СКНФ просматриваем строки таблицы, для которых функция равна 0. Составляем дизъюнкты таким образом,
если переменная в этой строке равна 0, то в дизъюнкт она входит без
отрицания, а если переменная в рассматриваемой строке равна 1,
то в дизъюнкт она войдет с отрицанием. Затем все дизъюнкты объединяем знаком конъюнкции и получаем СКНФ.
Напимер, для формулы (x ∨ y ) → (z ⊕ x) после составления таблицы истинности
x
y
z
x
y
z
х ∨ ó
z ⊕x
f
0
0
0
1
1
1
1
0
0
0
0
1
1
1
0
1
1
1
0
1
0
1
0
1
0
0
1
0
1
1
1
0
0
0
1
1
1
0
0
0
1
1
1
1
1
1
0
1
0
1
0
1
0
0
1
1
0
0
0
1
1
1
1
1
1
1
0
0
0
1
0
0
получаем
ÑÄÍÔ = xyz ∨ xyz ∨ xyz ∨ zyz ∨ zyz;
ÑÊÍÔ = (x ∨ y ∨ z) ∧ (x ∨ y ∨ z) ∧ (x ∨ y ∨ z) .
Примеры из практических работ, проводимых на занятиях, которые рекомендуется разобрать для закрепления изученного материала.
15
Задания:
1. Проверить, будут ли эквиваленты нижеприведенные формулы, двумя способами:
а) составлением таблиц истинности;
б) приведением формул к совершенным СДНФ или СКНФ с помощью эквивалентных преобразований.
2. С помощью эквивалентных преобразований привести последнюю формулу к ДНФ, КНФ, СДНФ и СКНФ.
Вариант 1.
1. x → (y ⊕ z) è (x → y) ⊕ ( x → z )
2. ( x ∨ y ) → ( z ⊕ x )
Вариант 2.
1. x (y → z) è ( x y ) → ( x z )
2. ( x ∨ y ) → (z ⊕ x)
Вариант 3.
1. x ∧ ( y ⊕ z ) è ( x ∧ y ) ⊕ ( x ∧ z )
2. ( x ∨ y ) → ( z ⊕ x )
Вариант 4.
1. x ∧ ( y ⊕ z ) è ( x ∧ y ) ⊕ ( x ∧ z )
2. ( x ∨ y ) → ( z ↔ x )
Вариант 5.
1. x ∧ (y ↔ z) è ( x ∧ y ) ↔ ( x ∧ z ) 2. ( x ∨ y ) → ( z ↔ x )
Вариант 6.
1. x ∧ ( y ↔ z ) è ( x ∧ y ) ↔ ( x ∧ z )
2. ( x y ) ⊕ (z → x)
Вариант 7.
1. x → (y ⊕ z) è (x → y) ⊕ ( x → z )
2. ( x ∨ y ) → ( z ⊕ x )
Вариант 8.
1. x (y → z) è ( x y ) → ( x z )
2. ( x ∨ y ) → (z ⊕ x)
Вариант 9.
1. x ∧ ( y ⊕ z ) è ( x ∧ y ) ⊕ ( x ∧ z )
2. ( x ∨ y ) → ( z ⊕ x )
Вариант 10.
1. x ∧ ( y ⊕ z ) è ( x ∧ y ) ⊕ ( x ∧ z )
16
2. ( x ∨ y ) → ( z ↔ x )
Вариант 11.
1. x ∧ (y ↔ z) è ( x ∧ y ) ↔ ( x ∧ z ) 2. ( x ∨ y ) → ( z ↔ x )
Вариант 12.
1. x ∧ ( y ↔ z ) è ( x ∧ y ) ↔ ( x ∧ z )
2. ( x y ) ⊕ (z → x)
Вариант 13.
1. x → (y ⊕ z) è (x → y) ⊕ ( x → z )
2. ( x ∨ y ) → ( z ⊕ x )
Вариант 14.
1. x (y → z) è ( x y ) → ( x z )
2. ( x ∨ y ) → (z ⊕ x)
Вариант 15.
1. x ∧ ( y ⊕ z ) è ( x ∧ y ) ⊕ ( x ∧ z )
2. ( x ∨ y ) → ( z ⊕ x )
Вариант 16.
1. x ∧ ( y ⊕ z ) è ( x ∧ y ) ⊕ ( x ∧ z )
2. ( x ∨ y ) → ( z ↔ x )
Вариант 17.
1. x ∧ (y ↔ z) è ( x ∧ y ) ↔ ( x ∧ z ) 2. ( x ∨ y ) → ( z ↔ x )
Вариант 18.
1. x ∧ ( y ↔ z ) è ( x ∧ y ) ↔ ( x ∧ z )
2. ( x y ) ⊕ (z → x)
Вариант 19.
1. x → (y ⊕ z) è (x → y) ⊕ ( x → z )
2. ( x ∨ y ) → ( z ⊕ x )
Вариант 20.
1. x (y → z) è ( x y ) → ( x z )
2. ( x ∨ y ) → (z ⊕ x)
Вариант 21.
1. x ∧ ( y ⊕ z ) è ( x ∧ y ) ⊕ ( x ∧ z )
2. ( x ∨ y ) → ( z ⊕ x )
Вариант 22.
1. x ∧ ( y ⊕ z ) è ( x ∧ y ) ⊕ ( x ∧ z )
17
2. ( x ∨ y ) → ( z ↔ x )
Вариант 23.
1. x ∧ ( y ↔ z) è ( x ∧ y ) ↔ ( x ∧ z ) 2. ( x ∨ y ) → ( z ↔ x )
Вариант 24.
1. x ∧ ( y ↔ z ) è ( x ∧ y ) ↔ ( x ∧ z )
2. ( x y ) ⊕ (z → x)
Вариант 25.
1. x → (y ⊕ z) è (x → y) ⊕ ( x → z )
2. ( x ∨ y ) → ( z ⊕ x )
7. Алгебра Жегалкина и многочлен Жегалкина
Сумма по mod 2 или x ⊕ y – это булева функция, которая равна 1
тогда и только тогда, когда равна 1 только одна из переменных (или
это отрицание эквивалентности, как указывалось ранее).
х
у
х ⊕ у
õ~ó
0
0
0
0
0
1
1
1
1
0
1
1
1
1
0
0
=
x ⊕ y õ ~ ó = (õ → ó) ∧ (ó → õ)
Законы алгебры логики для суммы по mod 2 рассматривались
в свойствах элементарных булевых функций; укажем только необходимые нам сейчас:
x⊕x =
0 ;
x⊕x =
1;
x ⊕1 =
x
x⊕0 =
x ;
и выпишем также необходимые в дальнейшем равенства:
x ⊕ y = x ∧ y ∧ x ∧ y (ДНФ для суммы по mod 2);
x ⊕ y = x ∧ y ∧ x ∧ y (ДНФ для отрицания по mod 2);
x ∨ y = x ∧ y ⊕ x ⊕ y;
x ∨ y = (x ∧ y) ⊕ x ⊕ y.
Рекомендуется самостоятельно доказать эти равенства либо аналитически, либо с помощью таблицы истинности.
18
Операция сложения по mod 2 используется в логических функциях, называемых многочленом Жегалкина.
Многочленом Жегалкина называется многочлен, являющийся суммой по mod 2 константы (0 или 1) и различных одночленов,
в которых все переменные входят не выше, чем в первой степени.
Многочлен Жегалкина константы равен самой константе.
Многочлен Жегалкина булевой функции одной переменной
имеет вид
f (x=
) a0 ⊕ a1x;
двух переменных
f (x, y) = a0 ⊕ a1 ⊕ a2 y ⊕ a12 ( x ∧ y ) ;
трех переменных
f (x, y, z) =a0 ⊕ a1x ⊕ a2 y ⊕ a3z ⊕ a12 ( x ∧ y ) ⊕ a13 ( x ∧ z ) ⊕
⊕a23 ( y ∧ z ) ⊕ a123 (x ∧ y ∧ z)
и т. д.
В общем виде правая часть равенства записывается так:
∑
i1,i2..ik
ai1,i2…ik xi1 xi2 ... xik , (3)
причем на каждом наборе (i1, i2 ,…, ik ) все ij ( j = 1..k) различны, а
ai1,i2..i ∈ {0,1}.
k
Подсчитаем число многочленов Жегалкина от n переменных
õ1, õ2 ,..., õn , т. е. число выражений вида (3). Число членов xi1 ,…, xik
равно количеству подмножеств вида {i1, i2 ,…, ik } множества из n чи2n. Так как ai ,…, aik = 1 èëè 0, то общее число
сел {1,2,…, n}, т. е.
2n
многочленов 2 . А так как число булевых функций от n переменn
ных так же равно 22 , то каждая булева функция может быть представима многочленом Жегалкина и притом единственным образом.
Рассмотрим примеры получения многочлена Жегалкина с помощью эквивалентных преобразований:
1)  õ ∨ ó = õ ∧ ó (де Моргана)
= ( õ ⊕ 1)( ó ⊕ 1) (òàê êàê õ= x ⊕ 1)
= (õ ⊕ 1)(ó ⊕ 1) ⊕ 1 (снова õ= x ⊕ 1 , и, умножая двучлен на двучлен)
0)
= xy ⊕ x ⊕ y ⊕ 1 ⊕ 1 (так как x ⊕ x =
= xy ⊕ x ⊕ y ;
19
2)  (õ → y) → õ = õ ∨ ó ∨ x (õ → ó = x ∨ ó)
= xy ∨ x (де Моргана)
= xyx ⊕ xy ⊕ x (òàê êàê x ∨ y = xy ⊕ x ⊕ y)
= xy ⊕ xy ⊕ x (x ∧ x = x)
= x (òàê êàê
=
x ⊕ x 0).
Следующие примеры рекомендуется выполнить самостоятельно:
1) х∨у∨z; ответ: хуz⊕ху⊕хz⊕уz⊕х⊕у⊕z;
2) получить многочлен Жегалкина для всех булевых функций
от двух переменных;
3)  ( õ | ó ) → z ; ответ: хуz⊕xz⊕yz⊕x⊕z;
4)  ((x ~ y) → z ) | x) ; ответ: xyz⊕xz⊕yz⊕x⊕z.
Нахождение многочлена Жегалкина
с помощью таблицы истинности
Для того чтобы найти многочлен Жегалкина, нужно записать
его в общем виде и коэффициенты находить последовательно из системы уравнений, которая получается из таблицы истинности.
Получим многочлен Жегалкина этим способом непосредственно
на примере.
y, z) x ~ y → z .
Пример: f (x, =
Общий вид многочлена Жегалкина запишем в виде
f (x, y, z) = c0 Å cx x Å cy y Å czz Å cxy xy Å cxz xz Å cyz yz Å cxyz xyz, ci Î {0,1},
где для удобства индексы коэффициентов привязаны к переменным.
х
y
z
x~y
z
f
0
0
0
1
1
1
0
0
1
1
0
0
0
1
0
0
1
1
0
1
1
0
0
1
1
0
0
0
1
1
1
0
1
0
0
1
1
1
0
1
1
1
1
1
1
1
0
0
Для получения коэффициентов здесь просматриваем последовательно все строки таблицы, начиная с первой. Здесь f(0,0,0) = 1.
20
Подставляя значения функции и переменных в многочлен общего
вида, получаем 1 = ñ0 или ñ0 = 1.
Во второй строке таблицы f(0,0,1) = 0. Также подставляя новые
0 ñ0 ⊕ cz,
значения функции и переменных в многочлен, имеем =
а так как ñ0 уже найдено, то будет 1 ⊕ cz = 0. Но нам известно, что
x ⊕1 =
õ , поэтому cz = 1 .
В третьей строке таблицы f(0,1,0) = 1, и после подстановки в многочлен будет 1= 1 ⊕ ñó или ñó = 0.
В четвертой строке f(0,1,1) = 1 и после подстановки найденных
коэффициентов ñ0 и cz будет 1 = 1 ⊕ 1 ⊕ ñóz. А так как x ⊕ x= 0 (1 ⊕ 1),
получаем ñóz = 1.
Продолжая такой перебор всех строк таблицы, последовательно получаем все остальные коэффициенты ñõ = 0, ñxz = 1, ñõó = 0 и
ñõóz = 0, и искомый многочлен Жегалкина будет иметь вид
f (x, y, z) = 1 ⊕ z ⊕ xz ⊕ yz.
Следующие примеры предлагаются для самостоятельного получения многочлена Жегалкина (любым способом):
1)  õ ↓ ó → z ; ответ: 1 ⊕ z ⊕ xz ⊕ yz ⊕ xyz ;
(
)
2)  (x ~ y) → z ; ответ: 1 ⊕ x ⊕ xz ⊕ xy ⊕ xyz ;
3)  õ ∨ ó ⊕ óz(x ∨ z); ответ: 1 ⊕ x ⊕ xy ⊕ zy .
Примеры из практической работы.
Задание:
Найти многочлен Жегалкина двумя способами.
За исходную формулу взять примеры второго задания из практических работ, проводимых на занятиях (первоначальное выражение этого примера).
8. Полнота и замкнутость булевых функций.
Теорема Поста
Система булевых функций G = {f1, f2,..., fm } называется полной,
если любая булева функция может быть выражена через функции
из G с помощью суперпозиции.
Ясно, что множество всех булевых функций является полной
системой.
Наименьшее число булевых функций из числа полной системы,
которое также остается полным, называется базисом.
Существуют конкретные системы (функционально полные наборы функций или базисы), суперпозицией которых могут быть
выражены любые булевы функции. Например, ранее в разд. 3
утверждалось, что любую логическую формулу можно представить
21
только в виде трех операций: ∨, ∧ и . Это и означает, что система
булевых функции {∨, ∧, } является полной. Но если из нее убрать ∨
или ∧, она также останется полной, т. е. {∨, } и {∧, } являются базисами. Известны также другие системы булевых функций, которые
являются базисами:
{|}, {→, }, {↓}, {~, ∨, 0}, {∧, ⊕, 1} и т. д.
Последний указанный здесь базис называется базисом Жегалкина.
Можно показать, что например, функция х|у есть полная система функций (т. е. {|} есть базис).
Для этого достаточно показать, что каждая из функций õ , х∨у и
х∧у может быть выражена через штрих Шеффера.
1)  õ = õ ∧ õ = õ | õ;
2)  õ ∨ ó = õ ∧ ó = ((õ | õ) ∧ (ó | ó)) = ( õ | õ ) (ó ó);
3)  õ ∧ ó = ((õ ∧ ó)) = (õ | õ) | (y | y).
В качестве упражнения рекомендуется также проверить на выбор указанную здесь любую систему аналогичным способом: является ли базисом такая система.
Наличие большого набора базисов важно для решения задач минимизации схем устройств дискретного действия, так как из базисных схем с помощью суперпозиций можно составлять схемы, соответствующие любой булевой функции.
Решение проблемы нахождения любых других базисов булевых
функций было найдено Постом в 1921 г. по мере изучения замкнутых классов таких функций. Постом было выделено 5 классов замкнутых функций, на основе которых была решена проблема базисов булевых функций.
Пусть N – произвольный набор булевых функций. Будем рассматривать всевозможные комбинации (или суперпозиции) из этого набора функций. Множество таких комбинаций называется замыканием этого набора функций и обозначается [N].
Если [N] = N, то такой набор функций называется замкнутым
классом функций.
Классификация замкнутых функций
1. Обозначим Ì0 класс функций, сохраняющих 0, т. е. функций f = (x1, x2 ,..., xn ), для которых f(0,0,…,0) = 0.
Примеры: ∧, ∨, ⊕ ∈ Ì0 , но ~,  ∉ Ì0 ; [Ì0 ] = Ì0 .
2. Обозначим через Ì1 класс функций, сохраняющих 1, т. е.
функций f( õ1 , õ2 ,…, õn ), для которых f(1, 1, …, 1) = 1.
22
Примеры: ∧, ∨, ~ ∈ Ì1 , но ⊕,  ∉ Ì1; [Ì1 ] = Ì1 .
3.  ÌL – класс линейных функций.
Функция n переменных f (x1, x2,..., xn ) называется линейной,
если ее многочлен Жегалкина имеет вид
n
f (x1, x2 ,..., xn ) = ñ0 ⊕ ∑cx xi ; [Ì1 ] = Ì1.
i =1
4.  Ììîí – класс монотонных функций.
Пусть X(x1, x2 ,..., xn ), и Y (ó1, ó2 ,..., ón ) – двоичные наборы.
Говорят, что X≤Y, если для i = 1,n выполняется õi ≤ y (т. е. наборы сравнимы).
Если это не выполняется, то такие наборы не cравнимы.
Замечание: в некоторых учебниках сравнимость обозначается {,
например, 0{0, 0{1, 1{1 – сравнимые наборы.
Булева функция f (x1, x2,..., xn ), называется монотонной, если
для всех ее сравнимых двоичных наборов должно выполнятся:
из X≤Y следует f (X) ≤ f (Y ); [ Ììîí ] = Ììîí.
Примеры: ∨, ∧ – монотонные функции, но  – не монотонная
функция.
5. Ìñàì – класс самодвойственных функций.
Двойственной функцией называется такая функция:
(
)
f * (õ1, õ2 ,..., õn ) = f õ1, õ2 ,…, õn .
Примеры:
f= x ∨ y;
f = x ↓ y = x ∨ y;
f= x ∧ y;
f * = x ∨ y= x ∧ y; f *
= (x ↓ y=
) (x ∨ y)= x ∧ y = x | y; f * = x ∧ y= x ∨ y.
Функция называется самодвойственной, если она двойственна
самой себе, т. е. f* = f, [Ìñàì ] = Ìñàì .
Пример: f = x ; f *= x= x .
Теорема Поста
Для того чтобы множество N булевых функций было полным, необходимо и достаточно, чтобы N содержало хотя бы одну функцию:
1) не сохраняющую 0;
2) не сохраняющую 1;
3) не линейную функцию;
4) не монотонную функцию;
5) не самодвойственную функцию.
23
То есть чтобы система булевых функций была полной, необходимо и достаточно, чтобы она целиком не содержалась ни в одном из
указанных здесь замкнутых классов.
Для проверки, выполняются ли для некоторой системы функций {f1, f2 ,..., fn } условия теоремы Поста, можно составлять таблицы Поста. В клетках таблицы ставится знак «+» или «–» в зависимости от того, ∈ ли рассматриваемая функция указанному замкнутому классу или нет. Для полноты системы функций необходимо и
достаточно, чтобы в каждом столбце был хотя бы один минус.
Примеры на определение полноты системы функций с помощью
теоремы Поста.
1. {∧, ∨, , f1}, где f1 = (x ∨ y) ∧ z . Здесь надо определить, к какому
классу Поста относятся булевы функции.
Здесь понадобится таблица истинности, а затем постепенно заполняем столбы таблицы Поста.
x
y
z
x∨y
f1
0
0
0
0
0
0
0
1
0
0
0
1
0
1
0
0
1
1
1
1
1
0
0
1
0
1
0
1
1
1
1
1
0
1
0
1
1
1
1
1
Ì0
Ì1
ÌL
Ììîí Ìñàì
∧
+
+
–
+
–
∨
+
+
–
+
–

–
–
+
–
+
f1
+
+
–
+
–
Для первых двух столбцов таблицы Поста сохранение 0 и 1 первыми тремя формулами заполнение очевидно ранее были примеры,
принадлежность же функции f1 классам M0 è M1 также очевидна,
достаточно посмотреть на нижнюю строку таблицы истинности.
В третьем столбце только формула õ линейна, так как ее многочлен Жегалкина имеет вид õ= x ⊕ 1. Остальные функции нелинейны, что проверяется элементарно достаточно получить для них
многочлен Жегалкина.
Знаки монотонности первых трех функций уже упоминались, а для функции f1 следует рассмотреть (это делается устно)
все сравнимые наборы переменных. Например, (0,0,0) ≤ (0,0,1),
(0,1,0) ≤ (0,1,1) и т. д. И последний столбец таблицы истинности по24
казывает, что значения функций для этих наборов также не возрастают, поэтому функция f1 монотонна.
Для проверки самодвойственности функции f1 = ( x ∨ y ) ∧ z находим двойственную функцию f1*= ( x ∨ y ) ∧ z= (z ∧ y) ∨ z и получаем,
что f1 íå = f1*. Поэтому для функции f1 ставим в последнем столбце
таблицы.
Окончательная таблица показывает, принадлежит или нет каждая из четырех функций указанному замкнутому классу Поста.
И так как в каждом столбце таблицы имеется хотя бы один минус,
то по теореме Поста заданная система функций является полной.
2. {–, ∧, ~}. Определить, является ли полной система функций и
образует ли она базис.
х
y
х–у
x∧y
х~у
0
0
0
0
1
0
1
0
0
0
1
0
1
0
0
1
1
0
1
1
Ì0
Ì1
ÌL
Ììîí Ìñàì
–
+
–
–
–
–
∧
+
+
–
+
–
~
–
+
+
–
–
Здесь среднюю строку таблицы Поста заполняем из предыдущего примера. Принадлежность же первой и третьей функций к Ì0 и
Ì1 очевидна из таблицы истинности. Для заполнения столбца ÌL
необходимо записать многочлены Жегалкина для операций – и ∼:
x - y = õ → ó = x ∨ y = x ∧ y = x(1 ⊕ y) = x ⊕ xy;
x ~ y = õ ⊕ ó =1 ⊕ x ⊕ y .
Для функций x–y и x∼y отмечаем отсутствие монотонности, так
как для первой функции сравнимый набор аргументов (1,0) ≤ (1,1)
показывает, что функция убывает, и для второй функции сравнимый набор (0,0) ≤ (0,1) также иллюстрирует убывание функции.
Двойственные функции имеют вид
( x - y )* = ( x - y ) = x → y = x ∨ y ;
( x ~ y )* = ( x ~ y ) = x ⊕ y = x ⊕ y .
Самодвойственности нет, так как обе двойственные функции
не равны своим функциям.
25
В результате решения получаем, что система из трех заданных
функций является полной. Кроме того, если убрать среднюю строку из таблицы (т. е. функцию x ∧ y ), то получим, что первая и третья функции составляют базис.
Примеры для самостоятельного решения.
Определить, является ли система функций полной и содержит
ли она базис.
1)  {→, ∨, ∧};
2)  {f1, f2 , f3 , f4 }, где f1 = x ⊕ y ⊕ z; f2 = x ∧ y; f3 = 0; f4 = 1;
3)  {⊕, ∨, →} .
Примеры из контрольной работы:
Задание: определить, является ли полным набор функций и что
может являться базисом в этом наборе.
Вариант 1. Вариант 2.
f1= x ∧ y f1 = (x - y) ⊕ x
f2 = (x - y) → x f2 = (x → y) → y
f3 = (x → y) → y f3 = (x → y) ⊕ x
Вариант 3. f=
1 (x ↓ y ) ~ x Вариант 4.
f1 = x
f=
2 (x → y) | x f2 = x(y ~ x) ~ yz
f3 = (x ~ y) - y f3 = x ⊕ y ⊕ z
Вариант 5.
f1 = xy Вариант 6.
f1 = 1
f2= x ∨ y f2 = x
f3= x ⊕ y f3 = x(y ~ z) ⊕ x (y ⊕ z)
f4 = xy ∨ yz ∨ xz f4= x ~ y
9. Алгебра Буля и теория множеств
Множеством называется набор элементов произвольной природы, объединенных по какому-либо единому признаку.
Обычно множества обозначаются большими латинскими буквами (A, B, X, M, ...), а их элементы – строчными (a, b, x, m, ...). При
этом элементы множества должны быть различными. Множество
обозначается фигурными скобками, внутри которых либо просто
перечисляются элементы, либо просто описываются их свойства.
26
Например, {3, 5, 7, 9, 11}; A = {x ∈ N } | x + 2 = 1} – множество натуральных чисел, удовлетворяющих условию x + 2 = 1; ясно, что
A = ∅ (пустое множество). Если необходимо указать, что элемент
x является частью множества M, то обозначают x ∈ M , иначе x не
∈ M. Если каждый элемент множества A есть элемент множества
В, то пишут A ⊂ B и говорят, что A является подмножеством множества B. Множества, состоящие из одних и тех же элементов, называются равными, т. е. А = В, в противном случае А ≠ В.
Если А = В < = > (А ⊂ В и В ⊂ А). Например, А = {2, 6, 10}; B = {четные числа}, тогда A ⊂ B.
Укажем известные числовые множества:
N = {1, 2, 3, ...} – множество натуральных чисел;
Z = {…, –2, –1, 0, 1, 2, …} – множество целых чисел;
m

Q=  | m ∈ Z, n ∈ N  – множество рациональных чисел;
n


R = {–∞, +∞} – множество вещественных чисел.
Операции над множествами
Объединением двух множеств А и В называется новое множество, состоящее из элементов, принадлежащих хотя бы одному из
множеств А или В:
A∪B
= {x | x ∈ À èëè x ∈ B}.
Пересечением множеств А и В называют новое множество, состоящее из элементов, принадлежащих одновременно обоим первоначальным множествам.
A∩B
= {x | x ∈ À è x ∈ B} .
Пересечение иногда называют произведением, а объединение –
суммой.
Для наглядного представления этих операций их изображают
диаграммами Эйлера – Венна. Например, на рис 9.1 изображено
объединение множеств А и В, а на рис. 9.2 – их пересечение.
A
A
B
Рис. 9.1
B
Рис. 9.2
27
Прямоугольником обозначают универсальное множество, внутри которого содержаться подмножества А и В.
Разностью A\В двух множеств А и В называется новое множество, состоящее из элементов множества А, не ∈ множеству В:
À\Â =
x | x ∈ A è íå ∈ B}.
Симметричной разностью множеств А и В называют новое множество С, которое ∈ одному из множеств А либо В, но не является
их общими элементами
Ñ = À ⊕ Â = ( À \ Â) ∪ (B \ A).
Также можно записать:
Ñ = À∆ = {x | (x ∈ A è íå ∈ B) èëè (x íå ∈ A è x ∈ Â)}.
Диаграммы Эйлера – Венна, изображающие разность и симметричную разность, представлены на рис. 9.3 и рис. 9.4.
A
A
B
Рис. 9.3
B
Рис. 9.4
Дополнением множества А до множества В называется множество элементов В, которое не ∈ A.
Дополнением над некоторым универсальным множеством U называется
=
À {x | x íå ∈ A }.
Диаграммы Эйлера – Венна, представляющие оба дополнения,
имеют вид, как указано на рис. 9.5 и 9.6.
A
A
B
B
Рис. 9.5
28
Рис. 9.6
Число элементов множества А называется его мощностью и обозначается |А|. Если |А| = |В|, то множества А и В равномощны.
Для усвоения операций над множествами рекомендуется решить следующие примеры:
Пример 1. Пусть А = {a,b,c,d,e}; B = {c,d,e,f}.
Найти А∪В, А∩В, А\В, В\А, А∆В.
Замечание: Дополнение À зависит от того, какое универсальное множество рассматривается. Если U = {a, b, c,d, e, f }, то À = {f },
но если U = {a, b, c,d, e, f, g}, то À = {f, g}. Пример 2. Доказать с помощью диаграмм Эйлера – Венна, чему
равно новое множество
À ∪ ( À ∩ Â) =
? ( À ∪ Â) ∩ ( À ∪ Â) =
? Ответ: А.
Пример 3. Доказать включение (А∪В)\С ⊂ А∪(В\С) с помощью
диаграмм Эйлера – Венна.
Пример 4. Перечислить элементы следующих множеств:
А = {x: х∈Z и 10 ≤ х ≤ 17};
B = {x: х∈Z и x2 < 24};
С = {x: х∈Z и 6x2 + х – 1 = 0};
D = {x: х∈R и 6x2 + х – 1 = 0}.
Указание: 6x2 + х – 1 = (3х – 1)(2х + 1).
Ответ: А = {10, 11, …, 17}; B = {–4, –3, –2, –1, 0, 1, 2, 3, 4}; C = ∅;
D = {–1/2, 1/3}.
Операции над множествами тесно связаны с логическими операциями, например, ∪ и ∩ множеств соответствуют логическим
операциям ∧ и ∨, дополнение множеств – логической операции отрицания, импликация – отрицанию логической разности. В разд. 2
мы установили, что импликация Х→Y эквивалентна дизъюнкции
Õ ∨ Y [равенство (1)]. Поэтому истина для Х→Y в теории множеств
будет иметь вид À ∪ B.
Основные законы алгебры множеств
1. Коммутативный закон:
А ∪ В = В ∪ А
А ∩ В = В ∩ А
2. Ассоциативность:
А∪(В∪С) = (А∪В)∪С А ∩ (В ∩ С) = (А ∩ В) ∩ С
3. Дистрибутивность:
А ∪ (В ∩ С) = (А ∪ В) ∩ (А ∪ С)А ∩ (В ∪ С) = (А ∩ В) ∪ (А ∩ С)
4. Закон идемпотентности:
А ∪ А = А
А ∩ А = А
В частности:
А ∪ ∅ = А А ∩ U = А
29
А ∪ U = U
A ∩ ∅= ∅
5. Закон поглощения:
А ∪ (А ∩ В) = А
А ∩ (А ∪ В) = А
6. Закон де Моргана:
À ∪  = À ∩  À∩Â= À∪Â
Доказательство, например, закона À ∪ Â = À ∩ Â (исходя из
определения равенства множеств и определения операций над множествами).
Пусть x ∈ A ∪ B. По определению дополнения: х ∉ А ∪ В, но х ∈ U
(универсальному множеству). Следовательно: х ∉ А и х ∉ В. Тогда
x ∈ À и x ∈ Â . Из определения операции пересечения x ∈ À ∩ Â.
А так как х – произвольный элемент, принадлежащий объединению A ∪ B, то имеем À ∪ Â ⊂ À ∩ Â.
Пусть теперь x ∈ A ∪ B. Значит, x ∈ À и x ∈ Â . Таким образом
х∉А и х∉В поэтому х∉А∪В. Следовательно, x ∈ U \ A ∪ B ( A ∪ B).
А так как х – произвольный элемент из À ∩ Â, то À ∩ Â ⊂ A ∪ B.
Окончательно, À ∩ Â = À ∪ Â .
Далее продолжим основные законы.
7. Закон двойного дополнения:
À=À
8. Закон включения:
À ⊂ Â <=> Â ⊂ À
9. Закон равенства:
A = B <=> (( À ⊂ Â) ∩ (Â ⊂ À) <=> ( À ∩ Â) ∪ ( À ∩ Â))
Доказательство всех перечисленных законов основано на определении равенства многочленов и определении операций над множествами. При доказательстве приводятся те же аргументы, что и
в приведенном ранее доказательстве закона де Моргана.
Пример. Опираясь на законы алгебры множеств, доказать, что
произвольные множества А и В удовлетворяют равенству
À∆ = ( À ∪ Â) ∩ ( A ∩ B).
Решение: Из определения симметричной разности множеств
имеем
À∆ = ( À ∩ Â) ∪ (B ∩ A) .
Затем, согласно законам алгебры множеств, имеем
( À ∪ Â) ∩ ( A ∩ B) =
де Моргана
= ( À ∪ Â) ∩ ( A ∪ B) = закон дистрибутивности
30
(( À ∪ Â) ∩ A) ∪ (( A ∪ B) ∩ B) =
закон коммутативности
= ( À ∩ ( À ∪ Â)) ∪ (Â ∩ ( À ∪ Â)) = закон дистрибутивности
= ( À ∩ À) ∪ ( À ∩ Â)) ∪ ((Â ∩ À) ∪ (Â ∩ B)) = закон коммутативности
= (( A ∩ A) ∪ (B ∩ A)) ∪ (( A ∩ B) ∪ (B ∩ Â)) = закон дополнения
= (∅ ∪ (B ∩ A) ∪ (( A ∩ Â) ∪ ∅) = закон коммутативности и идемпотентности
= ( À ∩ Â) ∪ (Â ∩ À).
Следовательно: À∆ = ( À ∪ Â) ∩ ( À ∩ Â).
Примеры из практической работы, данные преподавателем.
Цель работы: научиться выполнять операции над множествами
и применять аппарат теории множеств для решения задач.
Примеры заданий:
Вариант 1
Пример 1
В качестве универсального множества зафиксируем U = {p, q, r,
s, t, u, v, w}.
Пусть множества А = {p, q, r, s}, B = {r, t, v}, C = {p, s, t, u}.
Найти элементы следующих множеств:
а) À ∩ Â ;
б) À ∪ Ñ;
в) C ; г) À ∩ Â ∩ Ñ ;
д) ( À ∪ Â ) ∩ ( À ∩ Ñ );
е) ( À ∩ Â) ;
ж) Â \ Ñ ;
з) Â∆Ñ .
Пример 2
Нарисовать серию диаграмм Эйлера – Венна, иллюстрирующих
закон дистрибутивности
À ∩ (Â ∪ Ñ) = ( À ∩ B) ∪ (Â ∩ Ñ).
Доказать, что закон действительно справедлив для любых множеств А, В и С.
Пример 3
Доказать с помощью законов алгебры множеств тождество
( À ∩ ( Â ∪ Ñ )) =À ∪ ( Â ∪ Ñ ) =À ∪ Â ∪ Ñ .
Вариант 2
Пример 1
Даны множества
À = {x ∈ N | 2 < x ≤ 6},
B = {x ∈ N | 1 < x ≤ 4},
C = {x ∈ N | x2 - 4 = 0}. Из каких элементов состоят множества
( À ∪ Â ) ∪ ( Â ∪ Ñ ), Ñ × Â, Â × Ñ ?
31
Примечание: множество, элементами которого являются все
упорядоченные пары (а, b), где à ∈ À, b ∈ B , называется прямым
или декартовым произведением множеств А и В и обозначается
À × Â.
Например: А = {1,2}, В = {2,3}, тогда À × Â =
{(1,2),(1,3),(2,2),(2,3)} .
B× A =
{(2,1),(2,2),( 3,1),( 3,2)}.
Таким образом, декартово произведение не подчиняется коммутативному закону и À × Â = Â × À только если À = Â .
Пример 2
Нарисовать серию диаграмм Эйлера – Венна, иллюстрирующих
следующее тождество:
À ∩ (Â∆Ñ) = ( À ∩ Â)∆( À ∩ Ñ).
Показать на примере, что множество À ∩ (Â∆Ñ) не обязательно
совпадает с множеством ( À ∪ Â)∆( À ∪ Ñ).
Пример 3
Доказать с помощью законов алгебры множеств тождество
( À ∩ Â) ∪ Â =
À∪Â .
32
II. ЛОГИКА ВЫСКАЗЫВАНИЙ
Вернемся к понятию логическое высказывание, от которого мы
отошли в начале настоящего пособия, перейдя к логическим переменным для изучения алгебры логики.
Логика высказываний и теория булевых функций тесно связаны. Обе модели являются булевыми алгебрами. Фактически двоичные функции представляют собой функциональные модели логики
высказываний, в которых элементарные высказывания трактуются как двоичные переменные. Естественно, что в логике высказываний пользуются результатами и терминологией из теории двоичных функций.
Но при всей похожести теорий, задачи они решают разные. Теория двоичных функций занимается проблемой реализации преобразователей информации. А логика высказываний, называемая
формальной логикой, работает с абстракциями, построенными из
предложений и рассуждений естественного языка. Интерпретация
ее выводов также лежит в области естественного языка. С помощью
формальной логики проясняются многие задачи, которые сформулированы в естественном языке и представляются достаточно
сложными.
В булевой логике все доказательства строятся на отношении эквивалентности (равнозначности). В логике высказываний все доказательства строятся на отношении порядка, т. е. на отношении, которое
существует между причиной и следствием. Здесь отдельные звенья
цепи доказательства связаны символом импликации ( = >), который
здесь называется субъектной импликацией или метаимпликацией.
Также используются субъектные символы метаконъюнкции и метадизъюнкции (, и ;) вместо обычных символов (∨ и ∧). И утверждение,
которое требуется доказать, в логике высказываний оформляется
в виде следующего причинно-следственного отношения
(4)
Ð1, Ð2 ,..., Ðn -1, Ðn ⇒ C, где Ði – посылка (причина), i = 1,n; С – заключение (следствие). И
читается так: «Если посылки Ð1, Ð2 ,..., Ðn -1, Ðn истинны, то заключение С тоже истинно», а можно сформулировать и так: «Если причины Ð1, Ð2 ,..., Ðn -1, Ðn имели место, то будет иметь место и следствие С »; отношение такого типа называется клаузой (clause).
Клауза – метапредложение, в котором использовано отношение
порядка, оформленное через символ метаимпликации ( = >). Отношение порядка удовлетворяет трем законам:
33
1) А = >A – рефлексивность;
2) если А = >В, то Â ⇒ À – антисимметричность;
3) если А = >В и В = >С, то А = >С – транзитивность.
Антисимметричность можно еще записать так:
если А = >В и В = > А, то А = В.
Можно сказать, что клауза есть формальная записать доказываемого предложения. Вместо букв в ней можно подставить объектное высказывание, и тогда клауза наполнится конкретным содержанием, которое называется легендой.
Пример простейшей клаузы: А→В, А = > В.
И если принять за высказывания А и В, например, А = «Сверкнула
молния», В = «Грянул гром», – то можно составить следующую легенду.
Известно, что если сверкнула молния, то после этого грянет
гром. Молния сверкнула. Следовательно, должен и грянуть гром.
Клауза (4) может быть приведена к следующему логическому
выражению:
Ð1 ∧ Ð2 ∧ ... ∧ Ð1-n ∧ Ðn → C,
где вместо метаконъюнкции и метаимликации указаны объектная
конъюнкция и объектная импликация. Далее, преобразовав это
выражение в дизъюнкт, получим
(Ð1 ∨ Ð2 ∨ ... ∨ Ðn -1 ∨ Ðn ) ∨ C
[использовали формулу (1) из разд. 2 и закон де Моргана].
Отсюда можно объединить последнюю дизъюнкцию и снова использовать формулу (1), выражая наоборот дизъюнкцию через импликацию и опять используя закон де Моргана:
(Ð1 ∧ Ð2 ∧ ... ∧ Ðn -1 ) → (Ðn → C).
В результате клауза (1) может быть представлена в другой эквивалентной форме
(Ð1, Ð2,..., Ðn -1 ) ⇒ Ðn ; C. (2)
В силу коммутативности и конъюктивности на месте посылки
Ðn может оказаться любая другая, причем не одна. Например, клауза Ð1, Ð2, Ð3, Ð4 ⇒ C1; C2; C3 может быть преобразована в другую эквивалентную форму
Ð1, Ñ1, Ñ2 , Ð4 ⇒ Ð1; Ð2 ; C3 .
Если символ метаимликации клаузы (5) сместить в крайнее левое положение, то она превратится в тавтологию; если же его сместить в крайнее правое положение, то – в противоречие:
34
1 ⇒ Ð1; Ð2 ; … ; Ðn -1; Ðn ; C – тавтология;
Ð1, Ð2, …, Ðn -1, Ðn , Ñ ⇒ 0 – противоречие.
В общем случае, если клауза имеет вид
Ð1, Ð2, …, Ðn -1, Ðn , Ñ1, Ñ2, …, Ñm -1 =
> Ñm
и слева от метаимликации обобщенная посылка, а справа – обобщенное следствие, то аналогичными рассуждениями ее можно, например, преобразовать в такую эквивалентную клаузу:
Ð1, Ð2, …, Ðn -1, Ðn , Ñ1, Ñ2, …, Ñm -1 =
> Ñm .
Указанные преобразования логических клауз позволяют представить несколько конкретных методов их доказательства. Остановимся на одном из них.
Метод резолюций
Для доказательства методом резолюций клаузу необходимо
привести к конъюнктивному противоречию. Для этого переменные, которые в обобщенном следствии были соединены с другими
переменными субъектной дизъюнкцией, переносятся через знак
метаимпликации, отрицая эти переменные и присоединяя к обобщенной причине через операцию субъектной конъюнкции.
Было: Ð1, Ð2, …, Ðn -1, Ðn ⇒ Ñ1, Ñ2, …, Ñm -1, Ñm .
Стало: Ð1, Ð2, …, Ðn -1, Ðn , Ñ1, Ñ2, …, Ñm -1, Ñm =
> 0.
Затем используется клауза:
Õ ∨ À, Y ∨ À =
> Õ ∨ Y, (6)
(клауза метода резолюций), которая позволяет склеить два посылочных дизъюнкта с противоположными переменными в один
дизъюнкт, в котором уже не будет противоположных переменных.
Здесь Х, Y, А – произвольные переменные или целые дизъюнкты
с любым набором переменных.
Во всех выражениях перед использованием клаузы (6) следует
избавиться от лишних операций в конъюнктах, оставив только отрицание и дизъюнкцию.
Занумеровав дизъюнкты и используя клаузу метода резолюций,
нужно склеивать дизъюнкты и получить 0 (ноль).
При последовательном применении принципа резолюции происходит уменьшение числа переменных вплоть до их полного исчезновения. Ноль говорит о несовместимости заключения и посылок. Это и свидетельствует о справедливости исходной клаузы.
35
Если при переборе всех дизъюнктов ноль не получается, то клауза ложная.
Рассмотрим примеры доказательства клауз методом резолюций:
1. А→В, С ∨ А, Â → Ñ =
> A Приводим клаузу к КНФ, далее нумеруем дизъюнкты: А ∨ В, С ∨ А, Â ∨ Ñ, À => 0 (так как Õ → Y = Õ ∨ Y )
1.
2.
3.
4.
Далее склеиваем дизъюнкты, учитывая клаузу метода резолюций.
5. В(1,4) (так как А ∨ В, 0 ∨ À = > B ∨ 0).
6. C(2,4).
7.  B(3,6) .
8. 0(5,7).
Ответ: клауза доказана.
2) A ∨ D, B ∨ E, D→C, D ∨ C = > A ∧ C; E ∧ D; B.
Переносим конъюнкты и переменную В в левую часть метаимпликации, получая КНФ.
A ∨ D, B ∨ E, D ∨ C, D ∨ C, À ∨ Ñ, Å ∨ D, B => 0.
1.
2.
3.
4.
5.
6.
7.
Далее склеиваем дизъюнкты.
8. E(2,7). 11. D(10,4).
9. C(3,4). 12. E (11,6 ) .
10.  D ∨ C (1,5).
13. 0(8,12).
Ответ: клауза доказана.
Табличный метод доказательства клаузы
Составляется таблица истинности для обобщенной посылки и
обобщенного следствия. Клауза считается доказанной, если все
единицы обобщенной причины покрываются единицами обобщенного следствия.
Например, рассмотрим простейшую клаузу, о которой уже говорилось раннее.
А→В, А = >В, где А = «Сверкнула молния», В = «Грянул гром».
Таблица истинности имеет вид
А
В
А→В
(А→В) ∧ А
В
0
0
1
1
0
1
0
1
1
1
0
1
0
0
0
1
0
1
0
1
Клауза доказана, так как единица причины покрывается единицей следствия.
36
Примеры для самостоятельной работы
1. Доказать табличным методом клаузу метода резолюций.
2. Доказать клаузу табличным методом и методом резолюций:
(А∧В)→С = > А→(В→С)
3. Доказать клаузу методом резолюций:
D→E, E→C, A~D, B~C = > A→B.
Далее рассмотрим примеры некоторых клауз и примеры соответствующих легенд.
Клауза 1: À → Â, Â → Ñ, Å → (Â → D), D → F =
> (Â ∧ À ∧ E) → F .
За высказывания здесь, например, можно принять:
А = «Возникновение перепада напряжения в сети»;
В = «Перегорание предохранителя»;
С = «Необходимость замены предохранителя»;
D = «Телевизор работает нормально»;
E = «Телевизор подключен к сети питания»;
F = «Я смотрю новости».
Тогда легенда будет такова:
Если в сети был большой перепад напряжения, то сгорит предохранитель (А→В). Если предохранитель сгорел, необходима
его замена (В→С). Если телевизор включен в сеть, то телевизор
работает нормально при условии целостности предохранителя
(E → Â) → D)). Если телевизор работает нормально, я увижу новости (D→F). Я увижу новости при условии отсутствия перепада напряжения и подключения телевизора к сети питания (( À ∧ E) → F),
но это будет ложным. Истинным же будет: Я увижу новости
при условии целостности предохранителя, отсутствия перепада напряжения в сети и подключения телевизора к сети питания
((Â ∧ À ∧ E) → F).
Клауза 2: À → B, B → E, A → C, C → D, D → F, (E → F) =
> À.
За легенду здесь примем и запишем кратко следующее:
Если человек занимается спортом (А), то он хочет быть здоровым (В). Хорошее здоровье (В) ведет к счастливой жизни (Е). Кроме того, если человек занимается спортом (А), то он, как правило,
стремится достичь высоких спортивных результатов (С). Наличие
высоких результатов (С) позволяет одерживать победы на соревнованиях (D). Победы на соревнованиях (D) влекут за собой всеобщее
признание (F). Однако человек не хочет жить счастливо и иметь
всеобщее признание (E ∧ F). Значит, он не станет заниматься и
спортом ( À).
37
Примеры из проводимой на занятиях практической работы.
Алгебра высказываний
Цель работы: научиться строить доказательства на отношении
между причиной и следствием.
Задания:
1. Первую клаузу доказать двумя методами: табличным и резолюций.
2. Вторую клаузу – методом резолюций.
3. Составить легенду по одной из двух клауз.
Вариант 1
1.  ( A → C ) → ( A ∧ B ) =
> A∨B
2. A → B, C → D, A ∨ C, A → D, C → B =
> ( A ∨ B ) → ( A ∧ B )
Вариант 2
>A
1.  C → A, B ∨ C, B → D, D → A =
2.  A ∨ B, A → B, B → ( C → D ), A → D =
> A∧C
Вариант 3
1.  ( A ∧ B ) → C =
> A → (B → C)
2.  C, D → C, A → ( B → D ), B =
> A→C
Вариант 4
1. C → ( B → A ), B → D, C =
> A∨D
2. A → ( C → B ), D → A, C =
>D→B
Вариант 5
> ( B → C ) → A
1.  C, A ∨ B =
2. A, B ∨ C, C ~ D =
> ( B → A ) → ( B → D )
Вариант 6
1.  A ~ B, B → C, C ~ D =
> ( C → B ) → ( D → A )
2.  ( A ∧ ( B → C ) ) ~ D, E ~ A ∧ B ∨ C =
> ( D ∧ E ) ~ ( A ∧ C )
Вариант 7
1.  A, B ∨ C =
> A ∧ B; Ñ
2.  C → ( A → B) =
> À ∧ B ∧ C; À ∧ Ñ
Вариант 8
1.  C, ( A → B) → ( C → A ) =
>À
2.  A → B, B → D, D → A, B ∨ C, C → D =
>D
Вариант 9
1.  A, B → C ⇒ A ∧ Â; B ∧ Ñ
2. A → ( C → B ), D → A, C =
>D→B
( (
38
))
III. ЛОГИКА ПРЕДИКАТОВ
В логике высказываний рассматривались логические отношения, составленные из простых декларативных высказываний, которые с помощью логических операций ∧, ∨, , →, ~ принимают
только два значения: 0 или 1. То есть все высказывания рассматривались, как нераздельное целое и только с точки зрения их истинности или ложности. Структура высказываний и их содержание
игнорировались. В то же время на практике, да и в науке, используются заключения, зависящие как от структуры, так и от содержания используемых в них высказываний.
Не любые логические рассуждения могут быть описаны на языке исчисления высказываний. В некоторых случаях высказывания касаются свойств объектов или отношений между объектами.
В связи с этим возникает необходимость в расширении логики высказываний, в построении такой логической системы, средствами
которой можно было бы исследовать структуру и содержание тех
высказываний, которые в рамках алгебры высказываний считались бы элементарными.
Такой логической системой является логика предикатов, содержащая логику высказываний в качестве составной части. Помимо
элементарных высказываний, в логике предикатов рассматриваются высказывания, отнесенные к предмету, т. е. высказывания
распадаются на субъект и предикат.
Субъект – это то, о чем что-то утверждается в высказывании, а
предикат – это то, что утверждается о субъекте.
Логика предикатов – это расширение логики высказываний за
счет использования предикатов в роли логических функций.
Например, в высказывании «11 – простое число» «11» – субъект, «простое число» – предикат. Это высказывание утверждает,
что «11» обладает свойством «быть простым числом».
Если в этом примере заменить конкретное число «11» переменной х из множества натуральных чисел, то получим форму высказывания «х – простое число». При одних значениях х (например,
х = 7, х = 13) эта форма дает истинное высказывание, а при других
значениях х (например, х = 8, х = 12) – ложное высказывание.
Эта форма высказывания представляет собой функцию переменной х, определенную на множестве натуральных чисел N, которое
принимает значение 0 или 1. Здесь предикат становится функцией
субъекта и выражает свойства субъекта.
39
Одноместным предикатом Р(х) называется произвольная
функция переменного х, определенная на множестве M и принимающая значения из множества {1, 0}.
Множество M, на котором определен предикат P(x), называется предметной областью или областью определения предиката.
Множество всех х∈М, при которых предикат принимает значение
«истина», называется множеством истинности предиката P(x):
Ip =
{x | x ∈ M, P(x) =
1}.
Так, предикат Р(х) – «sinx = 0» – определен на множестве R, а его
множества истинности I p = {kπ, k ∈ Z }. Предикат Q(x) – «диагонали
параллелограмма х перпендикулярны» – определен на множестве
всех параллелограммов, а его множеством истинности является
множество всех ромбов.
Приведенные примеры одноместных предикатов выражают
свойства предметов.
Предикат Р(х), определенный на множестве N, называется тождественно истинным (тождественно ложным), если
I p = M (I p = ∅).
Естественным обобщением понятия одноместного предиката
является понятие многоместного предиката, с помощью которого
выражаются отношения между предметами.
Примером бинарного отношения (отношения между двумя
предметами) является отношение «меньше». И если это отношение
ввести на множестве Z целых чисел, то форма высказывания представляет предикат Р(х, у) – «х < y», где х, у ∈ Z, а предикат P(x, y)
будет определен на множестве Z × Z с множеством значений {1, 0}.
Двухместным предикатом P(x, y) называется функция двух переменных х и у, определенная на множестве M = Ì1 × Ì2 и принимающая значения из множества {1, 0}.
Так можно ввести трехместный предикат и т. д. и даже n-местный.
n-местным предикатом P(õ1, õ2,…, õn ) называется функция,
определенная на множестве
=
N Ì1 × Ì2 ×…× Ìn (декартово произведение) и принимающая на этом множестве одно из двух значений 1 или 0.
Простое высказывание, таким образом, представляет из себя
предикатную константу.
А при замещении какой-либо переменной õi в n-местном предикате P(õ1, õ2,…, õn ) предметной постоянной ai этот предикат
превращается в (n-1) местный P(õ1, õ2 ,…, ai , …, õn ). Если заменить
40
таким образом все переменные на предметные постоянные, то получится предикатная константа. К ней применимы все операции
логики высказываний и к предикату также, так как предикаты,
как и высказывания, принимают два значения: 0 и 1.
Пусть на некотором множестве определены два одноместных
предиката.
Конъюнкцией двух предикатов P(x) и Q(x) называется новый
предикат P(x) ∧ Q(x), который принимает значение «истина» при
тех и только тех значениях х ∈ М, при которых каждый из предикатов принимает значение «истина», и принимает значение «ложь»
во всех остальных случаях. Очевидно, что областью истинности
предиката P(x) ∧ Q(x) является переcечение I p ∩ Iq.
Дизъюнкцией двух предикатов Р(х) и Q(x) называется новый
предикат P(x) ∨ Q(x), который принимает значение «ложь» при тех
и только тех значениях х ∈ М, при которых каждый из предикатов
принимает значение «ложь», и принимает значение «истина» во
всех остальных случаях. Ясно, что областью истинности дизъюнкции является объединение I p ∪ Iq.
Отрицанием предиката Р(х) называется новый предикат Ð ( õ ) ,
который принимает значение «истина» при всех значения х ∈ М,
при которых Р(х) принимает значение «ложь», и наоборот. Здесь
очевидно, что I p = M / I p .
Импликацией Р(х) и Q(x) называется новый предикат P(x)→Q(x),
который является ложным при тех и только тех значениях х ∈ М,
при которых одновременно Р(х) – истина, а Q(x) – ложь, и принимает истинное значение во всех остальных случаях.
Примеры на определение предиката.
Пример 1. Среди предложений выделить предикаты и указать
для них область истинности, если М = R для одноместных предикатов и М = R × R для двухместных:
1) существует такое число х, что õ2 - 2õ + 1 =
0;
2)  õ + 2 < 3õ - 4;
3) однозначное число х кратно 3;
4)  ( õ + 2 ) - (3õ - 4);
5)  x2 + ó2 > 0.
Ответы: 1) предложение не является предикатом, это истинное
высказывание;
2) одноместный предикат Р(х), I=
p (x > 3);
3) одноместный предикат Р(х), I p = ( 0; 3; 6; 9 );
4) предложение не является предикатом;
41
5) предложение является двухместным предикатом Р(х, у),
I p= R × R \ {0,0}.
Пример 2. Выяснить, какие из следующих предикатов являются тождественно истинными:
1)  x2 + ó2 ≥ 0;
2
4) ( x + 1) > x - 1;
2
2
2)  x + ó > 0;
2
5) x2 + 1 ≥ ( x + 1) ;
1.
3)  sin2 x + cos2 x =
Ответы: Предикаты 1), 3), 4) являются тождественно истинными. В предикате 2) при х = 0, у = 0 неравенство нарушается, а в предикате 5) неравенство нарушается при всех положительных значениях х. Следовательно, предикаты 2), 5) не тождественно истинны.
Пример 3. Пусть даны предикаты Р(х) = «х – четное число» и
Q(x) = «х – кратно 3», определенные на множестве N. Найти области истинности предикатов:
1) Р(х)∧Q(x);
2) Р(х)∨Q(x);
3) Ð ( õ ) ;
4) Р(х)→Q(x).
Ответы: так как I=
= {3,6,9,…,3n,…}, то:
p {2,4,6,…,2n,…}, IQ
1) I p ∧=
I
∩
I
=
{
6
,
12
,
…
,
6
n
,
…
}
;
Q
p
Q
2)  I p∨ =
Q I p ∪ IQ = {2,4,6,…,2n,3n,…};
I p N \=
I p {1,3,5,…,2n - 1,…};
3) =
4)  I p=
=
IQ {1,3,5,…,2n - 1,…} ∪ {3,6,9,…,3n,…}.
→Q N \ I p ∪
Пример 4. На множестве М = {1,2,3,…,20} заданы предикаты
А(х) = «х – не делится на 5», В(х) = «х – четное число», С(х) = «х –
простое число», D(x) = «х – кратно трем». Найти множества истинности предикатов А(х) ∧ В(х) ∧ D(x), A(x) ∨ B(x), D(x) → C ( x ).
Ответы:
1) I p = {6,12,18};
2) I p = M \ {5,15};
3) I p = M \ {3}.
В следующих примерах предлагается самостоятельно найти область определения и область истинности предикатов. Нарисовать
на плоскости области.
1)  Ð ( õ=
2 0»;
) «õ2 - 3õ + =
õ, ó ) «log3 ( x=
+ y ) 3»;
2)  Ð (=
=
log2õ
ó».
3)  Ð
( õ, ó ) «=
42
Кванторные операции над предикатами
Функциональная природа предиката влечет за собой введение
еще одного понятия – квантора. Кванторные операции можно рассматривать как обобщение операций конъюнкции и дизъюнкции
в случае бесконечных областей. Поясним понятие квантора на следующих примерах:
1) «Все люди смертны. Сократ человек.
Следовательно, Сократ – смертен.»
2) «Некоторые люди гениальны. Сократ человек.
Следовательно, Сократ – гениален.»
Во втором примере чувствуется ложность заключения, так как
интуитивно мы понимаем, что Сократ мог и не попасть в число гениальных людей.
Ключевые слова здесь «все» и «некоторые». Когда какое-то правило распространяется на всех индивидуумов, оно, естественно,
распространяется и на Сократа. Если же правило касается только
некоторых, оно может в отношении Сократа оказаться и неверным.
Термин «для всех х» обозначается в логике предикатов ∀х и
называется квантором всеобщности (All – всякий). Термин «для
некоторых х» или «существует хотя бы одно значение х» обозначается через $х и называется квантором существования (Exist –
существовать).
Выставляя эти кванторы перед предикатами, мы как бы усиливаем или ослабляем их действие. Так, выражение ∀хР(х) означает
«для всех х свойство Р(х) истинно», а выражение $Р(х) означает
«существует по крайней мере одно значение х, для которого Р(х)
истинно».
В 1-м случае это все равно, что сказать «конъюнкция всех значений предикатной функции равна 1»:
∀хР(х) = Р(а) ∧ Р(в) ∧ Р(с), где напр. предметная область х = {a,b,c}.
Поэтому говорят, что квантор всеобщности имеет конъюнктивную природу.
Квантор существования означает дизъюнкцию всех значений
предикатной функции:
$хР(х) = Р(а) ∨ Р(в) ∨ Р(с), если предметная область х∈{a,b,c}.
То есть квантор существования имеет дизъюнктивную природу.
Ясно, что для ∀хР(х) это высказывание истинно в единственном
случае, когда Р(х) – тождественно истинный предикат, а высказывание $хР(х) ложно только тогда, когда Р(х) – тождественно ложный предикат.
43
Оба квантора можно отрицать и выражать один через другой на
основе закона де Моргана.
Например, при х ∈ {а,b}
∀õÐ ( õ ) =
Ð(à) ∧ Ð(b) =
P(a) ∨ P(b) =
$x P ( x ), т. е. ∀õÐ ( õ ) =
$x P ( x ),
что означает «неверно, что для ∀хР(х) истинно» эквивалентно тому,
что «найдется такое х, для которого Р(х) ложно». Или
$õÐ ( õ ) =
Ð(à) ∨ Ð(b) =
P(a) ∧ P(b) =
∀xP ( x ),
т. е. $xÐ ( õ ) =
∀xP ( x ), что означает «неверно, что существует такое
х, для которого Р(х) истинно» эквивалентно тому, что «для любого
х Р(х) ложно».
Пусть предметная область предиката Р(х) состоит из двух конкретных значений, т. е. х ∈ {a,b}. Учитывая, что ∀хР(х) = Р(а) ∧ Р(b)
и $хР(х) = P(a) ∨ P(b), составим таблицу истинности, из которой,
вспоминая табличный метод доказательства клауз, сразу видим
три истинные клаузы:
Р(а)
Р(b)
Р(а) ∧ Р(b)
P(a) ∨ P(b)
0
0
0
0
0
1
0
1
1
0
0
1
1
1
1
1
∀хР(х) = >Р(а); Р(а) = >$хР(х); ∀хР(х) = >$хР(х).
Также из таблицы следует, что $хР(х) = >∀хР(х) и P(b) = >P(a) –
ложные клаузы.
Кванторные операции применяются и к многоместным предикатам. Применение кванторной операции к многоместному предикату Р(х,у) по переменной х ставит в соответствие двухместному
предикату Р(х,y) одноместный предикат ∀хР(х,y) или $хР(х,y), зависящий от y и не зависящий от х. К двухместному предикату можно применить кванторные операции также по обеим переменным.
В результате получаем 8 высказываний:
1) ∀х∀yР(х,y); 5) ∀y∀хР(х,y);
2) $х∀yР(х,y); 6) ∀y$хР(х,y);
3) ∀х$yР(х,y); 7) $y∀хР(х,y);
4) $х$yР(х,y); 8) $y$хР(х,y).
В общем случае изменение порядка следования кванторов изменяет смысл высказывания и его логического значения, т. е., например, высказывания ∀х$yР(х,y) и $y∀хР(х,y) различны.
44
Пример 1. Пусть предикат Р(х,y) = «х + y = 0» при х, y ∈ R.
1) Тогда высказывание ∀х$yР(х,y) здесь истинно, так как для
любого вещественного числа у найдется (т. е. $) такое вещественное
число y, что х + y = 0 (какое бы число х мы не взяли, число y = –х обращает равенство х + y = 0 в тождество).
2) Высказывание $y∀хР(х,y) означает, что существует такое
вещественное число y, что для любого вещественного числа х выполняется равенство х + y = 0. Но это не так, не существует такого
вещественного числа у, обладающего этим свойством, т. е. высказывание ложно.
Пример 2. Пусть предикат М(х,y) означает, что х является матерью для y, тогда ∀y$хМ(х,y) означает, что у каждого человека есть
мать – истинное утверждение.
Высказывание $х∀yМ(х,y) означает, что существует мать всех
людей. Истинность этого утверждения зависит от множества значений, которые может принимать y: если это множество братьев и
сестер, то оно истинно, в противном случае оно ложно.
Пример 3. Установить истинность или ложность высказывания
$õ(õ ∈ {2,5} → (õ2 - 6õ + 8 =
0)).
Решение: преобразуем высказывание
$õ(õ ∈ {2,5} → (õ2 - 6õ + 8 =
0)) =
$õ(x ∈ {2,5}) ∨ (õ2 - 6õ + 8 =
0)) =
=
$õ(õ ∉ {2,5} ∨ õ ∈ {2,4}) =
$x(õ ∈ {2,4}).
Исходное высказывание истинно.
Пример 4. Установить истинность или ложность высказывания
∀õ(õ2 - 5õ + 6) =
0.
Рассуждаем аналогично:
õ2 - 5õ + 6 =
0 при õ1 = 2, õ2 = 3. Но õ2 - 5õ + 6 ≠ 0 при (х<2∨х>3).
Поэтому любым х не может быть. Высказывание ложно.
Основной задачей логики предикатов является установление истинности предикатных тождеств и клауз.
Рассмотрим сначала раскрытие кванторов через дизъюнкцию и
конъюнкцию. Пусть Р(х,y) – двухместный предикат и х,y ∈ {a,b}.
Зная, что $хР(х,y) = Р(а,y) ∨ Р(b,y) и ∀yР(х,y) = Р(х,а) ∧ Р(х,b), выразим высказывание $х∀yР(х,y), раскрывая сначала внутренний
квантор:
$х∀yР(х,y) = $х(Р(х,а) ∧ Р(х,b)) = (Р(а,а) ∧ Р(а,b) ∨ Р(b,a) ∧ Р(b,b)).
Пример 1. Доказать тождество ∀х(А→В(х)) = А→∀хВ(х), где а –
предикатная константа, х∈{a,b}.
45
Решение: рассмотрим левую часть
∀х(А→В(х)) = (А→В(а)) ∧ (А→В(b)) = равенство (1)
= ( À ∨ Â ( à ) ∧ ( À ∨ Â(b)) = закон дистрибутивности (справа налево)
=
À ∨ (Â ( à ) ∧ Â(b)) =
снова равенство (1) (но справа налево)
= А→(В(а) ∧ В(b)) = А→∀хВ(х). Получили правую часть тождества.
Пример 2. Доказать утверждение $хА(х)→∀хВ(х) = >$х(А(х)→В(х)),
где х ∈ {a,b}.
Решение: раскроем кванторы в левой и правой части от символа
метаимпликации
А(а) ∨ А(b)→В(а) ∧ В(b) = >(А(а)→В(а)) ∨ (А(b)→B(b)).
Затем известное равенство (1) и закон де Моргана:
(
) (
)
( À (a ) ∧ A (b) ∨ ( B (a ) ∧ B (b)) =
> A (à) ∨ B(a) ∨ A (b) ∨ B(b) .
Далее перемножаем отдельно и переносим все в левую сторону
от знака метаимпликации:
À ( à ) ∨ Â(à) , À ( à ) ∨ Â ( b ), À ( b ) ∨ B ( a ), À ( b ) ∨ B ( b ), A(a), B ( à ) ,
1.
2.
3.
4.
5.
6.
A(b), B ( b ) => 0 .
7.
8.
9. В(b) (2,5).
10. 0 (8,9).
Занумеровали дизъюнкты и склеили, используя клаузу метода
резолюции:
Õ ∨ À, Y ∨ À =
> Õ ⇒ Y .
(
)
Предикатная клауза доказана, так как в левой части получаем
ноль.
Примеры для самостоятельной работы.
Пример 1. Доказать тождество $хА(х)→∀yВ(y) = ∀х∀y(А(х)→В(y),
где х,y ∈ {a,b}.
Пример 2. Выяснить, верно ли тождество ∀х(А(х)→В(х)) =
=$хА(х)→∀хВ(х), где х ∈ {a,b}.
Пример 3. Доказать тождество. ∀х$y(А(y) ∨ В(х)) = $хА(х) ∨ ∀хВ(х).
Пример 4. Доказать утверждение ∀хР(х,b) = >$y∀хР(х,y).
Метод математической индукции
на языке логики предикатов
Пусть имеется предикат P(n), определенный для всех натуральных чисел n, т. е. n ∈ N.
46
Предположим, что:
1) P(1) истинно и
2) ∀ k ≥ 1 импликация (Р(k) = >Р(k+1)) верна.
Тогда Р(n) истинно при ∀ натуральном значении n.
Так звучит принцип математической индукции на языке логики предикатов.
Пример 1. Доказать методом математической индукции, что раn ( n + 1)
венство 1 + 2 +…+ n =
выполнимо при ∀ натуральном n.
2
n ( n + 1)
Решение: Пусть предикат P(n=
) «1 + 2 +…+ =
n
». При
2
n = 1, подсчитывая левую и правую часть равенства, получаем, что
P(1) истинно.
Предположим, что равенство имеет место для какого-то натуk ( k + 1)
рального числа k: 1 + 2 +…+ k =
. Тогда при n = k+1 будет
2
k ( k + 1)
 k  ( k + 1)( k + 2 )
.
1 + 2 +…+ k + (k + 1) =
+ (k + 1) = (k + 1)  + 1  =
2
2
2 
Таким образом, при ∀ k натуральном выполняется импликация:
P(k) = >P(k+1).
Значит, по принципу математической индукции предикат P(n)
имеет истинное значение при ∀ натуральном n.
Пример 2. Методом математической индукции доказать, что
7n - 1 делится на 6 при ∀ натуральном показателе n.
Решение: Известно, что целое число а делится, например, на целое
число b ↔, когда выполняется равенство а = m × b, где m – целое (например, 51 = 3 × 17). Кроме того, используем такое свойство делимости
чисел: «Сумма чисел, делящихся на b, сама делится на b».
Пусть предикат P(n) = «7n – 1 делится на 6».
При n = 1 имеем 7n - 1 = 7 - 1 = 6 , т. е. предикат P(1) имеет истинное значение.
n
Предположим, что 7 - 1 делится на 6 при каком-то натуральном k.
1 7(7k ) -=
1 7(7k ) - 7 + 7 -=
1 7(7k - 1) + 6. Так как 7k - 1
Тогда 7k+1 -=
делится на 6, то и вся сумма тоже делится на 6. Получаем, что при ∀
натуральном k импликация P(n) = > P(k + 1) истинна. Значит, индуктивным рассуждением доказана истинность предиката P(n) для всех
натуральных n.
Примеры для самостоятельного решения.
Методом математической индукции доказать, что:
1) 10n - 1 кратно 9 для ∀ n ∈ N;
47
1
1
1
1
n
+
+
+…+
=
;
1⋅2 2 ⋅ 3 3 ⋅ 4
n ( n + 1) n + 1
1  
1  n +1
 1  1 
3)   1 -  1 -  1 - … 1 - 2  =;
 4  9  16   n  2n
2) 
4)  1 ⋅ 2 + 2 ⋅ 5 + 3 ⋅ 8 +…+ n(3n - 1
=
) n2 (n + 1) ;
3
5) n + 5n кратно 6 при n ∈ N;
6) 4n - 1 кратно 3 при всех n > 0.
Примеры из практических работ.
Логические и квантовые операции над предикатами
Цель работы: научиться выполнять операции над предикатами,
находить область истинности предикатов и доказывать выполнимость формул логики предикатов.
Задания:
1. Найти область определения и область истинности предиката.
2. Доказать выполнимость формул логики предикатов.
3. Доказать высказывание методом математической индукции.
4. Даны предикаты, определенные на множестве R. Следует
установить их истинность или ложность.
Вариант 1
x2 + 3x + 2
1.
=0
x2 + 4 x + 3
2. $xP ( x, x ) => $x$yP ( x, y ) , x, y ∈ {a, b}
1
=
n2
n ( n + 1)( 2n + 1) для всех натуральных n
3. 12 + 22 +…+
6
4. P ( x=
) «x2 + x + 1 > 0 » è Q ( x=) «x2 - 4x + 3= 0»
а) ∀xP ( x ) б) $xP ( x )
в) ∀xQ ( x ) г) $xQ ( x )
Вариант 2
1. P(x,y) = «sin x = y»
2. $x∀yP ( x, y ) => ∀y$xP ( x, y ) 1
1
1
n
+
+…+
=
3.
для всех натуральных n
1·3 3·5
(2n - 1)(2n + 1) 2n + 1
4. $x ( x + 5 = x + 3 ) è $x  x2 + x + 1 = 0 
2


Вариант 3
x2 - 13x + 40 ≥ 0
1. 
2
 2x + x - 30 < 0
2. ∀x∀yP ( x, y ) => $x$yP ( x, y ), x, y ∈ {a, b}
48
3) Число n3 - n делится на 3 при всех натуральных значениях n
4) ∀x x2 + x + 1 > 0 è ∀x x2 - 5x + 6 ≥ 0
Вариант 4
log2x
y»
1) P=
( x, y ) «=
2) ∀x∀yP ( x, y ) => ∀x$yP ( x, y ), x, y ∈ {a, b}
3) 1 + 5 +…+ ( 4n =
- 3 ) n ( 2n - 1)
2
4) $x x - 5x + 6 ≥ 0 ∧ x2 - 2x + 1 > 0 и
((
(
)
(
((
) (
) (
((
) (
)
))
))
$x x2 - 5x + 6 ≥ 0 ∧ x2 - 6x + 8 ≤ 0
Вариант 5
π
1) P ( x, y )= «tg x= y + »
4
2) $x∀yP ( x, y ) => $x$yP ( x, y ), x, y ∈ {a, b}
2
1) n ( n + 1)
3)  1·4 + 2·7 + 3·10 +…+ n ( 3n +=
))
(
)
4) ∀x x2 - 6x + 8 ≥ 0 ∨ x2 - 6x + 8 < 0 è $x x2 + x + 0,5 =
0
Вариант 6
1) P ( x, y ) =
« x2 - 1 =-3»
2) ∀x$yP ( x, y ) => $x$yP ( x, y ), x, y ∈ {a, b}
3) n3 + 11n кратно 6 для всех n ∈ N
4) ∀x x2 - 5x + 6 ≥ 0 è $x x ∈ {2,5} → x2 - 6x + 8 =
0
(
)
(
(
) )
49
ЛИТЕРАТУРА
1. Лихтарников Л. М. Математическая логика: учеб. пособие.
СПб., 2009. 288 с.
2. Шевелев Ю. П. Дискретная математика: учеб. пособие. СПб.:
ЛАНЬ, 2016. 592 с.
3. Шапорев С. Д. Математическая логика: учеб. пособие. СПб.:
БХВ-Петербург, 2013. 416 с.
4. Игошин В. И. Математическая логика: учеб. пособие. М.: ИНФРА-М, 2016. 399 с.
5. Хаггарти Р. Дискретная математика для программистов. М.:
Бином. Лаборатория знаний, 2015. 627 с.
50
СОДЕРЖАНИЕ
Предисловие............................................................................ 3
I. Алгебра логики...................................................................... 1. Понятие высказывания..................................................... 2. Простейшие связки (или логические операции
над высказываниями).................................................... 3. Основные законы логических операций
(или законы булевой алгебры)........................................ 4. Дополнительные связки (или новые логические операции) .... 5. Булевы функции (функции алгебры логики)........................ 6. Дизъюнктивные и конъюнктивные нормальные формы......... 7. Алгебра Жегалкина и многочлен Жегалкина....................... 8. Полнота и замкнутость булевых функций. Теорема Поста...... 9. Алгебра Буля и теория множеств........................................ 4
4
4
7
7
9
13
18
21
26
II. Логика высказываний........................................................... 33
III. Логика предикатов.............................................................. 39
Литература .............................................................................. 50
Учебное издание
Черницина Валентина Яковлевна
ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ
ЛОГИКИ
Учебно-методическое пособие
Редактор А. Г. Ларионова
Компьютерная верстка Ю. В. Умницына
Подписано к печати 22.12.16. Формат 60 × 84 1/16.
Бумага офсетная. Усл. печ. л. 3,0. Уч.-изд. л. 3,2.
Тираж 50 экз. Заказ № 508.
Редакционно-издательский центр ГУАП
190000, Санкт-Петербург, Б. Морская ул., 67
Документ
Категория
Без категории
Просмотров
1
Размер файла
1 157 Кб
Теги
chernicina
1/--страниц
Пожаловаться на содержимое документа