Буль алгебрасы

Мысал.

1)М = Р₂. Бұл жағдайда [М] = Р₂ .

2) М = {1,х₁+х₂} . [М] - L барлық сызықты функциялар сыныбы:

f(х₁,...,х_в) = с₀+с₁х₁+...+с_nx_n, мұндағы с= 0,1(i =0,..,n), маңызды айнымалылар   коэффициенті   бірге   тең   де,   жалған   айнымалылар коэффициенті нөлге тең.

Тұйъқтаудыц қасиеттері

1)MÍ[M].

2)[[M]]=[M].

3) егер М₁ÍМ₂ , онда [М₁]Í[М₂] .

4) [M₁ÈМ₂] Ê[М₁]È[М₂] .

Анықтама.М сыныбы (жиыны) тұйық деп аталады, егер [М] = М.

Мысал.

1)  М =Р₂ сыныбы түйық сынып.

2)  М = {1,x₁+ х₂} сыныбы тұйық емес.

Толықтық анықтамасы бастапқыға эквивалентті : М - толық жүйе, егер [M]= Р₂.

 

7.Маңызды жабық сыныптар. Толықтық туралы теорема.

Р₂ жиыньшдағы маңызды түйық сыныптарды қарастырайық.

1. T₀  арқылы барлық f (x₁,…,x_n) буль функцияларының тұрақты нөлді сақтайтын сыныбын белгілейік,     яғни     f(0,...,0) = 0   орындалатын функцияларды.

0,х,x₁&х₂, х₁vх₂,x₁Åx₂ÎT₀,

1, ÏT₀.

Т₀- тұйық сынып.

T₁ арқылы тұрақты бірді сақтайтын барлық буль функцияларының сыныбын белгілейміз, яғни f(1,...,1)=1 теңдігі орындалатын функциялар сыныбы:

1,x,x₁&x₂,x₁vx₂ÎT_1,

0, ÏT₁. T₁ сыныбы T₂ сыныбына қосалқы. T₁ сыныбы тұйық сынып

 

3. S арқылы барлық өзіндік  қосалқы функциялар сыныбын белгілейміз,  яғни P₂ жиынындағы f * = f шарты орындалатын функциялар сыныбы.S сыныбы тұйық.

4. Жинақтардың векторлы жазылуын қолдана отырып:

=(a₁,…, a_n), =(b₁,…, b_n), f (a₁,…, a_n)=f ( ) екендігін аламыз.

Анықтама. Егер a₁£ b₁,...,a_n£b_n шарты орындалса, онда = (a₁,...,a_n) және =(b₁,..., b_n) екі жинағы үшін алдын алу қатынасы орындалады дейді.

Мысалы, (0,1,0,1) £ (1,1,0,1). Егер £ және £ , онда £ .

Анықтама. Егер £ шарты орындалатын кез-келген және жинақтары үшін 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) функциясының барлық жалған және елеулі айнымалыларын табу керек:

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

 

 

x1   x2   x3	f( ) =( x1, x2, x3)
0   0   0	0
0   0   1	0
0   1   0	1
0   1   1	1
1   0   0	1
1   0   1	1
1   1   0	0
1   1   1	0

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;

    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));

    StringGrid1.Options:=[goEditing];

  End;

  RadioGroup1.Visible:=False;

  Button1.Visible:=False;

  ComboBox1.Enabled:=True;

end;

 

procedure TForm1.Edit1Click(Sender: TObject);

begin

  Edit1.SelectAll;

end;

 

procedure TForm1.Button2Click(Sender: TObject);

Var Ret, i, j, N, M, p, k: IntType;

   Bol : Boolean;

   mT1 : Mas;

begin

  //Main Algorythm Block

  If ComboBox1.ItemIndex=-1 then

  Begin

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

    Exit;

  End;

 

  If ComboBox1.ItemIndex=0 then

  Begin

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

    Begin

      Ret:=0;

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

        Ret:=Ret or StrToInt(StringGrid1.Cells[j,i]);

      StringGrid1.Cells[StringGrid1.ColCount-1,i]:=IntToStr(Ret);

    End;

  End;

 

  If ComboBox1.ItemIndex=1 then

  Begin

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

    Begin

      Ret:=1;

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

        Ret:=Ret and StrToInt(StringGrid1.Cells[j,i]);

      StringGrid1.Cells[StringGrid1.ColCount-1,i]:=IntToStr(Ret);

    End;

  End;

 

  //Finding Fictive Vars

 

  M:=StringGrid1.ColCount-2;

  N:=StringGrid1.RowCount-1;

 

  For i:=1 to N do

    mT[i]:=StrToInt(StringGrid1.Cells[M+1,i]);

  k:=0;

  For i:=1 to M do

  Begin

    FillChar(mT1, SizeOf(mT1), 0);

    For j:=1 to N do

    Begin

      p:=Power(2,i-1);

      If ((j=1)or(mT1[j]<>-1))and(j+p<=N) then

      Begin

        Bol:=(mT[j]=mT[j+p]);

        If not Bol then

        Begin

          Label1.Caption:=Label1.Caption+' x'+IntToStr(M-i+1);

          k:=1;

          mT1[j]:=-1;

          mT1[j+p]:=-1;

          Break;

        End;

      End;

    End;

    If k=0 then

    Begin

      Label2.Caption:=Label2.Caption+' x'+IntToStr(M-i+1);

    End

    Else

      k:=0;

  End;

 

  // End Of Finding Fictive Vars

end;

 

procedure TForm1.Button3Click(Sender: TObject);

Var j, i, n, m, p, k : IntType;

     Bol : Boolean;

     mT1 : Mas;

begin

  ComboBox1.Enabled:=False;

 

   //Finding Fictive Vars

 

  M:=StringGrid1.ColCount-2;

  N:=StringGrid1.RowCount-1;

 

  For i:=1 to N do

    mT[i]:=StrToInt(StringGrid1.Cells[M+1,i]);

   

  k:=0;

  Label1.Caption:='Vulnerable:';

  Label2.Caption:='Fictive:';

  For i:=1 to M do

  Begin

    FillChar(mT1, SizeOf(mT1), 0);

    For j:=1 to N do

    Begin

      p:=Power(2,i-1);

      If ((j=1)or(mT1[j]<>-1))and(j+p<=N) then

      Begin

        Bol:=(mT[j]=mT[j+p]);

        If not Bol then

        Begin

          Label1.Caption:=Label1.Caption+' x'+IntToStr(M-i+1);

          k:=1;

          Break;

        End;

        mT1[j]:=-1;

        mT1[j+p]:=-1;

      End;

    End;

    If k=0 then

    Begin

      Label2.Caption:=Label2.Caption+' x'+IntToStr(M-i+1);

    End

    Else

      k:=0;

  End;

 

  // End Of Finding Fictive Vars

 

end;

end.

 

 

 

 

Қорытынды

 

Қорытындылай келе жасалған жұмыстың нәтижелерін белгілейік:

1. Алынған тақырып бойынша толық теориялық талдау жүргізілді.
2. Талдау бойынша жалған және елеулі айнымалыларды табу алгоритмі толықтай, өзге қосымша алгоритмдерді қолдана отырып, жүзеге асырылды.

Авторлармен жұмыс барысында  келесі ескертулер енгізілді:

1. Программа қолданысы кезіндегі кейбір шектеулер.
2. Көп айнмалылармен жұмыс істегендегі програма орындалуының тездігі.

 

Қолданылған әдебиеттер тізімі:

 

1. Яблонский С.В., “Введение в дискретную математику”, М., Высшая школа, 2002
2. Акимов О.Е., Дикретная математика, М., Лаборатория базовых знаний, 2001
3. Новиков, Дискретная математика для программистов, Питер, 2003
4. Тірек конспект,КБТУ, 2003,