Анықтама. Егер £ шарты орындалатын кез-келген және жинақтары үшін f ( )£f ( ) теңсіздігі орындалса, онда     f (х₁,...,х_п) функциясы монотонды деп аталады.

     М арқылы барлық монотонды функциялар жиынын белгілейік. 0,1, х, x₁ & х₂, х₁ v х₂ Î М. М сыныбы тұйық.

     5. L - барлық сызықты функциялар сыныбы.

     0,1,x, ,x₁Åx₂ÎL ,x₁&x₂, х₁ v х₂ÏL. L сыныбы тұйық.

     Алгебра логикасының негізгі есептерінің бірі- толықтылықтың қажетті және жеткілікті шарттарын қарастырайық.

     Айталық G={f₁,f₂,..,f₅,...} - Р₂ жиынындағы кез-келген функциялар жүйесі болсын.

     Осы жүйенің толықтылығын калай анықтауға  болатынына келесі теорема береді.

     Теорема (функционалды толықтық туралы).

     G функциялар жүйесі толық болуы үшін оның келесі бес тұйық сыныптың T₀,T₁,S,M және L бірде біреуінде толығымен   жатпауы   қажетті де жеткілікті. 

     8.Пост нәтижелері

     Р₂ жиынындағы тұйық сыныптарды американ математигі Э. Пост терең зерттеген. Ол Р₂ жиынындағы барлық түйық сыныптардың құрылымы сипатталған.

     Анықтама. М тұйық сыныбындағы {f₁,f₂,…,f_s,…} функциялар жүйесі толық деп аталады, егер оның тұйықтауы М сыныбымен беттеседі.

     Басқаша айтқанда, егер М сыныбындағы әрбір  функция берілген жиынның функциялары аркылы формула түрінде өрнектеле алса, онда М жиыны толық.

     Анықтама. Егер ол  М сыныбында толық , ал оның кез-келген өзіндік ішжиыны     М сыныбында толық болмаса, онда М тұйық сыныбындағы функциялар жүйесі {f₁,f₂,...,f_s,...} оньщ базисі деп аталады. Мысалдар.

     1)f₁=x₁x₂, f₂=0, f₃=1, f₄=x₁Åx₂Åx₃  функциялар жүйесі Р₂  жиынының базисі боып табылады. Дәлелдеу:

       { x₁x₂,0,1,x₁Åx₂Åx₃}- Р₂ жиынында толық.

     { x₁x₂,0,1}- Р₂ жиынында толық емес.

     2)  {0,1,x₁&x₂, х₁ v х₂} функциялар жүйесі М сыныбының базисі болып табылады.

     1 Пост теоремасы. Р₂ жиынындағы әрбір тұйық сынып ақырлы базиске ие.

     2 Пост теоремасы. Р₂ жиынындағы тұйық сыныптар жиынындағы қуаты санаулы.

    Буль  функцияларының жалған және елеулі айнымалылары

     Анықтама. Егер і-ші құрамдас бөлік бойынша көршілес және жинақтары табылатын болса, онда f (x₁,…,x_i-1,x_i,x_i+1,…,x_n) функциясының x_i (1£i£n) айнымалысы елеулі деп аталады (яғни

f ( )¹f ( ) қатынасы орындалатындай =(a₁,...,a_i-1,0,a_i+1,…,a_n) және =(a₁,...,a_i-1,1,a_i+1,…,a_n)  табылса). Кері жағдайда x_i (1£i£n) айнымалысы f (x₁,…,x_i-1,x_i,x_i+1,…,x_n) функциясының жалған айнымалысы деп аталады.

      Анықтама. Егер f ( ) және g( ) функциялардың маңызды айнымалылар жиыны бетессе және кез келген және  жинақтарда функциялардың мәндері бірдей болса:

f ( )=g( ),онда  f ( ) және g( ) функциялары тең деп аталады. Егер f ( ) және g( ) функциялары тең болса, онда олардың біреуін екіншісінен жалған айнымалыларды қосу немесе алып тастау арқылы алуға болады.

     

Есеп  шығару мысалы

      f( ) =(11110011) функциясының барлық жалған және елеулі айнымалыларын табу керек:

      ШЕШІМІ: Бұл функция үшін келесі кестені сызамыз: 
 

      x₁: f(0,0,0)¹f(1,0,0) яғни, берілген функцияның мәндері сәйкес келмейтін жинақты табуға болады. Қорытынды  - x₁айнымалысы f( ) функциясының елеулі аргументі.

      x₂: f(1,0,0)¹ f(1,1,0), яғни x₂ айнымалысы f( ) функциясының елеулі аргументі.

      x₃: f(0,0,0)=f(0,0,1)=0, f(0,1,0)=f(0,1,1)=1, f(1,0,0)=f(1,0,1)=1, f(1,1,0)=f(1,1,1,)=0, яғни берілген функцияның мәндері барлық көршілес жинақтарда бірдей.

    Буль  функцияларының жалған және елеулі

айнымалыларын программада жүзеге асыру

 

      Программалық  жүзеге асыру негізінен Delphi  ортасында  орындалды.Ол төменде көрсетілген: 

unit Finder; 

interface 

uses

  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

  Dialogs, StdCtrls, ExtCtrls, Grids; 

type

  TForm1 = class(TForm)

    ComboBox1: TComboBox;

    RadioGroup1: TRadioGroup;

    Button1: TButton;

    Edit1: TEdit;

    StringGrid1: TStringGrid;

    Button2: TButton;

    Button3: TButton;

    Label1: TLabel;

    Label2: TLabel;

    procedure Button1Click(Sender: TObject);

    procedure Edit1Click(Sender: TObject);

    procedure Button2Click(Sender: TObject);

    procedure Button3Click(Sender: TObject);

  private

    { Private declarations }

  public

    { Public declarations }

  end; 

Type IntType = LongInt;

    Mas = Array [1..10000] Of IntType;

var

  Form1     : TForm1;

  intVar    : IntType;

  mT        : Mas; 

implementation 

{$R *.dfm} 

FUNCTION Power(X : IntType; P : IntType) : IntType;

Var Ret : IntType;

    i  :IntType;

Begin

  If (p=0)or(x=1) then

  Begin

    Power:=1;

    Exit;

  End;

  Ret:=1;

  For i:=1 to P do

  Begin

    Ret:=Ret*X;

  End;

  Power:=Ret;

End; 

FUNCTION Meaning(X,Y : IntType) : IntType;

Var j, Ret : IntType;

Begin

  If X=1 then

  Begin

    Meaning:=0;

    Exit;

  End;

  Ret:=0;

  x:=x-1;

  For j:=1 to Y do

  Begin

    Ret:=X mod 2;

    X:=X div 2;

  End;

  Meaning:=Ret;

End; 

procedure TForm1.Button1Click(Sender: TObject);

Var i, j : IntType;

begin

  If RadioGroup1.ItemIndex=-1 then

  Begin

    ShowMessage('Выберите функцию');

    Exit;

  End Else

  If RadioGroup1.ItemIndex=0 then

  Begin

    Try

      intVar:=StrToInt(Edit1.Text);

    Except

      ShowMessage('Ввведите, все-таки, кол-во переменных');

      Exit;

    End;

  //Строим таблицу для удобства

    StringGrid1.Visible:=True;

    StringGrid1.ColCount:=intVar+1;

    StringGrid1.RowCount:=Power(2,intVar)+1;

    For i:=1 to StringGrid1.ColCount-1 do

      StringGrid1.Cells[i,0]:='x'+IntToStr(i);

    For i:=1 to StringGrid1.RowCount-1 do

      StringGrid1.Cells[0,i]:=IntToStr(i)+')';

    StringGrid1.ColCount:=StringGrid1.ColCount+1;

    StringGrid1.Cells[StringGrid1.ColCount-1,0]:='Function Value';

    Button2.Visible:=True;

    For i:=1 to StringGrid1.RowCount-1 do

      For j:=1 to StringGrid1.ColCount-2 do

        StringGrid1.Cells[j,i]:=IntToStr(Meaning(i,StringGrid1.ColCount-2-j+1));

  End

  Else

  If RadioGroup1.ItemIndex=1 then

  Begin

    StringGrid1.Visible:=True;

    Button3.Visible:=True;

    StringGrid1.EditorMode:=True;