Логика алгебрасы және буль функциялары: жіктелу, нормалдық формалар, толықтық және Жегалкин теоремасы
Мазмұны
Кіріспе..................................................................................3
Логика алгебрасының функциялары 5
Формулалардың эквиваленттігі. Қосалқылык принципі...............................................................................5
Буль функцияларын айнымалыларға жіктеу. Кемел дизъюнктивті
Толықтық және тұйықтық..................................................7
Жегалкин теоремасы.............................................................................8
Маңызды жабық сыныптар. Толықтық туралы теорема.................................................................................9
Пост нәтижелері.........................................................................10
Буль функцияларының жалған және елеулі айнымалылары..................................................................10
Буль функцияларының жалған және елеулі
айнымалыларын программада жүзеге асыру.................14
Қорытынды........................................................................19
Қлданылған әдебиеттер тізімі..........................................20
Кіріспе
Жалпы алғанда буль функцияларының жалған
Бұл айнымалылардың маңызы өте зор. Мысалы,
ЛОГИКА АЛГЕБРАСЫ
1. Логика алгебрасының функциялары
A
йталық U-{u1,и2,...,иm,...} - айнымалылардың бастапқы алфавиті
Бұл функциялар логика алгебрасыныц функциялары немесе
Теорема. х1,х2,...,хn п айнымалыға тәуелді
функциялар саны P2 (n) - 22
Логика алгебрасы функцияларың мысалдары:
ƒ1(x) =0 -тұрақты 0
ƒ2(x) =1-тұрақты 1;
ƒ3(x)=x –тепе-тең функция;
ƒ4(x)= - х
ƒ5(x1,x2)= (x1(x2) - x1 мен x2
ƒ6(x1,x2)= (x1∨x2) - x1 мен
ƒ6(x1,x2)=Бұл функциялардың мәні.
xx 0 0 11 xx
00 00 11
11 00 11
x1
0 0
0 1
0 0
1 1
1 0
1 1
1 1
0 1
0
0 1
1 1
2. Формулалар. Формулаларды функциялармен жузеге асыру
Анықтама. Айталық (- Р2 жиынындағы
болсын.
а) Индукция базисі. ( ішжиынындағы әрбір
b) Индуктивті өту. Айталық ƒ (x1,…,xm)
с) Формуланың индуктивті анықтамасына сүйене отырып,
d) Индукция базисі. Егер. F(х1,...,xn)
e) Индуктиві өту.
Онда индуктивті болжам
функциясы немесе
F(х1,...,xn) формуласына
Егер ƒ функциясы F формуласына сәйкес
F формуласына сәйкес келетін ƒ функциясы
3.Формулалардың эквиваленттігі. Қосалқылык принципі
Анықтама. F және G формулалары (
(х1◦х2) арқылы (x1(x2), (x1∨x2), (х1+х2) функцияларының
Логика алгебрасы фунщияларыныц цасиеттері
1) (x1◦х2) функциясы ассоциативтілік
((x1◦x2) ◦ x3 ) = (x1◦(x2◦x3)).
2) (х1◦х2) функциясы коммутативтілік
(x1◦x2)=(x2◦x1)
3) Конъюнкция және дизъюнкция үшін дистрибутивтілік
((x1∨x2) & x3) = ((x1(x3) ∨(x2(x3))
((x1(x2) ∨ x3)=((x1∨x2) ((x2∨x3)
4) =x ,
5) (x( )=0, (x∨
(x(0)=0, (x∨0)=x,
(x(1)=0, (x∨1)=x.
Анықтама. [ƒ (х1,...,xn)]*=
функциясына қосалқы функция деп аталады.
0 функциясы 1 функцияға қосалқы,
1 функциясы 0 функциясына қосалқы,
x функциясы х функциясына қосалқы,
функциясы функциясына қосалқы,
х&х2 функциясы х1vх2 функциясына қосалқы,
x1vх2 функциясы х1&х2 функциясына қосалқы.
Қосалқылықтың анықтамасынан ƒ ** =( ƒ
Қосалқылық принципі. Егер F=С[ƒ1,..., ƒ s]
функциясын жүзеге асырса, онда F формуласынан
ƒ1*,..., ƒs* функциясына ауыстыру аркылы алынған
Бұл формуланы F формуласына қосалқы формула
4.Буль функцияларын айнымалыларға жіктеу. Кемел дизъюнктивті
х =хσ∨хσ белгілеуін енгізейік,
xσ =
хσ = 1 тек сол жағдайда,
Теорема (Буль функцияларын айнымалыларға жіктеу туралы).
ƒ (х1,...,xm,xm+1,…,xn)= x1
(*)
мұнда дизъюнкция х1,...,хm айньмалыларының барлық мүмкін
Бұл көрініс функцияның х1,...,хm айнымалылары бойынша
Салдар ретінде жіктеудің арнайы екі түрін
Айнымалы бойынша жіктелу:
ƒ (х1,...,хn-1,хn) = хn & ƒ
ƒ (х1,..,хn-1,0) және
Барлық айньмалылар бойынша жіктеу:
ƒ (х1,...,xn)= x1 σ1
ƒ (х1,...,xn)≡0 орындалғанда жіктеу келесі түрге
x1 σ1 (…( xnσn ƒ(σ1,…,σn) =
Нәтижесінде
ƒ (х1,...,xn)= x1 σ1
(**)
екендігін аламыз.
Мұндай жіктелу кемел дизъюнктивті нормалъ қалып
Теорема. Логика алгебрасының
Функцияның мәні бірге тең болатын үш
x1 v x2 = x10 &
Конъюнктивті нормаль қалып деп аталатын жіктеуді
ƒ (х1,...,xn)=
конъюнктивті нормаль калып деп аталатын жіктеуді
5.Толықтық және тұйықтық
Анықтама. Егер кез-келген Буль функциясы осы
Толық жүйелердің мысалдары:
1. Р2 жүйесі- барлық
2. G = { ,x1&
Кез-келген жүйе толық бола бермейді, мысалы
Теорема. Айталық Р2 жиынында екі функциялар
G={f1,f2,…},
D={g1,g2,…},
олар туралы мына жағдай белгілі: (I)
Мысал:
D ={ ,x1&x2 } жүйесінің
Дәлелдеу: (I)
{ ,x1& х2,x1vx2 }, ал
x1vx2= тепе-теңдігін пайдаланамыз
Сонымен, (I) жүйенің әрбір
6.Жегалкин теоремасы.
Р2 жиынындағы әрбір функция mod
Мысал: (х1vх2) функциясын Жегалкин көпмүшесі түрінде
(x1vx2)=ax1x2+bx1+cx2+d.
(0,0) жинағында: x1=x2=0(0=a(0+b(0+c(0+d(d=0.
(0,1): x1=0,x1=1(1=a(0+b(0+c(1+d(c=1.
(1,0): x1=1,x2=0(1=a(0+b(1+c(0+d(b=1.
(1,1): x1=1,x2=1(1=a(1+b(1+c(1+d(a=1.
(x1vx2)=x1x2+x1+x2
Толықтық ұғымымен тұйықтау және тұйык сыныптар
Анықтама. Айталық
Мысал.
1)М = Р2. Бұл жағдайда [М]
2) М = {1,х1+х2} . [М]
f(х1,...,хв) = с0+с1х1+...+сnxn, мұндағы с= 0,1(i
Тұйъқтаудыц қасиеттері
1)M([M].
2)[[M]]=[M].
3) егер М1(М2 , онда [М1]([М2]
4) [M1(М2] ([М1]([М2] .
Анықтама.М сыныбы (жиыны) тұйық деп аталады,
Мысал.
1) М =Р2 сыныбы түйық
2) М = {1,x1+ х2}
Толықтық анықтамасы бастапқыға эквивалентті : М
7.Маңызды жабық сыныптар. Толықтық туралы теорема.
Р2 жиыньшдағы маңызды түйық сыныптарды қарастырайық.
1. T0 арқылы барлық f
0,х,x1&х2, х1vх2,x1(x2(T0,
1, (T0.
Т0- тұйық сынып.
T1 арқылы тұрақты бірді сақтайтын барлық
1,x,x1&x2,x1vx2(T1,
0, (T1. T1 сыныбы
3. S арқылы барлық өзіндік қосалқы
4. Жинақтардың векторлы жазылуын қолдана отырып:
=((1,…, (n), =((1,…, (n),
Анықтама. Егер (1( (1,...,(n((n шарты орындалса,
Мысалы, (0,1,0,1) ( (1,1,0,1). Егер
Анықтама. Егер (
М арқылы барлық монотонды функциялар жиынын
5. L - барлық сызықты функциялар
0,1,x, ,x1(x2(L ,x1&x2, х1
Алгебра логикасының негізгі есептерінің бірі- толықтылықтың
Айталық G={f1,f2,..,f5,...} - Р2 жиынындағы кез-келген
Осы жүйенің толықтылығын калай анықтауға болатынына
Теорема (функционалды толықтық туралы).
G функциялар жүйесі толық болуы үшін
8.Пост нәтижелері
Р2 жиынындағы тұйық сыныптарды американ математигі
Анықтама. М тұйық сыныбындағы {f1,f2,…,fs,…} функциялар
Басқаша айтқанда, егер М сыныбындағы әрбір
Анықтама. Егер ол М сыныбында
1)f1=x1x2, f2=0, f3=1, f4=x1(x2(x3 функциялар
{ x1x2,0,1,x1(x2(x3}- Р2 жиынында толық.
{ x1x2,0,1}- Р2 жиынында толық емес.
2) {0,1,x1&x2, х1 v х2}
1 Пост теоремасы. Р2 жиынындағы әрбір
2 Пост теоремасы. Р2 жиынындағы тұйық
Буль функцияларының жалған және елеулі айнымалылары
Анықтама. Егер і-ші құрамдас бөлік бойынша
f ( )(f (
Анықтама. Егер f ( )
f ( )=g( ),онда
Есеп шығару мысалы
f( ) =(11110011) функциясының барлық
ШЕШІМІ: Бұл функция үшін келесі кестені
x1 x2
0 0
0 0
0 1
0 1
1 0
1 0
1 1
1 1
x1: f(0,0,0)(f(1,0,0) яғни, берілген функцияның мәндері
x2: f(1,0,0)( f(1,1,0), яғни x2 айнымалысы
x3: 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,
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 :
intVar : IntType;
mT
implementation
{$R *.dfm}
FUNCTION Power(X : IntType; P :
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,
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
Пікірлер жүктелуде…