Математика. Раздел 1. Дискретная математика. Тетрадь 1.2. Казанцев Э.Ф. - 45 стр.

UptoLike

ВУЗ: 

МУМ | Москва

Составители: 

Рубрика: 

Не труд но за ме тить, что СДНФ функ ции f со дер жит ров но столь -
ко конъ юнк ций, сколь ко еди ниц в таб ли це ис тин но сти для f . Та ким
об ра зом, су ще ст ву ет вза им но — од но знач ное со от вет ст вие ме ж ду таб -
ли цей функ ции f(x
1
… x
n
) и ее СДНФ. Сле до ва тель но, как мы уже ви де -
ли ра нее, СДНФ для вся кой ло ги че ской функ ции един ст вен на.
При мер: функ ция, за дан ная таб ли цей 1.5.8 име ет сле дую щую
СДНФ:
( & & ) ( & & ) ( & & ) ( & & )x x x x x x x x x x x x
1
2 3
1
2 3
1
2 3
1
2 3
Ú Ú Ú
.
Ал геб ра
( ; ;&; )P
2
Ú Ø
, ос нов ным мно же ст вом ко то рой яв ля ет ся
мно же ст во ло ги че ских функ ций, а опе ра ция ми — дизъ юнк ция, конъ -
юнк ция и от ри ца ние, на зы ва ет ся бу ле вой ал геб рой ло ги че ских функ -
ций. Фак ти че ски мы име ем де ло не с са ми ми функ ция ми, а с пред став -
ляю щи ми их фор му ла ми, то есть с ал геб рой фор мул, ко то рых го раз до
боль ше, чем функций (каждую функцию представляет бесконечное
число формул).
Та ким об ра зом, ло ги че скую функ цию мож но за дать дву мя спо со -
ба ми: таб лич ным и фор муль ным. Таб лич ный спо соб уни вер са лен,
един ст ве нен, но гро моз док. Фор му ла бо лее ком пакт на, но за да ет функ -
цию че рез ком по зи цию дру гих функ ций. Воз ни ка ет во прос, вся кая ли
ло ги че ская функ ция пред ста ви ма фор му лой. Для бу ле вой сис те мы
функ ций S
0
= {&, Ú, Ø} — та кая фор му ла су ще ст ву ет — это СДНФ, зна -
чит она функ цио наль но пол на. Как ре ша ет ся этот во прос для про из -
воль ной сис те мы функ ции S? Этот во прос ре ша ет ся с по мо щью по ня -
тий пол но ты и замк ну то сти функ ций.
Сис те ма функ ций S на зы ва ет ся функ цио наль но пол ной сис те мой,
ес ли лю бая ло ги че ская функ ция мо жет быть пред став ле на фор му лой,
т.е. яв ля ет ся су пер по зи ци ей функ ций из сис те мы S.
а) сис те ма S
0
= {&, Ú, Ø} функ цио наль но пол на;
б) сис те мы S
1
= {&, Ø} и S
2
= {Ú, Ø} так же функ цио наль но пол ны.
Дей ст ви тель но, из за ко нов де Мор га на и двой но го от ри ца ния сле ду ет,
что в ка ж дой из этих двух сис тем, не дос таю щая до S
0
функ ция вы ра жа -
ет ся че рез ос таль ные две:
x x x x
1
2
1
2
Ú = &
;
x x x x
1
2
1
2
& = Ú
.
На при мер, бу ле ва фор му ла
x x x x
1
2 2 3 4
Ú Ú( )
в сис те ме S
1
пе рей дет в
фор му лу:
x x x x x
1
2 2 3 4
× × × ×
, в сис те ме S
2
— в фор му лу
x x x x x
1
2 2 3 4
Ú Ú Ú Ú
.
45
      Нетрудно заметить, что СДНФ функции f содержит ровно столь-
ко конъюнкций, сколько единиц в таблице истинности для f . Таким
образом, существует взаимно — однозначное соответствие между таб-
лицей функции f(x1 … xn) и ее СДНФ. Следовательно, как мы уже виде-
ли ранее, СДНФ для всякой логической функции единственна.
      Пример: функция, заданная таблицей 1.5.8 имеет следующую
СДНФ:

         ( x 1 & x 2 & x 3 ) Ú ( x 1 & x 2 & x 3 ) Ú ( x 1 & x 2 & x 3 ) Ú ( x 1 & x 2 & x 3 ).

       Алгебра (P2 ; Ú ; &; Ø), основным множеством которой является
множество логических функций, а операциями — дизъюнкция, конъ-
юнкция и отрицание, называется булевой алгеброй логических функ-
ций. Фактически мы имеем дело не с самими функциями, а с представ-
ляющими их формулами, то есть с алгеброй формул, которых гораздо
больше, чем функций (каждую функцию представляет бесконечное
число формул).
       Таким образом, логическую функцию можно задать двумя спосо-
бами: табличным и формульным. Табличный способ универсален,
единственен, но громоздок. Формула более компактна, но задает функ-
цию через композицию других функций. Возникает вопрос, всякая ли
логическая функция представима формулой. Для булевой системы
функций S0 = {&, Ú, Ø} — такая формула существует — это СДНФ, зна-
чит она функционально полна. Как решается этот вопрос для произ-
вольной системы функции S? Этот вопрос решается с помощью поня-
тий полноты и замкнутости функций.
       Система функций S называется функционально полной системой,
если любая логическая функция может быть представлена формулой,
т.е. является суперпозицией функций из системы S.

       а) система S0 = {&, Ú, Ø} функционально полна;

      б) системы S1 = {&, Ø} и S2 = {Ú, Ø} также функционально полны.
Действительно, из законов де Моргана и двойного отрицания следует,
что в каждой из этих двух систем, недостающая до S0 функция выража-
ется через остальные две: x 1 Ú x 2 = x 1 & x 2 ; x 1 & x 2 = x 1 Ú x 2 .
       Например, булева формула x 1 x 2 Ú x 2 ( x 3 Ú 4 ) в системе S1 перейдет в
формулу: x 1 × x 2 × x 2 × x 3 × x 4 , в системе S2 — в формулу x 1 Ú x 2 Ú x 2 Ú x 3 Ú x 4 .

                                                                                                  45

Страницы