Практическая  работа 

по предмету по предмету «Элементы математической логики»

Преподаватель Сипачева О.И.

Тема: Классы Поста.

Цель работы: знать определения классов Поста, теорему о функциональной полноте системы булевых функций, уметь  определять к какому классу Поста относится данная булева функция.

Ход работы.

1.        Изучить теоретические сведения к практической работе.

2.        Ответить на контрольные вопросы.

3.        Выполнить задание.

4.        Отчитаться  о проделанной работе.

 1. Краткие теоретические сведения и разобрать задачи с решениями. 

.

Американский математик Эмиль Пост ввёл в рассмотрение следующие замкнутые классы булевых функций:

Функции, сохраняющие константу 0 или 1;

Самодвойственные функции; Монотонные функции; Линейные функция.

Заметим, что существуют функции, не входящие ни в один из классов Поста. Любая такая функция сама по себе образует полную систему. В качестве примеров можно назвать штрих Шеффера или стрелку Пирса. для того чтобы записать полную систему функций надо проверить имеющиеся функции по всем яти классам Поста, а уже недостающую функцию записать исходя из теоремы "чтобы система булевых функций была полной, надо, чтобы в ней существовали:

-Хотя бы одна функция, не сохраняющая 0.

-Хотя бы одна функция, не сохраняющая 1.

-Хотя бы одна нелинейная функция.

-Хотя бы одна немонотонная функция.

-Хотя бы одна несамодвойственная функция.

 Важнейшие замкнутые классы

            Класс функций, сохраняющих константу 0

 Обозначим через T₀ класс всех булевых функций f(x₁,x₂,...,x_n), сохраняющих константу 0, то есть функций, для которых выполнено равенство f(0,0,...,0)=0. Очевидно,

что функции 0, x, x₁ x₂, x₁ x₂, x₁ x₂ принадлежат классу T₀, а функции 1, x , x₁ x₂ в него не входят.

 Поскольку таблица для функций f(x₁,x₂,...,x_n) из класса T₀ в первой строке содержит фиксированное значение 0, то в T₀ попадает 22^n1  1  22ⁿ функций, т.е. ровно 2

половина всех булевых функций.

 Покажем, что T₀ - замкнутый класс. Так как он содержит тождественную функцию, то для обоснования его замкнутости достаточно показать, что функция Ф=f(f₁,...,f_m) принадлежит классу T₀, если только f, f₁,..., f_m  принадлежат этому классу.  Ф(0,0,...,0)= f(f₁(0,0,...,0),...,f_m(0,0,...,0))= f(0,0,...,0)=0.

         Класс функций, сохраняющих константу 1

 Обозначим через T₁ класс всех булевых функций f(x₁,x₂,...,x_n), сохраняющих константу 1, то есть функций, для которых выполнено равенство f(1,1,...,1)=1. Этому

классу принадлежат функции 1, x, x₁ x₂, x₁ x₂, x₁ x₂ и не принадлежат функции 1, x , x₁x₂.

 Покажем, что класс T₁ состоит из функций, двойственных функциям из класса T₀ (говорят, что класс T₁ двойственен классу T₀).

             Пусть f(x₁,x₂,...,x_n) принадлежит T₁, т.е. выполняется равенство f(1,1,...,1)=1. Тогда,

воспользовавшись определением двойственной функции, получим:  f*(0,0,...,0)= f (0,0

,...,0)= f (1,1,...,1)=0. Это значит, что f*(x₁,x₂,...,x_n) принадлежит классу T₀.

         Из взаимной двойственности классов T₀ и T₁ следует, что T₁ также является замкнутым классом и что он содержит столько же булевых функций, что и класс T₀.

              Класс самодвойственных функций 

 Класс S включает в себя  все самодвойственные функции, то есть такие функции, для которых выполняется равенство: f(x₁,x₂,...,x_n)=f*(x₁,x₂,...,x_n). Очевидно, что функции x и

x самодвойственные (см. табл. 1.7). Менее тривиальным примером самодвойственной функции является функция h(x₁,x₂,x₃)=x₁x₂  x₁x₃  x₂x₃. Покажем, что это действительно так.

 Составим двойственную к h функцию h* и преобразуем ее:  h*(x₁,x₂,x₃) = (x₁x₂) & (x₁x₃) & (x₂x₃) = (x₁x₂x₃) & (x₂x₃) = x₁x₂  x₁x₃  x₂x₃ = h(x₁,x₂,x₃).

                                                                                                                                                                                                         

                                 Для самодвойственной функции имеет место тождество: f (^x₁,...,^x_n) 

f(x₁,...,x_n); иначе говоря, на наборах (₁,...,_n) и (^₁, ... ,^_n) , которые называются противоположными, самодвойственная функция принимает противоположные значения.  Отсюда следует, что самодвойственная функция полностью определяется своими

1 ⁿ

значениями на первой половине строк, которых для n переменных будет        2 . Поэтому 2

число     самодвойственных     функций,     зависящих     от     переменных     x₁,...,x_n,     равно

1 n

_2   ²n 2²  2 .

 Докажем, что класс S замкнут. Поскольку он содержит тождественную функцию, достаточно показать, что функция Ф=f(f₁,...,f_m) является самодвойственной, если функции f, f₁,..., f_m самодвойственны. Последнее устанавливается непосредственно:   Ф*= f*(f₁*,...,f_m*)= f*(f₁,...,f_m)= f(f₁,...,f_m)= Ф. Класс монотонных функций 

 Для двух наборов ~ =(₁,...,_n)  и ~ =(₁,..., _n),  выполнено отношение предшествования ~p~ , если ₁₁, ..., _n_n и хотя бы в  одной координате  i  выполнено условие _i < _i.

             Пример. (0, 1, 0, 1) p (1, 1, 0, 1), а наборы  (0, 1) и (1, 0) не сравнимы. 

 Очевидно, что отношение предшествования рефлексивно, антисимметрично, транзитивно и представляет собой, таким образом, отношение частичного порядка на множестве Bⁿ=BB...B.

 Функция f(x₁,...,x_n) называется монотонной, если для любых двух наборов ~ и ~ таких, что ~p~ , имеет место неравенство: f(~ )f(_~ ).

Например, функции 0, 1, x, x₁x₂, x₁ x₂ монотонные, а функции x , x₁ x₂, x₁x₂ монотонными не являются.

 Обозначим через M множество всех монотонных функций. Покажем, что класс монотонных функций замкнут. Поскольку тождественная функция принадлежит множеству M, то достаточно показать, что функция Ф=f(f₁,...,f_m)  является монотонной, если функции f, f₁,..., f_m монотонны.

        Пусть _~ и _~ - два набора длины n значений переменных x₁,...,x_n, причем _^~p_~ .

Так как  функции f₁,..., f_m монотонны, то выполняются соотношения f_i(^~ )f_i(~ ) при 1  i

 m, , поэтому набор (f₁(_~ ),..., f_m(_~ )) предшествует набору (f₁(_~ ),..., f_m(_~ )) или эти наборы равны.

            В обоих случаях в силу монотонности функции f справедливо неравенство:

f (f₁(_^~ ),..., f_m(_^~ ))   f (f₁(_^~ ),..., f_m(_^~ )), 

откуда следует, что Ф (~ )   Ф (~ ), т.е. Ф - функция монотонная. 

                                                                                                                                                                                                     

           Наборы ~ и _~ называются соседними по i-й координате, если 

~ =(₁,..., _i-1, _i, _i+1,... _n), ~ = (₁,..., _i-1, _i , _i+1,... _n).

Класс L линейных функций 

 Он содержит функции 0, 1, x, x , x₁x₂ и не содержит функций x₁x₂ и x₁ x₂. Выше было показано, что этот класс также замкнут. 

 Таблица 1 не содержит двух одинаковых столбцов. Это  хорошо иллюстрирует тот факт, что замкнутые классы T₀, T₁, S, M и L попарно различны (знак “+” здесь показывает, что функция содержится в классе, а “-” обозначает обратную ситуацию).

Таблица 1

Система функций {f₁, f₂,..., f_k} называется функционально полной, если любая булева функция может быть записана в виде формулы через функции этой системы.

Теорема Поста — одна из центральных теорем в теории булевых функций, устанавливающая необходимое и достаточное условие для того, чтобы некоторый набор булевых функций обладал достаточной выразительностью, чтобы представить любую булеву функцию. Впервые сформулирована  американским математиком Эмилем Постом Теорема о функциональной полноте. Для того, чтобы система функций P была полной, необходимо и достаточно, чтобы она целиком не содержалась ни в одном из пяти замкнутых классов T₀, T₁, S, M и L.

Каждая функция из P₂ может быть выражена при помощи полинома по модулю 2.

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

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

            Пример.                         x | y = xy = x& y = (xy) x ~ y...

Следовательно, множество всех формул можно разбить на классы эквивалентности таким образом, что все формулы, входящие в один класс, соответствуют одной и той же булевой функции; поэтому если функции, соответствующие некоторым формулам, равны, то сами эти формулы называют эквивалентными. Запись = означет, что формулы  и   эквивалентны.

2.Контрольные вопросы.

1.     Какие существуют классы Поста?

2.     Определения функций, принадлежащих различным классам Поста.

3.     Формулировка теоремы о функциональной полноте системы булевых функций

3.Задания.

Определить к каким классам Поста относятся булевы функции:

1в.

1.x y   x z 

2. z x z (yx)

     2в.  

1.      x y z   

2.      z  y      z       x

    3в 

1.     x y z 

2.     z   y     z x

    4в. 

1.z  y   z  x

2. z  y z    x

5в

1 . x yzx

2. z  y  z  x

6в

1 . x yzy

2. (x y)x z 

    7в. 

1.   (x y)x z

2.   z  y z (yx)

         8в. 

1.  zxyx

2.z x z (yx)

     9в 

1. x y z

3. x yzx

   10в. 

1. xyzx 3. x y z

     11в. 

1.   x y z  

2.   (x y)x z

12в.

1.zxyx^

2. z y z (yx)

13в.

1.   xyz x

2.   z  y z (yx)

      14в 

1. x y   x z

2. z  y z (zx)

15в 

1.   (x y)x z

2.   z y  z(yx)

4.Отчет.

1. Тема. 2. Цель.

3.   Ответ на контрольные вопросы.

4.   Практическое задание.

Критерии оценивания практической работы. 

      За полностью выполненную практическую работу ставится «зачет». Если какие-либо задания не выполнены или выполнены неверно, то студент получает от преподавателя указания для выполнения этих заданий.