Файл: Учебника по курсу Основы дискретной математики и логики.pdf

искомом ряду поставим формулу (4.35). Второе место займет формула (4.32), принимающая значение 1 только на одном наборе значений переменных. На третье место поставим формулу (4.33), которая принимает значение 1 уже на двух наборах значений переменных. Четвертое и пятое места займут формулы (4.31) и (4.34). Их можно располагать в любом порядке, поскольку принимаемые ими значения совпадают. Один из указанных способов расстановки формул представлен последовательностью (4.36).
Слайд 110
Введем понятие равносильности формул.
Пусть формулы F[эф] и G[жэ] зависят от одних и тех же переменных.
Если логические значения формул F[эф] и G[жэ] для всех значений переменных совпадают, то формулы F[эф] и G[жэ] называют эквивалентными, или равносильными. Для указания равносильности формул используют обозначение (4.37).
Из определения эквивалентности формул вытекают свойства рефлексивности, симметричности и транзитивности. Они выражаются соотношениями (4.38), (4.39) и (4.40) соответственно.
Наличие трех свойств эквивалентности формул говорит о том, что множество всех формул можно разбить на непересекающиеся классы. Все формулы одного и того же класса будут эквивалентны друг другу, а любые две формулы из разных классов не эквивалентны. Такие классы называются классами эквивалентности.
Слайд 111
Рассмотрим основные эквивалентности алгебры высказываний. Они вытекают непосредственно из определения операций отрицания, конъюнкции и дизъюнкции.
Соотношения (4.41) и (4.42) выражают коммутативные законы операций конъюнкции и дизъюнкции соответственно.

Соотношения (4.43) и (4.44) представляют ассоциативные законы операций конъюнкции и дизъюнкции.
Соотношения (4.45) и (4.46) выражают дистрибутивные законы операций конъюнкции и дизъюнкции.
Обратим внимание на порядок выполнения операций в левой части соотношения (4.45) и правой части соотношения (4.46). В связи с отмеченными ранее приоритетами логических операций в первую очередь в указанных формулах применяется операция конъюнкции, а затем – операция дизъюнкции.
Свойство ассоциативности операций конъюнкции и дизъюнкции позволяет опускать скобки в выражениях, представляющих собой дизъюнкцию или конъюнкцию нескольких высказывательных переменных.
Слайд 112
Для проверки эквивалентностей алгебры высказываний достаточно заполнить таблицы истинности рассматриваемых формул и убедиться в том, что последние столбцы этих таблиц совпадают. Наряду с уже рассмотренными эквивалентностями имеют место эквивалентности (4.47), называемые законами де Моргана. Они устанавливают связь между операциями конъюнкции и дизъюнкции. Заметим, что данные законы допускают обобщение на произвольное конечное число высказывательных переменных.
Обозначим тождественно истинное высказывание заглавной буквой
«И», а тождественно ложное высказывание – заглавной буквой «Л».
Нетрудно проверить справедливость эквивалентностей (4.48) и (4.49). Законы
(4.49) называют законами идемпотентности для операций конъюнкции и дизъюнкции.
Эквивалентность
(4.50) выражает закон противоположности.
Соотношение (4.51) представляет закон контрапозиции.

Используя эквивалентности, или равносильности, алгебры высказываний, можно от одних формул переходить к другим, им эквивалентным. Преобразования такого вида называются равносильными преобразованиями. Можно показать, что с помощью равносильных преобразований всякая формула приводится к виду, содержащему только знаки операций конъюнкции, дизъюнкции и отрицания.
Слайд 113
Введем понятие двойственной формулы.
Пусть формула F[эф] содержит только знаки операций конъюнкции, дизъюнкции и отрицания. Формула G[жэ] называется двойственной формуле
F[эф], если она получена из формулы F[эф] заменой в ней каждого знака операции конъюнкции знаком операции дизъюнкции и каждого знака операции дизъюнкции знаком операции конъюнкции. Обозначение двойственной формулы представлено выражением (4.52). Если формула
G[жэ]является двойственной для формулы F[эф], то формула F[эф]является двойственной для формулы G[жэ].
Если формула F[эф] образована из высказывательных переменных X
1
,
X
2
,… , X
n
[икс один, икс два и т.д., икс эн] только с помощью операций отрицания, дизъюнкции и конъюнкции, то справедливо соотношение (4.53).
Если формулы F[эф] и G[жэ], образованные из высказывательных переменных X
1
, X2,… , X
n
[икс один, икс два и т.д., икс эн] только с помощью операций отрицания, дизъюнкции и конъюнкции, эквивалентны, то двойственные им формулы также эквивалентны. Это отражено в соотношении (4.54).
Для формулы, представленной равенством (4.55), двойственной является формула (4.56).

Слайд 114
Тема 4.2. Булевы функции. Реализация функций формулами
Булева функция от n[эн] аргументов – это отображение f[эф] n-й [энной] декартовой степени множества B[бэ] на множество B[бэ], состоящее из двух элементов 0 и 1. Булеву функцию называют также логической функцией, или
функцией алгебры логики. Двухэлементное множество B[бэ] называется булевым множеством. Элементы этого множества можно интерпретировать как логические значения «истинно» и «ложно», но стоит отметить, что в общем случае они рассматриваются как формальные символы, не несущие определенного смысла. Неотрицательное целое число n[эн] называют арностью, или местностью функции, в случае n = 0[эн равного нулю] булева функция превращается в булеву константу. Элементы декартова произведения B[бэ]в степени n[эн]называют булевыми векторами.
Как известно, множество B[бэ]в степени n[эн] содержит 2 в степени
n[эн] элементов – упорядоченных наборов длины n[эн]. Его можно естественным образом упорядочить. Для этого достаточно считать каждый набор двоичным разложением целого числа k[ка], которое изменяется от нуля до двух в степени n[эн] минус один. При этом мы предполагаем, что число
k[ка] записано с помощью п[эн] двоичныхзнаков. Упорядочение наборов проводится по числу k[ка].
Такое упорядочение называют «скользящей единицей».
Слайд 115
Переменные, принимающие значения из булева множества, называются булевыми переменными. Булевы функции и переменные названы по фамилии математика Джорджа Буля.
Для задания булевой функции можно использовать таблицу ее значений, которую принято называть таблицей истинности.
Две функции от одних и тех же переменных будут равными, если их таблицы истинности совпадают.

Если последовательность наборов множества B[бэ] в степени n[эн] упорядочить, то это позволит определять булеву функцию только последним столбцом, который для экономии места часто записывают в строчку. Пример записи функции трех переменных приведен в формуле (4.57).
Общее число функций от n[эн] переменных можно вычислить по правилу произведения. В каждой строке таблицы истинности такой функции можно поставить два значения – нуль или один, а общее количество строк в таблице равно двум в степени n[эн]. Таким образом, теоретически количество всех функций от n[эн] переменных выражается числом 2 в степени 2 в степени n[эн]. Но некоторые из них являются по существу функциями меньшего числа переменных, а две – вообще константами.
Отметим, что все функции п[эн]переменных так же, как и наборы из нулей и единиц, можно занумеровать по принципу «скользящей единицы».
Слайд 116
Познакомимся с понятиями фиктивной и существенной переменных булевой функции.
На слайде представлено определение соседних по i-той[итой] переменной наборов. Как видно из определения, эти наборы отличаются только значениями i-той[итой] переменной, все остальные переменные принимают одинаковые значения. На основе данного определения вводится понятие фиктивной переменной.
Переменная x
i
[икс итое] называется фиктивной переменной булевой функции f[эф], если для всех пар соседних по этой переменной наборов функция принимает одинаковые значения на обоих элементах пары.
Переменная

Функции f
1
[эф один] и f
2
[эф два] называются равными, если функцию
f
2
[эф два] можно получить из f
1
[эф один] путем введения или удаления фиктивных переменных.
Слайд 117
Покажем на примере, как определять, какие переменные у функции являются существенными, а какие – фиктивными.
Обратимся к функции, представленной на слайде. Рассмотрим сначала переменную х[икс]. Наборами, соседними по этой переменной, будут первый и пятый, второй и шестой, третий и седьмой, четвертый и восьмой. Сравним значения функции на указанных наборах. Мы видим, что уже на элементах первой пары значения функции разные, следовательно, переменная х[икс] – существенная.
Для переменной y[игрек] соседними будут наборы первый и третий, второй и четвертый, пятый и седьмой, шестой и восьмой. На элементах всех этих пар значения функции одинаковые, а значит, переменная y[игрек] фиктивная.
Перейдем к переменной z[зет]. Соседними по ней будут наборы первый и второй, третий и четвертый, пятый и шестой, седьмой и восьмой.
Рассматривая первую пару, видим, что значения функции на ее элементах различны. Поэтому переменная z[зет] – существенная.
Слайд 118
Рассмотрим основные функции дискретной математики.
Сначала обратимся к функциям одной переменной. Согласно приведенной ранее формуле их количество равно двум во второй степени, т. е. четырем. Пронумеруем эти функции естественным образом и поместим их значения в таблицу.
Анализируя таблицу, мы видим, что функции f
0
[эф нулевое] и f
3
[эф третье] являются постоянными, т. е. эти две функции не зависят от х[икс].
Другими словами, переменная х[икс]является в данном случае фиктивной.

Функция f
0
[эф нулевое] представляет собой тождественный нуль, а функция
f
3
[эф третье] – тождественную единицу. Функция f
1
[эф первое] совпадает с переменной х[икс], т. е. она не меняет аргумента. Переменная х[икс] здесь – существенная. Так же обстоит дело и с функцией f
2
[эф второе]. Она принимает значения, противоположные значениям аргумента, и называется отрицанием.
Перейдем к рассмотрению булевых функций двух переменных. Число всех таких функций равно двум в четвертой степени, то есть шестнадцати.
Пронумеруем их по принципу «скользящей единицы» и внесем значения этих функций в таблицу.
Функции f
0
[эф нулевое] и f
15
[эф пятнадцатое] являются константами.
Первая из них – тождественный ноль, вторая – тождественная единица.
Функции f
3,
f
5,
f
10
, f
12
[эф третье эф пятое эф десятое и эф двенадцатое] являются по существу функциями одной переменной. Первая из них совпадает с х[икс], вторая – с у[игрек], третья представляет собой отрицание
у[игрек], последняя – отрицание х[икс]. Для функций f
3
[эф третье] и f
12
[эф двенадцатое] переменная у[игрек] является фиктивной. Для функций f
5
[эф пятое] и f
10
[эф десятое] фиктивной переменной является х[икс].
Наиболее важные функции двух переменных имеют специальные названия и обозначения.
Слайд 119
Остановимся более подробно на семи важнейших функциях алгебры логики.
Начнем с функции, называемой конъюнкцией. В приведенной ранее таблице это функция f
1
[эф первое]. Заметим, что вычисление значений этой функции осуществляется по обычным правилам умножения двоичной арифметики. Конъюнкция принимает значение один в том и только в том случае, когда оба ее аргумента принимают значение один. Эту функцию

называют по-другому функцией «и». На слайде приведены три возможных ее обозначения.
Следующая функция называется дизъюнкцией. В сводной таблице функций двух переменных она имеет седьмой номер. Эта функция принимает значение ноль тогда и только тогда, когда оба ее аргумента принимают значение ноль. Другое название данной функции – функция
«или». Ее обозначение представлено на слайде.
Обратимся к функции, имеющей в сводной таблице тринадцатый номер. Она называется импликацией, или следованием, читается «из х[икс]
следует у[игрек]». Импликация принимает значение ноль в том и только в том случае, когда ее первый аргумент принимает значение один, а второй – значение ноль. Другими словами, по определению мы считаем, что из истины не может следовать ложь. На слайде представлены два возможных обозначения данной функции.
Теперь рассмотрим функцию f
9
[эф девятое]. Она называется эквивалентностью, или подобием, читается «х[икс]эквивалентно у[игрек]».
Данная функция принимает значение один тогда и только тогда, когда оба ее аргумента принимают одинаковые значения. Еще одно название этой функции – биимпликация. На практике используются два различных обозначения данной функции, которые приведены на слайде.
Слайд 120
Обратимся к функции f
6
[эф шестое]. Она называется сложением по модулю два. Данная функция принимает значение один в том и только в том случае, когда ее аргументы принимают различные значения. По значениям этой функции видно, что она представляет собой отрицание эквивалентности. Обозначение данной функции приведено на слайде.
Перейдем к рассмотрению функции f
14
[эф четырнадцатое]. Ее называют штрихом Шеффера. Данная функция принимает значение ноль тогда и только тогда, когда оба ее аргумента принимают значение один. По

существу она представляет собой отрицание конъюнкции. Поэтому иногда эту функцию называют «не и». Ее обозначение представлено на слайде.
Функцию f
8
[эф восьмое] называют стрелкой Пирса, или штрихом
Лукасевича. Она принимает значение один в том и только в том случае, когда оба ее аргумента принимают значение ноль. Эта функция является отрицанием дизъюнкции, поэтому иногда ее называют «не или».
Три оставшиеся функции – f
2
,
f
4
и f
11
[эф второе, эф четвертое и эф одиннадцатое] – не имеют специальных названий, поскольку не играют особой роли в дискретной математике. Первая из них представляет собой импликацию «из y[игрек] следует x[икс]», две другие являются отрицаниями импликаций.
Слайд 121
На основе введенных выше элементарных функций можно строить формулы, которые, аналогично формулам алгебры высказываний, определяются индуктивно.
Рассмотрим множество М[эм], являющееся подмножеством множества всех булевых функций P
2
[пэ два]. Тогда
1) каждая функция из множества

[эм] называется формулой над

[эм];
2) если в формулу из

[эм] вместо каких-то переменных подставить некоторые формулы над

[эм], то полученное выражение также является формулой над

[эм].
Строгая математическая формулировка данного определения представлена на слайде.
Формулы называются эквивалентными, если реализуемые ими функции равны.
При записи формул для указания порядка выполнения операций используются скобки. Число скобок в записи формул можно уменьшить, если ввести следующие правила.