close

Вход

Забыли?

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

?

69.Булевы функции Рублев В С

код для вставкиСкачать
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Министерство образования и науки оссийской Федерации
Федеральное агентство по образованию
Ярославский государственный университет им. П. . Демидова
Каедра теоретической инорматики
В. С. ублев
Булевы ункции
(индивидуальные
работы ќ 4 и 5 по дисциплине
ѕОсновы дискретной математикиї)
Методические указания
екомендовано
Научно-методическим советом университета
для студентов, обучающихся по
специальности Инормационные технологии
Ярославль 2009
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
УДК 519.2
ББК В181я73
82
екомендовано
едакционно-издательским советом университета
в качестве учебного издания. План 2009 года
ецензент
каедра теоретической инорматики Ярославского государственного
университета им. П. . Демидова
ублев, В. С. Булевы ункции: методические указания
82
/ В. С. ублев; Яросл. гос. ун-т. Ярославль: ЯрУ, 2009.
48 с.
Методические указания содержат варианты индивидуальных заданий по теме Булевы ункции дисциплины Основы
дискретной математики, а также необходимый материал для
ее самостоятельного изучения и выполнения индивидуальных
заданий. Для качественного усвоения курса в издании даны
подробные определения, примеры, иллюстрации и обоснования.
Предназначены для студентов, обучающихся по специальности 010400 Инормационные технологии (дисциплина Основы дискретной математики, блок ЕН), очной ормы обучения.
УДК 519.2
ББК В181я73
Ярославский
государственный
университет, 2009
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
1
Булевы ункции
Самые простые дискретные ункции это ункции, аргументы ко-
торых имеют наименьшее число различных значений и которые также
имеют наименьшее число значений. Это наименьшее число значений
равно двум, так как ункция, у которой только одно значение константная, а потому мало интересна, а если аргумент имеет только одно
значение, то ункция актически не зависит от такого аргумента (значение ее не изменяется).
Так как безразлично, какие обозначения выбирать в качестве значений аргумента или ункции (всегда можно переобозначить), то мы
для дальнейшего выберем в качестве таких значений 0 и 1. Таким образом, простейшие дискретные ункции с
из прямого произведения
f0; 1g
n
n
аргументами действуют
на множество {0,1}. Впервые их стал
изучать английский математик и логик Джон Буль создатель ормальной логики, и они названы булевыми по его имени.
Самые простые булевы ункции имеют 1 аргумент. Таблица каждой
такой ункции состоит из двух строк, в каждой из которых дается
значение ункции в зависимости от значения аргумента. Например,
таблица некоторой булевой булевой ункции
следующим образом:
f (x)
может выглядеть
x f (x)
0
1
1
0
Так как в такой таблице булева ункция может принимать при каждом значении аргумента только 1 из 2 значений, то число различных
булевых ункций с 1 аргументом определяется как размещение с повторением из 2 (значений аргумента) по 2 (значения ункции), т. е.
имеется
22 = 4 различных ункции.
Выпишем табличное задание для всех 4-х ункций 1 аргумента:
x f1(x) = 0 f2(x) = x f3(x) = x f4(x) = 1
0
1
0
0
0
1
1
0
1
1
f1 и f4 принимают константные значения соответственно 0 и
1 и называются тождественный 0 и тождественная 1. Функция f2
Функции
3
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
принимает значение аргумента и называется
цией, а ункция
тождественной
унк-
f3 принимает значение, противоположное аргументу
(1 для 0 и 0 для 1), и называется
отрицанием.
Число различных булевых ункций с
n
аргументами можно под-
считать следующим образом:
1. Во-первых, число различных наборов аргументов определяется как
число элементов прямого произведения
jf0; 1g j = 2 .
n
n
2. Во-вторых, каждая ункция определяется как вектор из
единиц.
А потому число различных булевых ункций с
2
n
нулей и
n аргументами опреде-
ляется как число размещений с повторениями 2 элементов (значений
22 . Для n = 1 это число 22 = 4 мы
2 = 24 = 16. Для n = 3
уже нашли. Для n = 2 это число равно 2
2 = 256, а для n = 4 это число 216 = 65576, и далее оно
оно равно 2
ункции) на
2
n
n
местах и равно
2
3
растет очень быстро (сверхэкспонента). Но мы увидим в дальнейшем,
что для описания любой булевой ункции с любым числом аргументов вполне достаточно описать такие ункции с двумя аргументами и
использовать суперпозиции таких ункций.
Наибольшее использование булевы ункции нашли в операциях ормальной логики высказываний
1
, а потому мы их введем для описания
операций над высказываниями.
2
Высказывания и операции над ними
Под
высказыванием
понимается любое повествовательное предло-
жение, о котором имеет смысл говорить, что оно
ложно.
Например, утверждение ѕ
истинно
или оно
2 2 = 4ї является истинным вы-
сказыванием, а утверждение ѕЗемля вращается вокруг Марсаї является ложным высказыванием. Предложение ѕКак хорошо!ї не является
высказыванием (кому хорошо, а кому не очень). Также не является
высказыванием предложение ѕСегодня хорошая погодаї, так как оно
носит субъективный характер, и потому об истинности его ничего сказать нельзя. Не является высказыванием и вопросительное предложение ѕВсе ли студенты пришли на лекцию?ї.
1
Дж. Буль создавал их как раз для описания ормальной логики
4
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Для высказывания вводится истинностное значение, которое в различных системах описания по разному обозначается. Наиболее частыми обозначениями являются следующие:
true для обозначения истинного высказывания и false для обозначения ложного высказывания;
T и F аналогично;
И и Л аналогично;
1 для обозначения истинного высказывания и 0 для обозначения
ложного высказывания.
Мы будем использовать последнее обозначение 1 и 0, которые и ввел
Дж. Буль.
Из простых высказываний можно получать более сложные высказывания, соединяя их различными союзами или условными предложениями. Один из самых простых способов из высказывания
x получить его
отрицание, т. е. высказывание не x. Оно истинно тогда и только тогда,
когда ложно исходное высказывание
x. Операция отрицания является
унарной. Для ее обозначения используется знак
ем либо знак
(черты) над высказыванием. Мы будем использовать
последний. Например,
меньше 1 ї,
x 1.
: перед высказывани-
x<1
означает высказывание ѕневерно,
что x
которое можно записать и без операции отрицания как
В языке программирования
C ++
для отрицания используется вос-
клицательный знак ! перед высказыванием.
Приведем таблицу истинности для операции отрицания:
x x
0 1
1 0
Примером использования отрицания для множеств является
означает
x 2= A
или
x
x 2 A, что
2 A. Такое обозначение отрицания похоже на
обозначение операции дополнения для множеств, и далее мы увидим
тесную связь между этими операцией отрицания для высказываний и
операцией дополнения для множества.
5
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Другой способ получения более сложного высказывание это их
и.
объединение при помощи союза
и
sin x < 0ї
состоит из двух высказываний
единенных союзом
и.
x<1
Например, высказывание ѕ
x > 1
и
sin x < 0,
со-
Такое высказывание истинно тогда и только то-
гда, когда оба высказывания, составляющие его, являются истинными,
и называется
конъюнкцией высказываний.
Операция конъюнкции, та-
ким образом, соединяет 2 высказывания в одно, истинность которого
зависит от истинности входящих в него высказываний. Конъюнкция
высказываний
x
и
y
употребительны & и
имеет разные обозначения, из которых наиболее
^. Мы будем использовать последнее в то время,
C ++
как в языке программирования
используются два знака ампер-
санд && для операции конъюнкции.
Приведем таблицу истинности для операции конъюнкции:
x y x^y
0
0
1
1
0
1
0
1
0
0
0
1
Примером использования конъюнкции для множеств является
x2A
^ x 2 B;
что мы обычно записываем как x 2 A \ B . Обозначение операции пересечения множеств похоже на обозначение конъюнкции поэтому мы
и выбрали такое обозначение: в дальнейшем мы покажем, что между операцией пересечения для множеств и операцией конъюнкции для
высказываний есть тесная связь.
Еще один способ получения более сложного высказывания это соединение двух высказываний при помощи союза
или.
Например, вы-
x < 1 или sin x < 0ї состоит из двух высказываний x > 1
сказывание ѕ
и
sin x < 0, соединенных союзом или. Такое высказывание ложно тогда
и только тогда, когда оба высказывания, составляющие его, являются
ложными, и называется
дизъюнкцией высказываний.
Операция дизъ-
юнкции, таким образом, соединяет 2 высказывания в одно, истинность
которого зависит от истинности входящих в него высказываний. Дизъюнкция высказываний
x
и
y
имеет разные обозначения, из которых
6
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
наиболее употребительны
j и _. Мы будем использовать последнее в
то время, как в языке программирования
вертикальной черты
C ++ используются два знака
jj для операции дизъюнкции.
Приведем таблицу истинности для операции дизъюнкции:
x y x_y
0
0
1
1
0
1
0
1
0
1
1
1
Примером использования дизъюнкции для множеств является
x2A
_ x 2 B;
что мы обычно записываем как x 2 A [ B . Обозначение операции объединения множеств похоже на обозначение дизъюнкции поэтому мы
и выбрали такое обозначение: в дальнейшем мы покажем, что между
операцией объединения для множеств и операцией дизъюнкции для
высказываний есть тесная связь.
Следующий способ получения более сложного высказывания из двух
более простых их соединение при помощи условия ѕесли. . . ,
то. . . ї.
x = , то os x = 1ї получено из простых высказываний x = и os x =
1. Условие при этом можно выражать и другими разами, например, ѕиз x = следует os x =
1ї или ѕx = влечет os x = 1ї или ѕos x = 1 вытекает из x = ї. Такое
Например, ѕесли
импликацией, первое выназывается посылкой, а второе
соединение двух высказываний называется
сказывание в орме ѕесли. . . ,
заключением.
то. . . ї
Заметим, что импликация высказываний не устанав-
ливает причинно-следственную связь между посылкой и заключением,
поскольку импликация не является
выводом,
используемым при дока-
зательстве утверждений.
Импликация ложна тогда и только тогда, когда посылка истинна,
а заключение ложно независимо от смысла высказываний. При ложности посылки импликация всегда является истинной. Действительно,
2 2 = 5, то os x = 2ї можно интерпретировать следующим образом ѕУж если 2 2 = 5, то и os x = 2ї, а потому считать ее
разу ѕесли
7
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
истинной. При этом заключение не обязательно должно быть ложным.
2 2 = 5, то 2+2 = 4ї мы тоже
Например, высказывание ѕПоскольку
должны считать истинным. Для обозначения импликации использует-
!, который находится между посылкой и заключением (стрелка идет в сторону заключения). Например, x = ! os x =
1 или
++
2 2 = 5 ! 2 + 2 = 4. В языке программирования C для импликася знак
ции используется отношение <= (нетрудно видеть, что это отношение
для булевых значений 0 и 1 ложно тогда и только тогда, когда посылка
имеет значение 1, т. е. истинна, а заключение имеет значение 0, т. е.
ложно).
Приведем таблицу истинности для операции импликации:
x y x!y
0
0
1
1
0
1
0
1
1
1
0
1
Примером использования импликации для множеств является
x2A
! x 2 B:
Если это выполнено для любого элемента x 2 A, то мы пишем включение множества A в множество B : A B . Эту связь между отношением
включения для множеств и операцией импликации для высказываний
о принадлежности элементов множествам мы установим позже.
ассмотрим последнее широко употребительное соединение двух высказываний посредством условия ѕ. . . тогда
и только тогда, когда . . . ї
или аналогичных ему: ѕ. . . в том и только в том случае, когда . . . ї,
ѕДля . . . необходимо и достаточно, чтобы . . . ї, ѕ. . . эквивалентно . . . ї
и т.д. Такая операция соединения двух высказываний называется эквиваленцией.
Эквиваленция истинна тогда и только тогда, когда оба высказывания, входящие в нее, имеют одинаковые значения истинности, т. е. либо
оба истинны, либо оба ложны. Для эквиваленции мы будем использовать знак двусторонней стрелки
$. Например, x =
sin x = 0: В языке программирования
C ++
k; k
2
N
$
для импликации использу-
ется отношение == (нетрудно видеть, что это отношение для булевых
8
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
значений 0 и 1 истинно тогда и только тогда, когда оба операнда этого
отношения имеют одинаковые значения, т. е. оба 0, или оба 1). Приведем таблицу истинности для операции эквиваленции:
x y x$y
0
0
1
1
0
1
0
1
1
0
0
1
Примером использования эквиваленции для множеств является
x2A
$ x 2 B:
x 2 U (универсального мноравенство множеств A = B . Эту связь между
Если это выполнено для любого элемента
жества), то мы пишем
отношением равенства для множеств и операцией эквиваленции для
высказываний об элементах множеств мы установим позже.
Выпишем таблицу истинности для тех булевых ункций двух переменных, которые мы уже получили:
x y 0 1 x y x y x_y x^y x!y y !x x$y
0
0
1
1
0
1
0
1
0
0
0
0
1
1
1
1
0
0
1
1
0
1
0
1
1
1
0
0
1
0
1
0
0
1
1
1
0
0
0
1
1
1
0
1
1
0
1
1
1
0
0
1
Из 16 булевых ункций двух переменных мы в этой таблице указа-
тождественный 0, тождественная
1, тождественный первый аргумент, тождественный второй аргумент, и т.д. Две ункции из ункций, не вошедших в эту таблицу,
ли 11. Они имеют свои названия:
также имеют свои названия, но мы их введем позже.
3
Формулы высказываний и их выполнимость
Введенные операции над высказываниями позволяют выражать лю-
бые сложные высказывания. Но для того чтобы определить порядок
выполнения операций над высказываниями, необходимо либо каждый
9
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
операнд заключать в круглые скобки и выполнять операции в порядке
скобок, заменяя каждый операнд на вычисленное его значение, либо
договориться о приоритете операций и тогда расставлять скобки только в тех случаях, когда порядок операций не соответствует приоритету.
Последний случай более предпочтителен, так как делает запись ормулы высказываний более наглядной.
Принят приоритет операций в том порядке, в котором мы описывали операции, т. е.
; ^; _; !; $ в первую очередь, внутри самых
внутренних скобок выполняется отрицание, затем конъюнкция, дизъюнкция, импликация и, наконец, эквиваленция и т.д. в этом порядке;
затем самые внутренние скобки убираются (заменяются вычисленным
значением) и вычисления продолжаются в том же порядке.
Для еще большей наглядности опускают знак конъюнкции как в
алгебраическом выражении опускают знак умножения ведь таблица
ункции конъюнкции полностью совпадает с таблицей ункции умножения
x на y.
Пусть, например, необходимо вычислять ормулу
F1 = (((x ! y) $ (y _ z )) ^ (x ^ y)):
С учетом сделанных замечаний о приоритете и опускании знака операции конъюнкции ормула преобразуется в более наглядную:
F1 = (x ! y $ y _ z )(xy):
Пусть необходимо вычислить значение этой ормулы при следующих
значениях аргументов:
x = 1; y = 1; z = 0.
Тогда последовательным
вычислением в порядке приоритета получаем:
y = 0; y _ z = 1; x ! 0 = 0; 0 $ 1 = 0; xy = x ^ y = 1; F1 = 0 ^ 1 = 0;
и, следовательно, значение ормулы равно 0.
Каждая ормула выражает булеву ункцию, значение которой зависит от значений высказываний, входящих в ормулу. Булева ункция называется
выполнимой,
если существует такой набор значений
переменных (высказываний, входящих в ормулу), для которых значение ункции истинно (равно 1). Для определения свойства выполнимости булевой ункции пока неизвестны алгоритмы, отличные по
10
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
трудоемкости от вычисления значений ункции для всех наборов переменных (и, по всей видимости, они не существуют).
Поэтому для установления выполнимости булевой ункции, задан-
F1, составим последовательно таблицу истинности для
каждой операции, входящей в ормулу F1 , а затем и для значения
ормулы F1 :
ной ормулой
z}|{ z }| { z }| { z }| { z }| { z }| {
x y z y y _ z x ! f1 f3 $ f2 x ^ y f4 ^ f5
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
f1
f2
f3
f4
f5
F1
1
1
0
0
1
1
0
0
0
1
1
1
0
1
1
1
1
1
1
1
1
1
0
0
0
1
1
1
0
1
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
Из таблицы истинности следует, что ункция
ункция называется
тождественно ложной
F1 невыполнима. Такая
или
противоречием.
ассмотрим теперь ормулу
F2 = (x ! y $ y _ z )(x ^ y):
Ее таблица истинности, приведенная ниже, показывает, что эта ункция
F2 выполнима.
z}|{ z }| { z}|{ z }| { z }| { z }| { z }| {
x y z y y _ z f2 x ! f1 f4 $ f3 x ^ y f5 ^ f6
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
f1
f2
1
1
0
0
1
1
0
0
0
1
1
1
0
1
1
1
f3
1
0
0
0
1
0
0
0
f4
f5
f6
F2
1
1
1
1
1
1
0
0
1
0
0
0
1
0
1
1
0
0
0
0
0
0
1
1
0
0
0
0
0
0
1
1
11
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Если ункция выполнима при любом наборе переменных, то она называется
тождественно истинной
или
тавтологией.
Примером та-
кой ункции может служить ормула
F3 = (x ! y) ^ (y ! z ) ! (x ! z ):
Ее таблица истинности приведена ниже:
z }| { z }| { z }| {
z
}|
{
z
}|
{
x y z x ! y y ! z f1 ^ f2 x ! z f3 ! f4
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
f1
f2
1
1
1
1
0
0
1
1
1
1
0
1
1
1
0
1
f3
1
1
0
1
0
0
0
1
f4
1
1
1
1
0
1
0
1
F3
1
1
1
1
1
1
1
1
Эта тавтология выражает закон транзитивности импликации:
x следует y и из y следует z, то из x следует z.
если из
Тавтологии играют
исключительно важную роль при доказательстве утверждений. Поэтому приведем список тавтологий, выполняющих роль законов вывода:
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
x_x
x$x
x^x$x
x_x$x
x^y !x
x!x_y
x^y $y^x
x_y $y_x
x ^ (y ^ z ) $ (x ^ y) ^ z
x _ (y _ z ) $ (x _ y) _ z
x ^ (y _ z ) $ (x ^ y) _ (x ^ z )
x _ (y ^ z ) $ (x _ y) ^ (x _ z )
x^y $x_y
x_y $x^y
x!y$y!x
12
закон исключенного третьего
закон двойного отрицания
закон поглощения
закон поглощения
закон вывода
закон вывода
з. коммутативности конъюнкции
з. коммутативности дизъюнкции
з. ассоциативности конъюнкции
з. ассоциативности дизъюнкции
закон дистрибутивности
закон дистрибутивности
закон двойственности
закон двойственности
закон контрпозиции
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
16.
17.
18.
19.
20.
(x ! y) ^ (y ! z) ! (x ! z)
(x ! y) ^ (x ! y) ! x
(x _ y) ^ (x ! z) ^ (y ! z) $ z
(x $ y) ^ (y $ z) ! (x $ z)
(x $ y) $ (x $ y)
з. транзитивности импликации
з. косвенного доказательства
закон разбора случаев
з. транзитивности эквиваленции
закон противоположностей
Заметим, что ассоциативность дизъюнкции и ассоциативность конъюнкции позволяют ввести групповые операции конъюнкции и дизъюнкции:
^
n
=1
_
n
x;
i
=1
i
4
x:
i
i
авносильность (эквивалентность) ормул высказываний
Две ормулы высказываний равносильны (эквивалентны), если для
любых наборов значений переменных они принимают одинаковые значения. Тождество
A(x1; : : : ; x ) B (x1; : : : ; x )
n
следует читать
A равносильно B.
n
Если
A тавтология, то будем писать
A 1, а если A противоречие, то A 0.
Теорема 1. A B , (A $ B ) 1:
Действительно, если A B , то для любого
набора переменных зна-
чения обеих ормул одинаковы, и, значит, их эквиваленция является
тавтологией. Обратно, если эквиваленция ормул
A и B является тав-
тологией, то обе ормулы принимают одинаковые значения на каждом
наборе переменных, и, следовательно, они равносильны.
авносильность ормул позволяет их преобразовывать так же, как
это делается в алгебре числовых выражений. Приведем список равносильностей, часто используемых для этого:
1.
2.
3.
4.
5.
AA
A^B B^A
A_B B_A
A ^ (B ^ C ) (A ^ B ) ^ C
A _ (B _ C ) (A _ B ) _ C
закон двойного отрицания
коммутат. конъюнкции
коммутат. дизъюнкции
ассоциат. конъюнкции
ассоциат. дизъюнкции
13
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
A ^ (B _ C ) (A ^ B ) _ (A ^ C )
A _ (B ^ C ) (A _ B ) ^ (A _ C )
A^B A_B
A_B A^B
A_AA
A^AA
A^1A
A_0A
A_A=1
A^A=0
A^00
A_11
1!AA
A!11
A!0A
A!B A_B
A $ B (A _ B ) ^ (B _ A)
A $ B (A ^ B ) _ (A ^ B )
A ! B ^ C (A ! B ) ^ (A ! C )
A ^ B ! C A ! (B ! C )
A!BB!A
закон дистрибутивности
закон дистрибутивности
закон двойственности
закон двойственности
закон идемпотентности
закон идемпотентности
закон исключ. третьего
закон исключ. третьего
Используя равносильности ормул, можно приводить их к более простому виду. Приведем пример.
10
12
6
17
12
(A_A)^B _A A^B _A A^B _A^1 A^(B _1) A^1 A:
В этом примере над каждым использованием равносильности мы пишем ее номер в списке.
Подобно группированию конъюнкцией под одним знаком общей конъюнкции, а также группированию дизъюнкций под одним знаком общей дизъюнкции мы будем поступать и с равносильностью ормул,
используя знаки общей конъюнкции и общей дизъюнкции для ормул
группирования:
^
n
=1
_
n
A;
i
=1
i
A:
i
i
Заметим, что закон дистрибутивности конъюнкции относительно
дизъюнкции напоминает закон дистрибутивности умножения относи-
14
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
тельно сложения. Поэтому конъюнкцию часто называют логическим
2
умножением , а дизъюнкцию логическим сложением. Подобно алгебре чисел, где введены операции умножения, сложения и константы 1
и 0, введенные нами операции логического умножения, сложения, а
также логические константы 1 и 0 подчиняются аналогичным законам
(равносильности 1-13), и потому такая система операций называется
алгеброй Буля, или
Булевой алгеброй.
Таким образом, алгебра высказываний есть булева алгебра. Если
для алгебры множеств операцию пересечения интерпретировать как
конъюнкцию, операцию объединения интерпретировать как дизъюнкцию, а операцию дополнения как отрицание, то нетрудно убедиться,
что выполняются все законы с 1 по 13 для алгебры множеств. Поэтому
алгебра множеств также является булевой алгеброй.
Еще 1 пример булевой алгебры это множество точек отрезка
[a; b?
с введенными операциями:
сложение x _ y = maxfx; yg;
умножение x ^ y = minfx; yg;
отрицание x = a + b x (точка отрезку [a; b?, симметричная x
относительно середины отрезка
оль 0 играет левый конец отрезка
+
2
a
b
).
a, а роль 1 правый конец отрезка
b. Законы 113 непосредственно проверяются.
5
Связь алгебры множеств и алгебры высказываний
Так как обе алгебры множеств и высказываний являются Буле-
выми алгебрами, то можно установить такую связь между операциями над множествами и операциями над высказываниями, которая позволяла бы проверку некоторого утверждения для множеств свести к
проверке тождественной истинности высказывания. Последняя может
быть осуществлена при помощи компьютерной программы, что в значительной степени облегчает процесс доказательства утверждения для
множеств.
2
К тому же таблицы истинности для конъюнкции и умножения совпадают
15
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Пусть
U
некоторое универсальное множество и
подмножества. Для любого элемента
x2U
X1; X2; : : : ; X
n
его
введем высказывания
x = x 2 X (i 2 1; n):
i
Пусть
i
A произвольная ормула алгебры высказываний, не содержа-
щая констант 0 и 1, и содержащая только операции отрицания, конъ-
x1 ; x2 ; : : : ; x .
Обозначим через A(x) выражение, полученное из ормулы A заменой x на x 2 X . Например,
если A1 = x1 ^ x2 , то A1 (x) = x 2 X1 ^ x 2 X2 ,
а если A2 = x1 ^ x2 _ x3 , то A2 (x) = x 2 X1 ^ x 2 X2 _ x 2 X3 .
Обозначим через Z выражение, полученное из A заменой x на X
и символов ^; _;
на \; [;
соответственно. Например,
Z 1 = X1 \ X2; Z 2 = X1 \ X2 [ X3.
юнкции и дизъюнкции с переменными (высказываниями)
i
n
i
A
A
i
i
A
Теорема 2 (о связи операций над множествами и операций над
A, любого множества U и его
2 U A(x) истинно тогда и
Для любой ормулы
подмножеств X1 ; X2; : : : , любого x
только тогда, когда x Z .
высказываниями).
2
A
Доказательство. Доказательство ведем методом математической индукции по числу операций
степенью
данной ормулы
^; _;
в ормуле
A.
A.
Назовем это число
A равна 0. Тогда A = x ; A(x) = x 2 X ; Z = X
и утверждение теоремы превращается в тавтологию: x 2 X
,
x 2 X . Базис индукции доказан.
1. Пусть степень
i
i
A
i
i
i
2. Пусть утверждение теоремы верно для всех ормул степени, мень-
k. ассмотрим ормулу A степени k. Тогда последней выполняемой в ормуле A операцией является одна из операций множества f^; _; g, т. е. A имеет один из видов:
шей
1) A = B;
2) A = B _ C;
3) A = B ^ C;
B и C степени, меньшей k. ассмотрим каждый случай.
1) Z = Z ; A(x) = B (x). Так как A = B , высказывание A(x) истинно тогда и только тогда, когда ложно B (x), т. е. тогда и только
тогда, когда x 2
= Z , что эквивалентно x 2 Z . Случай доказан.
причем
A
B
B
A
16
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Z = Z [ Z ; A(x) = B (x) _ C (x). Так как A = B _ C , высказывание A(x) истинно т. и т.т., когда истинно B (x) _ C (x), т. е. т. и т.
т., когда x 2 Z или x 2 Z , что эквивалентно x 2 Z [ Z = Z .
2)
A
B
C
B
C
B
C
A
Случай доказан.
Z = Z \ Z ; A(x) = B (x) ^ C (x). Так как A = B ^ C , высказывание A(x) истинно т. и т.т., когда истинно B (x) ^ C (x), т. е. т. и
т. т., когда x 2 Z и x 2 Z , что эквивалентно x 2 Z \ Z = Z .
3)
A
B
C
B
C
B
C
A
Случай доказан.
Шаг индукции сделан. Теорема доказана.
Z = U , 8x : (x 2 U ) A(x) = 1).
Если для любого x 2 U A(x) = 1, то по теореме x 2 Z , т. е. Z = U .
Обратно, если Z = U , то для любого x 2 U : x 2 Z и, следовательно,
по теореме A(x) = 1 для любого x 2 U .
Следствие 2. Z = ; , 8x : (x 2 U ) A(x) = 0).
Если Z = ;, то 8x : x 2
= Z и по теореме A(x) = 0. Обратно, если для
любого x 2 U A(x) = 0, то по теореме x 2
= Z и, следовательно Z = ;.
Следствие 3. Z = Z
, 8x : (x 2 U ) A(x) = B (x)).
Если для любого x 2 U : A(x) = B (x), то в случае A(x) = B (x) = 1
по теореме x 2 Z ; x 2 Z ; а в случае A(x) = B (x) = 0 по теореме
x 2= A; x 2= B ; объединяя оба случая, получим, что Z и Z состоят
из одних и тех же элементов, т. е. Z = Z . Обратно, если Z = Z ,
то для любого x 2 U : x 2 Z
= Z по теореме A(x) = B (x) = 1;
а для любого x 2 U : x 2
= Z = Z по теореме A(x) = B (x) = 0; и,
следовательно, в обоих случаях A(x) = B (x).
Следствие 4. Z Z
, 8x : (x 2 U ) (A(x) ! B (x)) = 1).
Пусть Z
Z . Если x 2 Z , то x 2 Z и по теореме A(x) =
B (x) = 1; если же x 2= Z , то по теореме A(x) = 0 и, следовательно, A(x) ! B (x) = 1; объединяя оба случая, получим, что для всех
x 2 U : (A(x) ! B (x)) = 1. Обратно, пусть 8x (x 2 U ) (A(x) !
B (x)) = 1). Тогда, если x 2 Z , то по теореме A(x) = 1, а из условия следует B (x) = 1, а потому по теореме x 2 Z
и, следовательно,
Z Z .
Следствие 1.
A
A
A
A
A
A
A
A
A
A
A
B
A
B
A
A
A
A
A
A
B
B
A
B
B
B
B
B
A
B
A
A
B
A
B
Доказанные теорема 2 и следствия из нее дают возможность свести
доказательство утверждения для множеств к проверке тождественной
истинности соответствующего высказывания, которое получается следующими действиями:
17
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
1. Выделить из утверждения все отношения множеств (равенства,
включения).
2. Каждое отношение множеств в утверждении заменить на высказывание следующим образом:
1) каждое множество
X
i
заменить на высказывание
x =x2X;
i
i
2) каждую операцию пересечения множеств заменить на конъюнкцию соответственно полученных высказываний;
3) каждую операцию объединения множеств заменить на дизъюнкцию соответственно полученных высказываний;
4) каждую операцию дополнения множества заменить на отрицание соответственно полученного высказывания.
3. Подставить каждое полученное высказывание в исходное утверждение на место соответствующего отношения множеств.
Обоснование сведения зависит от отношений множеств, входящих в
утверждение, и мы его оставляем в качестве упражнения при выполнении задания. Пример такого сведения приведен в индивидуальном
задании 4.
6
Индивидуальное задание 4
1. ешить задачу 1 задания 1 путем сведения к проверке истинно-
сти ормулы алгебры высказываний. Обосновать сведение к ормуле
алгебры высказываний ссылками на теорему и следствия для каждой
ее части.
2. ешить комбинаторную задачу Сколько чисел с заданным числом знаков можно составить из цир заданного числа?. Обосновать
подробно весь ход решения.
6.1
Пример задачи 1 и ее решения
X1 \X2 \X3 = ; и X1 [X2 [X3 = U
18
$ (X2 nX3)[(X1 nX2) = X1 [X 3
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Z
Z
Введем обозначения
A
(X2 n X3) [ (X1 n X2); Z X1 [ X 3; Z X1 \ X2 \ X3;
X1 [ X2 [ X3:
Тогда Z = ; ^ Z = U $ Z = Z .
Преобразуем множество Z = (X2 \ X 3 ) [ (X1 \ X 2 ):
Пусть x 2 U произвольный элемент U . Введем обозначение для
B
C
D
C
D
A
B
A
высказываний
y
i
x2X:
i
Тогда по теореме о связи ормул алгебры множеств и ормул алгебры
высказываний:
x2Z
$ y2 ^ y3 _ y1 ^ y2 = 1; x 2 Z $ y1 _ y3 = 1;
$ y1 ^ y2 ^ y3 = 1; x 2 Z $ y1 _ y2 _ y3 = 1
A
x2Z
B
C
D
и, следовательно, по следствию 3 из теоремы:
Z =Z
A
B
$ (y2 ^ y3 _ y1 ^ y2 $ y1 _ y3 = 1);
а по следствиям 1 и 2:
Z =;
C
$ y1 ^ y2 ^ y3 = 0;
Z =U
D
$ y1 _ y2 _ y3 = 1:
Окончательно получаем
(Z = ; ^ Z = U $ Z = Z ) $
$ (y1 ^ y2 ^ y3 ^ (y1 _ y2 _ y3) $ (y2 ^ y3 _ y1 ^ y2 $ y1 _ y3));
C
D
A
B
и проверка утверждения задачи сводится к проверке тождественной
истинности следующей ормулы алгебры высказываний:
F
(y1 ^ y2 ^ y3 ^ (y1 _ y2 _ y3) $ (y2 ^ y3 _ y1 ^ y2 $ y1 _ y3)):
Обозначим
F1 y1 ^ y2 ^ y3; F2 y1 _ y2 _ y3; F3 y2 ^ y3; F4 y1 ^ y2;
F5 y1 _ y3:
Тогда F = F1 ^ F2 $ (F3 _ F4 $ F5 ):
Составим таблицу истинности F :
19
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
y1y2y3 F1 F2 F1 ^ F2 F3 F4 F3 _ F4 F5 F3 _ F4 $ F5 F
0 0 0
1
0
0
0
0
0
1
0
1
0 0 1
1
1
1
0
0
0
0
1
1
0 1 0
1
1
1
1
0
1
1
1
1
0 1 1
1
1
1
0
0
0
0
1
1
1 0 0
1
1
1
0
1
1
1
1
1
1 0 1
1
1
1
0
1
1
1
1
1
1 1 0
1
1
1
1
0
1
1
1
1
1 1 1
0
1
0
0
0
0
1
0
1
Из таблицы истинности видно, что
F
1, т. е. F тавтология, что
доказывает истинность утверждения для множеств.
6.2
Варианты второй задачи индивидуального задания 4
1. Сколько 5-значных чисел можно составить из цир числа 12115233?
2. Сколько 6-значных чисел можно составить из цир числа 12335233?
3. Сколько 6-значных чисел можно составить из цир числа 12235233?
4. Сколько 7-значных чисел можно составить из цир числа 12115233?
5. Сколько 6-значных чисел можно составить из цир числа 12135233?
6. Сколько 6-значных чисел можно составить из цир числа 12525233?
7. Сколько 7-значных чисел можно составить из цир числа 12333233?
8. Сколько 5-значных чисел можно составить из цир числа 12225233?
9. Сколько 6-значных чисел можно составить из цир числа 12125233?
10. Сколько 5-значных чисел можно составить из цир числа 12335333?
11. Сколько 4-значных чисел можно составить из цир числа 12115231?
12. Сколько 7-значных чисел можно составить из цир числа 12115233?
13. Сколько 5-значных чисел можно составить из цир числа 12335233?
14. Сколько 6-значных чисел можно составить из цир числа 21447752?
20
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
15. Сколько 4-значных чисел можно составить из цир числа 14477522?
16. Сколько 6-значных чисел можно составить из цир числа 767533432?
17. Сколько 7-значных чисел можно составить из цир числа 675433327?
18. Сколько 5-значных чисел можно составить из цир числа 754333276?
19. Сколько 4-значных чисел можно составить из цир числа 543327767?
20. Сколько 5-значных чисел можно составить из цир числа 881326644?
21. Сколько 6-значных чисел можно составить из цир числа 813662448?
22. Сколько 4-значных чисел можно составить из цир числа 136426848?
23. Сколько 7-значных чисел можно составить из цир числа 364862841?
24. Сколько 6-значных чисел можно составить из цир числа 974972671?
25. Сколько 5-значных чисел можно составить из цир числа 749627719?
26. Сколько 7-значных чисел можно составить из цир числа 496772917?
27. Сколько 4-значных чисел можно составить из цир числа 694277179?
28. Сколько 5-значных чисел можно составить из цир числа 942177976?
29. Сколько 7-значных чисел можно составить из цир числа 421977679?
30. Сколько 4-значных чисел можно составить из цир числа 219767497?
31. Сколько 6-значных чисел можно составить из цир числа 197672794?
32. Сколько 4-значных чисел можно составить из цир числа 882233315?
33. Сколько 6-значных чисел можно составить из цир числа 282383153?
34. Сколько 7-значных чисел можно составить из цир числа 823138352?
35. Сколько 5-значных чисел можно составить из цир числа 231838253?
36. Сколько 6-значных чисел можно составить из цир числа 141455666?
37. Сколько 4-значных чисел можно составить из цир числа 414565616?
38. Сколько 5-значных чисел можно составить из цир числа 145654166?
21
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
39. Сколько 7-значных чисел можно составить из цир числа 456154661?
40. Сколько 5-значных чисел можно составить из цир числа 822735544?
41. Сколько 7-значных чисел можно составить из цир числа 227535484?
42. Сколько 6-значных чисел можно составить из цир числа 275453284?
43. Сколько 4-значных чисел можно составить из цир числа 754235248?
44. Сколько 6-значных чисел можно составить из цир числа 243342517?
45. Сколько 7-значных чисел можно составить из цир числа 433542172?
46. Сколько 5-значных чисел можно составить из цир числа 353124274?
47. Сколько 4-значных чисел можно составить из цир числа 531422753?
48. Сколько 7-значных чисел можно составить из цир числа 857531222?
49. Сколько 5-значных чисел можно составить из цир числа 573221258?
50. Сколько 6-значных чисел можно составить из цир числа 732122585?
51. Сколько 5-значных чисел можно составить из цир числа 832122585?
7
Двойственные булевы ункции и принцип двойственности
f (x1; : : : ; x ) = f (x1; : : : ; x ) называется двойственной к
ункции f (x1; : : : ; x ).
Заметим, что отрицание f в этом определении означает, что в табФункция
n
n
n
лице истинности все значения ункции инвертируются (нули заменяются единицами, единицы нулями). Отрицание каждого аргумента
x (i = 1; : : : ; x )
i
n
означает, что мы переходим к противоположному
набору аргументов. При лексикограическом упорядочивании наборов
аргументов в таблице истинности противоположные наборы симметричны относительно их середины. Поэтому верен следующий способ
получения по таблице истинности какой-либо булевой ункции таблицы истинности для ее двойственной ункции:
инвертировать столбец ункции;
22
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
перевернуть столбец.
Эти действия можно выполнять в любом порядке. Например, в следующей таблице истинности приведена одна из булевых ункции с 3-мя
аргументами и ее двойственная ункция, полученная описанными действиями (инвертирование и переворот столбца).
x y z f f
0 0 0
1
1
0 0 1
0
0
0 1 0
1
1
0 1 1
1
0
1 0 0
1
0
1 0 1
0
0
1 1 0
1
1
1 1 1
0
0
Нетрудно видеть, что ункция, двойственная к двойственной ункции, является исходной ункцией, т. е.
f = (f ) = f . В самом деле, в
таблице истинности нужно дважды инвертировать и дважды перевернуть столбец, что приведет к таблице истинности исходной ункции.
Поэтому на парах булевых ункций определяется
симметричное от-
ношение двойственности. Так, ункция 0 двойственна к ункции 1, и,
наоборот, ункция 1 двойственна к ункции 0. Функции конъюнкции
и дизъюнкции двойственны друг другу. Взаимодвойственными являются ункции эквиваленции и исключающей дизъюнкции (сложения
по модулю 2).
Булева ункция, двойственная сама себе, называется
самодвойствен-
x, тождественная ункция x или ункция, выраженная ормулой: xy _ xy .
ной.
Таковы, например, ункция отрицания
как по ормуле булевой ункции получить ормулу двойственной ункции, которая называется
двойственной ормулой. Следующая теорема двойственности отвеПоследний пример приводит к задаче:
чает на этот вопрос.
Теорема двойственности.
Для любой ормулы булевой ункции
(x1; : : : ; x ) = f ( f1(x11; : : : ; x1 ); : : : ; f (x 1; : : : ; x
p1
n
23
m
m
mpm
) );
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
где
[
fx1; : : : ; x g = fx 1; : : : ; x g;
m
n
i
ipi
=1
двойственная ункция выражается ормулой
i
(x1; : : : ; x ) = f ( f1(x11; : : : ; x1 ); : : : ; f (x 1; : : : ; x
p1
n
m
m
mpm
) );
полученной заменой ункций, входящих в суперпозицию исходной ункции, на двойственные к ним.
Доказательство.
(x1; : : : ; x
) = (x1; : : : ; x ) =
= f ( f1(x11; : : : ; x1 ); : : : ; f (x 1; : : : ; x ) ) =
= f ( f1(x11; : : : ; x1 ); : : : ; f (x 1; : : : ; x ) ) =
= f ( f1(x11; : : : ; x1 ); : : : ; f (x 1; : : : ; x ) ) =
= f ( f1(x11; : : : ; x1 ); : : : ; f (x 1; : : : ; x ) ):
n
n
p1
m
m
mpm
p1
m
m
mpm
p1
m
m
mpm
p1
m
m
mpm
Из теоремы двойственности следует принцип двойственности:
Для любой ормулы A(f1; : : : ; f ) двойственная к ней ормула получается заменой всех входящих в нее ункций на двойственные, т. е.
s
A(f1; : : : ; f ).
s
Таким образом, для получения двойственной ормулы необходимо
^ на _, _ на ^ и т.д. Например, для ормулы
x _ y ^ z получаем двойственную ормулу x ^ (y _ z ).
заменить 0 на 1, 1 на 0,
Из принципа двойственности следует:
Теорема о равносильности двойственных ормул.
B равносильные ормулы, то ормулы A
Например, из первого закона де Моргана
второй закон де Моргана
x _ y = x ^ y.
Если
Aи
и B также равносильны.
x^y = x _ y
вытекает
Другой пример: какая ормула двойственна для импликации
A!
B ? Двойственная ормула выражается как A ! B . Как ее упростить?
Проще использовать равносильную ормулу A _ B для импликации.
Тогда двойственная для нее ормула A ^ B , т. е. A ! B = A ^ B . Таким
образом, принцип двойственности позволяет сократить тождественные
преобразования.
24
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
8
еализация булевой ункции ормулой
Каждая ормула высказываний представляет собой некоторую бу-
леву ункцию. Используя равносильности ормул, можно преобразовывать ормулы. Некоторые из видов ормул имеют специальное название
ормы. К
ним прежде всего относятся дизъюнктивно-нормаль-
ная орма (ДНФ) и
конъюнктивно-нормальная орма
(КНФ). Обе
ормы являются ормулами, содержащими только 3 операции из рассмотренных 5: отрицание, конъюнкцию и дизъюнкцию. Для их определения введем понятия
элементарной конъюнкции
и
элементарной
дизъюнкции.
Элементарной конъюнкцией называется конъюнкция переменных,
входящих в ормулу, или их отрицаний. При этом каждая переменная
входит в ормулу элементарной конъюнкции не более 1 раза. Напри-
x ^ y ^ z и y являются элементарными конъюнкциями,
а ормула x ^ y _ z не является таковой.
мер, ормулы
Элементарной дизъюнкцией называется дизъюнкция переменных,
входящих в ормулу, или их отрицаний. При этом каждая переменная
входит в ормулу элементарной конъюнкции не более 1 раза. Напри-
x _ y _ z и y являются элементарными дизъюнкциями,
а ормула x _ y ^ z не является таковой.
мер, ормулы
Дизъюнктивно-нормальной ормой называется дизъюнкция элементарных конъюнкций. Например, ормулы xyz x y и xy являются
ДНФ, а ормула
xy таковой не является.
_
Конъюнктивно-нормальной ормой называется конъюнкция элементарных дизъюнкций. Например, ормулы xyz (x y ) и x y
являются КНФ, а ормула
xy таковой не является.
^
_
_
Можно ли любую булеву ункцию представить ормулой? Можно
ли любую ормулу привести эквивалентными преобразованиями (равносильностями) к ДНФ или к КНФ? Мы дадим положительный ответ
на эти вопросы и покажем, как это сделать.
Введем обозначение:
x =
vi
i
x ; v = 1;
x ; v = 0:
i
i
i
i
25
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
а??смотрим ормулу
_
f (v1; : : : ; v ) ^ x11 ^ ^ x :
v
vn
n
n
v1 ;:::;vn
Это ДНФ, у которой каждый конъюнктивный член дизъюнкции имеет
вид:
f (v1; : : : ; v ) ^ x11 ^ ^ x :
v
vn
n
n
Например,
f (0; 1; : : : ; 1; 0)x01x12 : : : x1 1x0 = f (0; 1; : : : ; 1; 0)x1x2 : : : x 1x :
При значениях переменных ормулы x1 ; : : : ; x , равных соответственно v1 ; : : : ; v , каждое x
= 1 (i 2 1; n). Действительно, при v = 1
x = x = v = 1, а при v = 0 x = x = 1. Поэтому при значениях переменных ормулы x1 ; : : : ; x , равных соответственно v1 ; : : : ; v ,
1
конъюнктивный член f (v1 ; : : : ; v ) ^ x1 ^ ^ x
= f (v1; : : : ; v ); а на
n
n
n
n
n
vi
n
i
i
vi
i
vi
i
i
i
i
i
n
n
v
vn
n
n
n
любом другом наборе эта конъюнктивный член равен 0 (для какого-то
индекса
i, где x =
6 v x = 0, а потому и значение такого конъюнкvi
i
i
i
тивного члена равно 0).
Тем самым мы показали, что на каждом наборе переменных значение ункции
f (x1; : : : ; x ) совпадает со значением указанной ДНФ.
n
Таким образом, мы доказали теорему о разложении булевой ункции
по переменным:
Теорема о разложении булевой ункции по переменным.
Любая булева ункция представляется в виде ДНФ :
_
f (x1; : : : ; x ) =
n
f (v1; : : : ; v ) ^ x11 ^ ^ x :
v
n
vn
n
v1 ;:::;vn
Полученную ормулу можно упростить, сделав ее зависящей только
от переменных. Для этого
1) нужно опустить все слагаемые, для которых
f (v1; : : : ; v ) = 0, так
n
как каждый соответствующий конъюнктивный член равен 0, а в
силу равносильности ормул
A _ 0 A, т. е. все нулевые слагае-
мые (логические) можно опустить;
f (v1; : : : ; v ) = 1 нужно опустить этот множитель (логический) f (v1 ; : : : ; v ), так как A ^ 1 A.
2) в остальных слагаемых
n
n
26
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Получившаяся при этом упрощении ДНФ называется
совершенной ди-
зъюнктивно-нормальной ормой (СДНФ).
СДНФ это такая ДНФ, каждая элементарная конъюнкция которой содержит все переменные ормулы или их отрицания по 1 разу.
xy _ yz
Например, ДНФ
и
xyx _ yxy
не являются СДНФ, так как в
первой ормуле элементарные конъюнкции содержат не все переменные, а во второй переменные в каждой элементарной конъюнкции
повторяются.
Алгоритм получения СДНФ булевой ункции по ее таблице истинности довольно прост:
1. Для каждого
единичного набора переменных
(набора, где унк-
ция принимает значение 1) составить элементарную конъюнкцию,
в которую переменная входит сама, если ее значение в наборе равно 1, и входит отрицание переменной, если ее значение в наборе
равно 0.
2. Составить дизъюнкцию всех полученных элементарных конъюнкций.
Пример 1. Записать СДНФ булевой ункции от трех переменных,
которая принимает значение 1 тогда и только тогда, когда значения
всех переменных одинаково.
ешение. Единичными будут только 2 набора:
x1 = x2 = x3 = 1. Поэтому
СДНФ: x1 x2 x3 _ x1 x2 x3 .
x1 = x2 = x3 = 0 и
наша ункция записывается следующей
Из теоремы следуют также ответы на поставленные вопросы: любую
ункцию можно записать в виде ормулы и любую ормулу можно
привести к ДНФ.
_
ассмотрим ормулу для отрицания ункции:
f (x1; : : : ; x ) =
f (v1; : : : ; v ) ^ x11 ^ ^ x
v
n
n
vn
n
v1 ;:::;vn
W
и применим отрицание к обеим частям равенства:
f (x1; : : V
:;x ) = 1
f (v1; : : : ; v ) ^ x11 ^ ^ x =
= 1 f (v1; : : : ; v ) _ x11 _ _ x :
n
v
v
vn
n
v ;:::;vn
vn
n
n
v ;:::;vn
n
^
Получим представление в виде КНФ:
f (x1; : : : ; x ) =
n
f (v1; : : : ; v )_x11 _ : : : _x :
v
n
v1 ;:::;vn
27
vn
n
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Если в этой ормуле
1) опустить все элементарные дизъюнкции, для которых
f (v1; : : : ; v ) = 1, так как A ^ 1 A;
n
2) опустить в оставшихся множителях (логических) слагаемые
f (v1; : : : ; v ) = 0, так как A _ 0 A,
n
совершенную конъюнктивно-нормальную орму (СКНФ).
СКНФ это такая КНФ, каждая элементарная дизъюнкция которой содержит все переменные ормулы или их отрицания по 1
разу. Например, КНФ (x y ) (y z ) и (x yx) (y x y ) не
то мы получим
_ ^ _
_
^ _ _
являются СКНФ, так как в первой ормуле элементарные дизъюнкции содержат не все переменные, а во второй переменные в каждой
элементарной дизъюнкции повторяются.
Алгоритм получения СКНФ булевой ункции по ее таблице истинности также прост:
1. Для каждого
нулевого набора переменных
(набора, где ункция
принимает значение 0) составить элементарную дизъюнкцию, в
которую переменная входит сама, если ее значение в наборе равно
0, или входит отрицание переменной, если ее значение в наборе
равно 1.
2. Составить конъюнкцию всех полученных элементарных дизъюнкций.
Пример 2. Представить в виде ормулы ункцию
f (x1; x2; x3; x4).
равную 1 тогда и только тогда, когда хотя бы 2 аргумента принимают
значение 0.
ешение. Всего
24 = 16 строк в таблице истинности ункции. Сколь-
ко в ней строк (наборов переменных), где есть хотя бы 2 нуля? Без
нулей 1 строка, а с 1 нулем 4 строки. Поэтому единичных наборов будет 11, и, следовательно, СДНФ будет содержать 11 слагаемых.
Нулевых наборов всего 5, а потому запись в виде СКНФ предпочтительна:
f (x1; x2; x3; x4) = (x1 _ x2 _ x3 _ x4)(x1 _ x2 _ x3 _ x4)(x1 _ x2 _ x3 _ x4)
(x1 _x2 _x3 _x4)(x1 _x2 _x3 _x4).
28
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
9
Полнота системы булевых ункций
Мы видели, что любая булева ункция может быть выражена в виде
ормулы через 3 элементарные ункции
x; x ^ y; x _ y. Система этих
3 ункций полна с точки зрения представления любой ункции.
f
g
Система булевых ункций f1 ; : : : ; f ; : : : называется ункционально полной (полной), если любая булева ункция может быть
представлена через ункции этой системы.
k
Таким образом полна вышеуказанная система 3 ункций: отрицания, конъюнкции и дизъюнкции. Другим примером (крайним) полной
системы является система
P2
всех булевых ункций. Какие есть еще
системы ункций, обладающих этим свойством? На этот вопрос ответ
может дать следующая теорема.
Теорема о полноте системы булевых ункций.
полная система булевых ункций
Пусть дана
F = ff1; f2; : : : g:
Если известно, что каждая ункция системы
ормулы через ункции другой системы
F
выражается в виде
G = fg1; g2; : : : g;
G также является полной.
Доказательство. Пусть p 2 P2 любая булева ункция. Тогда
p = A(f1; f2; : : : ):
По условию теоремы, f1 = A1 (g1 ; g2 ; : : : ); f2 = A2 (g1 ; g2 : : : ); : : : .
то система ункций
Поэтому
A(f1; f2; : : : ) = A( A1(g1; g2; : : : ); A2(g1; g2; : : : ); : : : ) = A (g1; g2; : : : ):
Таким образом, p = A (g1 ; g2 ; : : : ); т. е. любая булева ункция выражается через ункции системы G. Следовательно, G полна.
0
0
Как следствия теоремы представим следующие полные системы булевых ункций:
fx; x ^ yg является полной. Для этого достаточно показать, что все ункции полной системы fx; x ^ y; x _ y g выражаются
1. Система
через ункции этой системы. 2 ункции обеих систем совпадают.
Но, используя законы де Моргана, получаем
требовалось.
29
x _ y = x ^ y , что и
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
2. Система
fx; x _ yg является полной. Доказательство аналогично
предыдущему.
Мы видим, что полная система булевых ункций может содержать
всего 2 ункции. А может ли это число быть уменьшенным, т. е. существует ли полная система из одной ункции? На этот вопрос следует
положительный ответ: такими ункциями являются
штрих Шеера,
определяемый как отрицание конъюнкции (его обозначение вертикальная черта | между операндами), и
стрелка Пирса,
определяемая
как отрицание дизъюнкции (его обозначение вертикальная стрелка
вниз
# между операндами). Приведем таблицу истинности этих унк-
ций:
x y xjy x # y
0 0
1
1
0 1
1
0
1 0
1
0
1 1
0
0
Покажем, что система булевых ункций
fjg, которая включает толь-
ко штрих Шеера, является полной. Для этого достаточно согласно
теореме о полноте выразить ункции какой-либо полной системы через штрих Шеера. Возьмем в качестве такой систему, содержащую
отрицание и конъюнкцию. Так как
xjy = x ^ y, то xjx = x ^ x = x, и
отрицание выражено через штрих Шеера:
x = xjx:
Применив отрицание к обеим частям определения штриха Шеера,
а затем выразив отрицание через штрих Шеера, получим
x ^ y = xjy = (xjy)j(xjy):
Пример 1. Выразить через штрих Шеера дизъюнкцию:
x _ y = x ^ y = (xjy)j(xjy ) = ((xjx)j(yjy))j((xjx)j(yjy)) =
= ((xjx)j(yjy))j((xjx)j(yjy))j((xjx)j(yjy))j((xjx)j(yjy)):
Выражение громоздкое, но каждая операция только штрих Шеера.
30
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
ассмотрим еще одну часто используемую систему:
G = f1; 0; xy; x + y(mod2)g;
состоящую из двух констант, произведения и суммы по модулю 2 (остатка от деления суммы на 2). Формула, построенная из ункций этой
системы, после раскрытия скобок и алгебраических преобразований
переходит в многочлен по модулю 2, который называется
Жегалкина.
Полноту системы
полиномом
G обосновывает следующая теорема.
Каждая булева ункция может быть выражена единственным образом в виде полинома Жегалкина.
Теорема Жегалкина.
Доказательство. Любой полином Жегалкина выражается суммой по
X
модулю 2:
1
i ;:::;is
x 1 :::x :
i
is
i1 ;:::;is
При этом 0 выражается единственным образом все коэициенты
1
i ;:::;is
= 0,
эициенты
и потому 2 различных полинома имеют различные ко-
1
i ;:::;is
(иначе их разность будет равна 0, что противоре-
чит их различности). Число членов
x 1 :::x
равно числу подмножеств
fi1; : : : ; i g из n чисел 1; : : : ; n, т. е. 2 . Коэициенты i
is
n
s
потому число различных полиномов Жегалкина
22
n
i1 ;:::;is
2 0; 1, а
, т. е. столько же,
сколько существует булевых ункций. Значит, каждая булева ункция
имеет единственного представителя в виде многочлена Жегалкина, что
и требовалось доказать.
Пример 2. Выразить полиномом Жегалкина дизъюнкцию.
Запишем дизъюнкцию в виде полинома Жегалкина с неопределен-
x _ y = axy + bx + y + d.
При x = y = 0 : 0 = x _ y = d.
При x = 0; y = 1 : 1 = x _ y = + d = ) = 1.
При x = 1; y = 0 : 1 = x _ y = b + d = b ) b = 1.
При x = 1; y = 1 : 1 = x _ y = a + b + + d = a ) a = 1.
Таким образом x _ y = xy + x + y .
ными коэициентами:
Подобным образом можно получить ормулы для отрицания и конъюнкции
x = x + 1; x ^ y = xy.
31
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
10
Замкнутые классы булевых ункций и теорема
Поста о полноте
Приведенная в предыдущем разделе теорема о полноте не является достаточно конструктивной, так как для ее использования не ясно,
как в общем случае установить возможность выражения какой-либо
полной системы ункций через заданную. Если попытки не позволяют установить такое для какой-либо ункции полной системы, то не
ясно, возможно ли это может заданная система не является полной,
а может мы еще не проявили достаточного умения для этого. Поэтому
требуется критерий для установления является ли система полной или
нет, который бы проверялся просто. Такой критерий впервые был дан
замкнутого класса множеств.
Пусть F подмножество множества P2 булевых ункций.
Замыканием [F ? множества F булевых ункций называется множество ункций, которые могут быть представлены через ормулы, содержащие только ункции F .
Примерами замыканий являются весь класс булевых ункций: [P2 ? =
P2 и класс L = [ 0; 1; x + y (mod2) ? линейных ункций, которые могут
Э. Постом, и он использует понятие
f
g
быть представлены в виде
f (x1 : : : ; x ) = a0 + a1x1 + + a x (a
n
n
n
i
2 f0; 1g i 2 0; 1):
Свойства замыкания:
[F ? F:
2. [[F ?? = [F ?:
1.
3.
4.
F1 F2 ) [F1? [F2?:
[F1 [ F2? [F1? [ [F2?:
Класс F булевых ункций называется замкнутым, если [F ? = F .
Примерами замкнутых классов являются P2 ; L. Не является замкнутым множество
f0; 1; x + y(mod2)g. С помощью понятий замы-
кания и замкнутого класса можно дать другое определение полноты
системы булевых ункций.
F
полная система, если
[F ? = P2.
32
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Для ормулирования теоремы Поста о полноте системы булевых
ункций мы рассмотрим 5 замкнутых классов булевых ункций:
T0
класс булевых ункций,
сохраняющих 0,
т. е.
f (0; 0; : : : ; 0) = 0:
f0;
x; x ^ y; x _ y; x + yg T0 1; x 2= T0:
Так как на наборе из нулей значение ункций из T0 определены,
а на остальных наборах значений могут быть любые, то jT0 j =
Примеры:
22
n
1
= 12 22 , т. е. половина всех булевых ункций сохраняют 0.
n
T0. Пусть f; f1; : : : ; f
бой ункции f (f1; : : : ; f ) = :
Покажем замкнутость
m
2 T0. Тогда для лю-
m
(0; : : : ; 0) = f (f1(0; : : : ; 0); : : : ; f (o; : : : ; 0)) = f (0; : : : ; 0) = 0:
m
T1
класс всех булевых ункций,
сохраняющих 1,
т. е.
f (1; 1; : : : ; 1) = 1:
f1;
x; x ^ y; x _ yg T1 0; x; x + y 2= T1:
T1 состоит из ункций, двойственных классу T0. Поэтому будем
говорить T1 двойственно T0 .
Отсюда следует, что класс T1 также имеет половину всех булевых
Примеры:
ункций и тоже замкнут.
S класс самодвойственных
f.
булевых ункций, т. е.
f
2 S ) f =
fx; xg S x + y; x $ y 2= S . Нетривиальный пример:
h(x1; x2; x3) = x1x2 _ x2x3 _ x1x3 = (x1 _ x2)(x2 _ x3)(x1 _ x3) = h
Примеры:
также самодвойственная ункция.
Так как на противоположных наборах аргументов самодвойственная ункция принимает противоположное значение, то для опре-
p
jS j = 22 2 = 22 . Покажем замкнутость S . Пусть
деления самодвойственных ункций достаточно половины наборов. Поэтому
f; f1; : : : ; f
m
n
n
=
2 S . Тогда для любой ункции f (f1; : : : ; f ) = :
m
= f (f1; : : : ; f ) = f (f1; : : : ; f ) = f (f1; : : : ; f ) = :
m
m
33
m
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
M
класс
монотонных
ункций. Вводится отношение частичного
порядка для наборов аргументов:
~ = (1; : : : ; ) ~ = (1; : : : ; ) , 1 1; : : : ; Функция f называется монотонной (f 2 M ), если
n
n
n
:
n
~ ~
) f (~) f (~):
Примеры: f0; 1; x; x ^ y; x _ y g M
x + y; x ! y; x $ y 2= M .
Для доказательства замкнутости возьмем произвольные монотонные ункции
2 M и = f (f1; : : : ; f ), каждая из
f; f1; : : : ; f
n
m
которых определена соответственно на наборах аргументов
x = (x1; : : : ; x ); x = (x 1; : : : ; x ) (i
fi
n
i
ipi
2 1; m), причемSx со=1 x .
x и стоит из тех и только тех аргументов, которые входят в
m
fi
i
и два произвольных набора аргументов
. Они определяют значения и аргументов x (i 2 1; m)
такие, что . Из монотонности f1 ; : : : ; f
следует
f1( 1 ) f1( 1 ); : : : ; f1( ) f ( ). Поэтому
(f1( 1 ); : : : ; f ( )) (f1( 1 ); : : : ; f ( )) и в силу монотонности f :
f ( f1( 1 ); : : : ; f ( ) ) f ( f1( 1 ); : : : ; f ( ) ).
Отсюда ( ) ( ), что обосновывает монотонность и замкнутость M .
Пусть
fi
fi
f
fi
fi
fi
m
f
fm
f
fm
m
f
m
fm
m
f
m
fm
fm
f
m
fm
L класс линейных ункций.
Примеры: f0; 1; x; x; x + y g L xy; xjy 2
= L.
класса
L обоснована в предыдущем разделе.
Замкнутость
T0; T1; S; M; L попарно различны. Это показывает следующая таблица принадлежности ункций 0, 1 и x.
Классы
f T0 T1 S M L
0 +
1
+
x
+ +
+ +
+
+
Совершенно ясно, что полная система булевых ункций не может целиком принадлежать ни одному из этих пяти классов. Э. Пост доказал,
что это условие является не только необходимым, но и достаточным.
34
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
Теорема Поста о полноте (критерий полноты системы булевых
ункций).
Система ункций полна тогда и только тогда, когда она не содержится целиком ни в одном из 5 замкнутых классов T0; T1; S; M; L.
Пример 1. Является ли система ункций
fxy; 0; 1; x + y + zg пол-
ной? Является ли она замкнутой?
ешение. Составим таблицу истинности ункций системы, введя
для них по порядку обозначения
f1(x; y; z ) = xy; f2(x; y; z ) = 0; f3(x; y; z ) = 1; f4(x; y; z ) = x + y + z .
x y z f1 f2 f3 f4
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
T0
T1
S
M
L
0
1
0
1
0
1
0
1
0
0
0
0
0
0
1
1
+
+
0
0
0
0
0
0
0
0
+
0
1
1
0
1
0
0
1
+
+ +
+
+ + +
+ + +
Установление принадлежности классам
1
1
1
1
1
1
1
1
T0; T1; S; M
или не принад-
лежности им делается по самой таблице истинности непосредственно
T0; T1 нужно посмотреть соответственно на набор значений из нулей и набор значений из единиц; для S нужно перевернуть, инвертировать столбец и сравнить его с исходным, а для M нужно последо(для
вательно сравнить каждый единичный набор с каждым нулевым на
предмет монотонного порядка). Установление принадлежности
лается непосредственно для ункций 0, 1,
x+y+z
L
де-
из их вида, а то,
f1 не принадлежит L, делается попыткой выразить ее в линейном
виде ax + by + :
f1(0; 0) = 0 = ;
f1(0; 1) = 0 = b + = b;
что
35
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
f1(1; 0) = 0 = a + = a;
f1(1; 1) = 1 = a + b + = 0, что приводит к противоречию 1=0.
Мы установили, что f3 2
= T0; f2 2= T1; f1; f2; f3 2= S; f4 2= M; f1 2= L.
Поэтому выполнены условия критерия Поста (каждый из 5 классов не
содержит, по крайней мере, одну из ункций системы). Таким образом,
система
fxy; 0; 1; x + y + zg полна.
Из этого следует, что система не является замкнутой, так как с ее
помощью можно образовать любую булеву ункцию, не принадлежащую системе (например,
x_y
не принадлежит системе, так как ее
таблица истинности не тождественна таблицам истинности ни одной
из ункций системы).
система булевых ункций
не замкнута.
Ответ:
fxy; 0; 1; x + y + zg полна, но
Любая подсистема рассмотренной в примере системы ункций не
является уже полной, так как все ее ункции принадлежат одному из
базисом.
Система булевых ункций f1; f2 ; : : : из замкнутого класса F
называется полной в F , если [ f1; f2; : : : ? = F .
Система булевых ункций f1; f2; : : :
F называется базисом в
F , если она полна в F и никакая ее подсистема не полна в F .
Э. Пост установил, что каждый замкнутый класс из P2 имеет ко5 базовых замкнутых классов. Такая система называется
f
f
f
g
g
g
нечный базис не более, чем из четырех ункций. Минимальный базис
состоит из одной ункции (например, штрих Шеера для
для
[f ?).
Пример 2. Является ли система ункций
P2
или
f
fx; 0; 1; xg полной? Яв-
ляется ли она замкнутой?
ешение. Составим таблицу истинности ункций системы (см. ниже), введя для них по порядку обозначения
f1(x) = x; f2(x) = 0; f3(x) = 1; f4(x) = x. Установление принадлежности классам T0 ; T1 ; S; M или не принадлежности им делается по
самой таблице истинности непосредственно (для T0 ; T1 нужно посмотреть соответственно на набор значений из нулей и набор значений из
единиц; для
S
нужно перевернуть, инвертировать столбец и сравнить
его с исходным, а для
M нужно последовательно сравнить каждый еди-
ничный набор с каждым нулевым на предмет монотонного порядка).
36
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
L делается непосредственно для ункций x, 0, 1, а то, что x принадлежит L, делается попыткой выразить
ее в линейном виде ax + b:
f4(0) = 1 = ;
f4(1) = 0 = a + b = a + 1 ) a = 1, что приводит к линейному виду
ункции x = x + 1.
x f1 f2 f3 f4
Установление принадлежности
0 0 0
1 1 0
T0 + +
T1 +
S +
M + +
L + +
1 1
1 0
+
+
+
+ +
Мы установили, что все ункции системы принадлежат классу
L,
и потому, по теореме Поста, система не полна.
Так как существует всего 4 булевых ункции одного аргумента и
все они входят в систему, то она замкнута (никакими операциями не
удастся получить какую-либо другую ункцию).
Ответ:
та.
11
система булевых ункций
fx; 0; 1; xg не полна, но замкну-
Индивидуальное задание 5
1. Булеву ункцию, полученную в ходе решения задачи 1 задания
4 для равенства множеств, представить в следующих ормах (с обоснованием при помощи вывода и проверкой совпадения таблиц истинности):
1)
СДНФ;
2)
СКНФ;
3)
полином Жегалкина;
4)
ормулу, содержащую только штрих Шеера.
37
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
2. Установить, является ли заданная система булевых ункций полной и замкнутой. Обосновать подробно весь ход решения.
3. ешить комбинаторную задачу Каким числом способов можно
вынуть заданное число карт с заданными свойствами из полной колоды
в 52 карты?. Обосновать подробно весь ход решения.
11.1
Пример задачи 1 и ее решения
Для равенства множеств:
(X2 n X3) [ (X1 n X2) = X1 [ X 3
в задании 4 была получена следующая булева ункция:
G y2 ^ y3 _ y1 ^ y2
$ y1 _ y3:
В дальнейшем для большей наглядности знак операции конъюнкции
будем опускать, подразумевая его между любыми выражениями, написанными подряд, где не стоит знак другой бинарной операции.
G = y2y3 _ y1y2
$ y1 _ y3:
G:
y1y2y3 y2y3 y1y2 y2y3 _ y1y2 y1 _ y3 G = y2y3 _ y1y2
Составим таблицу истинности
0 0 0
0
0
0
1
0
0 0 1
0
0
0
0
1
0 1 0
1
0
1
1
1
0 1 1
0
0
0
0
1
1 0 0
0
1
1
1
1
1 0 1
0
1
1
1
1
1 1 0
1
0
1
1
1
1 1 1
0
0
0
1
0
$ y1 _ y3
В дальнейших выводах мы над знаками эквивалентности будем обязательно писать номера используемых при преобразовании равносильностей (см. далее Список равносильностей).
1) Выведем СДНФ.
22
G = y2y3 _ y1y2 $ y1 _ y3 (y2y3 _ y1y2 _ y1 _ y3)(y1 _ y3 _ y2y3 _ y1y2) 38
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
99
(y2y3 y1y2 _ y1 _ y3)(y1y3 _ y2y3 _ y1y2) 8 ((y2 _ y3)(y1 _ y2) _ y1 _ y3)(y1y3 _ y2y3 _ y1y2)
;
Преобразуем отдельно левый операнд полученной конъюнкции:
67
((y2 _ y3)(y1 _ y2) _ y1 _ y3) y2 y1 _ y2y2 _ y3y1 _ y3y2 _ y1 _ y3 15 12
y2 y1 _0_y3y1_y3y2_y1 _y31 1314 y2 y1_y3y1_y3y2_y1_y3(y1_y1) ;
;
;
36
y2 y1 _ y3y2 _ y1 _ y3y1 _ y3 y1 _ y3y1 6 y2 y1 _ y3y2 _ y1 _ (y3 _ y3)y1 _ y3y1 14 12
y2 y1 _ y3y2 _ y1 _ y1 _ y3y1 14 y2 y1 _ y3y2 _ 1 _ y3y1 17 1:
;
;
Поэтому
12
G = 1(y1y3 _ y2y3 _ y1y2) y1y3 _ y2y3 _ y1y2 12 y1y3(y2 _ y2) _ y2y3(y1 _ y1) _ y1y2(y3 _ y3) 6 y1y3y2 _ y1y3y2 _ y2y3y1 _ y2y3 y1 _ y1y2y3 _ y1y2 y3 3 y1 y2y3 _ y1 y2y3 _ y1y2y3 _ y1y2 y3 _ y1y2y3 _ y1y2y3;
что соответствует определению СДНФ по единичным наборам таблицы
истинности.
2) Определение СКНФ произведем по таблице истинности, образуя
для каждого нулевого набора элементарную дизъюнкцию, для которой
значению 0 переменной в наборе соответствует она сама, а значению
1 ее отрицание. После этого образуем конъюнкцию всех полученных
элементарных дизъюнкций. Получим:
(y1 _ y2 _ y3)(y1 _ y2 _ y3):
3) Для получения полинома Жегалкина возьмем в качестве начального выражения СКНФ (как более короткое выражение в данном
примере) и будем производить последовательную замену выражений
x = x + 1),
сначала с операциями отрицания (
затем с операциями
x _ y = x y + x + y) и, наконец, с операцией конъюнкции
(x ^ y = x y ). При этом будем раскрывать скобки и упрощать при
дизъюнкции (
помощи сложения (по модулю 2) подобных частей выражения:
y1 _ y2 = (y1 + 1) (y2 + 1) + (y1 + 1) + (y2 + 1) =
= y1 y2 + y1 + y2 + 1 + y1 + y2 + 1 + 1 = y1 y2 + 1
y1 _ y2 _ y3 = (y1 _ y2) _ y3 = (y1 y2 +1) (y3 +1)+(y1 y2 +1)+(y3 +1) =
= y1 y2 y3 + y1 y2 + y3 + 1 + y1 y2 + 1 + y3 + 1 = y1 y2 y3 + 1
39
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
y1 _ y2 = y1 y2 + y1 + y2
y1 _ y2 _ y3 = (y1 _ y2) _ y3 =
= (y1 y2 + y1 + y2) y3 + y1 y2 + y1 + y2 + y3 =
= y1 y2 y3 + y1 y3 + y2 y3 + y1 y2 + y1 + y2 + y3 =
= y1 y2 y3 + y1 y2 + y1 y3 + y2 y3 + y1 + y2 + y3
(y1 _ y2 _ y3) ^ (y1 _ y2 _ y3) =
= (y1 y2 y3 +1) (y1 y2 y3 + y1 y2 + y1 y3 + y2 y3 + y1 + y2 + y3) =
= y1 y2 y3 + y1 y2 y3 + y1 y2 y3 + y1 y2 + y1 y2 y3 + y1 y3 +
+ y1 y2 y3 + y2 y3 + y1 y2 y3 + y1 + y1 y2 y3 + y2 + y1 y2 y3 + y3 =
= y1 y2 + y1 y3 + y2 y3 + y1 + y2 + y3
Построим таблицу истинности A = y1 y2 + y1 y3 + y2 y3 + y1 + y2 + y3 :
y1y2y3 y1 y2 y1 y3 y2 y3 A
0 0 0
0
0
0
0
0 0 1
0
0
0
1
0 1 0
0
0
0
1
0 1 1
0
0
1
1
1 0 0
0
0
0
1
1 0 1
0
1
0
1
1 1 0
1
0
0
1
1 1 1
1
1
1
0
Одинаковость таблиц истинности для
G и A подтверждает, что вывод
сделан верно и
G = y1 y2 + y1 y3 + y2 y3 + y1 + y2 + y3:
4) Для получения ормулы, содержащей только штрих Шеера, произведем для данного примера сначала замену выражений с опе-
x = xjx), затем замену выражений с операциями
дизъюнкции (x _ y = (xjx)j(y jy )), и, наконец, замену выражений с операциями конъюнкции (x ^ x = (xjy )j(xjy )):
y1 _ y2 = y1 ^ y2 = y1jy2
рацией отрицания (
y1 _ y2 _ y3 = (y1 _ y2) _ y3 = (y1jy2) _ y3 = y1jy2 ^ y3 = ((y1jy2)j(y1jy2))jy3
y1 _ y2 = (y1jy1)j(y2jy2)
y1 _ y2 _ y3 = (y1 _ y2) _ y3 = (((y1jy1)j(y2jy2))j((y1jy1)j(y2jy2)))j(y3jy3)
40
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
(y1 _ y2 _ y3) ^ (y1 _ y2 _ y3) =
= (( (((y1jy2)j(y1jy2))jy3)j((((y1jy1)j(y2jy2))j((y1jy1)j(y2jy2)))j(y3jy3)) )j
j(( ((y1jy2)j(y1jy2))jy3)j((((y1jy1)j(y2jy2))j((y1jy1)j(y2jy2)))j(y3jy3)) ))
Для проверки правильности вывода построим таблицу истинности
выведенной ормулы. Для этого введем обозначения:
a y jy (i = 1; 2; 3); b y1jy2; bjb; d a1ja2 ; e djd;
f jy3 ; g eja3; h = f jg:
i
i
i
Тогда
(y1 _ y2 _ y3) ^ (y1 _ y2 _ y3) = hjh:
y1y2y3 a1 a2 a3 b d e f g h hjh
0 0 0
1
1
1
1
0
0
1
1
0
1
0
0 0 1
1
1
0
1
0
0
1
1
1
0
1
0 1 0
1
0
1
1
0
1
0
1
1
0
1
0 1 1
1
0
0
1
0
1
0
1
1
0
1
1 0 0
0
1
1
1
0
1
0
1
1
0
1
1 0 1
0
1
0
1
0
1
0
1
1
0
1
1 1 0
0
0
1
0
1
1
0
1
1
0
1
1 1 1
0
0
0
0
1
1
0
0
1
1
0
Одинаковость таблиц истинности для
G
и
hjh
подтверждает, что
вывод сделан верно и
G = (( (((y1jy2)j(y1jy2))jy3)j((((y1jy1)j(y2jy2))j((y1jy1)j(y2jy2)))j(y3jy3)) )j
j(( ((y1jy2)j(y1jy2))jy3)j((((y1jy1)j(y2jy2))j((y1jy1)j(y2jy2)))j(y3jy3)) )):
11.2
Варианты второй задачи индивидуального задания 5
fx ^ y; xg
2. f0; 1; x; y; x _ y g
3. fx ! y; xg
4. f0; 1; x; y; x ^ y g
5. fx + y; 1; x; x ! y g
6. fx; x; y; y g
1.
41
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
fy ! x; x ^ yg
8. fx; x; x + y; y; x $ y g
9. fx _ y; x ^ y g
10. f0; 1; x; xg
11. fx _ y; x ^ y g
12. fx; x _ y; x ! y; y ! xg
13. fx ! y; xg
14. f0; 1; x; y; x + y g
15. fx ! y; xg
16. f0; 1; x; y; x $ y g
17. fx + y; x $ y g
18. fx + y; x y g
19. f0; 1; x; y; x ^ y g
20. fx + y; 1; x; x ! y g
21. fy ! x; x ^ y g
22. fx; x + y; y; x $ y g
23. fx _ y; x ^ y g
24. fx; x _ y; x ! y; y ! xg
25. fx ! y; xg
26. fx ! y; xg
27. fx; x _ y; x ! y; y ! xg
28. fy ! x; x ^ y g
29. f0; 1; x; y; x ^ y g
30. f0; 1; x; y; x _ y g
7.
42
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
fx + y; x yg
32. fx + y; x $ y g
33. fx; x _ y; x ! y; y ! xg
34. f0; 1; x; y; x ^ y g
35. fx ! y; xg
36. fx _ y; x ^ y g
37. fx ^ y; xg
38. f0; 1; x; xg
39. fx; x; y; y g
40. fy ! x; x ^ y g
41. fx + y; 1; x; x ! y g
42. fx ! y; xg
43. fx; x; x + y; y; x $ y g
44. f0; 1; x; y; x $ y g
45. fx; x + y; y; x $ y g
46. fx _ y; x ^ y g
47. fx _ y; x ^ y g
48. fx ! y; xg
49. f0; 1; x; y; x + y g
50. fx + y; 1; x; x ! y g
51. fx ! y; 0; y g
31.
43
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
11.3
Варианты третьей задачи индивидуального задания 5
1. Каким числом способов можно из полной колоды в 52 карты выбрать покерную комбинацию 5 карт, содержащую 2 различных по
двойки (2 карты одинакового значения),
тройки (3 карты одинакового значения)?
значению
щую
но не содержа-
2. Каким числом способов можно из полной колоды в 52 карты выбрать покерную комбинацию 5 карт, содержащую 1
двойку
(2 кар-
ты одинакового значения), но не содержащую другой покерной
комбинации (остальные карты имеют другие различные значения)?
3. Каким числом способов можно из полной колоды в 52 карты выбрать покерную комбинацию 5 карт, содержащую
одинакового значения) и
тройку
двойку
(2 карты
(3 карты одинакового значения)?
4. Каким числом способов можно из полной колоды в 52 карты выбрать покерную комбинацию 5 карт, содержащую
каре
(4 карты
одинакового значения)?
5. Каким числом способов можно из полной колоды в 52 карты выбрать покерную комбинацию
стрит
(5 карт, значения которых
идут подряд; например, 8, 9, 10, В, Д)?
6. Каким числом способов можно из полной колоды в 52 карты выбрать покерную комбинацию
цвет
(5 карт одной масти)?
7. Каким числом способов можно из полной колоды в 52 карты выбрать 5 карт, содержащих все масти и 2 значения?
8. Каким числом способов можно из полной колоды в 52 карты выбрать 5 карт, содержащих 3 масти и 2 значения?
9. Каким числом способов можно из полной колоды в 52 карты выбрать 5 карт, содержащих 2 масти и 3 значения?
10. Каким числом способов можно из полной колоды в 52 карты выбрать 4 карты, содержащие 2 значения и не все масти?
11. Каким числом способов можно из полной колоды в 52 карты выбрать 6 карт, содержащих 3 масти и 3 значения?
44
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
12. Каким числом способов можно из полной колоды в 52 карты выбрать 6 карт, содержащих 2 масти и 4 значения?
13. Каким числом способов можно из полной колоды в 52 карты выбрать 7 карт, содержащих все масти и 3 значения?
14. Каким числом способов можно из полной колоды в 52 карты выбрать 7 карт, содержащих 3 масти и 3 значения?
15. Каким числом способов можно из полной колоды в 52 карты выбрать 7 карт, содержащих 2 масти и 5 значений?
16. Каким числом способов можно из полной колоды в 52 карты выбрать 7 карт, содержащих 5 различных значений и все масти?
17. Каким числом способов можно из полной колоды в 52 карты выбрать 7 карт, содержащих 4 различных значения и 3 масти?
18. Каким числом способов можно из полной колоды в 52 карты выбрать 7 карт, содержащих 5 различных значений и 2 масти?
19. Каким числом способов можно из полной колоды в 52 карты выбрать 7 карт, содержащих 5 различных значений и все масти?
20. Каким числом способов можно из полной колоды в 52 карты выбрать 6 карт, содержащих 4 различных значения и 3 масти?
21. Каким числом способов можно из полной колоды в 52 карты выбрать 6 карт, содержащих 3 различных значения и не все масти?
22. Каким числом способов можно из полной колоды в 52 карты выбрать 7 карт, содержащих 4 различных значения и 2 масти?
23. Каким числом способов можно из полной колоды в 52 карты выбрать 8 карт, содержащих 5 различных значений и 3 масти?
24. Каким числом способов можно из полной колоды в 52 карты выбрать покерную комбинацию 5 карт, содержащую красную
(2 красных карты одинакового значения) и
накового значения)?
45
тройку
двойку
(3 карты оди-
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
25. Каким числом способов можно из полной колоды в 52 карты выбрать покерную комбинацию черный
стрит
(5 карт черного цве-
та, значения которых идут подряд; например, 8, 9, 10, В, Д)?
26. Каким числом способов можно из полной колоды в 52 карты выбрать 7 карт, содержащих 3 масти и 3 значения?
27. Каким числом способов можно из полной колоды в 52 карты выбрать 6 карт, содержащих 4 различных значения и 3 масти?
28. Каким числом способов можно из полной колоды в 52 карты выбрать покерную комбинацию 5 карт, содержащую 1
двойку
(2 кар-
ты одинакового значения), но не содержащую другой покерной
комбинации (остальные карты имеют другие различные значения)?
29. Каким числом способов можно из полной колоды в 52 карты выбрать 5 карт, содержащих все масти?
30. Каким числом способов можно из полной колоды в 52 карты выбрать 7 карт, содержащих 4 различных значения и 2 масти?
31. Каким числом способов можно из полной колоды в 52 карты выбрать покерную комбинацию 5 карт, содержащую
каре
(4 карты
одинакового значения)?
32. Каким числом способов можно из полной колоды в 52 карты выбрать 6 карт, содержащих 3 масти и 3 значения?
33. Каким числом способов можно из полной колоды в 52 карты выбрать 7 карт, содержащих 5 различных значений и все масти?
34. Каким числом способов можно из полной колоды в 52 карты выбрать покерную комбинацию
стрит
(5 карт, значения которых
идут подряд; например, 8, 9, 10, В, Д)?
35. Каким числом способов можно из полной колоды в 52 карты выбрать 5 карт, содержащих 3 масти и 2 значения?
36. Каким числом способов можно из полной колоды в 52 карты выбрать покерную комбинацию 5 карт, содержащую красную
46
двойку
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
(2 красных карты одинакового значения) и
тройку
(3 карты оди-
накового значения)?
37. Каким числом способов можно из полной колоды в 52 карты выбрать 7 карт, содержащих 4 различных значения и 2 масти?
38. Каким числом способов можно из полной колоды в 52 карты выбрать 8 карт, содержащих 5 различных значений всех мастей?
39. Каким числом способов можно из полной колоды в 52 карты выбрать 5 карт, содержащих 2 масти и 3 значения?
40. Каким числом способов можно из полной колоды в 52 карты выбрать покерную комбинацию черный
стрит
(5 карт черного цве-
та, значения которых идут подряд; например, 8, 9, 10, В, Д)?
41. Каким числом способов можно из полной колоды в 52 карты выбрать 7 карт, содержащих все масти и 3 значения?
42. Каким числом способов можно из полной колоды в 52 карты выбрать покерную комбинацию 5 карт, содержащую 2 различных по
двойки (2 карты одинакового значения),
тройки (3 карты одинакового значения)?
значению
щую
но не содержа-
43. Каким числом способов можно из полной колоды в 52 карты выбрать покерную комбинацию 5 карт, содержащую
одинакового значения) и
тройку
двойку
(2 карты
(3 карты одинакового значения)?
44. Каким числом способов можно из полной колоды в 52 карты выбрать 8 карт, содержащих 5 различных значений и 3 масти?
45. Каким числом способов можно из полной колоды в 52 карты выбрать 6 карт, содержащих все масти и 3 значения?
46. Каким числом способов можно из полной колоды в 52 карты выбрать 7 карт, содержащих 2 масти и 5 значений?
47. Каким числом способов можно из полной колоды в 52 карты выбрать 6 карт, содержащих 4 различных значения и 2 масти?
48. Каким числом способов можно из полной колоды в 52 карты выбрать покерную комбинацию
цвет
47
(5 карт одной масти)?
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
49. Каким числом способов можно из полной колоды в 52 карты выбрать 7 карт, содержащих 4 различных значения и 3 масти?
50. Каким числом способов можно из полной колоды в 52 карты выбрать 6 карт, содержащих 3 масти и 5 значений?
51. Каким числом способов можно из полной колоды в 52 карты выбрать 8 карт, содержащих 2 масти и 5 значений?
Учебное издание
ублев Вадим Сергеевич
БУЛЕВЫ ФУНКЦИИ
(индивидуальные работы ќ 4 и 5 по дисциплине
ѕОсновы дискретной математикиї)
Методические указания
едактор, корректор И. В. Бунакова
Компьютерная верстка В. С. ублева
Подписано в печать 25.05.2009 г. Формат 60
84/16.
Усл. печ. л. 2,79. Уч.-изд. л. 2,1. Тираж 80 экз. Заказ
Оригинал-макет подготовлен
в редакционно-издательском отделе ЯрУ.
Отпечатано на ризограе.
Ярославский государственный университет
150000 Ярославль, ул. Советская, 14.
колько 6-значных чисел можно составить из цир числа 275453284?
43. Сколько 4-значных чисел можно составить из цир числа 754235248?
44. Сколько 6-значных чисел можно составить из цир числа 243342517?
45. Сколько 7-значных чисел можно составить из цир числа 433542172?
46. Сколько 5-значных чисел можно составить из цир числа 353124274?
47. Сколько 4-значных чисел можно составить из цир числа 531422753?
48. Сколько 7-значных чисел можно составить из цир числа 857531222?
49. Сколько 5-значных чисел можно составить из цир числа 573221258?
50. Сколько 6-значных чисел можно составить из цир числа 732122585?
51. Сколько 5-значных чисел можно составить из цир числа 832122585?
7
Двойственные булевы ункции и принцип двойственности
f (x1; : : : ; x ) = f (x1; : : : ; x ) называется двойственной к
ункции f (x1; : : : ; x ).
Заметим, что отрицание f в этом определении означает, что в табФункция
n
n
n
лице истинности все значения ункции инвертируются (нули заменяются единицами, единицы нулями). Отрицание каждого аргумента
x (i = 1; : : : ; x )
i
n
означает, что мы переходим к противоположному
набору аргументов. При лексикограическом упорядочивании наборов
аргументов в таблице истинности противоположные наборы симметричны относительно их середины. Поэтому верен следующий способ
получения по таблице истинности какой-либо булевой ункции таблицы истинности для ее двойственной ункции:
инвертировать столбец ункции;
22
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
перевернуть столбец.
Эти действия можно выполнять в любом порядке. Например, в следующей таблице истинности приведена одна из булевых ункции с 3-мя
аргументами и ее двойственная ункция, полученная описанными действиями (инвертирование и переворот столбца).
x y z f f
0 0 0
1
1
0 0 1
0
0
0 1 0
1
1
0 1 1
1
0
1 0 0
1
0
1 0 1
0
0
1 1 0
1
1
1 1 1
0
0
Нетрудно видеть, что ункция, двойственная к двойственной ункции, является исходной ункцией, т. е.
f = (f ) = f . В самом деле, в
таблице истинности нужно дважды инвертировать и дважды перевернуть столбец, что приведет к таблице истинности исходной ункции.
Поэтому на парах булевых ункций определяется
симметричное от-
ношение двойственности. Так, ункция 0 двойственна к ункции 1, и,
наоборот, ункция 1 двойственна к ункции 0. Функции конъюнкции
и дизъюнкции двойственны друг другу. Взаимодвойственными являются ункции эквиваленции и исключающей дизъюнкции (сложения
по модулю 2).
Булева ункция, двойственная сама себе, называется
самодвойствен-
x, тождественная ункция x или ункция, выраженная ормулой: xy _ xy .
ной.
Таковы, например, ункция отрицания
как по ормуле булевой ункции получить ормулу двойственной ункции, которая называется
двойственной ормулой. Следующая теорема двойственности отвеПоследний пример приводит к задаче:
чает на этот вопрос.
Теорема двойственности.
Для любой ормулы булевой ункции
(x1; : : : ; x ) = f ( f1(x11; : : : ; x1 ); : : : ; f (x 1; : : : ; x
p1
n
23
m
m
mpm
) );
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
где
[
fx1; : : : ; x g = fx 1; : : : ; x g;
m
n
i
ipi
=1
двойственная ункция выражается ормулой
i
(x1; : : : ; x ) = f ( f1(x11; : : : ; x1 ); : : : ; f (x 1; : : : ; x
p1
n
m
m
mpm
) );
полученной заменой ункций, входящих в суперпозицию исходной ункции, на двойственные к ним.
Доказательство.
(x1; : : : ; x
) = (x1; : : : ; x ) =
= f ( f1(x11; : : : ; x1 ); : : : ; f (x 1; : : : ; x ) ) =
= f ( f1(x11; : : : ; x1 ); : : : ; f (x 1; : : : ; x ) ) =
= f ( f1(x11; : : : ; x1 ); : : : ; f (x 1; : : : ; x ) ) =
= f ( f1(x11; : : : ; x1 ); : : : ; f (x 1; : : : ; x ) ):
n
n
p1
m
m
mpm
p1
m
m
mpm
p1
m
m
mpm
p1
m
m
mpm
Из теоремы двойственности следует принцип двойственности:
Для любой ормулы A(f1; : : : ; f ) двойственная к ней ормула получается заменой всех входящих в нее ункций на двойственные, т. е.
s
A(f1; : : : ; f ).
s
Таким образом, для получения двойственной ормулы необходимо
^ на _, _ на ^ и т.д. Например, для ормулы
x _ y ^ z получаем двойственную ормулу x ^ (y _ z ).
заменить 0 на 1, 1 на 0,
Из принципа двойственности следует:
Теорема о равносильности двойственных ормул.
B равносильные ормулы, то ормулы A
Например, из первого закона де Моргана
второй закон де Моргана
x _ y = x ^ y.
Если
Aи
и B также равносильны.
x^y = x _ y
вытекает
Другой пример: какая ормула двойственна для импликации
A!
B ? Двойственная ормула выражается как A ! B . Как ее упростить?
Проще использовать равносильную ормулу A _ B для импликации.
Тогда двойственная для нее ормула A ^ B , т. е. A ! B = A ^ B . Таким
образом, принцип двойственности позволяет сократить тождественные
преобразования.
24
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
8
еализация булевой ункции ормулой
Каждая ормула высказываний представляет собой некоторую бу-
леву ункцию. Используя равносильности ормул, можно преобразовывать ормулы. Некоторые из видов ормул имеют специальное название
ормы. К
ним прежде всего относятся дизъюнктивно-нормаль-
ная орма (ДНФ) и
конъюнктивно-нормальная орма
(КНФ). Обе
ормы являются ормулами, содержащими только 3 операции из рассмотренных 5: отрицание, конъюнкцию и дизъюнкцию. Для их определения введем понятия
элементарной конъюнкции
и
элементарной
дизъюнкции.
Элементарной конъюнкцией называется конъюнкция переменных,
входящих в ормулу, или их отрицаний. При этом каждая переменная
входит в ормулу элементарной конъюнкции не более 1 раза. Напри-
x ^ y ^ z и y являются элементарными конъюнкциями,
а ормула x ^ y _ z не является таковой.
мер, ормулы
Элементарной дизъюнкцией называется дизъюнкция переменных,
входящих в ормулу, или их отрицаний. При этом каждая переменная
входит в ормулу элементарной конъюнкции не более 1 раза. Напри-
x _ y _ z и y являются элементарными дизъюнкциями,
а ормула x _ y ^ z не является таковой.
мер, ормулы
Дизъюнктивно-нормальной ормой называется дизъюнкция элементарных конъюнкций. Например, ормулы xyz x y и xy являются
ДНФ, а ормула
xy таковой не является.
_
Конъюнктивно-нормальной ормой называется конъюнкция элементарных дизъюнкций. Например, ормулы xyz (x y ) и x y
являются КНФ, а ормула
xy таковой не является.
^
_
_
Можно ли любую булеву ункцию представить ормулой? Можно
ли любую ормулу привести эквивалентными преобразованиями (равносильностями) к ДНФ или к КНФ? Мы дадим положительный ответ
на эти вопросы и покажем, как это сделать.
Введем обозначение:
x =
vi
i
x ; v = 1;
x ; v = 0:
i
i
i
i
25
Copyright ??? «??? «??????» & ??? «A???????? K????-C?????»
а?
Документ
Категория
Без категории
Просмотров
4
Размер файла
353 Кб
Теги
булева, функции, рублев
1/--страниц
Пожаловаться на содержимое документа