Реферат тақырыбы: Формулалар. Функцияларды формулалар арқылы іске асыру

Функцияларды формулалармен іске асыру

жүктеу/скачать 128,63 Kb.

бет	4/6
Дата	15.12.2022
өлшемі	128,63 Kb.
	#57521
түрі	Реферат

1 2 3 4 5 6

Логикалық формулалардың ақиқаттық кестесі

Функцияларды формулалармен іске асыру

Көптеген логикалық функциялар болсын. F-тен жоғары формула ұғымы индуктивті түрде анықталады:

1. F-тен әр айнымалы және әр логикалық функция F-тен жоғары формулалар болып табылады.
2. Егер F-тен жоғары формулалар болса, онда F-тен әр функция үшін көрініс өрнегі F-тен жоғары формула болып табылады.
F-тен жоғары әр формула осы формуланы түсіндіру деп аталатын логикалық функцияға сәйкес келеді. Түсіндіру, формула сияқты, индуктивті түрде анықталуы мүмкін:
1. Формуланы түсіндіру элементті элементпен салыстырады .
2. Формуланы түсіндіру функциялар қажет болған жағдайда жалған айнымалылармен толықтырылатын мәндерді қабылдайды.
Мысал
Болсын . Содан кейін,, және-F-тен жоғары формулалар, өйткені

Егер G формуласының түсіндірмесі F логикалық функциясы болса, онда G формуласы f функциясын жүзеге асыру деп аталады.

Мысалы, формулалар мен 1-ге тең, өйткені функция барлық үшін 1 мәндерін алады .
Эквивалентті формулалардың көптеген сыныптары операцияларға қатысты логикалық алгебраны құрайды:
& , Ú , Ø,
Линденбаум – Тарский алгебрасы деп аталады.
Келесі бөлімде барлық логикалық функциялардың над формулаларымен орындалатындығы дәлелденеді, сондықтан тең логикалық функциялардың кластарын осы логикалық алгебраның элементтері ретінде қарастыруға болады.
Логикалық формулалардың ақиқаттық кестесі
Егер f*(x1,x2,…,xn)= онда f*(x1,x2,…,xn) функциясы f(x1,x2,…,xn) функциясына түйіндес функция деп аталады. f(x1,x2,…,xn) функциясына түйіндес функцияны анықтау үшін, барлық айнымалылар және функцияның өзін оның қарама-қарсы мәндеріне ауыстыру керек.
Мысал.Үш айнымалыдан тәуелді
функциясын буль формуласы яғни МДҚФ-түрінде өрнектеу керек.

					v
0	0	0	0	0	0	0	1
0	0	1	0	0	1	0	1
0	1	0	1	1	0	0	0
0	1	1	1	1	1	1	1
1	0	0	1	1	1	0	0
1	0	1	1	1	1	0	0
1	1	0	0	0	1	1	1
1	1	1	0	0	1	1	1

Іздеп отырған МДҚФ
=
Түйіндестік принципі: Егер f функциясын өрнектейтін F формуласындағы барлық операция белгілерін түйіндес функцияның операция белгілеріне алмастырғаннан алынған F* формуласы берілген f функциясының түйіндес функциясын өрнектейтін болады.
Тек &, Ú, а, ж символдарымен ғана байланысқан формулаларды қарастырамыз. &, Ú, а, ж символдары бір біріне түйіндес деп аталады.
Мысалдар: ақиқат–формуласының түйіндесі - жалған;

Егер f1, f2 функциялары тең болса, онда оларға сәйкес түйіндес формулалар да тең болады.  онда  . Түйіндестік принцип дизъюнкция, конъюнкция, терістеу арқылы байланысқан формулалармен берілген функциялардың түйіндестерін табу үшін ыңғайлы. Бұл жағдайда берілген формулада конъюнкция дизъюнкцияға, дизюнкция конъюнкцияға ауысады. Сөйтіп ДҚФ–КҚФ, КҚФ-ДҚФ, МДҚФ–МКҚФ немесе керісінше.
Мысалы: (
Егер j формуласы m-ге эквивалент болса:j~m онда оларға сәйкес түйіндес формулалар да эквивалентті болады ,яғни j* ~m* болады.
Егер f* (x1,x2,…,xn)=f(x1,x2,…,xn) онда f(x1,x2,…,xn) функциясы өзіне-өзі түйіндес функция деп аталады. Мысалы, j =xyÚxzÚyz функциясы өзіне өзі түйіндес функцияны кескіндейді. Оған (б1,б2,б3) және (1-б1, 1-б2 , 1-б3) жиынтықтарының қарама-қарсы мәндерінде функция да қарама-қарсы мән қабылдайтындығына көз жеткізуге болады. Ол үшін ақиқаттық кесте құрып:

екендігін көреміз.
Мысал: Түйідестік принципіне сүйене отыра, буль алгебрасындағы түйідестік принципінің дұрыстығын дәлелдеу керек. Буль алгебрасында  үш амал бар:  ;
Буль алгебрасының әр бір амалына түйіндес амалдарды анықтайық.
а) Айталық,  болсын.
Олай болса   ;
б) Айталық,   ;Олай болса   ;
в) Айталық,   ; Олай болса  ;
Сонымен конъюнкция дизъюнкцияға, дизъюнкция конъюнкцияға түйіндес, ал терістеу өзіне өзі түйіндес.

Мысалдар
1. Логикалық формулалардың ақиқаттық кестесін құру.

1-мысал.
f(x,y) = (x→y)/(x~y) формуланың ақиқат болатын жиналымдар жиынын тап.

1-кесте.

x,y

F₁=x→y

F₂=x~y

f=F₁/F₂

0 0

1

1

0

0 1

1

0

1

1 0

0

0

1

1 1

1

1

0

1-кестеге сәйкес N_f¹ ={01 ; 10} .

2-мысал.
f (x₁,x₂,x₃)= ¬(x₁~x₂~x₃) функцияның ақиқат болатын жиналымдар жиынын тап.

2-кесте

x₁x₂ x₃	F₁=x₁+x₂+x₃	F₂=x₁~x₂~x₃	F₃= ¬F₂	f=F₁→F₃
0 0 0	0	0	1	1
0 0 1	1	1	0	0
0 1 0	1	1	0	0
0 1 1	0	0	1	1
1 0 0	1	1	0	0
1 0 1	0	0	1	1
1 1 0	0	0	1	1
1 1 1	1	1	0	0

N_f¹={000,011,101,110}.

3-мысал.
теңдік ақиқат болатын жиналымдар жиынын тап.

3-кесте

х₁х₂ х₃	(¬x₁~x₂)/x₃
0 0 0	1	1
0 0 1	1	1
0 1 0	1	0
0 1 1	0	0
1 0 0	1	1
1 0 1	0	0
1 1 0	1	1
1 1 1	1	1

N_f¹ ={000,001,011,100,101,110,111}.

4-мысал.
F(x₁,x₂) = (¬x₁~x₂)/(x₁+¬x₂) ;

4-кесте.

x,y

(¬x1~x2)

(x1+¬x2)

f=F₁/F₂

0 0

0

1

1

0 1

1

0

1

1 0

1

0

1

1 1

0

1

0

1-кестеге сәйкес N_f¹ ={00 ; 01 ; 10} .

5-мысал.
F(x₁,x₂) = (¬x₁¬x₂→x₁x₂)~ x₂;
5-кесте.

x,y
0 0	0	1
0 1	1	1
1 0	1	0
1 1	1	1

N_f¹ ={00 ; 01 ; 11} .

6-мысал.
F(x₁,x_2,) = (x₁x₂→)( 6-кесте

x₁x₂ x₃	F₁	F₂	F₃	(F₁F₃
0 0 0	1	1	0	0
0 0 1	0	0	0	1
0 1 0	1	0	0	1
0 1 1	0	1	1	0
1 0 0	1	0	1	0
1 0 1	1	1	1	1
1 1 0	1	1	0	0
1 1 1	0	0	1	0

N_f¹ ={001,010,101}.

7-мысал.
F(x₁,x_2,) =
7-кесте

x₁x₂ x₃	F₁	F₂	F₃	(F₁F₃
0 0 0	0	1	1	0
0 0 1	0	1	0	0
0 1 0	1	1	1	1
0 1 1	0	1	0	0
1 0 0	1	1	0	0
1 0 1	0	1	1	0
1 1 0	1	0	1	0
1 1 1	0	1	0	0

N_f¹ ={010}.
8-мысал.

8-кесте

x₁x₂ x₃	F₁	F₂	F₃	F₁F₃
0 0 0	0	0	0	1
0 0 1	1	1	1	0
0 1 0	0	1	0	1
0 1 1	1	0	1	1
1 0 0	0	1	1	0
1 0 1	1	0	1	1
1 1 0	0	1	0	1
1 1 1	0	1	1	0

N_f¹ ={000,010,011,101,110}.
9-мысал.

9-кесте

x₁x₂ x₃	F₁	F₂	F₃	(F₁F₃
0 0 0	1	1	0	0
0 0 1	1	0	0	0
0 1 0	1	1	0	1
0 1 1	1	1	0	0
1 0 0	0	1	0	1
1 0 1	0	1	1	1
1 1 0	0	0	1	1
1 1 1	0	1	0	1

N_f¹ ={010,100,101,110,111}.

10-мысал.

Функцияны өте жай формулаға келтіріңдер:

Шешімі: Бұл жерде элементар функциялардың 4 (идемпотенттік заңы), 5 (екі рет терістік заңы), 6(Де Морган заңы), 7(логикалық қарама-қайшылық заңы) және 9(түрақтылар амалы) пункттерде көрсетілген теңдіктерінен пайдаланамыз:

.

жүктеу/скачать 128,63 Kb.

Достарыңызбен бөлісу:

1 2 3 4 5 6